Methods and apparatus for providing a booth multiplier
View Patent ↗Methods and apparatus for converting a radix 2 multiplier to respective groups of radix 4 encoded bits representing numbers of the group consisting of −2, −1, 0, 1, 2, wherein the set of encoded bits includes: a first bit that is true when the associated number is 2, a second bit that is true when the associated number is −2, a third bit that is true when the associated number is either negative or zero, and a fourth bit that is true when the associated number has an absolute value of 1.
1. An apparatus, comprising:
at least one encoder circuit including a plurality of logic gates operable to convert from radix 2 to radix 4 by receiving a group of bits of a multiplier and producing a set of encoded bits representing numbers of the group consisting of −2, −1, 0, 1, 2, wherein the set of encoded bits includes:
a first bit that is true when the associated number is 2,
a second bit that is true when the associated number is −2,
a third bit that is true when the associated number is either negative or zero, and
a fourth bit that is true when the associated number has an absolute value of 1; and
a plurality of selector circuits, each operable to:
(i) receive the encoded bits from the at least one encoder and a respective group of bits of the multiplicand, and
(ii) produce a respective bit of a partial product wherein:
each selector circuit is operable to receive a respective group of two bits of the multiplicand, Ai, Aj to produce the respective bit of a partial product, and
each selector circuit includes a plurality of logic gates that are operable to produce an output bit, Si, in accordance with the following Boolean expression: Si=(B 1 !AND Aj) !AND (B 2 !AND Aj) !AND (B 4 !AND (B 3 XOR Ai)).
2. The apparatus of claim 1 , wherein the encoder circuit includes:
a first circuit operable to receive three bits of the multiplier, yi, yj, yk and to produce the first bit of the set of encoded bits;
a second circuit operable to receive the yi, yj, yk bits and to produce the second bit of the set of encoded bits;
a third circuit operable to receive the yi bit and to produce the third bit of the set of encoded bits; and
a fourth circuit operable to receive the yj, yk bits and to produce the fourth bit of the set of encoded bits.
3. The apparatus of claim 2 , wherein the first circuit includes one or more logic gates that operate in accordance with the following truth table:
first
yi
yj
yk
bit
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
1
1
0
0
0
1
0
1
0
1
1
0
0
1
1
1
0.
4. The apparatus of claim 2 , wherein the second circuit includes one or more logic gates that operate in accordance with the following truth table:
second
yi
yj
yk
bit
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
0
1
0
0
1
1
0
1
0
1
1
0
0
1
1
1
0.
5. The apparatus of claim 2 , wherein the third circuit includes one or more logic gates that operate in accordance with the following truth table:
third
yi
yj
yk
bit
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
0
1
0
0
1
1
0
1
1
1
1
0
1
1
1
1
1.
6. The apparatus of claim 2 , wherein the fourth circuit includes one or more logic gates that operate in accordance with the following truth table:
fourth
yi
yj
yk
bit
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
0
0
0
1
0
1
1
1
1
0
1
1
1
1
0.
7. The apparatus of claim 1 , further comprising N/2 encoder circuits, where N is a number of bits in the multiplier, and each encoder circuit is operable to receive a different group of three bits of the multiplier, except for a last one of the encoders which receives a group of two bits of the multiplier and a null bit.
8. The apparatus of claim 7 , wherein:
the multiplier includes bits y 0 , y 1 , y 2 , y 3 , . . . yN−1;
a first of the encoders receives bits y 0 , y 1 , y 2 ;
a second of the encoders receives bits y 2 , y 3 , y 4 ; and
any further of the encoders receives bits in accordance with the pattern established by the above convention.
9. An apparatus, comprising:
at least one selector circuit operable to: (i) receive respective groups of encoded bits of a multiplier and a respective group of bits of a multiplicand; and (ii) produce a respective bit of a partial product,
wherein the encoded bits represent a radix 4 conversion of radix 2 numbers, the radix 4numbers being a group consisting of −2, −1, 0, 1, 2, and the set of encoded bits includes:
a first bit that is true when the associated number is 2,
a second bit that is true when the associated number is −2,
a third bit that is true when the associated number is either negative or zero, and
a fourth bit that is true when the associated number has an absolute value of 1;
the at least one selector circuit is operable to receive a respective group of two bits of the multiplicand, Ai, Aj to produce the respective bit of a partial product; and
the at least one selector circuit includes a plurality of logic gates that are operable to produce an output bit, Si, in accordance with the following Boolean expression: Si=(B 1 !AND Aj) !AND (B 2 !AND Aj) !AND (B 4 !AND (B 3 XOR Ai)), where Bi are the first, second, third and fourth encoded bits.
10. The apparatus of claim 9 , further comprising N selector circuits, where N is a number of bits in the multiplicand, and each selector circuit is operable to receive a different group of two bits of the multiplicand, except for a last one of the selector circuits which receives one bit of the multiplicand and a null bit.
11. The apparatus of claim 10 , wherein:
the multiplicand includes bits A 0 , A 1 , A 2 , A 3 , . . . AN−1;
a first of the selector circuits receives bits A 0 , A 1 ;
a second of the selector circuits receives bits A 1 , A 2 ;
a third of the selector circuits receives bits A 2 , A 3 ; and
any further of the selector circuits receives bits in accordance with the pattern established by the above convention.
12. The apparatus of claim 11 , wherein:
an aggregate of the output bits Si for a given group of encoded bits is a partial product of a product of the multiplier and the multiplicand; and
a sum of the partial products is the product of the multiplier and the multiplicand.
13. A method, comprising:
utilizing at least a processor for converting a set of radix 2 encoded bits of a multiplier to respective groups of radix 4 encoded bits representing numbers of the group consisting of −2, −1, 0, 1, 2,
wherein the set of encoded bits includes:
a first bit that is true when the associated number is 2,
a second bit that is true when the associated number is −2,
a third bit that is true when the associated number is either negative or zero, and
a fourth bit that is true when the associated number has an absolute value of 1;
receiving a respective group of two bits of the multiplicand, Ai, Aj and a respective group of encoded bits, Bi; and
producing a bit, Si, of a partial product in accordance with the following Boolean expression:
Si=(Bl !AND Aj) !AND (B 2 !AND Aj) !AND (B 4 !AND (B 3 XOR Ai)).
14. The method of claim 13 , further comprising producing the first, second, third and fourth bits in accordance with the following truth table:
1 st
2 nd
3 rd
4 th
yi
yj
yk
bit
bit
bit
bit
0
0
0
0
0
0
0
0
0
1
0
0
0
1
0
1
0
0
0
0
1
0
1
1
1
0
0
0
1
0
0
0
1
1
0
1
0
1
0
0
1
1
1
1
0
0
0
1
1
1
1
1
0
0
1
0.
15. The method of claim 14 , further comprising converting respective groups of three bits of the multiplier into the encoded bits, except for a last one of the groups which receives includes two bits of the multiplier and a null bit, wherein:
the multiplier includes bits y 0 , y 1 , y 2 , y 3 , . . . yN−1;
a first group of three bits of the multiplier includes y 0 , y 1 , y 2 ;
a second group of three bits of the multiplier includes y 2 , y 3 , y 4 ; and
any further groups of three bits of the multiplier includes bits in accordance with the pattern established by the above convention.
16. The method of claim 13 , further comprising: receiving a respective group of encoded bits and a respective group of bits of the multiplicand; and producing a respective bit of a partial product.
17. The method of claim 13 , wherein:
the multiplicand includes bits A 0 , A 1 , A 2 , A 3 , . . . AN−1;
a first group of two bits of the multiplicand consists of bits A 0 , A 1 ;
a second group of two bits of the multiplicand consists of bits A 1 , A 2 ;
a third group of two bits of the multiplicand consists of bits A 2 , A 3 ; and
any further groups of two bits of the multiplicand consists of bits in accordance with the pattern established by the above convention.
18. The method of claim 17 , further comprising assembling an aggregate of the bits Si for a given group of encoded bits to produce a partial product of a product of the multiplier and the multiplicand.
19. The method of claim 18 , further comprising summing the partial products to produce the product of the multiplier and the multiplicand.