GATE CS 1999 Q1.21 — Computer Arithmetic

An $n \times n$ array multiplier is used to multiply two $n$-bit numbers. It consists of two main stages:

1. Generation of Partial Products: This requires $n^2$ AND gates operating in parallel. The delay for this stage is constant, i.e., $O(1)$ gate delay.
2. Addition of Partial Products: The partial products are added using a 2D grid of Full Adders (FAs) and Half Adders (HAs).
   • The array consists of $n-1$ rows of adders.
   • In the worst-case scenario, the carry propagates from the top row down to the bottom row, and then ripples through the final vector-merge adder (ripple-carry adder) at the bottom.
   • The critical path (longest path) passes through at most $O(n)$ adder cells.

Since each adder cell has a constant gate delay (independent of $n$), the total maximum propagation delay along the critical path is proportional to the number of levels, which is $O(n)$.

Thus, the maximum gate delay for any output to appear is $O(n)$.