Information Technology Reference
In-Depth Information
c
j
+
1
s
j
s
j
g
j
p
j
FA
j
c
j
c
j
+
1
v
j
u
j
v
j
u
j
c
j
Figure 2.15
A full adder realized with gates.
THEOREM
2.7.1
The addition function
f
(
n
)
n
+
1
can be realized with a ripple adder
with the following size and depth bounds over the basis
Ω=
2
n
add
:
B
→B
{∧
∨
⊕}
,
,
:
C
Ω
f
(
n
)
add
≤
5
n
−
3
D
Ω
f
(
n
)
add
≤
3
n
−
2
(Do the ripple adders actually have depth less than 3
n
−
2?)
2.7.1 Carry-Lookahead Addition
The ripple adder is economical; it uses a small number of gates. Unfortunately, it is slow. The
depth of the circuit, a measure of its speed, is linear in
n
, the number of bits in each integer.
The carry-lookahead adder described below is considerably faster. It uses the parallel prefix
circuit described in the preceding section.
The
carry-lookahead adder
circuit is obtained by applying the prefix operation to pairs
B
2
using the associative operator
:(
B
2
)
2
→B
2
defined below. Let
(
a
,
b
)
and
(
c
,
d
)
be
in
B
2
.Then
arbitrary pairs in
is defined by the following formula:
(
a
,
b
)
(
c
,
d
)=(
a
∧
c
,
(
b
∧
c
)
∨
d
)
To s h ow t h a t
is associative, it suffices to show by straightforward algebraic manipulation that
for all values of
a
,
b
,
c
,
d
,
e
,and
f
the following holds:
((
a
,
b
)
(
c
,
d
))
(
e
,
f
)=(
a
,
b
)
((
c
,
d
)
(
e
,
f
))
=(
ace
,
bce
∨
de
∨
f
)
π
[
k
,
k
]
. By induction it is
straightforward to show that the first component of
π
[
j
,
k
]
is 1 if and only if a carry propagates
through the full adder stages numbered
j
,
j
+
1,
...
,
k
and its second component is 1 if and
only if a carry is generated at the
r
th stage,
j
Let
π
[
j
,
j
]=(
p
j
,
g
j
)
and, for
j<k
,let
π
[
j
,
k
]=
π
[
j
,
k
−
1
]
≤
r
≤
k
, and propagates from that stage through
the
k
th stage. (See Problem
2.26
.)
The prefix computation on the string
(
π
[
0, 0
]
,
π
[
1, 1
]
,
...
,
π
[
n
−
1,
n
−
1
])
with the op-
erator
produces the string
(
π
[
0, 0
]
,
π
[
0, 1
]
,
π
[
0, 2
]
,
...
,
π
[
0,
n
−
1
])
. The first component of
Search WWH ::
Custom Search