Wallace tree

The Wallace tree is a variant of long multiplication. The first step is to multiply each digit (each bit) of one factor by each digit of the other. Each of this partial products has weight equal to the product of its factors. 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 ${\displaystyle n^{2}}$ bits; the partial product of bits ${\displaystyle a_{m}}$ by ${\displaystyle b_{n}}$ has weight ${\displaystyle 2^{(m+n)}}$

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:-

• 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.

In the third and final step, the two resulting numbers are fed to an adder, obtaining the final product.

${\displaystyle n=4}$, multiplying ${\displaystyle a_{3}a_{2}a_{1}a_{0}}$ by ${\displaystyle b_{3}b_{2}b_{1}b_{0}}$:

1. First we multiply every bit by every bit:
   • weight 1 – ${\displaystyle a_{0}b_{0}}$
   • weight 2 – ${\displaystyle a_{0}b_{1}}$, ${\displaystyle a_{1}b_{0}}$
   • weight 4 – ${\displaystyle a_{0}b_{2}}$, ${\displaystyle a_{1}b_{1}}$, ${\displaystyle a_{2}b_{0}}$
   • weight 8 – ${\displaystyle a_{0}b_{3}}$, ${\displaystyle a_{1}b_{2}}$, ${\displaystyle a_{2}b_{1}}$, ${\displaystyle a_{3}b_{0}}$
   • weight 16 – ${\displaystyle a_{1}b_{3}}$, ${\displaystyle a_{2}b_{2}}$, ${\displaystyle a_{3}b_{1}}$
   • weight 32 – ${\displaystyle a_{2}b_{3}}$, ${\displaystyle a_{3}b_{2}}$
   • weight 64 – ${\displaystyle a_{3}b_{3}}$
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 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
3. Wires at the output of reduction layer 1:MESCOE
   • 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 of integers and an adder to add them.

• Dadda tree

• Savard, John J. G. (2018) [2006]. "Advanced Arithmetic Techniques". quadibloc. Archived from the original on 2018-07-03. Retrieved 2018-07-16.

• Generic VHDL Implementation of Wallace Tree Multiplier.