Information Technology Reference
In-Depth Information
a binary number
(
c
1
,
s
0
)
,where
c
1
2
1
+
s
0
2
0
=
u
0
+
v
0
, then the sum can be replaced by
n−
1
(
u
j
+
v
j
)
2
j
+(
u
1
+
v
1
+
c
1
)
2
1
+
s
0
2
0
|
u
|
|
v
|
+
=
j
=
2
where the least significant bit is now Boolean. In turn, the sum
u
1
+
v
1
+
c
1
can be represented
in binary by
(
c
2
,
s
1
)
,where
c
2
2
+
s
1
=
u
1
+
v
1
+
c
1
.Thesum
|
u
|
+
|
v
|
can then be replaced
by one in which the two least significant coefficients are Boolean. Repeating this process on all
coefficients, we have the
ripple adder
shown in Fig.
2.14
.
In the general case, the
j
th stage of a ripple adder combines the
j
th coefficients of each
binary number, namely
u
j
and
v
j
, and the carry from the previous stage,
c
j
, and represents
their integer sum with the binary notation
(
c
j
+
1
,
s
j
)
,where
c
j
+
1
2
+
s
j
=
u
j
+
v
j
+
c
j
Here
c
j
+
1
, the number of 2's in the sum
u
j
+
v
j
+
c
j
, is the carry into the
(
j
+
1
)
st stage
and
s
j
, the number of 1's in the sum modulo 2, is the external output from the
j
th stage.
The circuit performing this mapping is called a
full adder
(see Fig.
2.15
). As the reader can
easily show by constructing a table, this circuit computes the function
f
FA
:
3
2
,where
B
→B
f
FA
(
u
j
,
v
j
,
c
j
)=(
c
j
+
1
,
s
j
)
is described by the following formulas:
p
j
u
j
⊕
v
j
=
g
j
u
j
∧
v
j
=
(2.6)
c
j
+
1
=
p
j
∧
c
j
)
∨
g
j
s
j
=
p
j
⊕
c
j
Here
p
j
and
g
j
are intermediate variables with a special significance. If
g
j
=
1, a carry is
generated
at the
j
th stage. If
p
j
=
1, a carry from the previous stage is
propagated
through
the
j
th stage, that is, a carry-out occurs exactly when a carry-in occurs. Note that
p
j
and
g
j
cannot both have value 1.
The full adder can be realized with five gates and depth 3. Since the first full adder has
value 0 for its carry input, three gates can be eliminated from its circuit and its depth reduced
by 2. It follows that a ripple adder can be realized by a circuit with the following size and
depth.
s
4
s
3
s
2
s
1
s
0
FA
4
FA
3
FA
2
FA
1
FA
0
0
c
5
c
4
c
3
c
2
c
1
v
4
u
4
v
3
u
3
v
2
u
2
v
1
u
1
v
0
u
0
Figure 2.14
A ripple adder for binary numbers.
Search WWH ::
Custom Search