Multiplication and Division

Introduction

Arithmetic instructions in digital computers work on data to produce the results necessary for solving computational problems. These instructions are responsible for processing data on a computer. There are four basic arithmetic operations, addition, subtraction, multiplication, and division. 

This article will discuss multiplication and division arithmetic algorithms and show the procedure for digital hardware implementation.

Recommended Topic, Microinstruction in Computer Architecture and Difference Between Jfet and Mosfet

Multiplication Algorithm

Multiplication of fixed-point binary numbers in signed-magnitude representation is done by successive shift and add operations. For example, multiplication of numbers 10111(23) and 10011(19).

23        10111

19      x 10011

             10111

           10111x

         00000xx      +(adding all)

       00000xxx

      110110101     Product 437

The process consists of looking at successive Multiplier, least significant bit first. If the Multiplier is 1, the multiplicand is copied down; otherwise, zero is copied. And like we do in standard multiplication, the numbers copied down in successive lines are shifted one position to the left. Finally, all binaries are added, and the total sum is the result. The sign of the product(result) is determined from the signs of multiplicand and Multiplier. If they are alike, the final product sign is positive. If they are unlike, the sign of the product is negative. 

Recommended Topic - Shift Registers in Digital Electronics and what is middleware

Hardware Implementation for Signed-Magnitude Data

Multiplication is implemented in digital computers by changing the process slightly. First, instead of providing registers to store bits and binary numbers simultaneously, it is better to give an adder for the sum of only two binary numbers and then successively accumulate the partial product. In the second step, instead of shifting the multiplicand to the left, shift the partial product to the right. In the third step, the corresponding bit of the Multiplier is zero(0); there is no need to add zeros to the partial product since it will not change the value.

The hardware multiplication consists of registers and the equipment shown above. The Multiplier is stored in the register Q and its sign is Qs. Registers Q and B are used to store multiplicand and Multiplier, respectively, and register A store's partial products during multiplication.

The sequence counter(SC) at the beginning is set to a number equal to the number of bits in the Multiplier, and the counter is decremented by one after forming each partial product. The product begins when the counter reaches zero, and the process stops.

Three flip flops are required to store the sign bit of registers (sign A, sign B, and sign Q).

Flip flop E-stores carry bits generated during partial product addition.

This hardware unit Complement and Parallel adder calculate a partial product, i.e., perform addition required.

Hardware Algorithm

The diagram below shows the flowchart of the hardware multiply algorithm. At the start, the multiplicand is in B, and the Multiplier is Q. Their corresponding signs are in Bs and Qs. 

• We compare the signs of registers B(Bs) and Q(Qs) using the functionality of XOR and output stored in As (the sign of A register). 

Note: Initially, register A  and E flip flops have a value 0. The sequence counter is initialized with the value n, n is the number of bits in the Multiplier.

• Now we check the least significant bit of Multiplier. Add the multiplicand (register B) with the content of register A if it is 1. The result is assigned in A register with a carry bit in flip flop E. Content of E A Q is shifted to the right by one position, i.e., the content of E is shifted to most significant bit (MSB) of A, and least significant bit of A is shifted to the most significant bit of Q.
• If Qn = 0, only shift right operation on the content of E A Q is performed similarly.
• Content of Sequence counter is decremented by 1.
• Check the content of the Sequence counter (SC) content; if it is 0, end the process, and the final product is present in registers A and Q, or repeat the process.

Time for an Example:

We have to multiply two numbers B and Q, B=10111, Q=10011 ( the signed bits of these numbers will be handled separately, for that you can find xor of B and Q and the result will be stored in signed bits of A and Q).

Initially, A and E are accumulators initialized to 0. SC is a sequence counter which is initially equal to the number of bits in multiplier or multiplicand( here 5)

Since the value of Qn(last bit) is 1, A will be added to B 00000 + 10111 = 10111 and then shift right will be performed. (It's just a simple right shift operation in which the last bit of Q will be lost and all other bits shifted rightwards).

Again the value of Qn is 1, B will be added to A( 10111+ 01011= 00010 and E=1), then shift right will be performed. The bit 1 in E will be right-shifted to A

Now the value of Qn is 0 therefore only a shift right has to be performed without adding B

Again Qn=0, the shift right has to be performed. 

Now, Qn =1, adding B to A then right shift.

The sequence counter has reached 0, therefore no further computation needs to be performed. The values of A and Q store the final result.