Digital Signal Processing Reference
In-Depth Information
Level 0
HA
FA
FA
FA
FA
HA
Level 1
FA
FA
FA
FA
FA
HA
Level 2
FA
FA
FA
HA
FA
FA
Level 3
FA
FA
FA
FA
FA
HA
P
4
P
0
P
P
P
3
2
1
CPA
Free product bits
Figure 5.30
Carry save reduction scheme layout for a 6
6 multiplier
Figure 5.30 shows a layout of carry save reduction for reducing PPs of a 6
6 multiplier. The
layout clearly shows use of HAs and FAs and production of free bits. There are four levels of logic
and each level reduces three layers to two.
5.8.3.2 Dual Carry Save Reduction
The partial products are divided into two equal-size sub-groups. The carry save reduction scheme is
applied on both the sub-groups simultaneously. This results in two sets of partial product layers in
each sub-group. The technique finally results in four layers of PPs. These layers are then reduced as
one group into three, and then into two layers.
5.8.3.3 Wallace Tree Reduction
Partial products are divided into groups of three PPs each. Unlike the linear time array reduction of
the carry save and dual carry save schemes, these groups of partial products are reduced
simultaneously using CSAs. Each layer of CSAs compresses three layers to two layers. These
two layers from each group are re-grouped into a set of three layers. The next level of logic again
reduces three-layer groups into two layers. This process continues until only two rows are left. At this
stage any CPA can be used to compute the final product.
Figure 5.31 shows the implementation of Wallace tree reduction of 12 partial products. The PPs
are divided into four groups of three PPs each. In level 0, carry save reduction is applied on each
group simultaneously. Each group reduces its three layers to two layers, and as a result eight layers
are produced. These eight layers are further grouped into three PPs each; this forms two groups of
three layers each, and two layers are left as they are. In level 1, these two groups of three layers are
Search WWH ::
Custom Search