Karnaugh map simplification (2,3,4 variables)

3.1.11 · Hardware › Boolean Algebra & Logic Gates

K-map KYA hota hai?

Gray code kyun, binary order kyun nahi? Agar hum columns ko 00, 01, 10, 11 label karte, toh columns 01 aur 10 (paper par adjacent) do bits se differ karte — unhe group karna galat hota. Gray code order 00, 01, 11, 10 guarantee karta hai ki har neighbour (wrap-around edges samait) ek bit se differ kare, yahi poora point hai.

Grouping kaam kyun karta hai? (Pehle principles se derive karo)

Humhe sirf ek Boolean law chahiye — combining theorem: $X Y + X \overset{ˉ}{Y} = X (Y + \overset{ˉ}{Y}) = X \cdot 1 = X$

Ab generalise karo. Agar $1$ s ka ek group $k$ variables ke saare combinations cover karta hai jabki baaki $n - k$ variables fixed rehte hain, toh combining theorem ko baar baar apply karne se saare $k$ varying variables eliminate ho jaate hain:

$2^{1} = 2$ cells ka group → 1 variable eliminate hoti hai.
$2^{2} = 4$ cells ka group → 2 variables eliminate hoti hain.
$2^{3} = 8$ cells ka group → 3 variables eliminate hoti hain.

Legal group ke rules (saare poore hone chahiye):

Sirf 1s contain kare (aur don't-cares agar help kare).
Size power of two ho: $1, 2, 4, 8, 16$ .
Shape rectangle (ya square) ho — koi diagonal nahi, koi L-shape nahi.
Edges wrap around karte hain (left↔right, top↔bottom) — map ek torus hai.
Groups overlap ho sakte hain; overlap use karo agar koi group bada banta ho.
Har 1 ko kam se kam ek baar cover karo, sabse kam, sabse bade groups use karke.

Figure — Karnaugh map simplification (2,3,4 variables)

Har map kaise banayein

2-variable ( $A, B$ )

$2 \times 2$ grid. Rows = $A$ , columns = $B$ .

3-variable ( $A, B, C$ )

$2 \times 4$ grid. Rows = $A$ (0,1), columns = $B C$ Gray order mein 00,01,11,10.

4-variable ( $A, B, C, D$ )

$4 \times 4$ grid. Rows = $A B$ Gray 00,01,11,10, columns = $C D$ Gray 00,01,11,10.

Cell numbering minterm index $m_{i}$ use karta hai jahan $i$ input bits ki decimal value hai.

Worked Example 1 — 3 variables

$F (A, B, C) = \sum m (1, 3, 5, 7)$ — matlab minterms 1,3,5,7 ke liye output 1.

$A \ B C$	00	01	11	10
0	0	1	1	0
1	0	1	1	0

Step 1 — 1s place karo. Minterms 1(001),3(011),5(101),7(111). Yeh step kyun? Yeh decimals us $A B C$ pattern mein convert hote hain jo har cell ko name deta hai.

Step 2 — sabse bada group dhundho. Saare chaar 1s columns 01 aur 11 mein ek $2 \times 2$ block banate hain. Yeh step kyun? Bada group ⇒ zyada variables eliminate.

Step 3 — surviving literals padho. Is group mein: $A$ 0 aur 1 dono leta hai (vary karta hai → drop), $B$ 0 aur 1 dono leta hai (drop), $C = 1$ har cell mein (rehta hai). Yeh step kyun? $n - k = 3 - 2 = 1$ literal bachta hai, aur wahi group mein constant rehta hai.

$F = C$

Sanity check: $m 1, 3, 5, 7$ exactly wahi minterms hain jahan $C = 1$ hai. ✓

Worked Example 2 — 4 variables

$F (A, B, C, D) = \sum m (0, 1, 2, 3, 8, 9, 10, 11)$

$A B \ C D$	00	01	11	10
00	1	1	1	1
01	0	0	0	0
11	0	0	0	0
10	1	1	1	1

Step 1 — plot karo. Row 00 (AB=00) aur row 10 (AB=10) saari 1 hain. Kyun? Minterms 0–3 → AB=00; 8–11 → AB=10.

Step 2 — wrap-around ke saath group karo. Rows 00 aur 10 top aur bottom edges hain, jo wrap se adjacent hain. Mil ke yeh $8$ cells ka group banate hain (torus par ek $2 \times 4$ block). Yeh step kyun? Edge wrap legal hai; 8 cells lene se 3 variables eliminate hoti hain ( $4 - 3 = 1$ ).

Step 3 — literals padho. Is group mein $C, D$ dono vary karte hain (drop), $A$ dono rows mein vary karta hai (drop)... check: row 00 mein $A = 0$ , row 10 mein $A = 1$ → $A$ vary karta hai, drop. $B = 0$ dono rows mein → rehta hai. $F = \overset{ˉ}{B}$

Worked Example 3 — Don't-cares ( $\times$ )

$F (A, B, C, D) = \sum m (1, 3, 7, 11, 15) + d (0, 2, 5)$

Don't-cares ko 1 ya 0, jo bhi bada group de treat kiya ja sakta hai.

$A B \ C D$	00	01	11	10
00	d	1	1	d
01	0	d	1	0
11	0	0	1	0
10	0	0	1	0

Step 1 — CD=11 column (m3,7,15,11) saari 1 hai → 4 ka group → term $C D$ ( $C = 1, D = 1$ , rows vary karte hain). Kyun? $4 - 2 = 2$ literals, dono column mein constant hain.

Step 2 — don't-cares use karke row 00 lo. Cells 0(d),1(1),3(1),2(d): saaro ko =1 banane se row 00 mein 4 ka group milta hai → $\overset{ˉ}{A} \overset{ˉ}{B}$ ( $A = 0, B = 0$ ; CD vary karta hai). Kyun? Don't-cares 0 aur 2 free 1s hain jo size-4 group banane dete hain ek lonely pair ki jagah.

$F = C D + \overset{ˉ}{A} \overset{ˉ}{B}$ Hum un don't-cares (5) ko simply ignore karte hain jo humne nahi liye — woh koi extra term force nahi karte.

Common mistakes

Active Recall

Recall K-map rows/columns mein Gray code kyun use hona chahiye?

Taaki physically adjacent cells exactly ek variable se differ karen, jo combining theorem $X Y + X \overset{ˉ}{Y} = X$ ko neighbours ke liye valid banata hai.

Recall 4-variable map mein 8 cells ka group kitne literals deta hai?

$n - k = 4 - 3 = 1$ literal.

Recall Don't-care ko kaise treat karte hain?

1 ki tarah agar woh group badata hai, warna 0 (ignore karo). Sirf don't-care cover karne ke liye koi term require mat karo.

Recall 3 cells ka group illegal kyun hai?

Cancellation sirf powers of two ke liye kaam karta hai; size-3 group ek single product term mein reduce nahi ho sakta.

Recall Feynman: 12-saal ke bacche ko explain karo

Socho fridge par ek sticker chart hai jo donut ki tarah shaped hai. Tum jahan answer "yes" ho wahan star lagate ho. Agar do stars ek doosre ke bilkul paas hon, iska matlab hai ek cheez (say, light on thi ya nahi) matter nahi karti thi — answer waise bhi yes tha — toh tum us cheez ko apne rule se cross kar dete ho. Jitna bada block of stars tum circle kar sako (2, 4, 8...), utna zyada stuff cross out hota hai, aur tera rule chhota aur simple hota jaata hai. Woh chhota rule ek sasta circuit hai.

Connections

Boolean Algebra Laws — combining theorem $X Y + X \overset{ˉ}{Y} = X$ engine hai.
Sum of Products and Product of Sums — K-map minimal SOP output karta hai (0-grouping POS deta hai).
Truth Tables — raw data jo K-map rearrange karta hai.
Logic Gate Minimisation — kam literals ⇒ kam gates ⇒ sasta hardware.
Quine-McCluskey Method — tabular alternative jab variables > 4 hon.
Don't-care Conditions — flexible cells jo groups badata hai.

Flashcards

K-map truth table par kaun si rearrangement karta hai?

Outputs ko ek grid mein place karta hai taaki adjacent cells exactly ek variable se differ karen (Gray-code labelling).

Grouping ko kaun sa Boolean theorem justify karta hai?

Combining theorem

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

n

-var map mein

2^{k}

ones ke group se kitne literals milte hain?

n - k

literals.

Legal K-map group sizes kya hain?

Powers of two: 1, 2, 4, 8, 16.

Straight binary ki jagah Gray code order kyun use hota hai?

Taaki neighbouring cells sirf ek bit se differ karen, adjacency valid rakhne ke liye.

K-map groups overlap ho sakte hain?

Haan, agar overlapping kisi group ko bada kare.

Map ki edges ko kaise treat kiya jaata hai?

Yeh wrap around hoti hain (torus) — left↔right aur top↔bottom adjacent hain.

Don't-care ko kaise handle karte hain?

1 ki tarah agar woh group badata hai, warna ignore karo (0 treat karo).

A, B, C

ke liye

F = \sum m (1, 3, 5, 7)

simplify hokar kya banta hai?

F = C

3 cells ko group kyun nahi kar sakte?

Cancellation sirf powers-of-two groups ke liye collapse hoti hai; 3 ka koi clean reduction nahi hai.