Power-efficient sign extension for booth multiplication methods and systems

• US 7,797,366 B2
• Filed: 02/15/2006
• Issued: 09/14/2010
• Est. Priority Date: 02/15/2006
• Status: Active Grant

• Current Assignee: Qualcomm, Inc.
• Original Assignee: Qualcomm, Inc.
• Inventors: Anderson, William C., Krithivasan, Shankar, Koob, Christopher Edward
• Primary Examiner(s): Mai; Tan V
• Application Number:
  US11/356,359
• Publication Number:
  US 20070192399A1
• Time in Patent Office: 1,672 Days
• Field of Search: 708620-632
• US Class Current: 708/628
• 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., code division multiple access) 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 method comprising:

during a stage of a Booth multiplication operation at a hardware processing device, generating a sign extension bit for a sum portion of a partial product; and

using an adder to add the sum portion of the partial product to a zero extended carry portion of the partial product to generate a multiplication result.

2. The method of claim 1, wherein the Booth multiplication operation includes generating a plurality of partial product rows, each of the partial product rows having a corresponding sign bit.

3. The method of claim 2, wherein the sign extension bit is generated based on the sign bit corresponding to one of the partial product rows.

4. The method of claim 3, wherein the sign extension bit is generated by adding a carry bit based on the sign bit corresponding to the one of the partial product rows to a one-extended bit of the one of the partial product rows.

5. The method of claim 1, further comprising evaluating a sticky one bit corresponding to a partial product row of the Booth multiplication operation, and based on the evaluated sticky one bit, assigning data bit values to selected bits of a portion of another partial product row.

6. The method of claim 5, further comprising assigning the data bit values to the selected bits using a multiplexer to select the data bit values.

7. The method of claim 1, further comprising generating a data signal using the multiplication result and using a transmitter to transmit the data signal.

8. A method comprising:

during a stage of a Booth multiplication operation at a hardware processing device, generating a sign extension bit for a sum portion of a partial product associated with a first multiplier to form a sign extended sum portion of the partial product; and

using an adder to add the sign extended sum portion of the partial product to a value external to the first multiplier.

9. The method of claim 8, further comprising zero extending a carry portion of the partial product associated with the first multiplier.

10. The method of claim 8, further comprising sign extending a sum portion of a second partial product associated with a second multiplier.

11. The method of claim 8, wherein the value is at least one of a second sum portion and a second carry portion generated by a second multiplier.

12. The method of claim 8, further comprising adding a carry portion of the partial product to the value.

13. The method of claim 8, wherein the hardware processing device includes at least one of a processor, a multiplexer, and an accumulator.

14. The method of claim 8, wherein the partial product associated with the first multiplier corresponds to a first portion of a first operand multiplied with a first portion of a second operand, and wherein the value external to the first multiplier corresponds to a second portion of the first operand multiplied with a second portion of the second operand.

15. An apparatus comprising:

sign value resolution circuitry configured to generate a sign extension bit for a sum portion of a partial product during a stage of a Booth multiplication operation; and

multiplication circuitry configured to add the sum portion of the partial product to a zero extended carry portion of the partial product to generate a multiplication result.

16. The apparatus of claim 15, wherein the Booth multiplication operation generates a plurality of partial product rows, each of the partial product rows having a corresponding sign bit.

17. The apparatus of claim 16, wherein the sign extension bit is added to one of the plurality of partial product rows prior to resolving the plurality of partial product rows.

18. The apparatus of claim 16, wherein the sign extension bit is generated based on a sign bit of one of the plurality of partial product rows.

19. The apparatus of claim 16, wherein the sign extension bit is generated by adding a carry bit based on the sign bit of the one of the partial product rows to a one-extended bit of the one of the partial product rows.

20. The apparatus of claim 15, wherein at least one of the sign value resolution circuitry and the multiplication circuitry comprises a device that includes at least one of a processor, a multiplexer, a multiplier, and an accumulator.

21. The apparatus of claim 15, wherein the sign resolution circuitry is further configured to evaluate a sticky one bit corresponding to the partial product, and based on the evaluated sticky one bit, the sign resolution circuitry is configured to assign data values to selected bits of a portion of another partial product.

22. The apparatus of claim 21, further comprising a multiplexer configured to provide the data values at least partially based on the evaluated sticky one bit.

23. An apparatus comprising:

sign value resolution circuitry configured to generate a sign extension bit for a sum portion of a partial product associated with a first multiplier to form a sign extended sum portion of the partial product during a stage of a Booth multiplication operation; and

an adder configured to add the sign extended sum portion of the partial product to a value external to the first multiplier.

24. The apparatus of claim 23, wherein the Booth multiplication operation generates a plurality of partial product rows, each of the partial product rows having a corresponding sign bit.