Multipliers:Multiplier Based on Wallace Tree.

Multiplier Based on Wallace Tree

In the multiplier based on Wallace tree [13], the multiplicand-multiples are summed up in parallel by means of a tree of carry save adders. A carry save adder sums up three binary numbers and produces two binary numbers (i.e., a partial sum and a partial carry). Therefore, using n/3 carry save adders in parallel, we can reduce the number of multiplicand-multiples from n to about 2n/3. Then, using about

2n/9 carry save adders, we can further reduce it to 4n/9. Applying this principle about log3/2 n times, the number of multiplicand-multiples can be reduced to only two. Finally, we sum up these two multiplicand- multiples by means of a fast carry propagate adder.

Figure 42.4 illustrates a block diagram of a multiplier based on Wallace tree. This consists of full adders, just like the array multiplier described previously. (Recall that a carry save adder consists of full adders.) The delay is small. It is proportional to log n when a fast carry propagate adder with O(log n) delay is used for the final addition. The number of logic gates is about the same as that of an array multiplier and is proportional to n2. However, its circuit structure is not suited for VLSI realization because of the complexity.

The 2-bit Booth’s method can be also applied to this type of multiplier. However, it is not as effective as in the array multiplier, because the height of the Wallace tree decreases by only one or two, even though the number of the multiplicand-multiples is reduced to about half.

A full adder, which is used as the basic cell in a multiplier based on Wallace tree, can be regarded as a counter which counts up 1’s in the three-input bits and outputs the result as a 2-bit binary number. Namely, a full adder can be regarded as a 3-2 counter. We can also use larger counters, such as 7-3 counters and 15-4 counters, as the basic cells, instead of full adders.

We can increase the regularity in the circuit structure by replacing Wallace tree with a 4-2 adder tree [12], where a 4-2 adder is formed by connecting two carry save adders, shown in the dot-lined rectangles, in series, as shown in Figure 42.5. A 4-2 adder is an adder that sums up four binary numbers, A = [an–1 …a0], B = [bn–1 …b0], C = [cn–1 …c0], and D = [dn–1 …d0], and produces two binary numbers, E = [en …e0] and

F = [fn …f0], where f0 = 0. We can form a 4-2 adder tree by connecting 4-2 adders in a binary tree form. The delay of a multiplier based on a 4-2 adder tree is slightly larger than that of a multiplier with Wallace tree but is still proportional to log n. The number of logic gates is about the same as a multiplier based on Wallace tree, and is proportional to n2. It is more suited for VLSI realization than the Wallace tree.