Design Options for Basic Building Blocks - Digital Design of Signal Processing Systems: A Practical Approach - page 229

Consider the following sequence from aWallace tree reduction scheme given as the upper limit of
column 1 in Table 5.3:

2 3 4 6 9 13 19 28

; ... :

; ; ; ; ; ; ;

Each number represents the maximum number of partial products at each level that requires a
fixed number of adder levels. The sequence also depicts that two partial products can be obtained
from at most three partial products, three can be obtained from four, four from six, and so on.
The Dadda tree reduction considers each column separately and reduces the number of logic levels
in a column to the maximum number of layers in the next level. For example, reducing PPs in a
12

12-bit multiplier, Wallace reduction reduces 12 partial products to eight whereas the Dadda
scheme first reduces them to the maximum range in next the group, and this is nine as reducing twelve
layers to eight will require the same number of logic levels as eight but results in less hardware.
In theDadda tree each column is observed for the number of dots. If the number of dots in a column
is less than the maximum number of PPs required to be reduced in the current level, they are simply
dropped down to the next level of logic without any processing. Those columns that have more dots
than the required dots for the next level are reduced to take the maximum layers in the next level.
Example: Figure 5.33 showsDadda reductionon an8 8 partial-product array. FromTable 5.3 it is

evident that eight PPs should be reduced to six PPs. In level 0, this reduction scheme leaves the
columns that have less thanor equal tosixdots andonlyapply reductiononcolumnswithmore thansix

Figure 5.33 Dadda reduction levels for reducing eight PPs to two