GATE CS 2003 Q11 — Computer Arithmetic

An array multiplier is used to multiply two $n$-bit numbers. The multiplication process consists of two main steps:

1. Generation of Partial Products: There are $n^2$ partial products generated using $n^2$ two-input AND gates. Since all these AND gates operate in parallel, this step takes a constant delay of $\Theta(1)$ (specifically, $1$ gate delay).
2. Addition of Partial Products: The partial products are added using a two-dimensional array of Full Adders (FAs) and Half Adders (HAs).
   • The array consists of $n$ rows of adders.
   • In a standard carry-save array multiplier, the carry outputs of one stage are passed diagonally to the next stage, avoiding horizontal carry propagation delay within the intermediate rows. Thus, the delay through the $n-1$ intermediate adder stages is proportional to $n$, i.e., $\Theta(n)$.
   • The final stage requires a vector addition (typically using a Ripple Carry Adder of size $n$) to merge the final sum and carry vectors, which introduces a delay proportional to the word length, i.e., $\Theta(n)$.

Summing these up, the critical path delay of the array multiplier is:

Therefore, the total delay of the array multiplier is $\Theta(n)$.