Bit pair recoding

Slides

1. 1
Fast Multiplication
Bit-Pair Recoding of Multipliers

2. 2
Bit-Pair Recoding of
Multipliers z
Bit-pair recoding halves the maximum number of
summands (versions of the multiplicand).
1+1−
(a) Example of bit-pair recoding derived from Booth recoding
0
0 0 0
11010
Implied 0 to right of LSB
1
0
Sign extension
1
2 1−−
−

3. 3
Bit-Pair Recoding of
Multipliers
i1+i1
(b) Table of multiplicand selection decisions
selected at positioni
Multiplicand
Multiplier bit-pair
i
0
0
1
1
1
0
1
0
1
1
1
1
0
0
0
1
1
0
0
1
0
0
1
Multiplier bit on the right
00×M
1+
1
1+
0
1
2
2+
−
−
−
−
×M
×M
×M
×M
×M
×M
×M

4. 4
Bit-Pair Recoding of
Multipliers
1-
0000
111110
000011
1111100
000000
0 00 0111 111
01101
0
10 10011111
11110011
000000
1110110010
0
1
00
10
1
00
0
01
0
01
10
0
010
01101
11
1-
6-()
13+()
1+
78-()
1-2-
´
Multiplication requiring only n/2 summands.