Low-error fixed-width modified booth multiplier
View Patent ↗A low-error fixed-width multiplier receives a W-bit input and produces a W-bit product. In an embodiment, a multiplier (Y) is encoded using modified Booth coding. The encoded multiplier (Y) and a multiplicand (X) are processed together to generate partial products. The partial products are accumulated to generate a product (P). To compensate for the quantization error, Booth encoder outputs are used for the generation of error compensation bias. The truncated bits are divided into two groups, a major least significant bit group and a minor least significant bit group, depending upon their effects on the quantization error. Different error compensation methods are applied to each group.
1. A method for fixed-width modified Booth multiplication, comprising:
generating partial products for a W-bit multiplier encoded using modified Booth coding and a multiplicand; and
accumulating the partial products to form a W-bit product,
wherein said accumulating step comprises
dividing truncated bits into two groups, LP MAJOR and LP MINOR , wherein LP is least significant product,
generating an approximate carry value using the bits of LP MINOR with a circuit that
produces a pre-selected number (N AC ) of approximate carry signals (a_carry_ 0 , a_carry_ 1 , . . . , a_carry_N AC-1 ),
wherein an approximate carry signal (a_carry_i) has a value of 1 if at least “2i+1” of a plurality of coded values y″ w/2-2 , y″ w/2-3 , . . . , y″ 1 and y″ 0 have a value of 1, and
generating an exact carry value for LP MAJOR using the approximate carry value and the bits of LP MAJOR .
2. The method of claim 1 , wherein said accumulating step comprises:
accumulating more than W most significant bits; and
truncating the result to W-bits.
3. The method of claim 1 , wherein said accumulating step comprises:
accumulating more than W most significant bits; and
rounding the result to W-bits.
4. The method of claim 1 , wherein said accumulating step comprises:
accumulating exactly W most significant bits.
5. A fixed-width modified Booth multiplier, comprising:
a module that processes a W-bit multiplier encoded using modified Booth coding and a multiplicand to generate partial products; and
a module that accumulates the partial products to form a W-bit product,
wherein said module that accumulates comprises a circuit that generates an approximate carry value using bits of a bit group LP MINOR wherein LP is least significant product, with a sub-circuit that
produces a pre-selected number (N AC ) of approximate carry signals (a_carry_ 0 , a_carry_ 1 , . . . , a_carry_N AC-1 ),
wherein an approximate carry signal (a_carry_i) has a value of 1 if at least “2i+1” of a plurality of coded values y″ w/2-2 , y″ w/2-3 , . . . , y″ 1 and y″ 0 have a value of 1.
6. The multiplier of claim 5 , wherein the module that accumulates comprises:
a plurality of adder circuits used to generate the approximated carry value.
7. The multiplier of claim 5 , wherein the module that accumulates accumulates more than W most significant bits; and truncates the result to W-bits.
8. The multiplier of claim 5 , wherein the module that accumulates accumulates more than W most significant bits; and rounds the result to W-bits.
9. The multiplier of claim 5 , wherein the module that accumulates accumulates exactly W most significant bits.
10. A multiplier, comprising:
a circuit that accumulates partial products to generate a product, the circuit comprising
a first sub-circuit that associates truncated bits with a bit group LP MAJOR or a bit group, LP MINOR wherein LP is least significant product,
a second sub-circuit that generates an approximate carry value using the bits associated with the bit group LP MINOR , wherein the second sub-circuit
produces a pre-selected number (N AC ) of approximate carry signals (a_carry_ 0 , a_carry_ 1 , . . . , a_carry_N AC-1 ),
wherein an approximate carry signal (a_carry_i) has a value of 1 if at least “2i+1” of a plurality of coded values y″ w/2-2 , y″ w/2-3 , . . . , y″ 1 and y″ 0 have a value of 1, and
a third sub-circuit that generates an exact carry value using the approximate carry value and the bits associated with the bit group LP MAJOR .
11. The multiplier of claim 10 , wherein an output of a Booth encoder is used to generate the approximate carry value.
12. The multiplier of claim 10 , wherein a plurality of adder circuit carry signals are used to generate the approximate carry value.
13. The multiplier of claim 10 , wherein the circuit accumulates more than W-bits and truncates the result to W-bits.
14. The multiplier of claim 10 , wherein the circuit accumulates more than W-bits and rounds the result to W-bits.
15. The multiplier of claim 10 , wherein the circuit accumulates exactly W-bits.