Electronic digital logic circuitry – Multifunctional or programmable – Array
Reexamination Certificate
2000-10-03
2001-09-11
Tokar, Michael (Department: 2819)
Electronic digital logic circuitry
Multifunctional or programmable
Array
C326S040000, C708S235000
Reexamination Certificate
active
06288570
ABSTRACT:
FIELD OF THE INVENTION
This invention relates to large integrated circuits, more particularly to programmable or configurable logic devices.
BACKGROUND
One kind of function performed in programmable logic devices is arithmetic. A device such as a configurable logic array of Xilinx, Inc., assignee of the present invention, can perform arithmetic as well as a multitude of other logic functions. Such devices are described in U.S. Pat. Nos. 4,870,302 and 4,706,216, and U.S. patent application Ser. No. 07/387,566, which are incorporated herein by reference. Because these devices are intended for general purpose functions, arithmetic is relatively slow and requires a significant amount of silicon area.
Other programmable logic devices, such as the programmable array logic device described in Birkner, U.S. Pat. No. 4,124,899 and user programmable devices described in Elgamal et al, U.S. Pat. No. 4,758,745 also can be programmed to perform arithmetic. These two patents are also incorporated by reference. In these devices, the speed of performing arithmetic and other functions which use carry logic is limited by propagation of the carry signal. Also, the general purpose logic used to implement the carry function is significant.
For understanding how logic devices perform arithmetic, and particularly what causes delay, the following discussion of arithmetic functions will focus on adders. However, the discussion can easily be extended to apply to subtractors, incrementers, decrementers, and accumulators, in addition to other circuits which use carry-logic.
The following discussion will focus on operation of the middle stages in a multi-bit adder. The least significant bit is a special case because there can be no carry signal to be received from a less significant bit. The most significant bit is a special case because the carry bit can be used for determining an overflow condition. These two special cases will be discussed in detail later.
By reference to
FIGS. 1
a
,
1
b
and
2
, it will be explained how the speed of a single bit ripple carry adder (FIGS. i
a
and
1
b
), and thus a multi-bit ripple carry adder constructed by cascading single bit adders (
FIG. 2
) is constrained by the speed at which the signal at the carry-in terminal is propagated to the carry-out terminal.
The Boolean logic equations governing the behavior of the single bit adder shown in
FIG. 1
a
are:
S
i
(
A
i
@B
i
)@
C
i
(1)
C
i+1
=A
i
·B
i
+(
A
i
@B
i
)·
C
i
(2)
where
@ represents the exclusive-or (XOR) function,
· represents the AND function, and
+ represents the OR function.
Eq.(1) shows that the sum is a function of a carry-in from a less significant bit in addition to the single bits A
i
and B
i
being added. The ripple carry adder algorithm of Eqs. (1) and (2) shows that the sum for a particular bit cannot be calculated until the carry-out from the previous bit is available. The sum S
i
is the output of an XOR gate and cannot be generated until each of its inputs, one of which is the carry-in signal C
i
, is available.
Furthermore, the carry-out C
i+1
also cannot be generated until the less significant carry bit C
i
is available. Referring now to
FIG. 2
, the propagation of the carry signal through successive stages of a ripple carry adder will be explained. AND gate
67
in the second adder stage Add
i+1
receives one of its inputs from the output of XOR gate
66
after only 1 gate delay. However, assuming that the carry-in signal C
i
is preset (that is, that Add
i
is the least significant bit), AND gate
67
could wait an additional 3 gate delays for the effect of A
i
and B
i
to propagate through gates
61
,
62
and
65
before its other input, the carry-out C
i+1
from the less significant bit, has been generated from the carry out of the less significant bit C
i
and the less significant bits A
i
and B
i
to be added. Furthermore, the carry-out C
i+2
of the second bit Add
i+1
is further delayed through 2 more gates after the carry bit C
i+1
has been generated. That is, combining the inputs on A
i+1
, and B
i+1
with the carry in signal C
i+
to generate C
i+2
requires that C
i+1
propagate through AND gate
67
and OR gate
70
. Thus, there will not be a valid carry-in signal C
i+2
for input to a third stage until 5 gate delays after the application of the input signals A
i
and B
i
. Thus, the speed of the conventional ripple carry adder is constrained by the speed of propagation of the carry signal. The propagation delay of a conventional ripple carry adder is 2
n+
1
gates where n is the number of stages in the multi-bit adder.
Since addition is the foundation of many other important functions and operations, it has been important to the computer industry to devise faster adder circuits by speeding up the carry propagation time. In general, these methods work by trading component density and complexity for carry propagation speed.
One well-known algorithm which achieves a faster carry propagation speed is called look-ahead carry logic. A circuit for implementing look-ahead carry logic is shown in FIG.
3
. Understanding this logic requires the introduction of two new variables:
P
i
=A
i
@B
i
(3)
G
i
=A
i
·B
i
(4)
The variable P is called “carry propagate” because when P is high, carry-in is propagated to carry-out. The variable G is called “carry generate” because when G is high, a carry-out is generated by the bits being added.
Eqs. (1) and (2) can be rewritten in terms of these new variables:
S
i
=P
i
@C
i
(5)
C
i+1
=G
i
+P
i
·C
i
(6)
With some minor algebraic manipulation, Eq. (6) can be used to write new equations where the carry bit at each level is dependent only on the addends at each level and the least significant carry bit. The following equations are implemented in the four bit adder shown in FIG.
3
:
C
1
=A
0
B
0
=G
0
(7
a
)
C
2
=G
1
+P
1
C
1
=G
1
+P
1
C
1
(7
b
)
C
3
=G
2
+P
2
C
2
=G
2
+P
2(
G
1
+P
1
C
l
)=
G
2
+P
2
G
1
+P
2
P
1
C
1
(7
c
)
C
4
=G
3
+P
3
C
3
=G
3
+P
3
(G
2
+P
2
G
1
+P
2
P
1
C
1
)=G
3
+P
3
G
2
+P
3
P
2
G
1
+P
3
P
2
P
1
C
1
(7
d
)
Each G
i
and P
i
is a function only of A
i
and B
i
and not of previous carry values, as can be seen in Eqs. 3 and 4. Second, note in Eq. 7
b
that C
2
is calculated as a function of G
1
, P
1
, and C
1
, and that in Eq. 7
c
, C
3
is calculated as a function of G
2
, P
2
and C
2
. But since C
2
has been solved in terms of C
1
, C
3
can also be solved in terms of C
1
. Attention to Eq. 7
d
, and the more general Eq. 6 will reveal that each C
i+1
is a function of several G
i
's, P
i
's, and C
1
. As can be seen in
FIG. 3
, the less significant bit is fed into the next significant bit only for the calculation of the sum, not for the calculation of the carry bit. Since each carry bit is a function of several G
i
's, P
i
's, and C
1
, each carry bit is not dependent on the carry-out of any but the least significant bit. Thus the carry propagation delay of the look-ahead carry circuit is independent of the number of bits being added.
Referring still to FIG.
3
and
FIG. 1
a
, the delay from the application of the input signals (A's and B's) to the appearance of a valid signal at the generate outputs (G
i
's) and propagate outputs (P
i
's) of an adder stage is 1 gate (this can be discerned from
FIG. 1
a
). The delay added in
FIG. 3
by the carry restorer portion of the look ahead carry circuitry is 2 gates, which makes a total of a 3-gate delay from the application of the input signals to the adder until the last carry-out bit is available. This relationship is independent of the number of bits being added. For a multibit adder circuit, the delay will be sign
Chang Daniel D.
Tokar Michael
Xilinx , Inc.
Young Edel M.
LandOfFree
Logic structure and circuit for fast carry does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Logic structure and circuit for fast carry, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Logic structure and circuit for fast carry will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2459194