GATE CS 1997 Q2.5 — Computer Arithmetic

To design an $N$-bit carry lookahead adder using 4-bit ALU slices (IC 74181) and 4-bit carry lookahead generators (IC 74182), we organize the components in a hierarchical tree structure:

1. Level 1: The $N$-bit inputs are divided into groups of 4 bits. Each group uses one 4-bit ALU (IC 74181) to generate local sum bits along with group propagate ($P$) and group generate ($G$) signals.
2. Higher Levels: The $P$ and $G$ outputs from 4 lower-level blocks are combined using one IC 74182 carry lookahead generator. This process is repeated hierarchically.

Since each level of IC 74182 handles 4 inputs from the level below it, the height (number of levels) of this lookahead tree for an $N$-bit adder is:

The total propagation delay for the carry signals to propagate up to the root of the tree and then back down to generate the final sum is directly proportional to the height of the tree.

Therefore, the minimum addition time is proportional to $\log N$.