To study and implement Booth's Multiplication Algorithm for multiplying two signed binary numbers in two's complement notation. The simulator demonstrates the step-by-step process of addition, subtraction, and arithmetic right shifts based on the multiplier bits.
Theory
What is Booth's Algorithm?
Booth's multiplication algorithm is a multiplication algorithm that multiplies two signed binary numbers in two's complement notation. Invented by Andrew Donald Booth in 1950, it is widely used in computer architecture because it can handle both positive and negative numbers uniformly without requiring a sign-correction step at the end.
How It Works
The algorithm examines the multiplier bits in overlapping pairs. It looks at the current least significant bit (Q0) and the previous least significant bit (Q-1, initially 0). Depending on these two bits, an operation is performed on the Accumulator (A).
Q0
Q-1
Action
Reasoning
0
0
Arithmetic Right Shift (ARS) only
Middle of a string of zeros
0
1
A = A + M, then ARS
End of a string of ones
1
0
A = A - M, then ARS
Beginning of a string of ones
1
1
Arithmetic Right Shift (ARS) only
Middle of a string of ones
Registers Used
M (Multiplicand): Holds the multiplicand value.
Q (Multiplier): Initially holds the multiplier. During the process, the product's lower half shifts into this register.
A (Accumulator): Initialized to 0. Holds the upper half of the intermediate product.
Q-1: A single flip-flop initialized to 0, holding the bit shifted out from Q0.
Count: Counter initialized to the number of bits (n).
Arithmetic Right Shift (ARS)
When shifting the A, Q, and Q-1 registers to the right, the most significant bit (MSB) of A is preserved (duplicated) to maintain the sign of the number. This is crucial for handling negative numbers correctly.
Worked Example: 3 × (-4)
Let n = 4. M = 3 (0011). Q = -4 (1100). -M = -3 (1101).
Step
A
Q
Q-1
M
Operation
Initial
0000
1100
0
0011
Initialization
1
0000 0000
1100 0110
0 0
0011
Q0Q-1=00. Shift right.
2
0000 0000
0110 0011
0 0
0011
Q0Q-1=00. Shift right.
3
1101 1110
0011 1001
0 1
0011
Q0Q-1=10. A=A-M. Shift right.
4
1110 1111
1001 0100
1 1
0011
Q0Q-1=11. Shift right.
Final Product = AQ = 11110100. In two's complement, this is -12, which is the correct answer.
Advantages
Works for both positive and negative numbers without modifications.
Can be faster than standard shift-and-add algorithms if there are long runs of 1s or 0s in the multiplier (since it skips addition/subtraction in the middle of a run).
Pretest
Question 1
What is the primary advantage of Booth's Algorithm over basic multiplication algorithms?
a) It uses fewer registers
b) It handles signed numbers natively without sign correction
c) It always takes exactly 1 clock cycle
d) It only works for positive numbers
Answer: b) Booth's algorithm natively processes numbers in two's complement form, effectively handling both positive and negative operands correctly.
Question 2
In Booth's algorithm, what action is taken if Q0 = 1 and Q-1 = 0?
a) Arithmetic Right Shift only
b) Add Multiplicand (M) to Accumulator (A), then shift
c) Subtract Multiplicand (M) from Accumulator (A), then shift
d) Halt the operation
Answer: c) The pattern 10 marks the beginning of a string of 1s in the multiplier. The algorithm dictates subtracting M from A, followed by an arithmetic right shift.
Question 3
What happens during an Arithmetic Right Shift (ARS)?
a) A 0 is always shifted into the most significant bit.
b) A 1 is always shifted into the most significant bit.
c) The most significant bit is discarded.
d) The sign bit (most significant bit) is preserved (duplicated).
Answer: d) ARS preserves the sign of a two's complement number by duplicating the MSB as it shifts right.
Question 4
What is the initial value of the Q-1 bit?
a) 0
b) 1
c) The MSB of the multiplier
d) The LSB of the multiplicand
Answer: a) The algorithm always initializes the Q-1 flip-flop to 0 before the first iteration.
Question 5
How many iterations does Booth's algorithm perform for multiplying two 4-bit numbers?
a) 3
b) 4
c) 8
d) 16
Answer: b) The number of iterations equals the number of bits in the multiplier, which is 4 in this case.
Question 6
If the multiplier contains a long string of 1s (e.g., ...011110...), what makes Booth's algorithm efficient?
a) It turns it into a string of 0s
b) It only performs addition/subtraction at the boundaries of the 1s, and only shifts in the middle
c) It divides by 2
d) It ignores strings of 1s
Answer: b) For a pattern like 11, Booth's algorithm only shifts (no add/sub). It performs a subtraction when the 1s start (10) and an addition when they end (01). This requires fewer ALU operations than shift-and-add for every 1.
Question 7
In a 4-bit implementation, how many bits wide is the final product?
a) 4 bits
b) 8 bits
c) 16 bits
d) 5 bits
Answer: b) The product of two n-bit numbers requires 2n bits. In a 4-bit simulator, the 8-bit result is stored across the A and Q registers combined (AQ).
Question 8
What is the two's complement of -5 in 4 bits?
a) 0101
b) 1010
c) 1011
d) 1101
Answer: c) +5 is 0101. Invert bits: 1010. Add 1: 1011.
Procedure
Follow these steps to operate the Booth's Multiplication Simulator:
1
Navigate to the Simulation tab to see the Booth multiplier datapath.
2
Set Multiplicand (M): Click the bit buttons (M3, M2, M1, M0) to enter the 4-bit signed multiplicand. The decimal equivalent is shown in the HUD. Keep in mind that the leftmost bit (M3) is the sign bit.
3
Set Multiplier (Q): Click the bit buttons (Q3, Q2, Q1, Q0) to enter the 4-bit signed multiplier.
4
Run the Simulation: Click the "Multiply" button. The simulator will automatically calculate the result.
5
Observe Iteration Steps: The Iteration Table on the right will populate with the 4 steps of the algorithm. Watch the values of A, Q, and Q-1 change.
6
Follow the Animation: The circuit diagram will visually highlight the active operation (Add, Subtract, or Shift) for each step in sequence. The active path pulses.
7
Final Result: The final 8-bit product is formed by combining the A and Q registers (A3A2A1A0 Q3Q2Q1Q0) after 4 iterations. This is displayed at the bottom right.