Efficient Multipliers Based on Multiple-Radix Representations

• US 20110270902A1
• Filed: 02/25/2011
• Published: 11/03/2011
• Est. Priority Date: 02/26/2010
• Status: Abandoned Application

• Current Assignee: UTI Limited Partnership
• Original Assignee: UTI Limited Partnership
• Inventors: Dimitrov, Vassil S., Adikari, Jithra, Järvinen, Kimmo U.
• Application Number:
  US13/035,467
• Publication Number:
  US 20110270902A1
• Time in Patent Office: Days
• US Class Current: 708/204
• CPC Class Codes: G06F 7/483 Computations with numbers represented by a non-linear combination of denominational numbers, e.g. rational numbers, logarithmic number system or floating-point numbers G06F7/4806, G06F7/4824, G06F7/49, G06F7/491, G06F7/544 take precedence
• CPC Class Codes: G06F 7/523 Multiplying only

Abstract

Methods and apparatus for multiplying integers using a double-base numbering system are presented. In one embodiment, a method includes splitting a first integer into a plurality of binary blocks. The method may also include encoding the plurality of binary blocks into a plurality of encoded blocks in a double-base numbering system. Additionally, the method may include producing a plurality of multiples of a second integer. The method may also include producing a plurality partial results. The method may include selectively shifting the plurality of partial results to generate a plurality of shifted partial results, and adding the plurality of partial results and the shifted partial results to create the product of a plurality of integers.

Claims

1. A method for multiplying integers in an integrated circuit, comprising:

splitting in an integrated circuit a first integer into a plurality of binary blocks;

encoding the plurality of binary blocks into a plurality of encoded blocks;

producing a plurality of multiples of a second integer;

producing a plurality of partial results from the plurality of encoded blocks and the plurality of multiples;

selectively shifting the plurality of partial results to generate a plurality of shifted partial results; and

adding at least one of the plurality of partial results and one of the shifted partial results to create the product of the first integer and the second integer.

2. The method of claim 1, wherein producing the partial results comprises:

selecting a first multiple of the second integer in response to a first subset of the encoded block;

selecting a second multiple of the second integer in response to a second subset of the encoded block;

shifting the first multiple of the second integer in response to a third subset of the encoded block;

shifting the second multiple of the second integer in response to a fourth subset of the encoded block; and

selectively adding or subtracting the first shifted multiple of the second integer and the second shifted multiple of the second integer in response to a fifth subset of the encoded block.

3. The method of claim 1, wherein the plurality of encoded blocks correspond to a number in a double-base numbering system.

4. The method of claim 3, where the double-base numbering system uses Booth encoding.

5. The method of claim 3, wherein the double base numbering system uses a 6-bit window and “

something-minus-something”

encoding.

6. The method of claim 3, wherein the double base numbering system uses a 5-bit window and “

something-minus-something”

encoding.

7. The method of claim 3, wherein the double base numbering system uses a 4-bit window and “

something-minus-something”

encoding.

8. The method of claim 2, wherein the first multiple is selected from the plurality of multiples of the second integer.

9. The method of claim 2, wherein the second multiple is selected from the plurality of multiples of the second integer.

10. The method of claim 1, wherein the partial results are selectively shifted in response to at least one of the width of the binary block and the position of the binary block.

11. The method of claim 1, wherein the multiples of the second integer comprise 1, 3, 5, and 7 times the second integer.

12. The method of claim 1, wherein the multiples of the second integer comprise 1, 3, 5, 7, 11, and 13 times the second integer.

13. The method of claim 1, wherein the multiples of the second integer comprise 1, 3, 5, 7, 11, and 119 times the second integer.

14. An apparatus comprising:

a splitter configured to convert a first integer into a plurality of binary blocks;

an encoder coupled to the splitter, the encoder configured to encode the plurality of binary blocks into a plurality of encoded blocks;

a processing module configured to produce a plurality of multiples of a second integer;

a partial results circuit coupled to the encoder and the processing module, the partial results circuit configured to produce a plurality partial results;

a shifter coupled to the partial results block, the shifter configured to selectively shift the plurality of partial results to generate a plurality of shifted partial results; and

an adder coupled to the shifter, the adder configured to add the plurality of partial results and the shifted partial results to create the product of a plurality of integers.

15. The apparatus of claim 14, wherein the partial results circuit is configured to:

select a first multiple of the second integer in response to a first subset of the encoded block;

select a second multiple of the second integer in response to a second subset of the encoded block;

shift the first multiple of the second integer in response to a third subset of the encoded block;

shift the second multiple of the second integer in response to a fourth subset of the encoded block; and

selectively add or subtract the first shifted multiple of the second integer and the second shifted multiple of the second integer in response to a fifth subset of the encoded block.

16. The apparatus of claim 14, wherein the plurality of encoded blocks correspond to a number in a double-base numbering system.

17. The apparatus of claim 16, where the double-base numbering system uses Booth encoding.

18. The method of claim 16, wherein the double base numbering system uses a 6-bit window and “

something-minus-something”

encoding.

19. The method of claim 16, wherein the double base numbering system uses a 5-bit window and “

something-minus-something”

encoding.

20. The method of claim 16, wherein the double base numbering system uses a 4-bit window and “

something-minus-something”

encoding.

21. The apparatus of claim 15, wherein the first multiple is selected from the plurality of multiples of the second integer.

22. The apparatus of claim 15, wherein the second multiple is selected from the plurality of multiples of the second integer.

23. The apparatus of claim 14, wherein the partial results circuit is further configured to selectively shift in response to at least one of the width of the binary block and the position of the binary block.

24. The apparatus of claim 14, wherein the multiples of the second integer comprise 1, 3, 5, and 7 times the second integer.

25. The apparatus of claim 14, wherein the multiples of the second integer comprise 1, 3, 5, 7, 11, and 13 times the second integer.

26. The apparatus of claim 14, wherein the multiples of the second integer comprise 1, 3, 5, 7, 11, and 119 times the second integer.