Wallace tree

This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed. Find sources: "Wallace tree" – news · newspapers · books · scholar · JSTOR (December 2009) (Learn how and when to remove this message)

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:

1. Multiply each bit of one of the arguments, by each bit of the other.
2. Reduce the number of partial products to two by layers of full and half adders.
3. Group the wires in two numbers, and add them with a conventional adder.^[3]

Compared to naively adding partial products with regular adders, the benefit of the Wallace tree is its faster speed. It has ${\displaystyle O(\log n)}$ reduction layers, but each layer has only ${\displaystyle O(1)}$ propagation delay. A naive addition of partial products would require ${\displaystyle O(\log ^{2}n)}$ time. As making the partial products is ${\displaystyle O(1)}$ and the final addition is ${\displaystyle O(\log n)}$, the total multiplication is ${\displaystyle O(\log n)}$, not much slower than addition. From a complexity theoretic perspective, the Wallace tree algorithm puts multiplication in the class NC¹. 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.

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

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