GATE CS 2016 Set 1 Q.43 (CS Q.33): Number Representations and Computer Arithmetic

Consider a carry lookahead adder for adding two $n$ -bit integers, built using gates of fan-in at most two. The time to perform addition using this adder is

$\Theta(1)$

$\Theta(\log(n))$

$\Theta(\sqrt{n})$

$\Theta(n)$

Official answer and solution

Official answer: B
From: Official GATE 2016 answer key

Solution

Evaluate tree depth required to compute prefix carries when gate fan-in is bounded by two.

In a Carry Lookahead Adder (CLA), carry generation terms $G_i = A_i B_i$ and propagation terms $P_i = A_i \oplus B_i$ are computed in $O(1)$ time.

The $i$ -th carry $C_i$ is expressed as:

C_i = G_i + P_i C_{i-1} = G_i + P_i G_{i-1} + P_i P_{i-1} G_{i-2} + \dots + P_i P_{i-1} \dots P_0 C_{-1}

For an $n$ -bit adder, this expression involves an $n$ -input OR gate and AND gates with fan-in up to $n$ .

When gate fan-in is restricted to at most 2, an $n$ -input Boolean function must be implemented using a binary tree of 2-input logic gates.
The height (depth) of a balanced binary tree with $n$ inputs is $\lceil \log_2 n \rceil$ .

Using parallel prefix adder architectures (such as Brent-Kung or Kogge-Stone), prefix carries can be computed in $\Theta(\log n)$ gate levels.
Therefore, the addition time is $\Theta(\log n)$ .

Final answer

Common trap

Assuming CLA addition takes $\Theta(1)$ time, forgetting that $\Theta(1)$ requires unbounded gate fan-in, which is physically prohibited by the fan-in $\le 2$ constraint.

The answer is the one in the official GATE answer key. The solution is this site's own explanation.

Source

Paper: GATE 2016 Computer Science and Information Technology (CS) Session 1
Question: 43 of 65, printed as CS Q.33
Section: Computer Science and Information Technology

Report an error in this question

GATE questions are the work of the organising institutes. This site is independent and is not affiliated with them.

Question

Solution

Source