3X adder

Details 3X adder 3X adder

1998-10-14

2001-07-31

Malzahn, David H. (Department: 2187)

Electrical computers: arithmetic processing and calculating

Electrical digital calculating computer

Particular function performed

Reexamination Certificate

active

06269386

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to adders, and more particularly to adders for adding a binary number a to
2
a.
BACKGROUND
Performing floating point multiplication of binary operands with Booth encoding requires several multiples of the operands. Specifically, for radix-
8
Booth encoding with an operand a, the products ±a, ±2a, ±3a, and ±4a are required. All such products except ±3a are easily obtained with simple bit shifts. One way to obtain 3a is to add 2a to a, where 2a is obtained from a by a bit shift. However, the integer sum of 2a with a is required. We shall refer to an adder for providing a signal indicative of 3a for any binary number a as a 3x adder.
A Kogge-Stone adder can be useful for performing integer summation. Like a Carry Look Adder (CLA), the Kogge-Stone adder provides generate and propagate terms. However, to exploit parallelism, various bits of the operands are grouped together and the Kogge-Stone adder operates on these groups in parallel to provide group generate and group propagate terms for these groups. These group generate and group propagate terms are eventually used by the Kogge-Stone adder to provide the carry terms, from which the sum is obtained from these carry terms and the original operands. This is now described in more detail below.
A functional diagram for a Kogge-Stone adder is shown in FIG.
1
. The binary numbers a and b are added together to obtain their sum s. We denote the i
th
component of these binary numbers by a
i
, b
i
, and s
i
, respectively. In
FIG. 1
, the components of a and b are grouped into n+1 groups, where only the first (group 0), second (group 1), and last (group n) groups are explicitly shown. Not all groups need have the same number of components. For example, in
FIG. 1
, group
0
has j+1 components, group
1
has k+1 components, and group n has m+1 components.
PG generators
102
,
104
,
106
, and
108
provide group generate and group propagate terms. PG generators
102
,
104
, and
106
constitutes a first stage (level) and may be operated in parallel, and PG generator
108
constitutes a second stage (level). C generator
116
generates carry-out terms. CSS (Conditional Sum Selector) generators
110
,
112
, and
114
provide the sum s, and may be operated in parallel. Pipelining may be employed in which the first stage of PG generators operates on new data when the CSS generators are operating on old data.
The lines in
FIG. 1
represent data flow lines. Their physical realization may comprise more than one wire for carrying a signal, or signals may be time-multiplexed on a single wire (and ground plane). The designation of data represented by a data flow line is indicated in FIG.
1
. For example, PG generator
102
provides the terms gg
m
n
and gp
m
n
on data flow line
116
. These terms represent, respectively, the highest order (m) group generate and group propagate terms for group n. When describing group generate and group propagate terms for an arbitrary group, the superscripts for these terms will not be indicated.
An arbitrary PG generator is shown in FIG.
2
. For an arbitrary index i, gg
i
=1 if a carry-out term is generated when adding the binary number (x
i
x
i−1
. . . x
0
) to the binary number (y
i
y
i−1
. . . y
0
). The group generate term is zero otherwise. The group propagate term is given by gp
i
=1 if a carry-in term is propagated when adding the binary numbers (x
i
x
i−1
. . . x
0
) and (y
i
y
i−1
. . . y
0
). The group propagate term is zero otherwise.
The group generate and group propagate terms can be written in terms of the generate terms g
i
and propagate terms p
i
as indicated in
FIG. 2
, where p
i
=x
i
+y
i
and g
i
32
x
i
y
i
. Although the symbol + has been used before to indicate the ordinary summation symbol in the field of integers, in the previous sentence and elsewhere it is also used to indicate the logical (Boolean) OR in which the operands are now the Boolean elements “1” and “0”, and its particular meaning will be clear from context. The product of Boolean variables indicates the logical AND of the Boolean variables. In
FIG. 1
, the summation symbol &Sgr; indicates the logical OR sum. By definition, gg
0
=g
0
.
As shown in
FIG. 1
, the input data to PG generator
108
are the highest order group generate and group propagate terms from each PG generator in the first stage of the CLA. These quantities are operated on by PG generator
108
to provide new (effective) group generate and group propagate terms gg
i
and gp
i
, i=0, 1, . . . , n. These effective group generate and group propagate terms are interpreted as follows. Let a
i
denote group i of the components of a. Similarly for b
i
. For example, according to the grouping indicated in
FIG. 1
, a
0
=(a
j
a
j−1
. . . a
0
). Then, gg
i
=1 indicates that a carry-out term is generated when adding the two binary numbers (a
i
a
i−1
. . . a
0
) and (b
i
b
i−1
. . . b
0
), where these two binary numbers are formed from the concatenation of the first i+1 groupings of a and b, respectively. If gg
i
=0, then no carry-out term is generated. Similarly, gp
i
=1 indicates that a carry-in term is propagated when adding the two binary numbers (a
i
a
i−1
. . . a
0
) and (b
i
b
i−1
. . . b
0
). If gp
i
=0 , then no carry-in term is propagated.
As shown in
FIG. 1
, C generator
116
provides carry-out terms c
out
i
for i=0, 1, . . . n.
FIG. 3
also illustrates C generator
116
and provides the Boolean expression for the carry-out terms as a function of the effective group generate and group propagate terms and the carry-in term Cin . A carry-out term c
out
i
for some i is the carry-out term obtained by adding (a
i
a
i−1
. . . a
0
) and (b
i
b
i−1
. . . b
0
) in which the carry-in term is c
in
. This carry-in term may result from the sum of other bits not shown in FIG.
1
. For example, a
0
and b
0
need not be the least significant bits of the actual binary numbers to be added, in which case there may be other copies of the adder in
FIG. 1
to provide other sum bits, or the adder of
FIG. 1
may be used more than once in an iterative manner to obtain all sum bits.
As shown in
FIG. 1
, the carry-out terms from C generator
116
are provided to the CSS generators. For 0≦i<n, the carry-out term c
out
i
is the carry-in term to the CSS generator corresponding to group i+1. The carry-in term to CSS generator
114
for group
0
is c
in
. As shown in
FIG. 1
, the carry-out term c
out
0
is provided to CSS generator
112
corresponding to group
1
and the carry-out term c
out
n−1
is provided to CSS generator
110
corresponding to group n. Note that carry-out term c
out
n
is available for other adders (not shown), or to indicate overflow, etc.
FIG. 4
illustrates CSS generator
114
and provides the Boolean expression for the i
th
sum bit, s
i
. The symbol ⊕ denotes exclusive OR. The carry-in term c
i
is the carry-in term for bit position i, and its expression in terms of gg
i
, gp
i
, and c
in
(the carry-in term for CSS generator
114
) is also given in FIG.
4
. Similar expressions are easily generalized for the other CSS generators in the Kogge-Stone adder of
FIG. 1. A
circuit at the logic gate level for the CSS generator of
FIG. 4
is provided in
FIG. 5
, where MUX
502
switches to line
504
if c
in
=0 and switches to line
506
if c
in
=1.
From the expression for gg
i
given in
FIG. 2
, it is seen that obtaining the highest order group generator term gg
j
for a PG generator of size j+1(i.e., a PG generator corresponding to groupings of a and b with j+1 bits each) requires evaluating the logical OR of j+1 product terms, where the most complicated product term is the logical AND of j+1 terms.
For example, a domino or dynamic logic gate realization for obtaining the group generator term gg
4

Affiliated with

Also associated with

Rating

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

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2469561