Wallace tree

A Wallace tree is an efficient hardware implementation of a digital circuit that multiplies two integers.

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.

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\; n)^2$ 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.

Weights Explained

2 to the power of the index, so
$a\_0b\_0$ - both have index of 0; $2^0\; *\; 2^0\; =\; 1$, so the weight is 1.
$a\_3b\_2$ - have indexes of 3 and 2; $2^3\; *\; 2^2\; =\; 32$, so the weight is 32.

Example

$n=4$, multiplying $a\_3a\_2a\_1a\_0$ by $b\_3b\_2b\_1b\_0$:

# First we multiply every bit by every bit:
#* weight 1 - $a\_0b\_0$
#* weight 2 - $a\_0b\_1$, $a\_1b\_0$
#* weight 4 - $a\_0b\_2$, $a\_1b\_1$, $a\_2b\_0$
#* weight 8 - $a\_0b\_3$, $a\_1b\_2$, $a\_2b\_1$, $a\_3b\_0$
#* weight 16 - $a\_1b\_3$, $a\_2b\_2$, $a\_3b\_1$
#* weight 32 - $a\_2b\_3$, $a\_3b\_2$
#* weight 64 - $a\_3b\_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 integers and an adder to add them.

ee also

*Dadda tree