Information Technology Reference
In-Depth Information
A multiplier for two
n
-bit binary can be formed by first creating the
n
(
2
n
−
1
)
-bit binary
numbers shown in (
2.8
) and then adding them, as explained above. These
n
numbers can be
added in groups of three, as suggested in Fig.
2.18
.
Let's now count the number of levels of carry-save adders in this construction. At the
zeroth level there are
m
0
=
n
numbers. At the
j
th level there are
m
j
=
2
m
j−
1
/
3
+
m
j−
1
−
m
j−
1
/
3
=
m
j−
1
−
m
j−
1
/
3
3
m
j−
1
/
3
binary numbers. This follows because there are
groups of three binary numbers and
each group is mapped to two binary numbers. Not combined into such groups are
m
j−
1
−
m
j−
1
/
3
binary numbers, giving the total
m
j
.Since
(
x
−
2
)
/
3
≤
x/
3
≤
x/
3, we have
2
3
m
j−
1
≤
2
3
m
j−
1
+
2
3
m
j
≤
from which it is easy to show by induction that the following inequality holds:
2
3
n
+
2
1
j
j
2
3
j
2
3
2
3
j
n
≤
m
j
≤
−
≤
n
+
2
Let
s
be the number of stages after which
m
s
=
2. Since
m
s−
1
≥
3, we have
log
2
(
n/
2
)
log
2
n
log
2
(
3
/
2
)
+
1
The number of carry-save adders used in this construction is
n
log
2
(
3
/
2
)
≤
s
≤
2. This follows from the
observation that the number of carry-save adders used in one stage is equal to the decrease in
the number of binary numbers from one stage to the next. Since we start with
n
and finish
with 2, the result follows.
After reducing the
n
binary numbers to two binary numbers through a series of carry-save
adder stages, the two remaining binary numbers are added in a traditional binary adder. Since
each carry-save adder operates on three
(
2
n
−
1
)
gates and have depth 3. Summarizing, we have the following theorem showing that carry-save
addition provides a multiplication circuit of depth
O
(log
n
)
but of size quadratic in
n
.
−
1
)
-bit binary numbers, they use at most 5
(
2
n
−
p
0
p
1
p
2
p
3
p
4
p
5
p
6
p
7
p
8
Figure 2.18
Schema for the carry-save combination of nine 18-bit numbers.
Search WWH ::
Custom Search