Computer Arithmetic

Which describes a Wallace tree used in fast multipliers?

  1. AA tree of carry-save adders reduces partial products in parallel, with logarithmic depth
  2. BPartial products are added one at a time in sequence, giving the smallest but slowest circuit
  3. CProducts are simply looked up in a table, with no adders at all
Show answer and explanation

Answer: A. A tree of carry-save adders reduces partial products in parallel, with logarithmic depth

An n-bit multiplication produces n partial products. A Wallace tree applies carry-save adders, which reduce three numbers to two, in parallel at each level, cutting the count by about a third per level. The number of levels needed to reach two is therefore roughly logarithmic in the width, far faster than adding sequentially. A fast adder then sums the final two numbers. Sequential addition is a small but slow array scheme, and table lookup is impractical for large widths.

  • A. Correct. Partial products are reduced in parallel with logarithmic depth.
  • B. Sequential addition is a different, small but slow scheme.
  • C. Table lookup is impractical for large bit widths.
Practice this topic Back to topic

More Computer Arithmetic questions

  1. What is the main effect of using radix-4 Booth's algorithm (Booth encoding) in a multiplier?
  2. When two unsigned 8-bit numbers are multiplied, how many bits are needed to represent the result without overflow?
  3. Which expression multiplies an integer x by 10 using shifts and additions instead of a multiply instruction?
  4. Why do typical integer dividers (restoring or non-restoring, producing one quotient bit at a time) tend to be slower than multipliers?
  5. What is the result of arithmetic right-shifting the 8-bit signed integer −8 (1111 1000) by one bit?