Lesson plan

Wallace tree

(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.…

Back to article

Article summary

(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.…

Key claims

No claims recorded.

Discussion questions

  1. Summarise the article in your own words. Which single claim would you verify first, and why?
  2. Which claim in this article is most likely to be revised as the sources update? How would you check its current status?
  3. If two sources disagreed about one of these facts, what would you need in order to trust one over the other?

Bibliography

No sources recorded.

Key claims and bibliography are generated from the same tracked claims and sources as the article page.