Incorporation of split-adder logic within a carry-skip adder...

Details Incorporation of split-adder logic within a carry-skip adder... Incorporation of split-adder logic within a carry-skip adder...

2000-05-11

2003-06-24

Malzhahn, David H. (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S710000

Reexamination Certificate

active

06584484

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to electronic circuits and more particularly to adders for use in semiconductor integrated circuits and other electronic devices.
BACKGROUND OF THE INVENTION
Adders are fundamental components of microprocessors, memory circuits, digital signal processors, communications hardware and numerous other electronic devices. The ever-increasing demand for higher speed and bandwidth in such devices requires that adders operate faster and support a longer word length.
In a conventional ripple-carry adder, a carry generated by an earlier adder stage is supplied to the next adder stage before the next stage can generate its carry. The carry propagation delay is therefore proportional to the number of stages in the adder.
A carry-skip adder provides reduced propagation delay relative to a ripple-carry adder by evaluating at a given adder stage each carry from the previous adder stages to determine if any stages can be skipped without affecting the addition result. The carry-skip adder is based on the principle that the carry propagation process can skip any adder stage j for which a
j
≠b
j
, where a
j
and b
j
denote the two binary numbers to be added in stage j. In other words, any adder stage j for which a propagate signal p
j
satisfies the condition p
j
=a
j
⊕b
j
=1 can be skipped. Several stages can be skipped if all such stages satisfy a
j
≠b
j
.
FIG. 1
shows an example of a conventional n-stage carry-skip adder
100
. The n-stage adder
100
includes n k-bit ripple-carry adders
102
-
1
, . . .
102
-j, . . .
102
-n, where 0<j≦n, and a set of carry-skip logic circuitry
104
. The number k is also referred to as the block length of the carry-skip adder, and each of the ripple-carry adders are also referred to as carry-skip stages or simply stages. Each of the k-bit ripple-carry adders
102
-i, i=1, 2, . . . n, receives corresponding partial inputs a
i
, b
i
, and generates a corresponding partial sum s
i
. In addition, each of the ripple-carry adders
102
-i other than the first adder
102
-
1
receives a corresponding primary carry input signal C
INi
generated by the carry-skip logic circuitry
104
. The first stage
102
-
1
receives a first carry input C
1
. All of the ripple-carry adders
102
-i other than the last adder
102
-n supply a corresponding carry output signal C
OUTi
to the carry-skip logic circuitry
104
.
Each of the k-bit adders
102
-i also generates a block-carry-propagate signal. For example, for the stage j adder
102
-j the block-carry propagate signal is defined as:
P
j
j+k−1
=p
j
·p
j+1
. . . p
j+k−1
, where
k<j.
The carry out C
OUTj
of the k-bit adder
102
-j may be expressed as
c
j+k
=P
j
j+k−1
·c
j
+G
j
j+k−1
where G
j
j+k−1
is a block-generate signal for the adder
102
-j.
Examples of conventional carry-skip adders are described in greater detail in U.S. Pat. No. 5,337,269 issued Aug. 9, 1994 in the name of inventors S. C. McMahan et al. and entitled “Carry Skip Adder with Independent Carry-In and Carry Skip Paths,” and U.S. Pat. No. 5,581,497 issued Dec. 3, 1996 in the name of inventor S. Kumar and entitled “Carry Skip Adder with Enhanced Grouping Scheme,” both of which are incorporated by reference herein.
It is generally desirable when designing a carry-skip adder to vary the block size k so as to optimize the carry propagation timing. In addition, it may also be possible to improve performance through the use of a multi-level skip.
Carry-skip adders are also often configured to include so-called split-adder logic. For example, many high speed communication and processing applications require an adder to perform full 32-bit additions as well as two parallel 16-bit additions. A conventional 32-bit carry-skip adder with split-adder logic uses a “split” control signal to configure the adder to perform either a 32-bit addition or two parallel 16-bit additions.
FIG. 2
illustrates the manner in which the above-described split function is implemented for an n-bit carry-skip adder with a three-stage carry skip, where each “stage” in this context corresponds to a particular bit of the n-bit carry-skip adder. More specifically,
FIG. 2
shows a portion of the (n/2+1)th carry-skip stage of the n-bit carry-skip adder. In the figure, a logic circuit
200
associated with this (n/2+1)th carry-skip stage includes a series arrangement of first level skip elements
202
-
1
,
202
-
2
and
202
-
3
. A carry C
INj
is applied to an input of the first level skip element
202
-
1
. The carry outputs of the skip elements
202
-
1
,
202
-
2
and
202
-
3
are denoted C
OUT
A
, C
OUT
B
and C
OUT
C
, respectively. Propagate signal outputs of the skip elements
202
-
1
,
202
-
2
and
202
-
3
are denoted P
A
, P
B
and P
C
, respectively, and are applied to inputs of a three-input AND gate
204
.
The AND gate
204
generates a propagate signal p(j:n/2+1) which is applied as a control signal to a control input of a two-to-one multiplexer
206
. If the propagate signal has a value of logic zero, the output C
OUT
C
of the skip element
202
-
3
is passed through to the output of multiplexer
206
as the carry signal C(n/2+1). If the propagate signal has a value of logic one, the carry C
INj
is passed through to the output of multiplexer
206
as the carry C(n/2+1).
The carry C(n/2+1) is then applied to one input of a two-to-one multiplexer
208
as shown. The other input of the multiplexer
208
receives input carry C
1
. The output of the multiplexer
208
represents the input carry C
INj+1
to the next stage of the carry-skip adder. The above-noted “split” control signal is applied to the control input of the multiplexer
208
. If the split control signal has a value of logic one, the carry-skip adder is operating as a 32-bit adder and the output carry is C
1
. If the split control signal has a value of logic zero, the carry-skip adder is operating as two parallel 16-bit adders, and the output carry is C(n/2+1). The multiplexer
208
thus serves as an additional multiplexing stage between the low and high half of the carry-skip adder, and is operative to pass along the carry C
1
in a 32-bit addition or to zero the carry-in bit to the high word in the two parallel 16-bit addition case.
A significant problem with the above-described conventional arrangement for the incorporation of split-adder logic into a carry-skip adder is that the additional multiplexing stage results in an undesirable increase in the carry propagation delay. A need therefore exists for an improved approach which permits the incorporation of split-adder logic into a carry-skip adder without introducing additional propagation delay.
SUMMARY OF THE INVENTION
The present invention provides a carry-skip adder in which split-adder logic is incorporated without introducing additional propagation delay.
In accordance with the invention, an n-bit carry-skip adder includes a number of carry-skip stages and a logic circuit associated with one or more of the stages. The logic circuit includes split-adder logic and carry-skip logic configured such that a split control signal associated with the split-adder logic is applied to at least one gate of the carry-skip logic, so as to reduce a carry propagation delay of the adder. The gate of the carry-skip logic may be, for example, a gate which is also driven by a propagate signal of a carry-skip stage.
In an illustrative embodiment, the logic circuit is associated with an (n/2+1)th carry-skip stage of the adder, and the adder is configured to perform two parallel n/2-bit additions when the split control signal is at a first logic level, and to perform a single n-bit addition when the split control signal is at a second logic level.
The logic circuit in the illustrative embodiment may include a series arrangement of skip elements, a first one of the skip elements in the series receiving a first carry, and an output of a final one

Affiliated with

Also associated with

Rating

Incorporation of split-adder logic within a carry-skip adder... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Incorporation of split-adder logic within a carry-skip adder..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Incorporation of split-adder logic within a carry-skip adder... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3109690