Skip to content

Latest commit

 

History

History
13 lines (10 loc) · 1019 Bytes

README.md

File metadata and controls

13 lines (10 loc) · 1019 Bytes
Raw

Booth-Algorithm

Booth’s algorithm is an efficient method to multiply two signed binary numbers. The method requires a multiplier Q (n bits), a multiplicand M (n bits), a register A (2n bits), and an additional register Q-1 (1 bit). The 2n-bits register and the 1-bit register are initially initialized to zero. During the calculation, Q-1 stores the last bit of Q in the previous step, and additions and subtractions are performed over A.

The following are the three conditions needed for calculating the correct result.

  • If Q0 Q-1 is equal to 10, then perform A = A – M and the right shift.
  • If Q0 Q-1 is equal to 01, then perform A = A + M and the right shift.
  • If Q0 Q-1 is equal to 11, or 00, then just perform the right shift.

Constraints and Assumptions

  • The value of n (number of bits) considered in the program is 10.
  • The Multiplier and the Multiplicand should be strictly in the range (-512, 512).
  • The product obtained will be of 20 bits (2n).