Wallace tree
(two dots) and 38 full adders (three dots).
≈ 6 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
(two dots) and 38 full adders (three dots). The dots in each column are bits of equal weight. A Wallace multiplier is a hardware implementation of a binary multiplier, a digital circuit that multiplies two integers.
It uses a selection of full and half adders (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 Dadda multipliers 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 Chris Wallace in 1964. The Wallace tree has three steps: # Multiply each bit of one of the arguments, by each bit of the other. # 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.
Compared to naively adding partial products with regular adders, the benefit of the Wallace tree is its faster speed. It has O(\log n) reduction layers, but each layer has only O(1) propagation delay. A naive addition of partial products would require O(\log^2n) time.
As making the partial products is O(1) and the final addition is O(\log n) , the total multiplication is O(\log n) , not much slower than addition.…
(two dots) and 38 full adders (three dots). The dots in each column are bits of equal weight. ]] A Wallace multiplier is a hardware implementation of a binary multiplier, a digital circuit that multiplies two integers. It uses a selection of full and half adders (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 Dadda multipliers 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 Chris Wallace in 1964. The Wallace tree has three steps: Multiply each bit of one of the arguments, by each bit of the other.
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. Compared to naively adding partial products with regular adders, the benefit of the Wallace tree is its faster speed.
It has O(\log n) reduction layers, but each layer has only O(1) propagation delay. A naive addition of partial products would require O(\log^2n) time. As making the partial products is O(1) and the final addition is O(\log n) , the total multiplication is O(\log n) , not much slower than addition.
From a complexity theoretic perspective, the Wallace tree algorithm puts multiplication in the class NC 1 . 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 (each bit) of one factor by each digit of the other. Each of these 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 n^2 bits; the partial product of bits a_m by b_n has weight 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.
Example
n=4 , multiplying a_3a_2a_1a_0 by b_3b_2b_1b_0 : First we multiply every bit by every bit: weight 1 – a_0b_0 weight 2 – a_0b_1 , a_1b_0 weight 4 – a_0b_2 , a_1b_1 , a_2b_0 weight 8 – a_0b_3 , a_1b_2 , a_2b_1 , a_3b_0 weight 16 – a_1b_3 , a_2b_2 , a_3b_1 weight 32 – a_2b_3 , a_3b_2 weight 64 – a_3b_3 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 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 Reduction layer 2: Add a full adder for weight 8, and half adders for weights 4, 16, 32, 64 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 Group the wires into a pair of integers and an adder to add them.
See also
Dadda tree
Text derived from https://en.wikipedia.org/w/index.php?oldid=1354281806 under CC BY-SA 4.0; modifications have been made.