Combined adder and pre-adder for high-radix multiplier circuit

• US 9,684,488 B2
• Filed: 03/26/2015
• Issued: 06/20/2017
• Est. Priority Date: 03/26/2015
• Status: Active Grant

• Current Assignee: Altera Corporation (Intel Corporation)
• Original Assignee: Altera Corporation (Intel Corporation)
• Inventors: Langhammer, Martin
• Primary Examiner(s): Malzahn, David H
• Application Number:
  US14/669,288
• Publication Number:
  US 20160283196A1
• Time in Patent Office: 817 Days
• Field of Search: None
• CPC Class Codes: G06F 7/49 Computations with a radix, other than binary, 8, 16 or decimal, e.g. ternary, negative or imaginary radices, mixed radix non-linear PCM G06F7/4824 takes precedence
• CPC Class Codes: G06F 7/501 Half or full adders, i.e. basic adder cells for one denomination
• CPC Class Codes: G06F 7/5312 using carry save adders

Abstract

Circuitry accepting a first input value and a second input value, and outputting (a) a first sum involving the first input value and the second input value, and (b) a second sum involving the first input value and the second input value, includes a first adder circuit, a second adder circuit, a compressor circuit and a preprocessing stage. The first input value and the second input value are input to the first adder circuit to provide the first sum. The first input value and the second input value are input to the preprocessing stage to provide inputs to the compressor circuit, which provides first and second compressed output signals which in turn are input to the second adder circuit to provide the second sum. The preprocessing stage may include circuitry to programmably zero the first input value, so that the first sum is programmably settable to the second input value.

Claims

1. Circuitry accepting a first input value and a second input value and outputting (a) a first sum involving said first input value and said second input value, and (b) a second sum involving said first input value and said second input value, said circuitry comprising:

a first adder circuit;

a second adder circuit;

a compressor circuit; and

a preprocessing stage;

wherein;

said first input value and said second input value are input to said first adder circuit to provide said first sum;

said first input value and said second input value are input to said preprocessing stage to provide inputs to said compressor circuit, said compressor circuit providing first and second compressed output signals;

said first and second compressed output signals are input to said second adder circuit to provide said second sum.

2. The circuitry of claim 1 wherein said first adder circuit and said second adder circuit are carry-propagate adders.

3. The circuitry of claim 1 wherein:

said preprocessing stage comprises circuitry to programmably zero said first input value;

whereby;

said first sum is programmably settable to said second input value.

4. The circuitry of claim 3 wherein said circuitry to programmably zero said first input value comprises an AND gate having as inputs said first input value and ground.

5. The circuitry of claim 1 wherein:

said preprocessing stage comprises circuitry to double each of said first input value and said second input value for input to said compressor circuit along with said first input value and said second input value;

whereby;

said second sum is three times said first sum.

6. The circuitry of claim 1 wherein:

said compressor circuit comprises respective separate circuitry for processing respective bit positions;

for a respective bit position, said respective separate circuitry has as inputs respective bits of each of said first and second input values, and respective next-less-significant bits of each of said first and second input values, and further includes an exclusive OR gate combining said respective bits of each of said first and second input values; and

output of said exclusive OR gate in said respective separate circuitry for said respective bit position is shared with respective separate circuitry for a next-more-significant bit position.

7. The circuitry of claim 6 wherein in said respective separate circuitry for said respective bit position, said respective next-less-significant bits of each of said first and second input values are borrowed from respective separate circuitry for a next-less-significant bit position.

8. The circuitry of claim 6 wherein said first adder circuit comprises:

a prefix tree having as inputs respective bits of said first and second input values, and providing as outputs respective carry values for each bit position; and

respective exclusive OR gates for each bit position, each respective exclusive OR gate having as inputs said respective carry value for said respective bit position, and said output of said exclusive OR gate in said respective separate circuitry for said respective bit position.

9. The circuitry of claim 8 wherein said prefix tree is a Kogge-Stone prefix tree.

10. Adder circuitry for two input values, wherein one of said two input values being twice another of said two input values, said adder circuitry comprising:

respective input exclusive OR gates for each bit position, each respective input exclusive OR gate having as inputs respective bits of said two input values;

a prefix tree having as inputs respective bits of said two input values, and providing as outputs respective carry values for each bit position; and

respective output exclusive OR gates for each bit position, each respective output exclusive OR gate having as inputs said respective carry value for said respective bit position, and said output of said respective input exclusive OR gate;

wherein;

said prefix tree is customized by constructing an initial level of said prefix tree based on each respective bit of said one of said two input values being identical to a respective next-less-significant bit of said another of said two input values.

11. The adder circuitry of claim 10 wherein said constructing of said initial level comprises collapsing first and second levels of said prefix tree based on simplifying the logic structures of the first and second levels.

12. The adder circuitry of claim 10 wherein said prefix tree is based on a Kogge-Stone prefix tree.

13. Circuitry accepting a first input value at a first input port and a second input value at a second input port and outputting (a) a first sum involving said first input value and said second input value, and (b) a second sum involving said first input value and said second input value, said circuitry comprising:

a first adder circuit;

a second adder circuit;

a compressor circuit coupled to said second adder circuit; and

a preprocessing stage coupled between said first and second input ports, said compressor circuit, and said first adder circuit, wherein said preprocessing stage comprises circuitry to programmably zero said first input value;

whereby;

said first sum is programmably settable to said second input value and said second sum is programmable to be independent of said first input value.

14. The circuitry of claim 13 wherein said circuitry to zero said first input value comprises an AND gate having as inputs said first input value and ground.

15. The circuitry of claim 13 wherein:

said first input value and said second input value are input to said first adder circuit to provide said first sum;

said first input value and said second input value are input to said preprocessing stage to provide inputs to said compressor circuit, said compressor circuit providing first and second compressed output signals;

said first and second compressed output signals are input to said second adder circuit to provide said second sum.

16. The circuitry of claim 13 wherein said first adder circuit and said second adder circuit are carry-propagate adders.

17. The circuitry of claim 13 wherein:

said preprocessing stage comprises circuitry to double each of said first input value and said second input value for input to said compressor circuit along with said first input value and said second input value;

whereby;

said second sum is three times said first sum.

18. The circuitry of claim 13 wherein:

said compressor circuit comprises respective separate circuitry for processing respective bit positions;

for a respective bit position, said respective separate circuitry has as inputs respective bits of each of said first and second input values, and respective next-less-significant bits of each of said first and second input values, and further includes an exclusive OR gate combining said respective bits of each of said first and second input values; and

output of said exclusive OR gate in said respective separate circuitry for said respective bit position is shared with respective separate circuitry for a next-more-significant bit position.

19. The circuitry of claim 18 wherein in said respective separate circuitry for said respective bit position, said respective next-less-significant bits of each of said first and second input values are borrowed from respective separate circuitry for a next-less-significant bit position.

20. The circuitry of claim 18 wherein said first adder circuit comprises:

a prefix tree having as inputs respective bits of said first and second input values, and providing as outputs respective carry values for each bit position; and

respective exclusive OR gates for each bit position, each respective exclusive OR gate having as inputs said respective carry value for said respective bit position, and said output of said exclusive OR gate in said respective separate circuitry for said respective bit position.

21. The circuitry of claim 20 wherein said prefix tree is a Kogge-Stone prefix tree.