Wallace tree

A Wallace multiplier is a hardware implementation of a binary multiplier, a digital circuit that multiplies two integers.

It uses a selection of full and half adders (the Wallace tree or Wallace reduction) to sum partial products in stages until two numbers are left.

Wallace multipliers reduce as much as possible on each layer, whereas Dadda multipliers try to minimize the required number of gates by postponing the reduction to the upper layers.

[1] Wallace multipliers were devised by the Australian computer scientist Chris Wallace in 1964.

[2] The Wallace tree has three steps: Compared to naively adding partial products with regular adders, the benefit of the Wallace tree is its faster speed.

A naive addition of partial products would require

As making the partial products is

From a complexity theoretic perspective, the Wallace tree algorithm puts multiplication in the class NC1.

The downside of the Wallace tree, compared to naive addition of partial products, is its much higher gate count.

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

It is sometimes combined with Booth encoding.

[4][5] The Wallace tree is a variant of long multiplication.

The final product is calculated by the weighted sum of all these partial products.

The first step, as said above, is to multiply each bit of one number by each bit of the other, which is accomplished as a simple AND gate, resulting in

In the second step, the resulting bits are reduced to two numbers; this is accomplished as follows: As long as there are three or more wires with the same weight add a following layer:- In the third and final step, the two resulting numbers are fed to an adder, obtaining the final product.