Adder circuit with a regular structure

Details Adder circuit with a regular structure Adder circuit with a regular structure

2001-04-05

2004-07-27

Ngo, Chuong Dinh (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S710000

Reexamination Certificate

active

06769007

ABSTRACT:

BACKGROUND
1. Field of the Invention
The present invention relates to digital circuitry for performing an addition operation. More specifically, the present invention relates to a method and an apparatus for performing an addition operation using a carry circuit with a regular structure.
2. Related Art
Binary addition of two n-bit numbers and a carry-in bit involves computing the sum
s
i
=a
i
xorb
i
xorc
i
  (EQ 1)
for each bit i (n≧i≧1). The inputs a
i
and b
i
are given, but the carry-in c
i
to each bit must be computed based on all of the less significant bits and the carry-in bit (bit
0
). Therefore, the fundamental problem of addition is computing the carries for each bit.
There are a multitude of approaches to carry generation offering tradeoffs among speed, area, and ease of layout. Microprocessors generally require maximum speed and thus employ some form of prefix computation to produce all of the carry signals in parallel. Such computations are based on the notion of generate, propagate, and kill (g, p, k) defined for a bit or group of bits. For brevity, we will use the term group, with the understanding that a bit is a group of one. Each group of bits may receive a carry-in signal. We would like to know if the group will produce a carry-out signal. Generate means that the group will produce a carry-out signal independent of whether a carry-in signal arrives. Propagate means the group will produce a carry-out signal if and only if a carry-in signal arrives. Kill means that the group will not produce a carry-out signal even if a carry-in signal arrives.
We define a group with the subscript i:j to span bits i . . . j inclusive (n≧i≧j≧0). A single bit group corresponding to bit i is given the name i:i. We first define g, p, and k for single bit groups in terms of the inputs a and b:
g
i:i
=a
i
*b
i
  (EQ 2)
p
i:i
=a
i
xorb
i
  (EQ 3)
k
i:i
=not(
a
i
)*not(
b
i
)  (EQ 4)
We now define g, p, and k for multibit groups recursively in terms of shorter groups spanning bits i:m and (m−1):j (i≧m>j). We define the more significant group i:m to be the top part and the less significant group (m−1):j to be the bottom part. A group generates a carry if the top part of the group generates or if the top part propagates and the bottom part generates. A group propagates a carry if both the top and bottom parts of the group propagate. The group kills the carry if the top part kills or if the top part propagates and the bottom part kills.
g
i:j
=g
i:m
+p
i:m
*g
(m−1)·j
  (EQ 5)
p
i:j
=p
i:m
*p
(m−1):j
  (EQ 6)
k
i:j
=k
i:m
+p
i:m
*k
(m−1):j
  (EQ 7)
We can consider bit
0
to describe the carry-in signal (c
m
) to the adder. Bit
0
will generate if the adder receives a carry-in and kill otherwise. Therefore, we define the base case:
g
0
=c
in
  (EQ 8)
p
0
=0  (EQ 9)
k
0
=not(c
in
)  (EQ 10)
From these equations, we can determine the carry-in to each bit of the adder:
c
i
=g
(i−1):0
  (EQ 11)
In other words, we receive a carry-in signal to the ith bit if and only if the less significant bits of the adder, including c
in
, collectively generate a carry. Observe that for all i, the prefix propagate p
i:0
is
0
because bit
0
always either generates or kills and a group propagates only if all the bits in the group propagate. Therefore, the generate and kill signals g
i:0
and k
i:0
are complementary. This may be useful because CMOS implementations of the final sum XOR gate require true and complementary versions of c
i
.
In summary, in a prefix adder we perform three operations:
(1) compute the pgk terms for each bit using (EQ 2)-(EQ 4), (EQ 8)-(EQ 10);
(2) compute the carry-in for each bit using (EQ 5)-(EQ 7), (EQ 11); and
(3) compute the sum for each bit using an XOR gate using (EQ 1).
Steps 1 and 3 are trivial, so we will focus on step 2. The recursive nature of the group pgk equations leads to circuits in the form of trees.
There are a variety of known trees offering tradeoffs between speed, gate count, and bisection width, i.e. the number of wires crossing the middle of the adder. The Brent-Kung tree is shown in
FIG. 1B
; an Elementary Prefix tree is shown in
FIG. 2
; and the Kogge-Stone tree is shown in FIG.
3
. In each of these adder tree diagrams, a line indicates a bus carrying the three pgk signals. Rounded rectangles indicate logic blocks performing the logic of (EQ 5)-(EQ 7). Each block is labeled with the index of the group pgk signals it computes. Triangles represent buffers and may be omitted altogether if fine-grained pipelining is not required. The inputs at the bottom of each figure are the single-bit pgk signals produced in step 1. The outputs at the top of each figure are the full prefix pgk signals including c
i
=g
i−1:0
used as the carry-in to the step 3 XOR.
Table 1 compares the three carry trees as a function of the number of bits n. Delay is measured in number of stages; this is an oversimplification because long wires or large fanouts will increase the delay of each stage. The total number of logic blocks is related to the number of transistors in the tree; buffers are not considered. We define fanout as the number of blocks receiving a signal divided by the number of ganged drivers of that signal. These prior art designs all have a single driver for each signal, so the fanout is simply the number of receivers. The lateral tracks row of the table describes the maximum number of busses running between bits of the tree.
TABLE 1
Brent-Kung
Elementary Prefix
Kogge-Stone
Delay
2log
2
n − 2
log
2
n
log
2
n
Logic Blocks
2n − log
2
n − 2
(n/2)log
2
n
(n-1)log
2
n + 1
Max Fanout
3
n/2 + 1
2
Lateral Tracks
2
1
n/2
The Brent-Kung tree has the worst delay but the fewest number of logic blocks. The Elementary Prefix adder uses fewer levels of logic. Unfortunately, the fanout between levels grows with the number of bits being added. This increases the delay of the adder and requires some cells to use transistors wider than others to drive the greater loads. The irregular widths increase the number of unique cells that must be laid out and verified. The Kogge-Stone adder solves the fanout problem by distributing computations, achieving good delay and constant fanout at the expense of more logic blocks than the Brent-Kung tree. However, the distributed computation leads to a number of lateral tracks that increases with n. These long wires occupy much area and consume more power when driven. All of the trees also involve driving wires of different lengths at different stages. The capacitance and sometimes resistance of the long wires dominates the stage delay and requires larger drivers in some cells, reducing the regularity or performance of the design.
What is needed is a method and an apparatus for performing a fast addition operation with a limited fanout for logic blocks and with a limited number of lateral tracks between successive stages of logical blocks.
SUMMARY
One embodiment of the present invention provides an apparatus for facilitating an addition operation between two N-bit numbers, wherein the apparatus has a regular structure. The apparatus includes a carry circuit for generating at least one carry signal for the addition operation, wherein the carry circuit includes a plurality of logic blocks organized into rows that form approximately logN successive stages of logic blocks. Each of these logic blocks provides current for at most a constant number of inputs in a successive stage of logic blocks. Additionally, within a given stage of logic blocks, outputs from multiple logic blocks are ganged together to drive a signal line that feeds multiple inputs in a successive stage of logic blocks. Furthermore, there are at most a constant number of lateral tracks in a planar layout of signal lines between the successive stages of logic blocks. Hence, the present invention ca

Affiliated with

Also associated with

Rating

Adder circuit with a regular structure does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Adder circuit with a regular structure, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Adder circuit with a regular structure will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3205316