Carry skip adder

Details Carry skip adder Carry skip adder

2000-10-30

2004-05-11

Mai, Tan V. (Department: 2124)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06735612

ABSTRACT:

TECHNICAL FIELD
The present invention relates to a binary adder, and in particular to a multiple carry skip adder.
BACKGROUND OF THE INVENTION
A binary adder having multiple, 1024 to 2048, bits must be operated at high speed in order to process RSA encryption rapidly. However, according to a conventional technique, to be described below, the speed at which a binary adder can be operated is limited by a carry signal transmitted from a lower level, and a desirable operating speed can not be acquired. The conventional technique will now be described.
(1) Ripple Carry System
A ripple adder comprises parallel arranged full adders whose number is equivalent to that of the bits. But while a circuit required for a ripple carry system is not complicated, the maximum gate delay is equivalent to the total of the gate delays of the bits involved, and it is therefore very difficult to ensure a desirable operating speed.
(2) Carry Monitoring System
Since the maximum gate delay of the ripple adder is the maximum N stages for N bits, an ensured operating speed is reduced in inverse proportion to the number of bits. However, since the transfer of a carry is required only when two values, X and Y, to be added together are exclusively 1 and when a carry is transmitted from a lower level, these conditions are rarely sequential. For 1024 bits, as it is calculated that the above conditions happen for at most 11 sequential bits, the average operating speed is anticipated to be 100 times the ensured operating speed. In this system, a carry monitoring circuit is additionally provided to enter a waiting time when carries occur continuously. The carry monitoring system, however, requires a large circuit, and will increase power consumption and potentially will destabilize the operation.
(3) Carry Skip System
A binary adder is divided into several blocks to perform the addition in individual blocks, and a +1 compensation by a carry signal from a lower level. A binary adder according to this system is called a carry skip adder. Although it has a complicated circuit, the carry skip system requires only a small amount of power, and its operation is stable. The circuit for this system is more complicated than the ripple adder, and is as complicated as the adder for the carry monitor system.
In a one-stage carry step system, for the addition of N bits, n such that N≦n(n+2)/2+2 is acquired and (n+3) is a gate delay for n. For 1024 bits, N=1024 and n=45, i.e., a gate delay of 48 is obtained.
The carry skip system is described in, for example, Information Processing, Vol. 37, No. 1 pp. 80-85, Information Processing Institute, January 1996.
Furthermore, two-stage carry skip adder is described in IBM Technical Disclosure Bulletin Vol. 27, No. 11, April 1985, pp. 6785-6787. Since a binary adder is divided into blocks symmetrically, the operating speed is high for a small number of bits, but as the effect of skipping carries is reduced when handling a lot of bits, the operating speed becomes relatively slower.
OBJECTS AND SUMMARY OF THE INVENTION
It is, therefore, one object of the present invention to provide a binary adder that has two or more carry-skipped stages to enable a higher operating speed.
It is another object of the present invention to provide a high-speed multiplier that employs the carry skip adder.
An N-stage carry skip adder (N≧3), which is a first form of the present invention, includes a plurality of ripple adders, wherein at least one part of the plurality of ripple adders is divided into a plurality of groups. A carry signal is transferred from one group to one upper group, and if a group includes a plurality of ripple adders, a carry signal is transferred between ripple adders in the group. In addition, a circuit for calculating C=C
2
+F*C
1
is included, wherein the C
1
denotes a carry signal from the one group to the one upper group, and the F denotes a signal indicating whether or not outputs of all adders in the one upper group are 1s, and the C
2
denotes a carry signal associated with the most upper ripple adder in the one upper group.
Furthermore, if a group includes three or more ripple adders, the three or more ripple adders are organized into a plurality of groups at N−2 levels, the N-stage carry skip adder further comprises: a circuit for calculating C
2
1
=C
4
+F
2
0
*C
3
0
; and a circuit for calculating C
2
n+1
=C
2
n
+F
2
n
*C
3
n
, wherein 1≦n≦N−2, and C
2
N−1
=C
2
, and said C
3
0
denotes a carry signal transferred to the most upper ripple adder from a ripple adder in a group at a level 1 to which the most upper ripple adder belongs, and the level 1 is the lowest level, and the C
3
n
(1≦n≦N−2) denotes a carry signal transferred to a group at a level n to which the most upper ripple adder belongs from an adjacent group at the level n, and the C
4
denotes a carry signal of the most upper ripple adder, and the F
2
0
denotes a signal indicating whether or not outputs of all adder in the most upper ripple adder are 1s, and the F
2
n
denotes a signal indicating whether or not outputs of all adders upper than a ripple adder associated with a circuit outputting said C
3
n
and up to the most upper ripple adder are 1s.
By this configuration, the three or more-stage carry skip adder of the present invention can reduce a lot of gate delay. The carry signal is only transmitted to a upper adder, is never returned to a lower adder. In the three-stage carry skip adder, a plurality of ripple adders are further organized into groups at one level in addition to the primary grouping, and a circuit for calculating C
2
1
=C
4
+F
2
0
*C
3
0
and a circuit for calculating C
2
2
=C
2
=C
2
1
+F
2
1
*C
3
1
are included. In the four-stage carry skip adder, a plurality of ripple adders are further organized into groups at two levels in addition to the primary grouping, a circuit for calculating C
2
1
=C
4
+F
2
0
*C
3
0
, and a circuit for calculating C
2
2
=C
2
1
+F
2
1
*C
3
1
, and a circuit for calculating C
2
3
=C
2
=C
4
+F
2
2
*C
3
2
are included. The first form of the present invention indicates, for example, in
FIG. 3
, a set of AND circuit
435
and OR circuit
437
, a set of AND circuit
441
and OR circuit
443
, and a set of AND circuit
445
and OR circuit
447
.
C=C
2
+F*C
1
, C
2
1
=C
4
+F
2
0
*C
3
0
and C
2
n+1
=C
2
=C
2
n
+F
2
n
*C
3
n
mean that a carry signal of a specific adder is generated when a carry is generated by the specific adder, or when all adders of a block including the specific adder have outputs of 1 and a carry is forwarded from a preceding block.
In the first form of the present invention, there is a phrase “one part of the plurality of ripple adders” because a simple ripple adder or an adder in a different system may be additionally provided at a lower or an upper level of the above configured carry skip adder. Particularly, in an adder used in a multiplier, a modified circuit of the present invention, that deals with two types of carries independently generated, is connected to the lower level of the adder of the present invention.
The number of ripple adders in the one upper group may be equal to or more than that of ripple adders in the one group. Therefore, even if the number of bits becomes large, the speed of the addition can be enhanced.
A carry skip adder, which is a second form of the present invention, includes a plurality of carry skip adders, and at least one part of the plurality of ripple adders is divided into a plurality of groups, and a carry signal is transferred from one group to one upper group. The carry skip adder further comprises a circuit for calculating C=C
2
+F*C
1
, wherein the C
1
denotes a carry signal from the one group to the one upper group, and the F denotes a signal indicating whether or not outputs of all adders in the one upper group are 1s, and the C
2
denotes a carr

Affiliated with

Also associated with

Rating

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3201457