Pipelined carry-lookahead generation for a fast incrementer

Details Pipelined carry-lookahead generation for a fast incrementer Pipelined carry-lookahead generation for a fast incrementer

2002-01-18

2003-07-08

Malzahn, David H. (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06591286

ABSTRACT:

BACKGROUND OF INVENTION
This invention relates to computer arithmetic devices, and more particularly to incrementers.
Many types of computing systems include an arithmetic-logic-unit (ALU). The ALU may be capable of performing sophisticated logical and arithmetic operations including multiply and divide. Special logic blocks may be added to speed up the more complex operations. A dedicated multiplier can rapidly perform multiply operations, while an integer divider can perform divide operations that otherwise would require thousands of clock cycles of the basic ALU.
These auxiliary math units may themselves contain several smaller blocks, such as shifters, adders, and leading-zero and other condition detectors. In particular, a divider may use an adder to increment a value such as for rounding a value from a floating point datapath. A general-purpose adder could be used for this sub-function.
Adders are often constructed from a one-bit adder cell known as a half-adder.
FIG. 1
shows a prior-art half-adder cell. The one-bit input A of bit position (i) is added to a carry-in input CI from the next lower bit position (i−1).
Both a sum S and a carry-out CO to the next higher bit position (i+1) are generated by half-adder cell
10
. The sum at position (i) of A and CI can be generated by exclusive-OR (XOR) gate
14
, while the carry out CO to position (i+1) is generated by AND gate
12
.
This is known as a half-adder cell because to perform a full add of two inputs X, Y, two such half-adder cells are needed for each bit position. One half-adder cell adds bit (i) of inputs X and Y to generate A(i), while the second half-adder cell adds the intermediate result A(i) to the carry CI(i) to generate the final sum.
While a full adder can be used to increment a binary number, a dedicated incrementer can be constructed. This incrementer can only add 1 or 0 to an input; it cannot add an arbitrary number as can a full adder. However, the amount of logic inside the incrementer can be less than the logic inside a full adder. A single half-adder cell is needed for each bit position in the incrementer, while two half-adder cells are required for each bit position in the full adder.
FIG. 2
shows a dedicated ripple-carry incrementer. Seven half-adder cells
10
are strung together to form a 7-bit incrementer. The carry-input CI to the lowest (least-significant bit or LSB) half-adder cell
10
is set to 1 to perform an increment. This LSB carry input may also be set to zero when no increment is desired.
The LSB half-adder cell
10
adds this lowest CI to the LSB of input A, A(
0
), to form sum bit S(
0
). The carry output of bit
0
is coupled to the carry input CI of the half-adder cell
10
adding the next higher bit, A(
1
). This second half-adder cell
10
generates sum S(
1
) and a carry out CI that is connected to the carry input CI of the third half-adder cell
10
.
The carry output generated by each half-adder cell is applied to the carry input of the next higher half-adder cell. The final carry output CO(
6
) from bit
6
can be discarded, or it can signal an overflow when it is a 1.
Since the carries are propagated through an AND gate in each half-adder cell
10
, the LSB carry bit may have to pass through seven AND gates to reach the final carry out of bit
6
in a worst-case delay path. This is known as a ripple carry since the carry signal ripples through all bits of the adder or incrementer.
In full adders, various techniques have been used to reduce this worst-case delay of the carry rippling through all the bits of the adder. For example, look-ahead logic can be used to generate an intermediate carry by looking at the binary-number inputs and carry into a group of bits.
What is desired is a look-ahead for an incrementer rather than for a full adder. An incrementer with a carry-lookahead is desired to reduce carry ripple delays in a fast incrementer. A pipelined incrementer is desired to further reduce delays that occur within a clock cycle.


REFERENCES:
patent: 4084254 (1978-04-01), Birney et al.
patent: 4110832 (1978-08-01), Leininger et al.
patent: 4153939 (1979-05-01), Kudou
patent: 4486851 (1984-12-01), Christopher et al.
patent: 4623982 (1986-11-01), Ware
patent: 4685078 (1987-08-01), Torres
patent: 4858168 (1989-08-01), Hwang
patent: 4956802 (1990-09-01), Priem
patent: 5027310 (1991-06-01), Dalrymple
patent: 5062057 (1991-10-01), Blacken et al.
patent: 5095458 (1992-03-01), Lynch et al.
patent: 5119494 (1992-06-01), Garman
patent: 5208770 (1993-05-01), Ito
patent: 5280579 (1994-01-01), Nye
patent: 5375079 (1994-12-01), Uramoto et al.
patent: 5384724 (1995-01-01), Jagini
patent: 5517440 (1996-05-01), Widigen et al.
patent: 5548546 (1996-08-01), Jang et al.
patent: 5555517 (1996-09-01), Agrawal et al.
patent: 5619441 (1997-04-01), Bartling
patent: 5945974 (1999-08-01), Sharma et al.
patent: 6101620 (2000-08-01), Ranganathan
patent: 6199090 (2001-03-01), Mansingh et al.
patent: 6279024 (2001-08-01), Chappell et al.
patent: 6347327 (2002-02-01), Petro et al.
patent: 6516335 (2003-02-01), Martin et al.

Affiliated with

Also associated with

Rating

Pipelined carry-lookahead generation for a fast incrementer does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Pipelined carry-lookahead generation for a fast incrementer, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pipelined carry-lookahead generation for a fast incrementer will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3109440