Combinational logic — half adder, full adder, multiplexer, decoder

1.1.6 · Coding › How Computers Work

1. Core idea — WHY hume adders, muxes, decoders chahiye

WHY ye char?

Half/Full adder → taaki computer binary arithmetic kar sake (numbers add kare).
Multiplexer (MUX) → taaki hum bahut signals mein se ek select kar sake (data routing).
Decoder → taaki hum ek binary code se exactly ek output line activate kar sake (memory address karna, instructions choose karna).

2. Half Adder — do single bits add karna

Truth table se derive karo (first principles):

$A$	$B$	Sum	Carry
0	0	0	0
0	1	1	0
1	0	1	0
1	1	0	1

WHY ye table? Bas binary mein count karo: $1 + 1 = 1 0_{2}$ , toh Sum $= 0$ , Carry $= 1$ .

HOW hum ek truth table ko gates mein convert karte hain? Wo rows dhundho jahan output $1$ hai.

Sum tab $1$ hai jab $A, B$ alag hon → ye exactly XOR hai: $Sum = A \oplus B = \overset{ˉ}{A} B + A \overset{ˉ}{B}$
Carry tab $1$ hai jab dono $1$ hon → ye AND hai: $Carry = A \cdot B$

3. Full Adder — do bits plus ek carry-in add karna

Truth table (3 inputs):

$A$	$B$	$C_{in}$	Sum	$C_{o u t}$
0	0	0	0	0
0	0	1	1	0
0	1	0	1	0
0	1	1	0	1
1	0	0	1	0
1	0	1	0	1
1	1	0	0	1
1	1	1	1	1

Sum derive karo: Sum $= 1$ jab $(A, B, C_{in})$ mein $1$ s ki count odd ho. Teen bits ki odd-parity exactly chained XOR hai: $Sum = A \oplus B \oplus C_{in}$

Carry-out derive karo: $C_{o u t} = 1$ jab kam se kam do inputs $1$ hon (majority). Table se: $C_{o u t} = A B + A C_{in} + B C_{in}$

WHY ye step? Wo rows list karo jahan $C_{o u t} = 1$ : ${011, 101, 110, 111}$ — har ek mein ek aisa pair hai jo dono $1$ hai, jo kisi ek AND term se capture hota hai.

Figure — Combinational logic — half adder, full adder, multiplexer, decoder

4. Multiplexer (MUX) — data selector

2-to-1 MUX derive karo (1 select line $S$ ):

Jab $S = 0$ → output $= I_{0}$ .
Jab $S = 1$ → output $= I_{1}$ .

Use use Boolean mein convert karo: har input ko select condition ke through "gate" karo. $Y = \overset{ˉ}{S} I_{0} + S I_{1}$

WHY ye kaam karta hai: $\overset{ˉ}{S} I_{0}$ sirf tab $I_{0}$ pass karta hai jab $S = 0$ ho (doosra term $0$ hota hai); $S I_{1}$ sirf tab $I_{1}$ pass karta hai jab $S = 1$ ho. Kabhi bhi sirf ek hi term active hoti hai.

5. Decoder — binary code → one-hot

2-to-4 decoder derive karo: har output $D_{k}$ tab $1$ hona chahiye jab inputs binary mein $k$ ke barabar hon. Ye minterm hai: $D_{0} = \overset{ˉ}{A} \overset{ˉ}{B}, D_{1} = \overset{ˉ}{A} B, D_{2} = A \overset{ˉ}{B}, D_{3} = A B$

WHY: $D_{2} = A \overset{ˉ}{B}$ sirf tab true hai jab $A = 1, B = 0$ ho, matlab input $= 1 0_{2} = 2$ . Har output inputs ke true/complement form ka ek AND hai.

6. The 80/20 — sach mein kya yaad rakhna hai

Flashcards

Combinational circuit ko kya define karta hai?

Output sirf current inputs par depend karta hai; koi memory/state/clock nahi.

Half adder Sum expression?

Sum = A \oplus B

Half adder Carry expression?

Carry = A \cdot B

Half-adder Sum XOR kyun hai OR kyun nahi?

OR galti se 1 output karta hai jab dono inputs 1 hon; XOR us case ko exclude karta hai (wo carry ban jata hai).

Full adder Sum expression?

A \oplus B \oplus C_{in}

(teen bits ki odd parity).

Full adder Carry-out expression?

A B + A C_{in} + B C_{in} = A B + C_{in} (A \oplus B)

(majority function).

Full adder banane ke liye kitne half adders + gates chahiye?

Do half adders + ek OR gate.

2-to-1 MUX output equation?

Y = \overset{ˉ}{S} I_{0} + S I_{1}

MUX ki select lines kya control karti hain?

Kaun sa data input single output tak route hoga (ye output value mein appear nahi hoti).

2-to-4 decoder input 10 ke liye kya output deta hai?

One-hot 0100 (sirf

D_{2}

high).

Decoder line

D_{k}

ka general output?

Inputs ka

k

-wa minterm.

Decoder + OR gates koi bhi Boolean function kaise implement karte hain?

Function ki 1-rows ke corresponding minterm outputs ko OR kar do.

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

Socho tum do LEGO-coin piles add kar rahe ho, lekin har jagah sirf EK coin aa sakta hai. Half adder: do coins saath rakkho; agar dono hain toh do ho jaenge, toh ek ko "carry" ke roop mein agle jagah de do — ye carry-keeping AND hai, aur "yahan bacha hua" XOR hai. Full adder: same hai, lekin ab ek dost pichli jagah se tumhe ek coin aur deta hai. Multiplexer: ek TV remote jo, channel number press karne par, sirf EK channel ko through aane deta hai. Decoder: tum ek number zor se bolte ho, aur exactly ek light bulb jis par wo number likha hai jal uthti hai.

Connections

Boolean Algebra and Logic Gates — minterms, De Morgan's laws.
Binary Number System — carry exist kyun karta hai.
Ripple Carry Adder and ALU — full adders chain karna.
Sequential Logic and Flip-Flops — "memory" ka contrast.
Memory Addressing — decoders rows select karte hain.
Karnaugh Maps — in expressions ko simplify karna.