Low-error fixed-width modified booth multiplier

1. A method for fixed-width modified Booth multiplication, comprising:

encoding a W-bit multiplier using modified Booth coding;

processing the encoded multiplier and a multiplicand to generate partial products; and

accumulating the partial products to generate a W-bit product,

wherein said accumulating step comprises

dividing truncated bits into two groups, a major least significant bit group and a minor least significant bit group,

generating an approximate carry value using the bits of the minor least significant bit group, and

generating an exact carry value for the major least significant bit group using the approximate carry value and the bits of the major least significant bit group, and

wherein said approximate carry value is generated using a circuit designed in accordance with the steps of

forming a plurality of coded values y″ w/2−2 , y″ w/2−3 , . . . , y″ 1 and y″ 0 ,

selecting a number (N AC ) of approximate carry signals (a_carry — 0, a_carry — 1, . . . , a_carry_N AC−1 ) to be generated by said circuit,

assigning a value of 1 to an approximate carry signal (a_carry_i) if at least “2i+1” of the coded values y″ w/2−2 , y″ w/2−3 , . . . , y″ 1 and y″ 0 have a value of 1, and

applying a circuit design technique to the assigned values of the approximate carry signals (a_carry — 0, a_carry — 1, . . . , a_carry_N AC−1 ) to design said circuit.

2. The method of claim 1 , wherein said accumulating step comprises:

using an output of a Booth encoder to generate the approximate carry value.

3. The method of claim 1 , wherein said accumulating step comprises:

using a plurality of adder circuit carry signals to generate the approximate carry value.

4. The method of claim 1 , wherein said accumulating step comprises:

using adder circuits to accumulate more than W most significant bits; and

truncating the result of said accumulating step to W-bits.

5. The method of claim 1 , wherein said accumulating step comprises:

using adder circuits to accumulate more than W most significant bits; and

rounding the result of said accumulating step to W-bits.

6. The method of claim 1 , wherein said accumulating step comprises:

using adder circuits to accumulate exactly W most significant bits.

7. The method of claim 1 , wherein said accumulating step comprises:

using a plurality of digital logic circuits to generate the approximate carry value.

8. A fixed-width modified Booth multiplier, comprising:

a module that encodes a W-bit multiplier using modified Booth coding;

a module that processes the encoded multiplier and a multiplicand to generate partial products; and

a module that accumulates the partial products to generate a W-bit product,

wherein said module that accumulates comprises

means for generating an approximate carry value

designed in accordance with the steps of

forming a plurality of coded values y″ w/2−2 , y″ w/2−3 , . . . , y″ 1 and y″ 0 ,

selecting a number (N AC ) of approximate carry signals (a_carry — 0, a_carry — 1, . . . , a_carry_N AC−1 ) to be generated by said circuit,

assigning a value of 1 to an approximate carry signal (a_carry_i) if at least “2i+1” of the coded values y″ w/2−2 , y″ w/2−3 , . . . , y″ 1 and y″ 0 have a value of 1, and

applying a circuit design technique to the assigned values of the approximate carry signals (a_carry — 0, a_carry — 1, . . . , a_carry_N AC−1 ) to design said circuit.

9. The multiplier of claim 8 , wherein said module that encodes comprises:

a modified Booth encoder circuit.

10. The multiplier of claim 8 , wherein said module that processes comprises:

a partial product generation circuit.

11. The multiplier of claim 8 , wherein said module that accumulates comprises:

a plurality of digital logic circuits used to generate the approximated carry value.

12. The multiplier of claim 8 , wherein said module that accumulates comprises:

a plurality of adder circuits used to generate the approximated carry value.

13. A method for fixed-width multiplication, comprising:

(a) processing a modified Booth encoded multiplier and a multiplicand to generate a first group of N partial products and a second group of N partial products;

(b) associating each partial product of the first group of N partial products with a most significant bit group, a major least significant bit group, or a minor least significant bit group;

(c) associating each partial product of the second group of N partial products with the most significant bit group or the major least significant bit group;

(d) generating an approximate carry value for the minor least significant bit group;

(e) generating an exact carry value for the major least significant bit group using the approximate carry value and the value of each partial product associated with the major least significant bit group; and

(f) generating a product for the most significant bit group using the exact carry value and the value of each partial product associated with the most significant bit group,

wherein said approximate carry value is generated using a circuit designed in accordance with the steps of

forming a plurality of coded values y″ w/2−2 , y″ w/2−3 , . . . , y″ 1 and y″ 0 ,

selecting a number (N AC ) of approximate carry signals (a_carry — 0, a_carry — 1, . . . , a_carry_N AC−1 ) to be generated by said circuit,

assigning a value of 1 to an approximate carry signal (a_carry_i) if at least “2i+1” of the coded values y″ w/2−2 , y″ w/2−3 , . . . , y″ 1 and y″ 0 have a value of 1, and

applying a circuit design technique to the assigned values of the approximate carry signals (a_carry — 0, a_carry — 1, . . . , a_carry_N AC−1 ) to design said circuit.

14. The method of claim 13 , wherein said step of generating an approximate carry value comprises:

using an output of a Booth encoder to generate the approximate carry value.

15. The method of claim 13 , wherein said step of generating an approximate carry value comprises:

using a plurality of adder circuit carry signals to generate the approximate carry value.

16. A fixed-width multiplier, comprising:

a module that processes a modified Booth encoded multiplier (Y) and a multiplicand (X) to generate a first group of N partial products and a second group of N partial products;

a module that associates each partial product of the first group of N partial products with a most significant bit group, a major least significant bit group, or a minor least significant bit group;

a module that associates each partial product of the second group of N partial products with the most significant bit group or the major least significant bit group;

a module that generates an approximate carry value for the minor least significant bit group;

a module that generates an exact carry value for the major least significant bit group using the approximate carry value and the value of each partial product associated with the major least significant bit group; and

a module that generates a product for the most significant bit group using the exact carry value and the value of each partial product associated with the most significant bit group.

wherein said module that generates an approximate carry value is designed in accordance with the steps of

forming a plurality of coded values y″ w/2−2 , y″ w/2−3 , . . . , y″ 1 and y″ 0 ,

selecting a number (N AC ) of approximate carry signals (a_carry — 0, a_carry — 1, . . . , a_carry_N AC−1 ) to be generated by said circuit,

assigning a value of 1 to an approximate carry signal (a_carry_i) if at least “2i+1” of the coded values y″ w/2−2 , y″ w/2−3 , . . . , y″ 1 and y″ 0 have a value of 1, and

applying a circuit design technique to the assigned values of the approximate carry signals (a_carry — 0, a_carry — 1, . . . , a_carry_N AC−1 ) to design said circuit.

17. A method for designing a fixed-width multiplier comprising:

identifying a plurality of partial products formed for a W-bit multiplier and a W-bit multiplicand during modified Booth multiplication;

associating each of the partial products with a most significant bit group, a major least significant bit group, or a minor least significant bit group;

designing a circuit that generates an approximate carry value based on partial product values of the partial products associated with the minor least significant bit group;

designing a circuit that generates an exact carry value based on partial product values of the partial products associated with the major least significant bit group and an output of the circuit that generates an approximate carry value; and

designing a circuit that generates a product value based on partial product values of the partial products associated with the most significant bit group and an output of the circuit that generates an exact carry value

wherein said step of designing a circuit that generates an approximate carry value comprises

forming a plurality of coded values y″ w/2−2 , y″ w/2−3 , . . . , y″ 1 and y″ 0 ,

selecting a number (N AC ) of approximate carry signals (a_carry — 0, a_carry — 1, . . . , a_carry_N AC−1 ) to be generated by said circuit,

assigning a value of 1 to an approximate carry signal (a_carry_i) if at least “2i+1” of the coded values y″ w/2−2 , y″ w/2−3 , . . . , y″ 1 and y″ 0 have a value of 1, and

applying a circuit design technique to the assigned values of the approximate carry signals (a_carry — 0, a_carry — 1, . . . , a_carry_N AC−1 ) to design the approximate carry generation circuit.

18. The method of claim 17 , wherein said step of applying a circuit design technique comprises:

applying a Karnaugh map design technique.

19. A method for fixed-width modified Booth multiplication, comprising:

encoding a W-bit multiplier using modified Booth coding;

processing the encoded multiplier and a multiplicand to generate partial products; and

accumulating the partial products to generate a P-bit product, P being greater than W, and

wherein said accumulating step comprises

generating an approximate carry value

using a circuit designed in accordance with the steps of

forming a plurality of coded values y″ w/2−2 , y″ w/2−3 , . . . , y″ 1 and y″ 0 ,

selecting a number (N AC ) of approximate carry signals (a_carry — 0, a_carry — 1, . . . , a_carry_N AC−1 ) to be generated by said circuit,

assigning a value of 1 to an approximate carry signal (a_carry_i) if at least “2i+1” of the coded values y″ w/2−2 , y″ w/2−3 , . . . , y″ 1 and y″ 0 have a value of 1, and

applying a circuit design technique to the assigned values of the approximate carry signals (a_carry — 0, a_carry — 1, . . . , a_carry_N AC−1 ) to design said circuit.

20. The method of claim 19 , wherein said accumulating step comprises:

using adder circuits to accumulate more than P most significant bits; and

truncating the result of said accumulating step to P-bits.

21. The method of claim 19 , wherein said accumulating step comprises:

using adder circuits to accumulate more than P most significant bits; and

rounding the result of said accumulating step to P-bits.

22. A method for fixed-width modified Booth multiplication, comprising:

encoding a W-bit multiplier using modified Booth coding;

processing the encoded multiplier and a multiplicand to generate partial products; and

accumulating the partial products to generate a W-bit product,

wherein said accumulating step comprises generating an approximate carry value using a circuit designed in accordance with the steps of

forming a plurality of coded values y″ w/2−2 , y″ w/2−3 , . . . , y″ 1 and y″ 0 ,

selecting a number (N AC ) of approximate carry signals (a_carry — 0, a_carry — 1, . . . , a_carry_N AC−1 ) to be generated by said circuit,

assigning a value of 1 to an approximate carry signal (a_carry_i) if at least “2i+1” of the coded values y″ w/2−2 , y″ w/2−3 , . . . , y″ 1 and y″ 0 have a value of 1, and

applying a circuit design technique to the assigned values of the approximate carry signals (a_carry — 0, a_carry — 1, . . . , a_carry_N AC−1 ) to design said circuit.

23. The method of claim 22 , wherein said accumulating step comprises:

using an output of a Booth encoder to generate the approximate carry value.

24. The method of claim 22 , wherein said accumulating step comprises:

using a plurality of adder circuit carry signals to generate the approximate carry value.

25. The method of claim 22 , wherein said accumulating step comprises:

using adder circuits to accumulate more than W most significant bits; and

truncating the result of said accumulating step to W-bits.

26. The method of claim 22 , wherein said accumulating step comprises:

using adder circuits to accumulate more than W most significant bits; and

rounding the result of said accumulating step to W-bits.

27. The method of claim 22 , wherein said accumulating step comprises:

using adder circuits to accumulate exactly W most significant bits.

28. The method of claim 22 , wherein said accumulating step comprises:

using a plurality of digital logic circuits to generate the approximate carry value.