Power-efficient sign extension for booth multiplication methods and systems

• US 20070192399A1
• 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: Anderson, William, Krithivasan, Shankar, Koob, Christopher
• Granted Patent: US 7,797,366 B2
• Time in Patent Office: Days
• US Class Current: 708/620
• CPC Class Codes: G06F 7/49994 Sign extension
• CPC Class Codes: G06F 7/5338 each bitgroup having two new bits, e.g. 2nd order MBA
• CPC Class Codes: G06F 7/5443 Sum of products for applications thereof, see the relevant places, e.g. G06F17/10, H03H17/00

Abstract

Techniques for the design and use of a digital signal processor, including processing transmissions in a communications (e.g., CDMA) system. Power-efficient sign extension for Booth multiplication processes involves applying a sign bit in a Booth multiplication tree. The sign bit allows the Booth multiplication process to perform a sign extension step. This further involves one-extending a predetermined partial product row of the Booth multiplication tree using a sign bit for preserving the correct sign of the predetermined partial product row. The process and system resolve the signal value of the sign bit by generating a sign-extension bit in the Booth multiplication tree. The sign-extension bit is positioned in a carry-out column to extend the product of the Booth multiplication process. Then, the method and system form a final product from the Booth multiplication tree by adding the carry-out value to the sign bit positioned at least a predetermined column of the Booth multiplication tree. The result is to effectively extend the sum component of the final product with the sign and zero-extending the carry component of the final product.

Claims

1. A power-efficient sign extension method for facilitating a Booth multiplication process, comprising the steps of:

applying a sign bit in a Booth multiplication tree comprising a plurality of partial product rows, each of said partial product rows comprising a partial product for a Booth multiplication process, said sign bit for use in the event of the Booth multiplication process requiring a sign extension step;

one-extending a predetermined partial product row of said Booth multiplication tree using a sign bit for preserving the correct sign of said predetermined partial product row;

resolving the signal value of said sign bit by generating a sign-extension bit in said Booth multiplication tree, said sign-extension bit positioned to extend the product of the Booth multiplication process; and

forming a final product from said Booth multiplication tree by adding said carry-out value to said sign bit to at least a predetermined column of said Booth multiplication tree for effectively extending the sum component of said final product with the sign and zero-extending the carry component of said final product.

2. The method of claim 1, further comprising the step of reducing said plurality of partial products by

reducing nine partial product rows to six partial product rows using a first plurality of adder circuits;

reducing said six partial product rows to four partial product rows using a second plurality of adder circuits;

reducing said four partial product rows to a sum row and a carry row using a compressor circuit; and

modifying a sign bit to a 32^nd column of said 16×

16 Booth multiplication tree for performing sign extension for unsigned multiplication.

3. The method of claim 1, further comprising the step of including said sign bit as a bit, s8, in a last partial product row of said Booth multiplication tree.

4. The method of claim 1, wherein said Booth multiplication tree comprises a 16×

16 radix-4 Booth multiplication tree and further comprising the step of modifying columns higher than the 32^nd column only on or after the final stage of reduction of said plurality of partial products.

5. The method of claim 1, wherein said Booth multiplication tree comprises a 16×

16 radix-4 Booth multiplication tree and further comprising the step of forming a final product from said Booth multiplication tree by adding a carry-out value to the one-extension from the 32^nd and higher columns of said 16×

16 radix-4 Booth multiplication tree.

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

7. A power-efficient sign extension circuit associated with a digital signal process for performing a Booth multiplication process, comprising:

sign-application circuitry for applying a sign bit in a Booth multiplication tree comprising a plurality of partial product rows, each of said partial product rows comprising a partial product for a Booth multiplication process, said sign bit for use in the event of the Booth multiplication process requiring a sign extension step;

multiplication circuitry for one-extending a predetermined partial product row of said Booth multiplication tree using a sign bit for preserving the correct sign of said predetermined partial product row;

sign value resolution circuitry for resolving the signal value of said sign bit by generating a sign-extension bit in said Booth multiplication tree, said sign-extension bit positioned in a carry-out column to extend the product of the Booth multiplication process; and

said multiplication circuitry further for forming a final product from said Booth multiplication tree by adding said carry-out value to said sign bit to at least a predetermined column of said Booth multiplication tree for effectively extending the sum component of said final product with the sign and zero-extending the carry component of said final product.

8. The system of claim 7, further comprising:

a first plurality of adder circuits for reducing nine partial product rows to six partial product rows;

a second plurality of adder circuits rows for reducing said six partial product rows to four partial product rows;

a compressor circuit for reducing said four partial product rows to a sum row and a carry row using; and

encoding circuitry for adding a sign bit to a 32^nd column of said 16×

16 Booth multiplication tree for performing sign extension for unsigned multiplication.

9. The system of claim 7, further comprising encoding circuitry for adding said sign bit as a bit, s8, in a last partial product row of said Booth multiplication tree.

10. The system of claim 7, wherein said Booth multiplication tree comprises a 16×

16 radix-4 Booth multiplication tree and further comprising encoding circuitry for modifying columns higher than the 32^nd column only on or after the final stage of reduction of said plurality of partial products.

11. The system of claim 7, wherein said Booth multiplication tree comprises a 16×

16 radix-4 Booth multiplication tree and further comprising reduction circuitry for forming a final product from said Booth multiplication tree by adding a carry-out value to the one-extension from the 32nd and higher columns of said 16×

16 radix-4 Booth multiplication tree.

12. The system of claim 7, further multiplication 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 a power-efficient sign extension for a Booth multiplication process, said comprising the steps of:

means for applying a sign bit in a Booth multiplication tree comprising a plurality of partial product rows, each of said partial product rows comprising a partial product for a Booth multiplication process, said sign bit for use in the event of the Booth multiplication process requiring a sign extension step;

means for one-extending a predetermined partial product row of said Booth multiplication tree using a sign bit for preserving the correct sign of said predetermined partial product row;

means for resolving the signal value of said sign bit by generating a sign-extension bit in said Booth multiplication tree, said sign-extension bit positioned in a carry-out column to extend the product of the Booth multiplication process; and

means for forming a final product from said Booth multiplication tree by adding said carry-out value to said sign bit to at least a predetermined column of said Booth multiplication tree for effectively extending the sum component of said final product with the sign and zero-extending the carry component of said final product.

14. The digital signal processor of claim 13, further comprising means for reducing said plurality of partial products, said partial products reducing means comprising:

means for reducing nine partial product rows to six partial product rows using a first plurality of adder circuits;

means for reducing said six partial product rows to four partial product rows using a second plurality of adder rows;

means for reducing said four partial product rows to a sum row and a carry row using a compressor circuit; and

further

means for adding a sign bit to a 32^nd column of said 16×

16 Booth multiplication tree for performing sign extension for unsigned multiplication.

15. The digital signal processor of claim 13, further comprising the step of adding said sign bit as a bit, s8, in a last partial product row of said Booth multiplication tree.

16. The digital signal processor of claim 13, wherein said Booth multiplication tree comprises a 16×

16 radix-4 Booth multiplication tree and further comprising the step of modifying columns higher than the 32^nd column only on or after the final stage of reduction of said plurality of partial products.

17. The digital signal processor of claim 13, wherein said Booth multiplication tree comprises a 16×

16 radix-4 Booth multiplication tree and further comprising the step of forming a final product from said Booth multiplication tree by adding a carry-out value to the one-extension from the 32^nd and higher columns of said 16×

16 radix-4 Booth multiplication tree.

18. The digital signal processor of claim 13, further comprising the step of 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 a power-efficient sign extension method for a Booth multiplication process, comprising:

computer readable program code means for applying a sign bit in a Booth multiplication tree comprising a plurality of partial product rows, each of said partial product rows comprising a partial product for a Booth multiplication process, said sign bit for use in the event of the Booth multiplication process requiring a sign extension step;

computer readable program code means for one-extending a predetermined partial product row of said Booth multiplication tree using a sign bit for preserving the correct sign of said predetermined partial product row;

computer readable program code means for resolving the signal value of said sign bit by generating a sign-extension bit in said Booth multiplication tree, said sign-extension bit positioned in a carry-out column to extend the product of the Booth multiplication process; and

computer readable program code means for forming a final product from said Booth multiplication tree by adding said carry-out value to said sign bit to at least a predetermined column of said Booth multiplication tree for effectively extending the sum component of said final product with the sign and zero-extending the carry component of said final product.

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

computer readable program code means for reducing nine partial product rows to six partial product rows using a first plurality of adder circuits;

computer readable program code means for reducing said six partial product rows to four partial product rows using a second plurality of adder rows;

computer readable program code means for reducing said four partial product rows to a sum row and a carry row using a compressor circuit; and

computer readable program code means for adding a sign bit to a 32^nd column of said 16×

16 Booth multiplication tree for performing sign extension for unsigned multiplication.

21. The computer usable medium of claim 19, further comprising computer readable program code means for adding said sign bit as a bit, s8, in a last partial product row of said Booth multiplication tree.

22. The computer usable medium of claim 19, wherein said Booth multiplication tree comprises a 16×

16 radix-4 Booth multiplication tree and further computer readable program code means for modifying columns higher than the 32^nd column only on or after the final stage of reduction of said plurality of partial products.

23. The computer usable medium of claim 19, wherein said Booth multiplication tree comprises a 16×

16 radix-4 Booth multiplication tree and further comprising computer readable program code means for forming a final product from said Booth multiplication tree by adding a carry-out value to the one-extension from the 32^nd and higher columns of said 16×

16 radix-4 Booth multiplication tree.

24. 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.