Parallel-prefix adder and method

Patent metadata

Field	Value
Publication number	US-10705797-B2
Application number	US-201816200689-A
Country	US
Kind code	B2
Filing date	Nov 27, 2018
Priority date	Nov 27, 2018
Publication date	Jul 7, 2020
Grant date	Jul 7, 2020

Abstract

Disclosed is a parallel prefix adder structure with a carry bit generation circuit that generates primary carry bits for only some bit pairs and a sum circuit with ripple carry adders that use these primary carry bits to generate secondary carry bits and sum bits for a final sum. The carry bit generation circuit has different sections, which process different sequential sets of bit pairs and which have different sparsity configurations. As a result, generation of the primary carry bits is non-uniform. That is, in the different sections the primary carry bits are generated at different carry bit-to-bit pair ratios (e.g., the carry bit-to-bit pair ratios for the different sections can be 1:2, 1:4, and 1:2, respectively). For optimal performance, the specific bit pairs for which these primary carry bits are generated varies depending upon whether the maximum operand size is an odd number of bits or an even number.

First claim

What is claimed is:

1. An adder comprising:
a primary carry bit generation circuit configured to receive corresponding propagation and generation signals for all bit pairs of same position bits of two addends and to generate primary carry bits, wherein the primary carry bit generation circuit comprises:
a first section that uses the corresponding propagation and generation signals for each bit pair in a first sequential set of bit pairs to generate first primary carry bits at a first carry bit-to-bit pair ratio;
a second section using the corresponding propagation and generation signals for each bit pair in a second sequential set of bit pairs to generate second primary carry bits at a second carry bit-to-bit pair ratio that is less than the first carry bit-to-bit pair ratio; and
a third section using the corresponding propagation and generation signals for each bit pair in a third sequential set of bit pairs to generate third primary carry bits at a third carry bit-to-bit pair ratio that is equal to the first carry bit-to-bit pair ratio.

2. The adder of claim 1 , wherein the first carry bit-to-bit pair ratio and the second carry bit-to-bit pair ratio are each 1:2 and wherein the second carry bit-to-bit pair ratio is 1:4.

3. The adder of claim 1 ,
wherein the two addends each have a same maximum number of bits between seventeen and thirty-two,
wherein the first sequential set of bit pairs comprises a first bit pair corresponding to a least significant bit position of the two addends, a second bit pair, a third bit pair, a fourth bit pair, a fifth bit pair, a sixth bit pair, a seventh bit pair and an eighth bit pair,
wherein the second sequential set of bit pairs comprises a ninth bit pair, a tenth bit pair, an eleventh bit pair, a twelfth bit pair, a thirteenth bit pair, a fourteenth bit pair, a fifteenth bit pair and a sixteenth bit pair, and
wherein the third sequential set of bit pairs comprises a seventeenth bit pair up to a last bit pair corresponding to a most significant bit position of the two addends.

4. The adder of claim 3 ,
wherein the maximum number is an odd number,
wherein the first section generates the first primary carry bits for the second bit pair, the fourth bit pair, and the sixth bit pair, and
wherein the second section generates the second primary carry bits for the tenth bit pair and the fourteenth bit pair.

5. The adder of claim 3 ,
wherein the maximum number is an even number,
wherein the first section generates the first primary carry bits for the third bit pair, the fifth bit pair, and the seventh bit pair, and
wherein the second section generates the second primary carry bits for the eleventh bit pair and the fifteenth bit pair.

6. The adder of claim 1 , further comprising a sum circuit configured to receive the primary carry bits, wherein the sum circuit comprises multiple ripple carry adders configured to use the primary carry bits during generation of secondary carry bits and sum bits for computation of a final sum.

7. The adder of claim 6 , wherein at least some of the multiple ripple carry adders have different lengths.

8. An adder comprising:
a signals generation circuit configured to receive two addends and to generate, for all bit pair of same position bits in the two addends, corresponding propagation and generation signals; and
a primary carry bit generation circuit configured to receive the corresponding propagation and generation signals and to generate primary carry bits, wherein the primary carry bit generation circuit comprises:
a first section using the corresponding propagation and generation signals for each bit pair in a first sequential set of bit pairs to generate first primary carry bits at a first carry bit-to-bit pair ratio of 1:2;
a second section using the corresponding propagation and generation signals for each bit pair in a second sequential set of bit pairs to generate second primary carry bits at a second carry bit-to-bit pair ratio of 1:4; and
a third section using the corresponding propagation and generation signals for each bit pair in a third sequential set of bit pairs to generate third primary carry bits at a third carry bit-to-bit pair ratio of 1:2.

9. The adder of claim 8 , further comprising: a sum circuit configured to receive the primary carry bits, wherein the sum circuit comprises multiple ripple carry adders configured to use the primary carry bits during generation of secondary carry bits and sum bits for computation of a final sum.

10. The adder of claim 9 ,
wherein the two addends each have a same maximum number of bits between seventeen and thirty-two,
wherein the first sequential set of bit pairs comprises a first bit pair corresponding to a least significant bit position of the two addends, a second bit pair, a third bit pair, a fourth bit pair, a fifth bit pair, a sixth bit pair, a seventh bit pair and an eighth bit pair,
wherein the second sequential set of bit pairs comprises a ninth bit pair, a tenth bit pair, an eleventh bit pair, a twelfth bit pair, a thirteenth bit pair, a fourteenth bit pair, a fifteenth bit pair and a sixteenth bit pair, and
wherein the third sequential set of bit pairs comprises a seventeenth bit pair up to a last bit pair corresponding to a most significant bit position of the two addends.

11. The adder of claim 10 ,
wherein the maximum number is an odd number,
wherein the first section generates the first primary carry bits for the second bit pair, the fourth bit pair, and the sixth bit pair,
wherein the second section generates the second primary carry bits for the tenth bit pair and the fourteenth bit pair,
wherein multiple ripple carry adders comprise first ripple carry adders that generate sum bits for the first bit pair through the tenth bit pair and further generate secondary carry bits for the first bit pair, the third bit pair, the fifth bit pair and the seventh bit pair through the ninth bit pair, and
wherein the multiple ripple carry adders comprise second ripple carry adders that generate sum bits for the eleventh bit pair through an eighteenth bit pair and further generate secondary carry bits for the eleventh bit pair through the thirteenth bit pair and for the fifteenth bit pair through the seventeenth bit pair.

12. The adder of claim 11 ,
wherein the first ripple carry adders include three first ripple carry adders, each comprising two full adders in series, and one first ripple carry adder with four full adders in series, and
wherein the second ripple carry adders include two second ripple carry adders each with four full adders in series.

13. The adder of claim 10 ,
wherein the maximum number is an even number,
wherein the first section generates the first primary carry bits for the third bit pair, the fifth bit pair, and the seventh bit pair,
wherein the second section generates the second primary carry bits for the eleventh bit pair and the fifteenth bit pair,
wherein the multiple ripple carry adders comprise first ripple carry adders that generate sum bits for the first bit pair through the eleventh bit pair and further generate secondary carry bits for the first bit pair, the second bit pair, the fourth bit pair, the sixth bit pair and the eighth bit pair through the tenth bit pair, and
wherein the multiple ripple carry adders further comprise second ripple carry adders that generate sum bits for the twelfth bit pair through a nineteenth bit pair and further generate the secondary carry bits for the twelfth bit pair through the fourteenth bit pair and for the sixteenth bit pair through the eighteenth bit pair.

14. The adder of claim 13 ,
wherein the first rippl

Assignees

• Marvell Int Ltd

Inventors

• Lokappa Ranjan B
• Arsovski Igor

Classifications

• G06F2207/5063

  2-input gates, i.e. only using 2-input logical gates, e.g. binary carry look-ahead, e.g. Kogge-Stone or Ladner-Fischer adder · CPC title

• G06F7/506 Primary

  with simultaneous carry generation for, or propagation over, two or more stages · CPC title