Digital Signal Processing Reference
In-Depth Information
Fig. 16
4:2 compressor
composed of full adders
(3:2 counters)
x
1
x
2
x
3
x
4
FA
c
out
c
in
FA
cs
full adders. Clearly, there is no major advantage using 4:2 compressors that are
implemented as in Fig.
16
compared to using 3:2 counters (full adders). However,
other possible realizations are available. These should satisfy
x
1
+
x
2
+
x
3
+
x
4
+
c
in
=
s
+
2
c
+
2
c
out
(21)
and
c
out
should be independent of
c
in
. There exist realizations with lower logic depth
compared to full adders, and, hence, the total delay of the multi-operand addition
may be reduced using 4:2 compressors.
It is important to note that an
n
:
k
counter or compressor reduces the number of
bits in the computation with exactly
n
k
. Hence, it is easy to estimate the required
number of counters and compressors to perform any addition if the original number
of bits to be added and the number of bits for the result are known. It should also be
noted, that depending on the actual structure it is typically impossible to use only
one type of compressors and adders. Specifically, half adders (or 2:2 counters) may
sometimes be needed, despite not reducing the number of bits, to move bits to the
correct weights for further additions.
−
3
Multiplication
The process of multiplication can be divided into three different steps: partial
product generation that determines a number of bits to be added, summation of
the generated partial products, and, for some of the summation structures, carry-
propagation addition, usually called vector merging addition (VMA), as many
summation structures produce redundant results.
3.1
Partial Product Generation
For unsigned binary representation, the partial product generation can be readily
realized using AND-gates computing bit-wise multiplications as
