Booth multiplier with enhanced reduction tree circuitry

• US 7,809,783 B2
• Filed: 02/15/2006
• Issued: 10/05/2010
• Est. Priority Date: 02/15/2006
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Krithivasan, Shankar, Koob, Christopher Edward
• Primary Examiner(s): Mai; Tan V
• Application Number:
  US11/355,397
• Publication Number:
  US 20070192398A1
• Time in Patent Office: 1,693 Days
• Field of Search: 708/628
• US Class Current: 708/628
• CPC Class Codes: G06F 7/5338 each bitgroup having two new bits, e.g. 2nd order MBA

Abstract

Techniques for the design and use of a digital signal processor, including processing transmissions in a communications (e.g., CDMA) system. A modified Booth multiplication system and process determine a multiplicand, A, and a multiplier, B. Radix-m, (e.g., radix-4) Booth recoding on B generates “n” multiplication factors, where “n,” an integer, is approximating one half of the number of the multiplier bits. “n” partial products are generated using the “n” multiplication factors as multipliers of A. Then, a multiplication tree is formed using radix-m Booth encoding. The multiplication tree includes multiplier bits associated to generate a multiplication factors. In the event of a negative multiplication factor, a two'"'"'s complement of A is formed by inverting the bits of A and associating a sticky “1” to complete the two'"'"'s complementation. Furthermore, multiplication factors are reduced in multiple stages to a form sum and carry components of a pre-determined length. The additive inverse of A×B is formed by using novel techniques to calculate the product of A and −B.

Claims

1. A method for performing Booth multiplication in a digital signal processor, the method comprising:

determining, by the digital signal processor, a multiplicand, A, comprising a first plurality of bits and a multiplier, B, comprising a second plurality of bits;

performing, by the digital signal processor, radix-m Booth recoding on B to generate a first predetermined number, n, of multiplication factors, the n multiplication factors approximating one half of the number of the second plurality of bits;

generating, by the digital signal processor, n partial products using the n multiplication factors as multipliers of A;

in the event of a negative multiplication factor, forming, by the digital signal processor, a two'"'"'s complement of A by inverting the first plurality of bits of A and associating a sticky “

1”

to complete the two'"'"'s complementation; and

reducing, by the digital signal processor, the partial products in multiple stages of reduction to a set of sum and carry components of a pre-determined length; and

generating, based on the set of sum and carry components, by the digital signal processor, a product of A and B.

2. The method of claim 1, wherein determining a multiplicand, A, and a multiplier, B, further comprises determining A and B using a 16×

16 multiplier.

3. The method of claim 1 further comprising:

determining the negative product of A and B by setting negative B as the multiplier by determining the additive inverse of the multiplication factors; and

generating the product as a summand of the form [Z+−

(A×

B)], where Z represents a value to be accumulated in the digital signal processor.

4. The method of claim 1 further comprising adding a rounding constant to the multiplication of A and B by inserting a sticky “

1”

into a predetermined bit of at least one of the partial products.

5. The method of claim 1 wherein:

performing radix-m Booth recoding on B further comprises performing radix-4 Booth recoding on B to generate nine multiplication factors;

generating n partial products further comprises generating nine partial products using the nine multiplication factors as multiples of A; and

reducing the partial products to a set of sum and carry components of a pre-determined length further comprises reducing the partial products to a plurality of 32-bit sum and carry components.

6. The method of claim 1 further comprising performing the Booth multiplication process as a part of a 64-bit value accumulation during a MAC operation.

7. A system for operation in association with a digital signal processor for performing Booth multiplication in the digital signal processor, comprising:

processing circuitry configured to determine a multiplicand, A, comprising a first plurality of bits and a multiplier, B, comprising a second plurality of bits;

a multiplier block configured to perform radix-m Booth recoding on B to generate a first predetermined number, n, of multiplication factors, the n multiplication factors approximating one half of the number of the second plurality of bits;

a plurality of multiplier units associated with the multiplier block configured to generate n partial products using the n multiplication factors as multipliers of A;

inverter circuitry configured to form a two'"'"'s complement of A, in the event of a negative multiplication factor, by inverting the first plurality of bits of A and associating a sticky “

1”

to complete the two'"'"'s complementation; and

reduction circuitry associated with the multiplier units configured to reduce the partial products in multiple stages of reduction to a set of sum and carry components of a pre-determined length and generate, based on the set of sum and carry components, a product of A and B.

8. The system of claim 7 wherein the processing circuitry is further configured to determine A and B using a 16×

16 multiplier.

9. The system of claim 7 wherein:

the inverter circuitry is further configured to determine the negative product of A and B by setting negative B as the multiplier by determining the additive inverse of the multiplication factors; and

the system further comprises, accumulation circuitry configured to generate the product as a summand of the form [Z+−

(A×

B)], where Z represents a value to be accumulated in the digital signal processor.

10. The system of claim 7 further comprising:

bit insertion circuitry configured to add a rounding constant to the multiplication of A and B by inserting a sticky “

1”

into a predetermined bit of at least one of the partial products.

11. The system of claim 7 wherein:

the multiplier block is further configured to perform radix-4 Booth recoding on B to generate nine multiplication factors;

the multiplier units are further configured to generate nine partial products using the nine multiplication factors as multiples of A;

the reduction circuitry is further configured to reduce the partial products to a plurality of 32-bit sum and carry components.

12. The system of claim 7 further comprising:

circuitry configured to perform the Booth multiplication process as a part of a 64-bit value accumulation during a MAC operation.

13. A digital signal processor for operation in support of a personal electronics device, the digital signal processor performing Booth multiplication in a digital signal processor, the digital signal processor comprising:

means for determining, by the digital signal processor, a multiplicand, A, comprising a first plurality of bits and a multiplier, B, comprising a second plurality of bits;

means for performing, by the digital signal processor, radix-m Booth recoding on B to generate a first predetermined number, n, of multiplication factors the n multiplication factors approximating one half of the number of the second plurality of bits;

means for generating, by the digital signal processor, n partial products using the n multiplication factors as multipliers of A;

means for, forming, by the digital signal processor, in the event of a negative multiplication factor, a two'"'"'s complement of A by inverting the first plurality of bits of A and associating a sticky “

1”

to complete the two'"'"'s complementation;

means for reducing, by the digital signal processor, the partial products in multiple stages of reduction to a set of sum and carry components of a pre-determined length; and

means for generating, based on the set of sum and carry components, a product of A and B.

14. The digital signal processor of claim 13 further comprising means for determining A and B using a 16×

16 multiplier.

15. The digital signal processor of claim 13 further comprising:

means for determining the negative product of A and B by setting negative B as the multiplier by determining the additive inverse of the multiplication factors; and

means for generating the product as a summand of the form [Z+−

(A×

B)], where Z represents a value to be accumulated in the digital signal processor.

16. The digital signal processor of claim 13 further comprising means for adding a rounding constant to the multiplication of A and B by inserting a sticky “

1”

into a predetermined bit of at least one of the partial products.

17. The digital signal processor of claim 13 further comprising:

means for performing radix-4 Booth recoding on B to generate nine multiplication factors;

means for generating nine partial products using the nine multiplication factors as multiples of A; and

means for reducing the partial products to a plurality of 32-bit sum and carry components.

18. The digital signal processor of claim 13 further comprising means for performing the Booth multiplication process as a part of a 64-bit value accumulation during a MAC operation.

19. A computer usable medium having computer readable program code embodied therein for performing Booth multiplication in a digital signal processor, comprising:

computer readable program code for determining, by the digital signal processor, a multiplicand, A, comprising a first plurality of bits and a multiplier, B, comprising a second plurality of bits;

computer readable program code for performing, by the digital signal processor, radix-m Booth recoding on B to generate a first predetermined number, n, of multiplication factors, the n multiplication factors approximating one half of the number of the second plurality of bits;

computer readable program code for generating, by the digital signal processor, n partial products using the n multiplication factors as multipliers of A;

computer readable program code for forming, by the digital signal processor, in the event of a negative multiplication factor, a two'"'"'s complement of A by inverting the first plurality of bits of A and associating a sticky “

1”

to complete the two'"'"'s complementation;

computer readable program code for reducing, by the digital signal processor, the partial products in multiple stages of reduction to a set of sum and carry components of a pre-determined length; and

computer readable program code for generating, based on the set of sum and carry components, a product of A and B.

20. The computer usable medium of claim 19 further comprising computer readable program code for determining A and B using a 16×

16 multiplier.

21. The computer usable medium of claim 19 further comprising:

computer readable program code for adding a rounding constant to the multiplication of A and B by inserting a sticky “

1”

into a predetermined bit of at least one of the partial products.

22. The computer usable medium of claim 19 further comprising:

computer readable program code for performing radix-4 Booth recoding on B to generate nine multiplication factors;

computer readable program code for generating nine partial products using the nine multiplication factors as multiples of A;

computer readable program code for reducing the partial products to a plurality of 32-bit sum and carry components.

23. The computer usable medium of claim 19 further comprising computer readable program code for performing the Booth multiplication process as a part of a 64-bit value accumulation during a MAC operation.

24. The computer usable medium of claim 19 further comprising:

computer readable program code for determining the negative product of A and B by setting negative B as the multiplier by determining the additive inverse of the multiplication factors; and

computer readable program code for generating the product as a summand of the form [Z+−

(A×

B)], where Z represents a value to be accumulated in the digital signal processor.