Wallace tree


A Wallace tree is an efficient hardware implementation of a digital circuit that multiplies two integers. It was devised by the Australian computer scientist Chris Wallace in 1964.
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.
Compared to naively adding partial products with regular adders, the benefit of the Wallace tree is its faster speed. It has reduction layers, but each layer has only propagation delay. A naive addition of partial products would require time.
As making the partial products is and the final addition is, the total multiplication is, not much slower than addition. 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.
The Wallace tree can be also represented by a tree of 3/2 or 4/2 adders.
It is sometimes combined with Booth encoding.

Detailed explanation

The Wallace tree is a variant of long_multiplication. The first step is to multiply each digit 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 partial 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 bits; the partial product of bits by has weight
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 a adder, obtaining the final product

Example

, multiplying by :
  1. First we multiply every bit by every bit:
  2. * weight 1 –
  3. * weight 2 –,
  4. * weight 4 –,,
  5. * weight 8 –,,,
  6. * weight 16 –,,
  7. * weight 32 –,
  8. * weight 64 –
  9. Reduction layer 1:
  10. * Pass the only weight-1 wire through, output: 1 weight-1 wire
  11. * Add a half adder for weight 2, outputs: 1 weight-2 wire, 1 weight-4 wire
  12. * Add a full adder for weight 4, outputs: 1 weight-4 wire, 1 weight-8 wire
  13. * Add a full adder for weight 8, and pass the remaining wire through, outputs: 2 weight-8 wires, 1 weight-16 wire
  14. * Add a full adder for weight 16, outputs: 1 weight-16 wire, 1 weight-32 wire
  15. * Add a half adder for weight 32, outputs: 1 weight-32 wire, 1 weight-64 wire
  16. * Pass the only weight-64 wire through, output: 1 weight-64 wire
  17. Wires at the output of reduction layer 1:
  18. * weight 1 – 1
  19. * weight 2 – 1
  20. * weight 4 – 2
  21. * weight 8 – 3
  22. * weight 16 – 2
  23. * weight 32 – 2
  24. * weight 64 – 2
  25. Reduction layer 2:
  26. * Add a full adder for weight 8, and half adders for weights 4, 16, 32, 64
  27. Outputs:
  28. * weight 1 – 1
  29. * weight 2 – 1
  30. * weight 4 – 1
  31. * weight 8 – 2
  32. * weight 16 – 2
  33. * weight 32 – 2
  34. * weight 64 – 2
  35. * weight 128 – 1
  36. Group the wires into a pair of integers and an adder to add them.