threshold-booth-radix2

Booth radix-2 recoder for signed multiplication. Converts a 4-bit two's complement multiplier into add/subtract control signals.

Function

recode(Y[3:0]) -> [(add0, sub0), (add1, sub1), (add2, sub2), (add3, sub3)]

For each position i:

• add_i = 1: add multiplicand X shifted by i
• sub_i = 1: subtract multiplicand X shifted by i
• both 0: no operation

Booth Algorithm

Scans bit pairs (y_i, y_{i-1}) where y_{-1} = 0:

y_i	y_{i-1}	Operation
0	0	+0
0	1	+X
1	0	-X
1	1	+0

Logic:

• add_i = NOT(y_i) AND y_{i-1}
• sub_i = y_i AND NOT(y_{i-1})

Example Recodings

Y (signed)	Binary	Pos0	Pos1	Pos2	Pos3
0	0000	0	0	0	0
1	0001	-1	+1	0	0
7	0111	-1	0	0	+1
-1	1111	-1	0	0	0
-8	1000	0	0	0	-1

Note: 7 = 8 - 1 (one +1 at position 3, one -1 at position 0)

Architecture

Single-layer implementation:

y3  y2  y1  y0
 │   │   │   │
 ├───┼───┼───┼───► add0, sub0 (based on y0, 0)
 │   │   │   │
 ├───┼───┼───┼───► add1, sub1 (based on y1, y0)
 │   │   │   │
 ├───┼───┼───┼───► add2, sub2 (based on y2, y1)
 │   │   │   │
 └───┴───┴───┴───► add3, sub3 (based on y3, y2)

Each output is a single threshold neuron.

Parameters

Inputs	4
Outputs	8
Neurons	8
Layers	1
Parameters	40
Magnitude	21

Advantage of Booth

Booth recoding reduces the maximum number of non-zero partial products:

• Without Booth: up to n partial products
• With Booth: reduces runs of 1s to single operations

Example: 7 (0111) normally needs 3 additions. With Booth: 8-1 = one add at position 3, one subtract at position 0.

Usage

from safetensors.torch import load_file

w = load_file('model.safetensors')

# Use recoded signals to control shifted add/sub of multiplicand
# For full multiplier, combine with adder tree

License

MIT