Ripple-carry adder — Hinglish notes

3.3.2 · Hardware › Combinational Circuits

YEH HAI KYA?

Building block hai full adder (FA): ek circuit jo teen single bits $a$ , $b$ , $c_{in}$ ko add karta hai aur ek sum bit $s$ aur ek carry-out bit $c_{o u t}$ output karta hai.

YEH KAAM KYUN KARTA HAI? (Full adder ko scratch se derive karo)

Hum teen bits add karna chahte hain: $a$ , $b$ , aur $c_{in}$ . Inka arithmetic sum $0$ (sab zero) se $3$ (sab one) tak hota hai. Binary mein, values $0..3$ ke liye do output bits chahiye:

$a + b + c_{in} = 2 \cdot c_{o u t} + s$

Yahan $c_{o u t}$ "twos place" hai aur $s$ "ones place" hai. Chalo truth table banate hain aur har output derive karte hain.

$a$	$b$	$c_{in}$	sum(dec)	$c_{o u t}$	$s$
0	0	0	0	0	0
0	0	1	1	0	1
0	1	0	1	0	1
0	1	1	2	1	0
1	0	0	1	0	1
1	0	1	2	1	0
1	1	0	2	1	0
1	1	1	3	1	1

$s$ derive karna (XOR KYUN?): $s = 1$ tab exactly hota hai jab teen inputs mein se 1s ki sankhya odd ho. "Odd parity" precisely wahi hai jo XOR compute karta hai.

$s = a \oplus b \oplus c_{in}$

$c_{o u t}$ derive karna (majority KYUN?): $c_{o u t} = 1$ tab hota hai jab sum $\geq 2$ ho, yaani jab inputs mein se kam se kam do inputs 1 hon. Yahi majority function hai:

$c_{o u t} = ab + b c_{in} + a c_{in}$

Hum pehle se compute kiye gaye $p = a \oplus b$ ka use karke simplify kar sakte hain: carry produce hoti hai agar dono $a, b$ 1 hain (generate), ya agar unme se exactly ek 1 hai aur $c_{in} = 1$ hai (propagate):

$c_{o u t} = generate ab + propagate (a \oplus b) c_{in}$

N-BIT ADDER KAISE BANAYEIN

$n$ full adders ko chain karo. $i$ -ve bits $A_{i}, B_{i}$ aur neeche se carry $C_{i}$ ko FA $_{i}$ mein feed karo; $S_{i}$ aur $C_{i + 1}$ bahar nikalo:

$S_{i} = A_{i} \oplus B_{i} \oplus C_{i}, C_{i + 1} = A_{i} B_{i} + (A_{i} \oplus B_{i}) C_{i}$

jahan $C_{0}$ overall carry-in hai, aur $C_{n}$ final carry-out hai.

Timing / cost analysis (woh 80/20 jo matter karta hai)

Maano ek full adder ke carry path mein delay $t_{c}$ hai. Kyunki carry saare $n$ stages se ripple karta hai:

$T_{RCA} \approx n \cdot t_{c} \Rightarrow O (n) delay$

Hardware cost: $n$ full adders $\Rightarrow O (n) gates$ — sasta aur regular, lekin bade $n$ ke liye slow. Yahi slowness exact reason hai kyun faster schemes (carry-lookahead) exist karte hain.

Worked example Worked example 1 — do 4-bit numbers add karo

$A = 101 1_{2} (11)$ aur $B = 011 0_{2} (6)$ add karo, $C_{0} = 0$ ke saath.

Bit by bit chalo, LSB pehle:

Bit 0: $A_{0} = 1, B_{0} = 0, C_{0} = 0 \Rightarrow s = 1 \oplus 0 \oplus 0 = 1$ , carry $= 1 \cdot 0 + \dots = 0$ . Toh $S_{0} = 1, C_{1} = 0$ . Yeh step kyun? Yeh ones column hai; abhi tak koi carry nahi.
Bit 1: $A_{1} = 1, B_{1} = 1, C_{1} = 0 \Rightarrow s = 1 \oplus 1 \oplus 0 = 0$ , carry $= 1 \cdot 1 = 1$ . Toh $S_{1} = 0, C_{2} = 1$ . Kyun? $1 + 1 = 1 0_{2}$ , 0 likho carry 1.
Bit 2: $A_{2} = 0, B_{2} = 1, C_{2} = 1 \Rightarrow s = 0 \oplus 1 \oplus 1 = 0$ , carry $= 0 \cdot 1 + (0 \oplus 1) \cdot 1 = 1$ . Toh $S_{2} = 0, C_{3} = 1$ . Kyun? $0 + 1 + 1 = 1 0_{2}$ .
Bit 3: $A_{3} = 1, B_{3} = 0, C_{3} = 1 \Rightarrow s = 1 \oplus 0 \oplus 1 = 0$ , carry $= 1 \cdot 0 + (1 \oplus 0) \cdot 1 = 1$ . Toh $S_{3} = 0, C_{4} = 1$ . Kyun? $1 + 1 = 1 0_{2}$ .

Result: $S = C_{4} S_{3} S_{2} S_{1} S_{0} = 1000 1_{2} = 17$ . Check karo: $11 + 6 = 17$ . ✓ Dekho carry bit 1 se bilkul upar tak ripple kar gaya.

Common mistake Steel-manned common mistakes

Mistake A: " $c_{o u t} = a \oplus b \oplus c_{in}$ bhi." Yeh sahi kyun lagta hai: sum teeno ka XOR use karta hai, toh symmetry tumhe carry ke liye bhi XOR reuse karne ka laalach deti hai. Fix: carry magnitude ka 2 tak pahunchne ke baare mein hai, parity ke nahi. Parity kehta hai "odd count"; carry kehta hai "kam se kam do". Alag logic → carry majority hai ( $ab + b c_{in} + a c_{in}$ ), XOR nahi.

Mistake B: "MSB output inputs aate hi ready ho jaata hai." Yeh sahi kyun lagta hai: saare inputs $A, B, C_{0}$ simultaneously enter karte hain. Fix: $S_{n - 1}$ depend karta hai $C_{n - 1}$ pe, jo depend karta hai $C_{n - 2}$ pe, … Carry chain serial hai, isliye top bit sirf $\approx n \cdot t_{c}$ ke baad settle hoti hai. Yahi delay poora reason hai kyun RCA "slow" hai.

Mistake C: "Carry-out matlab overflow." Yeh sahi kyun lagta hai: unsigned numbers ke liye, $C_{n} = 1$ matlab result fit nahi hua. Fix: signed two's-complement ke liye, overflow hai $C_{n} \oplus C_{n - 1}$ (carry into MSB differ karta hai carry out of MSB se), sirf $C_{n}$ nahi.

Flashcards

n

-bit ripple-carry adder kis single-bit block se bana hota hai?

n

cascaded full adders se, har ek ka carry-out agle ke carry-in ko feed karta hai.

Full adder sum expression kya hai?

s = a \oplus b \oplus c_{in}

(odd-parity / teeno bits ka XOR).

Full adder carry-out expression kya hai?

c_{o u t} = ab + b c_{in} + a c_{in} = ab + (a \oplus b) c_{in}

(majority function).

c_{o u t}

majority function kyun hai, XOR kyun nahi?

Carry tab aata hai jab arithmetic sum

\geq 2

ho, yaani kam se kam do inputs 1 hon — yahi majority hai, odd-parity nahi.

n

-bit RCA ki worst-case delay kya hai?

O (n)

, approximately

n \cdot t_{c}

, kyunki carry har stage se serially ripple karna padta hai.

n

-bit RCA ki gate/area cost kya hai?

O (n)

— har bit ke liye ek full adder; sasta aur regular.

RCA ko

A - B

ke liye subtractor mein kaise convert karte hain?

B

ki har bit invert karo aur

C_{0} = 1

set karo (two's complement of

B

add karta hai).

Two's complement mein signed overflow condition kya hai?

C_{n} \oplus C_{n - 1}

(carry into MSB

\neq =

carry out of MSB).

"Generate" vs "propagate" kya hota hai?

Generate

= ab

(stage khud carry banata hai); propagate

= a \oplus b

(stage incoming carry ko pass karta hai).

RCA ka main drawback kya hai?

Speed — linear carry-propagation delay ise wide words ke liye slow banata hai; carry-lookahead ko motivate karta hai.

Recall Feynman: 12-saal ke bache ko samjhao

Socho paper pe do lambe numbers add kar rahe ho. Tum right se start karte ho, har column add karte ho, aur jab bhi koi column 10 ya zyada add ho jaaye tum 1 carry karte ho agle column mein. Tum left wale columns finish nahi kar sakte jab tak carry right se travel karke aa na jaaye. Ek ripple-carry adder choti machines ki ek row hai, ek machine har digit (bit) ke liye. Har machine apne do bits plus jo bhi carry apne right wale neighbour se aayi hai add karti hai, aur apni carry left wale neighbour ko de deti hai. "Carry" left ki taraf ek wave ki tarah travel karti hai — isliye ise ripple kehte hain. Yeh simple aur sasta hai, lekin agar number bahut lamba hai, tum thodi der wait karte ho carry ke liye poore raste chalne ka.

Connections

Full adder — upar derive kiya gaya repeated building block.
Half adder — full adder = do half adders + carries pe ek OR.
Carry-lookahead adder — generate/propagate signals use karke RCA ki $O (n)$ delay fix karta hai.
Two's complement — same adder ka subtraction reuse enable karta hai.
Overflow detection — signed arithmetic ke liye $C_{n} \oplus C_{n - 1}$ .
Combinational circuits — RCA ek canonical example hai (koi memory nahi, output = f(inputs)).
Propagation delay — woh timing concept jo RCA ko slow banata hai.