Carry-lookahead adder — Hinglish notes

3.3.3 · Hardware › Combinational Circuits

WHY do we need it?

WHAT we exploit: Bit $i$ pe ek single full adder ke liye, inputs $a_{i}, b_{i}$ aur incoming carry $c_{i}$ hain:

$s_{i} = a_{i} \oplus b_{i} \oplus c_{i}, c_{i + 1} = a_{i} b_{i} + (a_{i} \oplus b_{i}) c_{i}$

$c_{i + 1}$ dekho. Yeh do tarakon se 1 banta hai:

Bit apne aap carry generate karta hai: $a_{i} b_{i} = 1$ .
Bit ek incoming carry ko propagate karta hai: $(a_{i} \oplus b_{i}) c_{i} = 1$ .

Derivation from first principles

Carry equation mein substitute karo:

Ab recursion ko unroll karo taaki pichle carry pe dependence khatam ho. $c_{0}$ (input carry) se shuru karo:

$c_{1} = g_{0} + p_{0} c_{0}$

$c_{2} = g_{1} + p_{1} c_{1} = g_{1} + p_{1} (g_{0} + p_{0} c_{0}) = g_{1} + p_{1} g_{0} + p_{1} p_{0} c_{0}$

$c_{3} = g_{2} + p_{2} c_{2} = g_{2} + p_{2} g_{1} + p_{2} p_{1} g_{0} + p_{2} p_{1} p_{0} c_{0}$

The payoff: har $c_{i + 1}$ ab $g$ 's, $p$ 's aur $c_{0}$ ka ek 2-level AND-OR expression hai. Kyunki $g_{i}, p_{i}$ 1 gate delay mein compute hote hain, saare carries constant number of gate delays mein aate hain — $n$ se independent.

Delay comparison

Worked examples

Common mistakes

Block-level (hierarchical) CLA

Flashcards

Ripple-carry slow kyun hota hai?

Har carry serially pichle wale ka wait karta hai →

O (n)

delay (~

2 n

gate delays, 2 per carry stage).

Generate

g_{i}

define karo.

g_{i} = a_{i} b_{i}

: bit incoming carry ki parwah kiye bina carry banata hai.

Propagate

p_{i}

define karo.

p_{i} = a_{i} \oplus b_{i}

: bit ek incoming carry ko pass through karta hai.

Recursive carry equation?

c_{i + 1} = g_{i} + p_{i} c_{i}

Inputs ke terms mein expanded

c_{2}

c_{2} = g_{1} + p_{1} g_{0} + p_{1} p_{0} c_{0}

Sum bit formula?

s_{i} = p_{i} \oplus c_{i}

CLA vs ripple ka gate-delay?

CLA ~constant (~4 levels); ripple ~

2 n

(2 delays per carry stage).

4-bit block ke liye group propagate?

P = p_{3} p_{2} p_{1} p_{0}

4-bit block ke liye group generate?

G = g_{3} + p_{3} g_{2} + p_{3} p_{2} g_{1} + p_{3} p_{2} p_{1} g_{0}

Wide CLA ki main cost?

Bada gate fan-in aur gate count → hierarchy se solve hota hai.

Recall Feynman: ek 12-saal ke bachche ko explain karo

Socho ek row mein baithhe bacchon ko ek note pass karna hai. Ripple-carry = har bachche ko note milne ka wait karna padta hai phir aage pass karo, toh last bachcha bahut der tak wait karta hai. CLA smarter hai: game shuru hone se pehle, har bachcha sirf apne cards dekh ke do cheezein decide kar leta hai — "Main definitely haath uthaunga (generate)" ya "Main jo neeche wala karega wahi karunga (propagate)." Ab ek teacher saare ki cards ek saath dekhta hai aur turant announce kar deta hai ki kaun haath uthayega. Line mein koi waiting nahi!

Connections

Full Adder — CLA wahi $s_{i} = a_{i} \oplus b_{i} \oplus c_{i}$ logic reuse karta hai.
Ripple-Carry Adder — woh slow baseline jise CLA improve karta hai.
Boolean Algebra — recursion unroll karna pure substitution + distributive law hai.
Carry-Save Adder — alag speed trick (carries defer karo).
Propagation Delay & Fan-in — practice mein hierarchy kyun zaroori hai.
Prefix Adders (Kogge-Stone) — CLA ka logarithmic-depth generalization.