The maximum gate delay for any output to appear in an array multiplier for…

Concept

A combinational circuit’s propagation delay is determined by the number of dependent gate stages on its critical path, not by the total number of gates or cells. If the longest path crosses a number of constant-delay stages proportional to n, the asymptotic delay is O(n).

Application

1. An n-bit array multiplier forms n2 partial-product bits with AND gates. These bits are produced in parallel, so the n2 cell count measures hardware area rather than n2 sequential delay.

2. The partial products are reduced in the regular adder array. A signal on the longest diagonal carry/sum path crosses a number of adder cells proportional to n.

3. Each adder cell has constant gate delay. Therefore, a critical path containing c·n + k such stages has total delay proportional to n.

Cross-check and contrast

• O(n2) would require a critical path whose depth grows quadratically; the n2 array cells are not traversed serially by one signal.

• O(log n) describes a balanced tree-style reduction, such as a Wallace or Dadda tree, rather than a regular array path.

• O(1) would require a depth independent of operand width, but the longest array path acquires more stages as n increases.

Result

Hence, the maximum gate delay of the standard array multiplier is O(n).