Fast digital adder

Details Fast digital adder Fast digital adder

1999-02-18

2003-05-06

Malzahn, David H. (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06560625

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates to the field of digital adders, and more specifically to digital adders using a carry look-ahead technique.
2. Discussion of the Related Art
FIG. 1
schematically and partially shows a conventional carry look-ahead 8-bit adder that calculates A+B=S where, A, B, and S are coded over eight bits. A first block
1
of the adder includes eight identical cells
11
, each having two inputs and one pair of outputs. A cell
11
of rank i is connected to receive on its first input bit A
i
and on its second input bit B
i
. It generates a first signal P
i
such that P
i
=A
i
+B
i
and an output signal G
i
such that G
i
=A
i
•B
i
. A second block of the adder receives the 8 couples of signals {P
1
, G
1
} to {P
8
, G
8
} coming from block
1
. Block
2
is formed of identical elementary cells
21
connected to calculate from the eight signal couples {P
1
, G
1
} to {P
8
, G
8
}, eight couples of output signals {p
1
, g
1
5} to {p
8
, g
8
}. If k is included between 2 and 8, p
k
is such that
p
k
=
π
i
=
1
⁢
 
⁢
P
i
,
with
⁢
 
⁢
p
1
=
P
1
and g
k
is such that
g
k
=
∑
i
=
1
k
-
1
⁢
 
⁢
(
G
i
⁢
π
j
=
i
+
1
k
⁢
 
⁢
P
j
)
+
G
k
,
with
⁢
 
⁢
g
1
=
G
1
The 8 couples {p
1
, g
1
} to {p
8
, g
8
} generated by block
2
allow calculation of sum S such that A+B=S. If C
0
is the entering carry of operation A+B, each term S
i
of sum S is given by S
k
=(C
0
•P
k-1
+g
k-1
)⊕A
k
⊕B
k
, with S
1
=C
0
⊕A
k
⊕B
k
. Similarly, if C
n
is the exiting carry of operation A+B, C
n
is given by C
n
=C
0
•p
n
+g
n
. The calculation of terms S
k
and C
n
is performed by a block
3
of the adder, the structure of which is well known in the art.
An elementary cell
21
includes two input couples {E
1
, E
2
} and {E
3
, E
4
} and an output couple {O
1
, O
2
}. Output O
1
is such that O
1
=E
1
. E
3
and output O
2
is such that O
2
=E
2
. E
4
+E
3
. It should be noted that no cell
21
is required to calculate couple {p
1
, g
1
} since {p
1
, g
1
}={P
1
, G
1
}. Conversely, a cell
21
is required to calculate {p
2
, g
2
} from {P
1
, G
1
} and {P
2
, G
2
}. Similarly, an additional cell
21
is required to calculate {p
3
, g
3
} from {p
2
, g
2
} and {P
3
, G
3
}.
The adder considered is an 8-bit adder. 8=2
3
, and it can be considered that block
2
is organized in a array of eight rows and three columns, a location of the array being occupied by a cell
21
or left empty. It should be noted that cells
21
of the third column of block
2
receive on their first input couple {E
1
, E
2
} the output couple {O
1
, O
2
} generated by the last cell
21
of the first half of the second column of block
2
.
Similarly, considering a 16-bit adder, block
2
of the 16-bit adder include comprise four columns and sixteen rows, and the eight cells of the fourth column of block
2
would receive on their first input couple {E
1
, E
2
} the output couple {O
1
, O
2
} of the last cell
21
of the first half of the third column.
A major disadvantage of this architecture is that it includes a critical path in which a successive cell
21
controls twice as many cells as the preceding cell. More specifically, a cell
11
controls a single cell of the first column. Some cells of the first column each control two cells of the second column. Some cells of the second column each control four cells of the third column, etc. In order not to increase the propagation time between a first cell which controls n cells and one of these n cells, the fan-out of the first cell must be n, that is, the output transistors of the first cell must have a size n times higher than the minimum size. However, the size increase of the output transistors of a cell increases the propagation time of a cell, since the gate capacitances of these transistors are higher and take longer to be charged. Thus, it will not be possible to make the propagation time of a critical path as small as that of a non-critical path, lest the size of all the transistors on the critical path is adapted, which is practically impossible to implement.
Further, the circuit will include cells
21
of identical function but of different sizes. These cells
21
of different sizes will have to be created in a special library of a design system, which increases the number of cells to be managed by the designer.
Similarly, at the design of an adder, the physical implantation of the various cells
21
will have to be performed with great care to best optimize the critical path propagation time.
SUMMARY OF THE INVENTION
An object of the present invention is to provide an architecture that implements a carry look-ahead adder having a particularly fast operation.
Another object of the present invention is to provide such an adder which does not occupy a greater surface area than a conventional carry look-ahead adder.
Another object of the present invention is to provide such an adder architecture which simplifies the management of a design system library.
These objects as well as others are achieved by a digital adder that adds a first n-bit operand A and a second n-bit operand B, with n=2
m
, comprising:
a first block calculating couples of signals Pq and Gq based on the bits of rank q, Aq and Bq, of the first and second operand, with Pq=Aq+Bq and Gq=Aq•Bq;
a second block formed of an array of elementary cells of identical functions arranged in n rows and m columns, an elementary cell having two inputs couples {E
1
, E
2
]} and {E
3
, E
4
} and one output couples {O
1
, O
2
}, providing O
1
=E
1
•E
3
and O
2
=E
2
•E
4
+E
3
;
a normal elementary cell, that is, of a column i and of a row j, j being included between k2
i
−2
i-1
+1 and k2
i
, with k varying between 1 and 2
m-i
, receiving:
on its first input couple, couple {P
j-1
, G
j-1
} if i=1 and the output couple coming from the elementary cell of column i-1 and of row (k-1)2
i
+1 otherwise,
on its second input couple, couple {P
j
, G
j
} if j=k2
i
−2
i-1
+1 or i=1, or the output couple coming from the elementary cell of row j and of the column r+1, r being defined so that 2
r
+1≦j−(k−1)2
i
−2
i-1
≦2
r+1
otherwise; and
an auxiliary elementary cell, that is, of a column i and of a row j, j being included between (k−1)2
i
+1 and k2
i
−2
i-30 1
, having its inputs and outputs connected in parallel with those of the elementary cells corresponding to a same value of k and of i, receiving:
on its first input couple, couple {P
j
, G
j
} if i=1 and the output couple coming from the elementary cell of column i−1 and of row (k−1)2
i
+1 otherwise, and
on its second input couple, couple {P
j+1
, G
j+1
} if i=1 and the output couple coming from the elementary cell of column i−1 and of row k2
i
−2
i-1
+1.
According to an embodiment of the present invention, the normal cells have a lower size than the auxiliary cells.
According to another embodiment of the present invention, the digital adder comprises means for, at least in the column of highest rank, selecting as an output the output couples of the normal cells or the second input couples of these cells.
The foregoing objects, features and advantages of the present invention will be discussed in detail in the following non-limiting description of specific embodiments in connection with the accompanying drawings.


REFERENCES:
patent: 5396435 (1995-03-01), Ginetti
patent:

Affiliated with

Also associated with

Rating

Fast digital 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 Fast digital adder, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fast digital adder will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3040003