Booth multiplier with enhanced reduction tree circuitry

• US 20070192398A1
• Filed: 02/15/2006
• Published: 08/16/2007
• Est. Priority Date: 02/15/2006
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Krithivasan, Shankar, Koob, Christopher
• Granted Patent: US 7,809,783 B2
• Time in Patent Office: Days
• US Class Current: 708/620
• 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

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

processing circuitry for determining a multiplicand, A, comprising a first plurality of bits and a multiplier, B, comprising a second plurality of bits;

a multiplier block for performing radix-4 Booth recoding on B to generate a first predetermined number, n, of multiplication factors, said “

n”

multiplication factors approximating one half of the number of said second plurality of bits;

a plurality of multiplier units associated with said multiplier block for generating “

n”

partial products using said “

n”

multiplication factors as multipliers of A;

Booth encoding circuitry associated with said plurality of multiplier units for forming a multiplication tree using radix-4 Booth encoding, said multiplication tree comprising a plurality of multiplier bits, said multiplier bits being associated in said multiplier tree for generating a plurality of multiplication factors;

inverter circuitry associated with said Booth encoding circuitry for the event of a negative multiplication factor, and in such event forming a two'"'"'s complement of A by inverting said first plurality of bits of A and associating a sticky “

1”

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

reduction circuitry associated with said multiplier units for reducing said multiplication factors in multiple stages of reduction to a set of sum and carry components of a pre-determined length; and

inverter circuitry for determining the negative product of A and B by setting −

B as the multiplier by determining the additive inverse of said multiplication factors.

8. The system of claim 7, further comprising multiplication tree generating circuitry for generating a multiplication tree for determining A and B using a 16×

16 multiplier.

9. The system of claim 7, further comprising accumulation circuitry for generating said 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:

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

1”

into a predetermined position of said multiplication tree.

11. The system of claim 7, further comprising:

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

partial product generating circuitry associated with said plurality of multiplier units for generating nine partial products using said nine multiplication factors as multiples of A;

multiplication tree circuitry for forming a multiplication tree using radix-4 Booth encoding, said multiplication tree comprising nine rows; and

reduction tree circuitry for reducing said multiplication tree to a plurality of 32-bit sum and carry components.

12. The system of claim 7, further comprising:

multiplication tree circuitry for performing said 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, said digital signal process comprising means for performing Booth multiplication in a digital signal processor, comprising:

means for determining a multiplicand, A, comprising a first plurality of bits and a multiplier, B, comprising a second plurality of bits;

means for performing radix-4 Booth recoding on B to generate a first predetermined number, n, of multiplication factors, said “

n”

multiplication factors approximating one half of the number of said second plurality of bits;

means for generating “

n”

partial products using said “

n”

multiplication factors as multipliers of A;

means for forming a multiplication tree using radix-4 Booth encoding, said multiplication tree comprising a plurality of multiplier bits, said multiplier bits being associated in said multiplier tree for generating a plurality of multiplication factors;

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

1”

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

means for reducing said multiplication factors in multiple stages of reduction to a set of sum and carry components of a pre-determined length; and

means for determining the negative product of A and B by setting −

B as the multiplier by determining the additive inverse of said multiplication factors.

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 generating said 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 position of said multiplication tree.

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

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

generating nine partial products using said 9 multiplication factors as multiples of A;

forming a multiplication tree using radix-4 Booth encoding, said multiplication tree comprising 9 rows; and

reducing said multiplication tree to a plurality of 32-bit sum and carry components.

18. The digital signal processor of claim 13, further comprising means for performing said 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 means embodied therein for performing Booth multiplication in a digital signal processor, comprising:

computer readable program code means for determining a multiplicand, A, comprising a first plurality of bits and a multiplier, B, comprising a second plurality of bits;

computer readable program code means for performing radix-4 Booth recoding on B to generate a first predetermined number, n, of multiplication factors, said “

n”

multiplication factors approximating one half of the number of said second plurality of bits;

computer readable program code means for generating “

n”

partial products using said “

n”

multiplication factors as multipliers of A;

computer readable program code means for forming a multiplication tree using radix-4 Booth encoding, said multiplication tree comprising a plurality of multiplier bits, said multiplier bits being associated in said multiplier tree for generating a plurality of multiplication factors;

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

1”

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

computer readable program code means for reducing said multiplication factors in multiple stages of reduction to a set of sum and carry components of a pre-determined length; and

computer readable program code means for determining the negative product of A and B by setting −

B as the multiplier by determining the additive inverse of said multiplication factors.

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

determining a multiplicand, A, comprising a first plurality of bits and a multiplier, B, comprising a second plurality of bits;

performing radix-4 Booth recoding on B to generate a first predetermined number, n, of multiplication factors, said “

n”

multiplication factors approximating one half of the number of said second plurality of bits;

generating “

n”

partial products using said “

n”

multiplication factors as multipliers of A;

forming a multiplication tree using radix-4 Booth encoding, said multiplication tree comprising a plurality of multiplier bits, said multiplier bits being associated in said multiplier tree for generating a plurality of multiplication factors;

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

1”

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

reducing said multiplication factors in multiple stages of reduction to a set of sum and carry components of a pre-determined length; and

determining the negative product of A and B by setting −

B as the multiplier by determining the additive inverse of said multiplication factors.

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

16 multiplier.

3. The method of claim 1, further comprising the step of generating said 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 the steps of adding a rounding constant to the multiplication of A and B by inserting a sticky “

1”

into a predetermined position of said multiplication tree.

5. The method of claim 1, further comprising the steps of:

performing radix-4 Booth recoding on B to generate 9 multiplication factors;

generating nine partial products using said nine multiplication factors as multiples of A;

forming a multiplication tree using radix-4 Booth encoding, said multiplication tree comprising nine rows; and

reducing said multiplication tree to a plurality of 32-bit sum and carry components.

6. The method of claim 1, further comprising the steps of:

performing said Booth multiplication process as a part of a 64-bit value accumulation during a MAC operation.

20. The computer usable medium of claim 19, further comprising:

computer readable program code means for determining A and B using a 16×

16 multiplier.

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

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

1”

into a predetermined position of said multiplication tree.

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

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

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

computer readable program code means for forming a multiplication tree using radix-4 Booth encoding, said multiplication tree comprising nine rows; and

computer readable program code means for reducing said multiplication tree to a plurality of 32-bit sum and carry components.

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

20-1. The computer usable medium of claim 19, further comprising:

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

(A×

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