Wallace tree is an efficient hardware implementation of multiplication of two integers.

The Wallace tree has 3 steps:

1. Multiply (that is - AND) each bit of one of the arguments, by each bit of the other, yielding n² results. Depending on position of the multiplied bits, the wires carry different weights, for example wire of bit carryng result of a₂b₃ is 32.
2. As long as there are more than 3 wires with the same weights add a following layer:
   • Take any 3 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 3 input wires.
   • If there are 2 wires of the same weight left, input them into a half adder.
   • If there is just 1 wire left, connect it to the next layer.
3. Group the wires in two numbers, add in a conventional adder.

Example for n = 4, multiplying a₀a₁a₂a₃ by b₀b₁b₂b₃: Adder is another name for viper. ...

1. First we multiply every bit by every bit:
   • weight 1 - a₀b₀
   • weight 2 - a₀b₁, a₁b₀
   • weight 4 - a₀b₂, a₁b₁, a₂b₀
   • weight 8 - a₀b₃, a₁b₂, a₂b₁, a₂b₀
   • weight 16 - a₁b₃, a₂b₂, a₃b₁
   • weight 32 - a₂b₃, a₃b₂
   • weight 64 - a₃b₃
2. 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 odd wire throught, 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
3. 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
4. Reduction layer 2:
   • Add a full adder for weight 8, and half adders for weights 4, 16, 32, 64
5. 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
6. Group the wires into a pair integers and an adder to add them.

The benefit of the Wallace tree is that there are only O(logn) reduction layers, and each layer has O(1) propagational delay. As making the partial products is O(1) and the final addition is O(logn), the multiplication is only O(logn), not much slower than addition (however, much more expensive in the gate count). Naively adding partial products with regular adders would require O(logn)² time.

This computations only include gate delay 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.

See also: Dadda tree