10-08-2012, 02:33 PM
Wallace Tree Multiplier
Tree Multiplier.pptx (Size: 364.39 KB / Downloads: 99)
What is Wallace tree
A Wallace tree is an efficient hardwire implementation of a digital circuit that multiplies two integers.
The Wallace tree has three steps:
Multiply (that is - AND) each bit of one of the arguments, by each bit of the other, yielding n2 results. Depending on position of the multiplied bits, the wires carry different weights, for example wire of bit carrying result of a2b3 is 32.
Reduce the number of partial products to two by layers of full and half adders.
Group the wires in two numbers, and add them with a conventional adder.
The second phase is as follows.
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.
Advantages:
Each layer of the tree reduces the number of vectors by a factor of 3:2
Minimum propagation delay.
The benefit of the Wallace tree is that there are only O(log n) reduction layers, but adding partial products with regular adders would require O(log n)2 time.
Disadvantages:
Wallace trees do not provide any advantage over ripple adder trees in many FPGAs.
Due to the irregular routing, they may actually be slower and are certainly more difficult to route.
Adder structure increases for increased bit multiplication.
Conclusion:
Wallace Tree multiplier can also be implemented using Carry Save Adders.
Sometimes Wallace Tree Multiplier is Combined with Booth Encoding.
Various other researches have been done to reduce the number of adders, for higher order bits such as 16 & 32.
Applications, as the use in DSP for performing FFT,FIR, etc.,