Wallace tree

A Wallace multiplier is a <a href="/facts/Computer_hardware/8jSjsCNv">hardware</a> implementation of a <a href="/facts/Binary_multiplier/GfkwufDb">binary multiplier</a>, a digital circuit that multiplies two integers. It uses a selection of full and half <a href="/facts/Adder_(electronics)/Bc81gxBD">adders</a> (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 <a href="/facts/Dadda_multiplier/GkqLPXNE">Dadda multipliers</a> try to minimize the required number of gates by postponing the reduction to the upper layers. 
Wallace multipliers were devised by the Australian computer scientist <a href="/facts/Chris_Wallace_(computer_scientist)/vJDPpkRS">Chris Wallace</a> in 1964.
The Wallace tree has three steps:

<ol><li>Multiply each bit of one of the arguments, by each bit of the other.</li>
<li>Reduce the number of partial products to two by layers of full and half <a href="/facts/Adder_(electronics)/Bc81gxBD">adders</a>.</li>
<li>Group the wires in two numbers, and add them with a conventional adder.</li></ol>
Compared to naively adding partial products with regular adders, the benefit of the Wallace tree is its faster speed. It has 
 
 
 
 O
 (
 log
 ⁡
 n
 )
 
 
 {\displaystyle O(\log n)}
 
 reduction layers, but each layer has only 
 
 
 
 O
 (
 1
 )
 
 
 {\displaystyle O(1)}
 
 propagation delay. A naive addition of partial products would require 
 
 
 
 O
 (
 
 log
 
 2
 
 
 ⁡
 n
 )
 
 
 {\displaystyle O(\log ^{2}n)}
 
 time.
As making the partial products is 
 
 
 
 O
 (
 1
 )
 
 
 {\displaystyle O(1)}
 
 and the final addition is 
 
 
 
 O
 (
 log
 ⁡
 n
 )
 
 
 {\displaystyle O(\log n)}
 
, the total multiplication is 
 
 
 
 O
 (
 log
 ⁡
 n
 )
 
 
 {\displaystyle O(\log n)}
 
, not much slower than addition. From a <a href="/facts/Computational_complexity_theory/etHuVF3U">complexity theoretic</a> perspective, the Wallace tree algorithm puts multiplication in the class <a href="/facts/NC_(complexity)/4SY2L2Kg">NC1</a>.
The downside of the Wallace tree, compared to naive addition of partial products, is its much higher gate count.
These computations only consider <a href="/facts/Gate_delay/tUcrAwwe">gate delays</a> 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 <a href="/facts/Booth_encoding/CplEqXtt">Booth encoding</a>.

Wallace tree open-in-new

Wallace tree