Explain Booth’s algorithm with its hardware implementation.

1. Image shows the hardware implementation for Booth’s algorithm.

2. The circuit is similar to the circuit for positive number multiplication.

3. It consists of an n-bit adder, control logic and four register A, B, Q and Q_–1.

4. Multiplier and multiplicand are loaded into register Q and register B respectively.

5. Register A and Q_–1 and initially set to 0.

6. The n-bit adder performs addition, input of adders comes from multiplicand and content of register A.

7. In case of addition, Add / Sub line is 0, therefore, C_in = 0 and multiplicand is directly applied as a second input to the n-bit adder.

8. In case of subtraction, Add / Sub line is 1, therefore C_in = 1 and multiplicand is complemented and then applied to the n-bit adder. As a result, the 2’s complement of the multiplicand is added to the content of register A.

9. The control logic scans bit Q₀and Q_–1 one at a time and generates the control signals to perform the corresponding function.

10. If the two bits are same (1 – 1 or 0 – 0), then all the bits of A, Q and Q_{– 1} register are shifted to right 1 bit without addition or subtraction (Add/Subtract Enable = 0).

11. If the two bits differ, then the multiplicand is added to or subtracted from the A register, depending on the status of bits.

12. After addition or subtraction right shift occurs such that the left most bit of A (A_{n – 1}) is not only shifted into A_{n – 2,} but also remains in A_{n – 1.}

13. If the two bits differ, then the multiplicand is added to or subtracted from the A register, depending on the status of bits.

15. After addition or subtraction right shift occurs such that the left most bit of A (An – 1) is not only shifted into An – 2, but also remains in An – 1.

16. This is required to preserve the sign of the number in A and Q.