VLSI Digital Signal Processing Systems: Design and Implementation

E.3    WALLACE TREE AND DADDA MULTIPLIER

The principle of Wallace tree multiplication [5] is shown in Fig. E.5(a). It is clear from the figure that there are 16 partial products (shown as black dots) that have to be summed. The 1st step in the addition process involves grouping the partial products into sets of 3. For example, if there are p rows of partial products, 3 * () rows are grouped and the remaining p mod 3 rows are passed to the next stage. Therefore, in Fig. E.5 3 rows of partial products are grouped together in stage 1. These 3 rows are summed using full adders if there are 3 dots in 1 column and using half adders if there are 2 dots in 1 column. The resulting sum and carry signals from the half and full adders are passed on to the next stage. It turns out that this stage has exactly 3 rows of partial products to be summed. The resulting sum and carry signals are passed on to the 3rd stage. Since there are only 2 rows of partial products to be summed, this stage can be implemented using a fast carry-propagate adder. The implementation of the 4 × 4-bit Wallace tree multiplier is shown in Fig. E.5(b). The architecture requires only 5 full adders and 3 half adders to sum the 16 partial products.

The principle of Wallace tree multiplication can easily be extended to longer wordlengths. Fig. E.6 shows the operation of a 8 × 8-bit multiplier, where the partial products are ...