The multiplier and multiplicand bits are loaded into two registers Q and M. A third register A is initially set to zero. C is the 1-bit register which holds the carry bit resulting from addition. Now, the control logic reads the bits of the multiplier one at a time. If Q0 is 1, the multiplicand is added to the register A and is stored back in register A with C bit used for carry. Then all the bits of CAQ are shifted to the right 1 bit so that C bit goes to An-1, A0 goes to Qn-1 and Q0 is lost. If Q0 is 0, no addition is performed just do the shift. The process is repeated for each bit of the original multiplier. The resulting 2n bit product is contained in the QA register.
Fig: Block diagram of multiplication
There are three types of operation for multiplication.
- It should be determined whether a multiplier bit is 1 or 0 so that it can designate the partial product. If the multiplier bit is 0, the partial product is zero; if the multiplier bit is 1, the multiplicand is partial product.
- It should shift partial product.
- It should add partial product.
Signed Multiplication (Booth Algorithm) – 2’s Complement Multiplication
Multiplier and multiplicand are placed in Q and M register respectively. There is also one bit register placed logically to the right of the least significant bit Q0 of the Q register and designated as Q-1. The result of multiplication will appear in A and Q resister. A and Q-1 are initialized to zero if two bits (Q0 and Q-1) are the same (11 or 00) then all the bits of A, Q and Q-1 registers are shifted to the right 1 bit. If the two bits differ then the multiplicand is added to or subtracted from the A register depending on weather the two bits are 01 or 10. Following the addition or subtraction the arithmetic right shift occurs. When count reaches to zero, result resides into AQ in the form of signed integer [-2n-1*an-1 + 2n-2*an-2 +. +................. 21*a1 + 20*a0].