Wallace tree

basic principle known from manual multiplication

Example of reduction on an 8x8 multiplier. It's not a wallace multiplier because it violates rule 1

A Wallace tree is an efficient hardware implementation of a digital circuit that multiplies two integers, devised by Australian Computer Scientist Chris Wallace in 1964.^[1]

The Wallace tree has three steps:

Multiply (that is – AND) each bit of one of the arguments, by each bit of the other, yielding $n^{2}$ results. Depending on position of the multiplied bits, the wires carry different weights, for example wire of bit carrying result of $a_{2}b_{3}$ is 32 (see explanation of weights below).
Reduce the number of partial products to two by layers of full and half adders.
Group the wires in two numbers, and add them with a conventional adder.^[2]

The second phase works as follows. As long as there are three or more wires with the same weight add a following layer:

Take any three wires with the same weights and input them into a full adder. The result will be an output wire of the same weight and an output wire with a higher weight for each three input wires.
If there are two wires of the same weight left, input them into a half adder.
If there is just one wire left, connect it to the next layer.

The benefit of the Wallace tree is that there are only $O(\log n)$ reduction layers, and each layer has $O(1)$ propagation delay. As making the partial products is $O(1)$ and the final addition is $O(\log n)$ , the multiplication is only $O(\log n)$ , not much slower than addition (however, much more expensive in the gate count). Naively adding partial products with regular adders would require $O(\log^2n)$ time. From a complexity theoretic perspective, the Wallace tree algorithm puts multiplication in the class NC¹.

These computations only consider gate delays and don't deal with wire delays, which can also be very substantial.

The Wallace tree can be also represented by a tree of 3/2 or 4/2 adders.

It is sometimes combined with Booth encoding.^[3]^[4]

Weights explained

The weight of a wire is the radix (to base 2) of the digit that the wire carries. In general, $a_{n}b_{m}$ – have indexes of $n$ and $m$ ; and since $2^{n}2^{m}=2^{{n+m}}$ the weight of $a_{n}b_{m}$ is $2^{{n+m}}$ .

Example

$n=4$ , multiplying $a_{3}a_{2}a_{1}a_{0}$ by $b_{3}b_{2}b_{1}b_{0}$ :

First we multiply every bit by every bit:
- weight 1 – $a_{0}b_{0}$
- weight 2 – $a_{0}b_{1}$ , $a_{1}b_{0}$
- weight 4 – $a_{0}b_{2}$ , $a_{1}b_{1}$ , $a_{2}b_{0}$
- weight 8 – $a_{0}b_{3}$ , $a_{1}b_{2}$ , $a_{2}b_{1}$ , $a_{3}b_{0}$
- weight 16 – $a_{1}b_{3}$ , $a_{2}b_{2}$ , $a_{3}b_{1}$
- weight 32 – $a_{2}b_{3}$ , $a_{3}b_{2}$
- weight 64 – $a_{3}b_{3}$
Reduction layer 1:
- Pass the only weight-1 wire through, output: 1 weight-1 wire
- Add a half adder for weight 2, outputs: 1 weight-2 wire, 1 weight-4 wire
- Add a full adder for weight 4, outputs: 1 weight-4 wire, 1 weight-8 wire
- Add a full adder for weight 8, and pass the remaining wire through, outputs: 2 weight-8 wires, 1 weight-16 wire
- Add a full adder for weight 16, outputs: 1 weight-16 wire, 1 weight-32 wire
- Add a half adder for weight 32, outputs: 1 weight-32 wire, 1 weight-64 wire
- Pass the only weight-64 wire through, output: 1 weight-64 wire
Wires at the output of reduction layer 1:
- weight 1 – 1
- weight 2 – 1
- weight 4 – 2
- weight 8 – 3
- weight 16 – 2
- weight 32 – 2
- weight 64 – 2
Reduction layer 2:
- Add a full adder for weight 8, and half adders for weights 4, 16, 32, 64
Outputs:
- weight 1 – 1
- weight 2 – 1
- weight 4 – 1
- weight 8 – 2
- weight 16 – 2
- weight 32 – 2
- weight 64 – 2
- weight 128 – 1
Group the wires into a pair of integers and an adder to add them.

References

↑ C. S. Wallace, A suggestion for a fast multiplier, IEEE Trans. on Electronic Comp. EC-13(1): 14–17 (1964)
↑ Veech engineering Archived February 15, 2010, at the Wayback Machine.
↑ Tufts university Archived June 17, 2010, at the Wayback Machine.
↑ University of Massachusetts, Amherst Archived February 6, 2011, at the Wayback Machine.

External links

Generic VHDL Implementation of Wallace Tree Multiplier.

This article is issued from Wikipedia - version of the 11/14/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Wallace tree

Weights explained

Example

See also

References

External links