Digital Signal Processing Reference
In-Depth Information
23
20
15
10
5
1
5
Level 0
10
Level 1
Level 2
Level 3
Level 4
Level 5
Final Partial Product row that need carry
propagate adder
Free Product
Bits
Figure 5.31
Wallace reduction tree applied on 12 PPs
further reduced using carry save addition, and this produces four layers. These four layers are
combined with the two layers that are not processed in the previous level. Now in level 2 there are six
layers; they form two groups of three layers and are reduced to four layers. Only one group is formed
at this stage. Repeating the reduction process twicewill reduce the number of layers to three and then
two. The final two layers can then be added using any CPA to produce the final product.
Wallace reduction is one of the most commonly used schemes in multiplier architecture. It falls
into the category of log time array multiplier as the reduction is performed in parallel in groups of
threes and this results only in a logarithmic increase in the number of adder levels as the number of
PPs increases (i.e. the size of the multiplier increases). The number of adder levels accounts for the
critical path delay of the combinational cloud. Each adder level incurs one FA delay in the path.
Table 5.3 shows the logarithmic increase in the adder levels as the number of partial products
increases. As theWallace reduction works on groups of three PPs, the adder levels are the same for a
range of number of PPs. For example, if the number of PPs is five or six, it will require three adder
levels to reduce the PPs to two layers for final addition.
Example: Figure 5.32 shows the layout of the Wallace reduction scheme on PP layers for a 6
6
multiplier of the reduction logic. In level 0, the six PPs are divided into two groups of three PPs each.
Search WWH ::
Custom Search