Booth Multiplier

Multiplying signed binary numbers efficiently is a fundamental requirement in any general-purpose processor. The Booth multiplication algorithm provides an elegant method for multiplying two signed integers represented in two's complement form, using a combination of addition, subtraction, and arithmetic right shifts. It is particularly important in VLSI design because it reduces the number of partial products, leading to faster and more power-efficient multipliers.

Core Concept: The Need for Booth's Algorithm

A straightforward approach to multiplying two signed two's complement numbers would require sign extension and separate treatment of the sign bit. This leads to errors when the naively applied unsigned array multiplier is used directly on two's complement values. Booth's algorithm elegantly handles the signed representation without any special-casing, and as a bonus, it reduces the number of partial products when consecutive 1s appear in the multiplier, making it faster in practice.

The fundamental insight of Booth's algorithm is based on the identity: a string of consecutive 1s in the multiplier can be replaced by a subtraction at the beginning of the string and an addition at the end. For example, the binary pattern 0111 (decimal 7) equals 1000 - 0001, so instead of adding A three times shifted, we can do one addition of 8A and one subtraction of A. This replacement can dramatically reduce the number of non-zero partial products.

Algorithm Steps and Recoding Logic

In Booth's algorithm (Radix-2 version), the multiplier B is extended with an extra bit B[-1] initialized to 0 at the right. The algorithm examines two consecutive bits at each step: the current bit B[i] and the previous bit B[i-1]. Based on these two bits, one of three operations is selected: add the multiplicand A to the partial product accumulator (when B[i]=0, B[i-1]=1), subtract A from the accumulator (when B[i]=1, B[i-1]=0), or do nothing (when both bits are the same). After each decision, the accumulator is arithmetic right shifted by one position.

Modified Booth Encoding (Radix-4)

The standard Radix-2 Booth algorithm examines 2 bits per step and generates n partial products for an n-bit multiplier. Modified Booth Encoding (MBE), also called Radix-4 Booth, examines overlapping triplets of bits (B[2i+1], B[2i], B[2i-1]) and generates one of five operations: 0, +A, +2A, -A, or -2A. Since each triplet covers two multiplier bits, only n/2 partial products are generated. This halves the number of partial products compared to Radix-2, which directly halves the number of levels in the CSA reduction tree and significantly reduces hardware and delay.

The +2A and -2A operations are implemented by shifting the multiplicand left by one bit, which requires no extra adder. The subtraction operations (-A and -2A) are implemented by computing the two's complement of A (or 2A), which requires a bitwise inversion and adding 1 in the carry path. This sign correction is handled using a correction vector added to the most significant partial product position.

Mathematical Expression

For a Radix-2 Booth multiplier, the recoded digit at position i is defined as: d_i = B[i-1] - B[i]. This gives values of -1, 0, or +1, corresponding to subtract, no-op, and add operations. The product is then P = A * sum(d_i * 2^i) for i from 0 to n-1. For Modified Booth (Radix-4), the recoded digit at position i covers bits B[2i+1], B[2i], B[2i-1] and takes values from the set {-2, -1, 0, +1, +2}. The product becomes P = A * sum(d_i * 2^(2i)) for i from 0 to n/2 - 1.

Practical Understanding

Modified Booth Encoding is the de facto standard for multiplier design in modern CMOS processors. Nearly all high-performance multipliers in commercial microprocessors (ARM, Intel, AMD) use Modified Booth encoding at the front end to reduce partial products, followed by a Wallace or Dadda tree for CSA reduction, and a fast carry propagate adder at the final stage. This three-stage pipeline approach achieves the best combination of speed and area.

The algorithm also handles the most negative two's complement number correctly, which is a well-known edge case. For an n-bit multiplier, the most negative number is -2^(n-1), and Booth's algorithm correctly produces the right recoded digit for this case without overflow in the intermediate steps when sign extension is handled properly.

Solved Numerical Example

Use Radix-2 Booth algorithm to multiply A = +5 (0101) and B = -3 (1101) in 4-bit two's complement. Show each step of the operation with the accumulator state.

Given:
A = +5 = 0101 (4-bit two's complement)
B = -3 = 1101 (4-bit two's complement)
-A = 1011 (two's complement of A)
B[-1] = 0 (appended extra bit, initialized to 0)
Accumulator P = 0000 0000 (extended to 8 bits + extra bit)

Why this formula applies:
Booth examines B[i] and B[i-1] at each step,
performs add or subtract, then arithmetic right shifts.

Step-by-step (4 iterations):

Step 1: B[0]=1, B[-1]=0 → subtract A
  P = 00000000 - 0101 (upper half) → P = 11010000 + shift
  After arithmetic right shift: P = 1110 1000 extra_bit=0
  Examining bits 1,0: (1,0) → subtract
  Wait — restate with correct notation:

Initial: P = 0000, A = 0101, extra = 0
Step 1: B[0]=1, extra=0 → 1,0 → subtract A: P = 0000 - 0101 = 1011
  Arithmetic right shift P|B = 1011|1101 → 1101|1110 (shift right, keep MSB)
  Now examine next pair: B[3],B[2] = 1,1 → no operation
Step 2: B[1]=0, B[0]=1 → 0,1 → add A: P = 1101 + 0101 = 0010 (with carry)
  Arithmetic right shift: P = 0001, carry propagated
Step 3: B[2]=1, B[1]=0 → 1,0 → subtract A: P = 0001 - 0101 = 1100
  Arithmetic right shift: P = 1110
Step 4: B[3]=1, B[2]=1 → 1,1 → no operation
  Arithmetic right shift: P = 1111

Final Answer:
Product = -15 = 11110001 in 8-bit two's complement
Verification: +5 x -3 = -15 (correct)

Exam Tip: In GATE and university exams, Modified Booth (Radix-4) is the most commonly tested variant. Remember the key facts: Radix-4 Booth generates n/2 partial products (instead of n), uses overlapping triplets of multiplier bits, and the valid operations are 0, +A, +2A, -A, -2A. The algorithm correctly handles signed two's complement without special cases.

Mechanism: Booth Recoding and Partial Product Generation

• Radix-2 Booth examines two bits (current and previous) of the multiplier at each step. The recoded digit is +1, 0, or -1, corresponding to add A, no operation, or subtract A from the accumulator, followed by an arithmetic right shift.
• Modified Booth Encoding (Radix-4) groups the multiplier bits into overlapping triplets. Each triplet produces one partial product from the set {0, +A, +2A, -A, -2A}. For an n-bit multiplier, only n/2 partial products are generated.
• The +2A and -2A operations are implemented by a left shift of the multiplicand, requiring no extra adder. Negation for -A and -2A is implemented using bitwise NOT plus a correction bit added to the sign column.
• The resulting n/2 partial products are fed into a Wallace or Dadda CSA reduction tree to produce two final vectors, which are then summed using a fast carry propagate adder.
• Booth's algorithm handles two's complement signed numbers correctly by treating the most significant bit of the multiplier as having negative weight, which is naturally incorporated into the recoding step without extra hardware.

Quick Revision

• Booth's algorithm multiplies two signed two's complement numbers using add, subtract, and arithmetic right shift operations, avoiding the need for separate sign handling.
• Radix-2 Booth: examines 2 bits per step (B[i] and B[i-1]), generates n partial products, operations: 0, +A, -A.
• Modified Booth (Radix-4): examines overlapping triplets (B[2i+1], B[2i], B[2i-1]), generates n/2 partial products, operations: 0, +A, +2A, -A, -2A.
• Key formula: recoded digit for Radix-2 is d_i = B[i-1] - B[i], giving values in {-1, 0, +1}.
• Hardware: Booth encoder + PP generators → CSA tree → fast carry propagate adder. This three-stage structure is standard in commercial processor multipliers.
• Exam trap: Do not confuse Radix-2 Booth (n partial products) with Modified Booth Radix-4 (n/2 partial products). The exam commonly tests which generates fewer partial products.
• The most common practical use is Modified Booth Encoding paired with a Wallace tree, giving the best combination of signed multiplication support and O(log n) delay.