Project ForgeDigital Logic
Combinational & Sequential Circuits
GATE 2016
Hard
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
- AΘ(1)
- Θ(log(n))
- CΘ(√n)
- DΘ(n)
Explanation
With fan-in restricted to 2, computing each carry-lookahead term requires combining n inputs via a balanced binary tree of 2-input gates, which has depth Θ(log n). Since all carries can be computed in parallel via this lookahead structure (rather than rippling), the overall addition time is Θ(log n).
Source: GATE CS 2016 (Session 1 / Set A) (2016)
This question is part of a 15-day revision cycle — sign in and Project Forge will bring it back the day before you'd forget it.