Adder circuit

Details Adder circuit Adder circuit

1999-10-28

2002-08-20

Mai, Tan V. (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

C708S710000

Reexamination Certificate

active

06438571

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
The present invention relates generally to an adder circuit. More particularly, the invention relates to a carry look ahead system of a full adder circuit.
2. Description of the Related Art
An adder circuit has been used in various systems, such as a general purpose computer and so forth. In order to speed-up the adder circuit, a carry look ahead circuit has been used conventionally. It has been known that while a calculation period of n-bit adder circuit formed by serial connection of n in number of full adder circuits is proportional to n, the calculation period can be shortened in the extent of proportional to log
2
n by adding the carry look ahead circuit. It should be noted that the conventional carry look ahead circuit has been disclosed in Japanese Unexamined Patent Publication No. Heisei 8-123662 and Japanese Unexamined Patent Publication No. Heisei 9-167080, for example.
Necessity of the carry look ahead circuit will be discussed hereinafter with reference to
FIGS. 8 and 9
. In
FIGS. 8 and 9
, there are illustrated block diagrams showing example of adder circuits in the case of performing addition of two 6-bit integers
X
and
Y
. Full adders
1
.
1
to
1
.
6
for the least significant bits (X
1
, Y
1
) to the most significant bits (X
6
, Y
6
) are sequentially connected in serial connection so that respective carry outputs CO (generally representing C
1
to C
5
) in the preceding digits are supplied to carry inputs CI in the next digit. Respective results of addition are shown as Z
1
to Z
6
and final carry is taken as CO.
FIG. 8
shows a timing chart illustrating an example of calculation in the case where (X
i
, Y
i
) is (0, 1), and a carry input of the initial digit is “1”. On the other hand,
FIG. 9
shows a timing chart illustrating an example of calculation in the case where (X
1
, Y
1
), (X
3
, Y
3
), (X
4
, Y
4
), (X
6
, Y
6
) are (1, 0) and (X
2
, Y
2
), (X
5
, Y
5
) are (1, 1), and the carry input CI in the initial digit is “1”.
The example of
FIG. 8
shows the case where carry is caused in every digit in the six digits. Therefore, it can be appreciated that correct result of addition cannot be obtained until a flow of time (sequence of operation) becomes “8”. On the other hand, in the example of
FIG. 9
, the correct result of addition can be obtained at and after time flow “4”. In
FIG. 9
, considering the case that carry is caused sequentially, it can be appreciated that a correct output can be obtained by waiting three times of carry at minimum.
In the adder circuit constructed with a plurality of full adders connected in serial connection in the condition where the carry look ahead circuit is not provided, it cannot be known how long waiting period is required for determining the output with the carries unless the input data
X
and
Y
to be added are determined as in the examples shown in
FIGS. 8 and 9
. Therefore, in consideration of the worst case as exemplarily illustrated in
FIG. 8
, a waiting period permitting occurrence of carry in every digits is preliminarily provided to take out the output from the full adder in the final digit after the preset waiting period.
However, by checking how long waiting period is required in all of n-bit input data
X
and
Y
respectively, it can be appreciated that an average waiting period is a value proportional to log
2
n. This means that if an input data is assumed to be a random value, the correct result of calculation can be obtained by waiting for a preliminarily set waiting period proportional to log
2
n unconditionally.
In the general purpose computer or so forth, the adder circuit is typically used for performing addition of integer of thirty-two to sixty-four bits. In the recent year, in a public-key cryptosystem or so forth, it has been required to perform addition of large number of digits in the extent of a thousand twenty-four to two thousands forty-eight bits. However, if addition is attempted to speed-up by means of the conventionally known carry look ahead circuit in order to satisfy such requirement, for example, scale of the circuit inherently becomes large.
SUMMARY OF THE INVENTION
It is an object of the present invention to provide an adder circuit which can perform addition at high speed with a smaller scale circuit than that of an adder circuit employing a carry look ahead circuit.
In order to accomplish the above-mentioned and other objects, according to the first aspect of the present invention, an adder circuit performing addition of two integers respective consisted of n=k m bits wherein n, m and k are integers, comprises:
m in number of k-bit adding means connected in serial connection in such a manner that an carry output in a preceding digit is supplied to a carry input in a following digit;
m in number of carry propagation alarm means provided corresponding to respective of m in number of k-bit adding means, for outputting carry propagation alarm signal only when carry input of corresponding adding means is propagated to a carry output; and
OR means for performing OR for performing OR operation of the m in number of carry propagation alarm signals for generating a carry alarm signal,
wherein a fixed result of addition is derived from a final digit of the adding means in serial connection after extinction of generation of the carry alarm signal.
The adder circuit may further comprise means for leading the fixed result of addition after expiration of a given period which is set longer than a period for addition in each of the adding means and after extinction of the carry alarm signal.
According to the second aspect of the present invention, an adder circuit performing addition of two integers respective consisted of n=k m+b bits wherein n, m, b and k are integers, comprises:
m in number of k-bit adding means connected in serial connection in such a manner that an carry output in a preceding digit is supplied to a carry input in a following digit, and a single b-bit adding means;
m in number of carry propagation alarm means provided corresponding to respective of m in number of k-bit adding means, for outputting carry propagation alarm signal only when carry input of corresponding adding means is propagated to a carry output; and
OR means for performing OR for performing OR operation of the m in number of carry propagation alarm signals for generating a carry alarm signal,
wherein a fixed result of addition is derived from a final digit of the adding means in serial connection after extinction of generation of the carry alarm signal.
The m in number of k-bit adding means may be provided for each of m in number of blocks in the case where n bits of the two integer are divided into a b-bit lowermost block and into 1+m in number of blocks by dividing each s sequentially per k bits for performing addition of corresponding pair of k-bit blocks. Each of the k-bit adding means may be k-bit full adders.
In the preferred construction, each of the m in number of carry propagation alarm means may comprise:
k in number of exclusive OR means for performing exclusive OR operation of respective of corresponding bits of the two integers;
first AND means for performing AND operation of k in number of exclusive OR outputs;
single exclusive OR means for performing exclusive OR operation of the carry input and the carry output of the corresponding adding means; and
second AND means for performing AND operation of an output of the single exclusive OR means and an output of the first AND means, output of the second AND means serving as the carry propagation alarm signal.


REFERENCES:
patent: 5065353 (1991-11-01), Nojiri et al.
patent: 5109480 (1992-04-01), Sone et al.
patent: 3-75925 (1991-03-01), None
patent: 8-123662 (1996-05-01), None
patent: 9-167080 (1997-06-01), None

Affiliated with

Also associated with

Rating

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2929163