Information Technology Reference
In-Depth Information
2.9.1 Carry-Save Multiplication
We now describe a much faster circuit obtained through the use of the carry-save adder. Let
u
,
v
,and
w
be three binary
n
-bit numbers. Their sum is a binary number
t
. It follows that
|
t
|
can be represented as
|
t
|
=
|
u
|
+
|
v
|
+
|
w
|
n
−
1
(
u
i
+
v
i
+
w
i
)
2
i
=
i
=
0
With a full adder the sum
(
u
i
+
v
i
+
w
i
)
canbeconvertedtothebinaryrepresentation
c
i
+
1
2
+
s
i
. Making this substitution, we have the following expression for the sum:
|
t
|
=
|
u
|
+
|
v
|
+
|
w
|
n
−
1
(
2
c
i
+
1
+
s
i
)
2
i
=
i
=
0
=
|
c
|
+
|
s
|
Here
c
with
c
0
=
0isan
(
n
+
1
)
-tuple and
s
is an
n
-tuple. The conversion of
(
u
i
,
v
i
,
w
i
)
to
(
c
i
+
1
,
s
i
)
can be done with the full adder circuit shown in Fig.
2.15
of size 5 and depth 3 over
the basis
Ω=
{∧
∨
⊕}
,
,
.
The function
f
(
n
)
2
n
+
2
that maps three binary
n
-tuples,
u
,
v
,and
w
,
to the pair (
c
,
s
) described above is the
carry-save adder
. A circuit of full adders that realizes
this function is shown in Fig.
2.17
.
3
n
carry
-
save
:
B
→B
THEOREM
2.9.1
The carry-save adder function
f
(
n
)
3
n
2
n
+
2
can be realized with
carry
-
save
:
B
→B
the following size and depth over the basis
Ω=
{∧
∨
⊕}
,
,
:
C
Ω
f
(
n
)
carry
-
save
≤
5
n
D
Ω
f
(
n
)
carry
-
save
≤
3
Three binary
n
-bit numbers
u
,
v
,
w
can be added by combining them in a carry-save
adder to produce the pair
(
c
,
s
)
, which are then added in an
(
n
+
1
)
-input binary adder. Any
adder can be used for this purpose.
s
n−
1
s
1
s
0
u
n
−
1
u
1
u
0
...
FA
n−
1
FA
1
FA
0
c
n
c
2
c
1
w
n−
1
v
n−
1
w
1
v
1
w
0
v
0
Figure 2.17
A carry-save adder realized by an array of full adders.
Search WWH ::
Custom Search