Radix-4 Booth scans overlapping triplets of multiplier bits, with an implied zero below bit 0. Each triplet becomes one signed digit, so two multiplier bits yield one partial product.
Digits stay within -2 to +2. That bound is what keeps each multiple to a shift, a negation, or both.
Triplet (b1, b0, b-1) | Digit | Multiple |
|---|---|---|
000 | 0 | 0 |
001 | +1 | +x |
010 | +1 | +x |
011 | +2 | +2x |
100 | -2 | -2x |
101 | -1 | -x |
110 | -1 | -x |
111 | 0 | 0 |
Take x = 6 (0110) and y = -5 (1011). Two triplets give two rows, and their sum equals -30.
x = 6 = 0110, y = -5 = 1011 (4-bit two's complement), y[-1] = 0
group 0 = (y1, y0, y-1) = (1, 1, 0) -> -2 x 1 + 1 + 0 = -1
group 1 = (y3, y2, y1) = (1, 0, 1) -> -2 x 1 + 0 + 1 = -1
pp0 = -1 x 6 = -6 (shift 0)
pp1 = -1 x 6 = -6, shifted left 2 = -24
total = -6 + -24 = -30 = 6 x -5
rows: 2 instead of 4Radix-4 halves the row count: 8 rows become 4. Each recoded row needs the doubling bit, which sign extension to the full product width absorbs.
The same recoding covers the sign bit, so no separate sign row is needed. The Python check below proves that on every signed 4-bit pair.
The program recodes every signed 4-bit pair and compares against integer multiply. It also pins the digit bound and the halved row counts.
import sys
def booth_digits(yy, n):
ds = []
for i in range(n // 2):
b1 = (yy >> (2 * i + 1)) & 1
b0 = (yy >> (2 * i)) & 1
bp = (yy >> (2 * i - 1)) & 1 if i > 0 else 0
ds.append(-2 * b1 + b0 + bp)
return ds
def booth_mul(xs, ys, n):
yy = ys & ((1 << n) - 1)
total = 0
for i, d in enumerate(booth_digits(yy, n)):
total += d * xs * (1 << (2 * i))
return total
bad = 0
for xs in range(-8, 8):
for ys in range(-8, 8):
if booth_mul(xs, ys, 4) != xs * ys:
bad += 1
if bad != 0:
print("FAIL: " + str(bad) + " signed 4-bit products differ")
sys.exit(1)
for yy in range(16):
for d in booth_digits(yy, 4):
if d < -2 or d > 2:
print("FAIL: digit out of range")
sys.exit(1)
if len(booth_digits(0, 4)) != 2:
print("FAIL: 4-bit width needs 2 rows")
sys.exit(1)
if len(booth_digits(0, 8)) != 4:
print("FAIL: 8-bit width needs 4 rows")
sys.exit(1)
print("PASS: radix-4 Booth matches integer multiply on all 256 signed 4-bit pairs; 8-bit needs 4 rows, not 8")Four. Each digit consumes two multiplier bits, so 8 bits give 4 rows instead of 8.
The digit is -2. It selects -2x, a shift plus a negation.