Multiplication Algorithms

Multiplication via pen and paper method, ia a compound practice of successive left shift and addition. But while working on digital hardware, the method is slightly different. The shift operation is a right shift instead of a left shift while the rest of the task is implemented in the following two ways:

1. Hardware Algorithm
2. Booth Algorithm

Hardware Algorithm:

The multiplicand is stored in a register B and multiplier in Q. Another register A of same size is taken as to work like Accumulator. A sequence counter SC is taken and initialized by the total count of bits in register B. A flip-flop E is used to store the excess carry while adding A with B. A complete set of EAQ participates in logical right shift. With each shift operation the SC is decremented. When after many iterations, SC becomes absolutely zero, we stop the process and extract the result from AQ.

Consider the following flow-chart:

The following example shows the entire operation with multiplicand = 13 and multiplier = 17. The result that we get at last is 221.:

Booth Algorithm:

As an advanced method, Booth algorithm is developed for multiplication of signed numbers. The positive numbers are as usual while negative numbers are taken already in 2's complement format. Multiplicand is stored in B and to simplify the A-B operation, 2's complement of B is also computed. Multiplier is again in Q, A works as Accumulator. Another flip flop Q_n+1 is also taken and initialized by a zero. the flip-flop stores the discarded LSB of Q after shifting AQ. The shift operation is Arithmetic and hence ASHR is followed. SC is decremented after every shift operation.

Consider the following flow-chart:

The following example shows the entire operation with multiplicand = +13 and multiplier = +17. The result that we get at last is +221.: