Quine-McCluskey method — Hinglish notes

3.1.13 · Hardware › Boolean Algebra & Logic Gates

1. First principles: hum kar kya rahe hain?

2. Algorithm (WHAT / HOW)

Goal: minimize $f (A, B, C, D) = \sum m (0, 1, 2, 5, 6, 7, 8, 9, 10, 14)$ .

Step 0 — Minterms ko binary mein list karo, 1s ki count se group karo

1-count se grouping guarantee karti hai ki hum sirf adjacent groups compare karein (Hamming-1 neighbour exactly ek 1 mein alag hoga).

Group (#1s)	Minterm	ABCD
0	0	0000
1	1	0001
1	2	0010
1	8	1000
2	5	0101
2	6	0110
2	9	1001
2	10	1010
3	7	0111
3	14	1110

Step 1 — Adjacent groups combine karo (size-2 terms)

Har term ko next group ke har term se compare karo. Agar ek bit mein alag hain, combine karo aur us position par - rakho. Har woh term tick (✓) karo jo use ho gayi (ticked term khud prime nahi hoti).

Pair	ABCD
0,1	000-
0,2	00-0
0,8	-000
1,5	0-01
1,9	-001
2,6	0-10
2,10	-010
8,9	100-
8,10	10-0
5,7	01-1
6,7	011-
6,14	-110
10,14	1-10

Step 2 — Phir combine karo (size-4 terms)

Do size-2 terms tab combine hote hain jab - same position par ho AUR ek bit mein alag hon.

Quad	ABCD
0,1,8,9	-00-
0,2,8,10	-0-0
2,6,10,14	--10

Size-8 terms possible nahi. Jo bhi kabhi tick nahi hua woh prime implicant hai.

Step 3 — Prime Implicant Chart

Rows = PIs, columns = original minterms. Jahan PI minterm cover kare wahan ✗ mark karo.

EPIs dhundo: har column scan karo. Agar koi minterm sirf ek PI se cover ho, toh woh PI essential hai.

$m 9$ sirf $P I_{1}$ se covered → EPI ( $\overset{ˉ}{B} \overset{ˉ}{C}$ )
$m 14$ sirf $P I_{3}$ se covered → EPI ( $C \overset{ˉ}{D}$ )
$m 5$ sirf $P I_{4} = \overset{ˉ}{A} B D$ se covered → EPI

Abhi tak chosen EPIs: $\overset{ˉ}{B} \overset{ˉ}{C}, C \overset{ˉ}{D}, \overset{ˉ}{A} B D$ . Coverage check karo: yeh ${0, 1, 8, 9} \cup {2, 6, 10, 14} \cup {5, 7}$ = saare minterms cover karte hain. Done.

3. Worked example 2 (chhota, 3 vars)

Minimize $f (A, B, C) = \sum m (0, 1, 2, 5, 6, 7)$ .

1s se group karo: {0=000} | {1=001, 2=010} | {5=101, 6=110} | {7=111}

Combine (size-2):

0,1→00- ; 0,2→0-0 ; 1,5→-01 ; 2,6→-10 ; 5,7→1-1 ; 6,7→11-

Yeh step kyun? Yahan har pair ki Hamming distance 1 hai, toh ek variable cancel hota hai — seedha $X + \overset{ˉ}{X} = 1$ ka use.

Combine (size-4): koi bhi same dash position + ek bit difference share nahi karta → saare size-2 terms prime hain.

PIs decode karo (order $A B C$ ):

00- $= \overset{ˉ}{A} \overset{ˉ}{B} (0, 1)$
0-0 $= \overset{ˉ}{A} \overset{ˉ}{C} (0, 2)$
-01 $= \overset{ˉ}{B} C (1, 5)$
-10 $= B \overset{ˉ}{C} (2, 6)$
1-1 $= A C (5, 7)$
11- $= A B (6, 7)$

PI chart / EPI hunt:

$m 0$ ∈ {00-,0-0} → abhi unique nahi.
$m 7$ ∈ {1-1,11-}; $m 5$ ∈ {-01,1-1}; $m 6$ ∈ {-10,11-}.

Ek minimal cover chunno — hume saare ${0, 1, 2, 5, 6, 7}$ chahiye. Lo: $f = \overset{ˉ}{A} \overset{ˉ}{B} + A C + B \overset{ˉ}{C} (covers 0, 1; 5, 7; 2, 6) .$ Kyun: $\overset{ˉ}{A} \overset{ˉ}{B}$ →{0,1}, $A C$ →{5,7}, $B \overset{ˉ}{C}$ →{2,6}; union $= {0, 1, 2, 5, 6, 7}$ = saare chhah. ✔ (Sirf 3 terms, 6 literals — minimal.)

4. Common mistakes

5. Active recall

Recall Feynman: 12 saal ke bacche ko explain karo

Socho tum 0s aur 1s wale cards sort kar rahe ho. Tum unhe line up karte ho ki kitne 1s hain. Phir dekho do cards jo almost twins hain — same sirf ek jagah chhod ke. Unhe ek card mein glue karo jisme us jagah - blank ho, matlab "yeh jagah matter nahi karti." Tum baar baar bade aur bade stacks glue karte rehte ho. Jab kuch aur glue nahi hota, baaki bache stacks tumhare "sabse bade patterns" hain. Finally dekho kaunse patterns tum bilkul skip nahi kar sakte (kyunki sirf wahi kisi card ko cover karte hain) — woh tumhare machine ke liye sabse chhoti recipe mein jaate hain.

Flashcards

Quine–McCluskey ko power karne wala ek Boolean law kaun sa hai?

Combining theorem

A B + A \overset{ˉ}{B} = A

(yaani

X + \overset{ˉ}{X} = 1

Minterms ko 1s ki count se kyun group karte hain?

Hamming-distance-1 neighbour mein exactly ek zyada/kam 1 hota hai, toh woh adjacent group mein hota hai — yeh comparisons limit karta hai aur sirf valid combinations guarantee karta hai.

QM term mein - ka matlab kya hai?

Woh variable cancel ho gaya (

X + \overset{ˉ}{X}

) aur term ke liye irrelevant hai.

Prime implicant define karo.

Ek implicant jo kisi doosre se combine hokar literal nahi hata sakta; yaani combining ke dauran kabhi tick nahi hua.

Essential prime implicant define karo.

Ek PI jo kisi particular minterm ko cover karne wala akela PI ho — yeh final expression mein aana zaroor chahiye.

Do terms ek bade group mein tab combine ho sakte hain jab...

unke dashes SAME positions par hon AUR exactly ek bit mein alag hon.

QM mein don't-cares kaise use hote hain?

Combining ke waqt use hote hain (bade PIs banane ke liye) lekin prime implicant chart mein covered/columned nahi hote.

PI chart ka purpose kya hai?

Har minterm cover karne wala prime implicants ka ek minimal subset chunna (EPIs dhundo, phir baaki cover karo).

Kya 2 bits mein alag do minterms combine ho sakte hain?

Nahi — sirf Hamming distance 1 mein ek variable cancel ho sakta hai.

01-1 pattern ko ABCD order mein decode karo.

A = 0, B = 1, C

dropped,

D = 1 \Rightarrow \overset{ˉ}{A} B D

Connections

Karnaugh Maps — visual sibling; QM kai variables ke liye tabular generalization hai.
Sum of Products (SOP) — QM ek minimal SOP output karta hai.
Boolean Algebra Laws — combining/complement laws $X + \overset{ˉ}{X} = 1$ .
Prime Implicants and Petrick's Method — Petrick non-essential PI selection algebraically handle karta hai.
Logic Gate Minimization — kam literals ⇒ kam gates ⇒ sasta hardware.