Consider an array multiplier for multiplying two n bit numbers. If each gate…
2003
Consider an array multiplier for multiplying two n bit numbers. If each gate in the circuit has a unit delay, the total delay of the multiplier is
- A.
Θ(1)
- B.
Θ(log n)
- C.
Θ(n)
- D.
Θ(n2)
Attempted by 187 students.
Show answer & explanation
Correct answer: C
Answer: Θ(n).
Key idea: The critical path in a simple array multiplier involves generating partial products and then adding them with carry propagation across bit positions. The carry can ripple through O(n) adder stages, giving linear delay.
Partial-product generation: Each partial product is produced by an AND gate (one gate delay).
Addition of partial products: The array arranges adders so that carries can propagate from the least-significant column to the most-significant column. Each full adder contributes constant gate delay.
Critical path: A signal may need to go through one partial-product AND plus up to O(n) adder-stage carry propagations, so the total delay is proportional to n.
Note: Achieving sublinear delay (for example Θ(log n)) requires using faster adder structures (like carry-lookahead or tree adders) inside the multiplier. The standard array multiplier, however, uses ripple-style addition and therefore has Θ(n) delay.