Karnaugh Map Minimization

Karnaugh Map Minimization

Karnaugh Map (K-Map) एक graphical method है जिसका उपयोग Boolean expressions को simplify या minimize करने के लिए किया जाता है। इसके द्वारा complex Boolean expression को कम terms और कम variables वाले simpler expression में बदला जा सकता है।

Karnaugh Map का उपयोग विशेष रूप से digital logic circuit design में किया जाता है क्योंकि simplified Boolean expression से circuit में gates की संख्या और complexity कम की जा सकती है।

Why is K-Map Used?

Boolean Algebra के laws की सहायता से expressions को simplify किया जा सकता है, लेकिन जैसे-जैसे variables की संख्या बढ़ती है, simplification कठिन हो सकती है। K-Map इस process को graphical और systematic बनाता है।

• Boolean expressions को simplify करने के लिए।
• Logic circuits की complexity कम करने के लिए।
• Logical gates की संख्या कम करने के लिए।
• Circuit की cost और hardware requirement कम करने के लिए।
• Expression को minimum form में प्राप्त करने के लिए।

Karnaugh Map and Number of Variables

K-Map में cells की संख्या variables की संख्या पर निर्भर करती है। यदि variables की संख्या n है, तो cells की संख्या 2ⁿ होगी।

Variables	Number of Cells	K-Map Type
2	4	2-variable K-Map
3	8	3-variable K-Map
4	16	4-variable K-Map
5	32	5-variable K-Map

Class XII level पर सामान्यतः 2-variable, 3-variable और 4-variable K-Maps का अध्ययन किया जाता है।

2-Variable K-Map

दो variables A और B के लिए कुल 2² = 4 possible combinations होते हैं। इसलिए 2-variable K-Map में 4 cells होते हैं।

A \ B	0	1
0	m0	m1
1	m2	m3

यहाँ प्रत्येक cell एक minterm को represent करता है।

3-Variable K-Map

तीन variables A, B और C के लिए कुल 2³ = 8 combinations होते हैं। इसलिए 3-variable K-Map में 8 cells होते हैं।

K-Map में rows और columns को सामान्य binary order में नहीं बल्कि Gray Code order में arrange किया जाता है। Gray Code में adjacent values में केवल एक bit का difference होता है।

AB \ C	0	1
00	m0	m1
01	m2	m3
11	m6	m7
10	m4	m5

4-Variable K-Map

चार variables A, B, C और D के लिए कुल 2⁴ = 16 combinations होते हैं। इसलिए 4-variable K-Map में 16 cells होते हैं।

AB \ CD	00	01	11	10
00	m0	m1	m3	m2
01	m4	m5	m7	m6
11	m12	m13	m15	m14
10	m8	m9	m11	m10

What is a Group in K-Map?

K-Map में adjacent cells जिनमें 1 भरे होते हैं, उन्हें एक group में combine किया जाता है। Grouping के बाद variable values को देखकर simplified Boolean term प्राप्त किया जाता है।

एक group में cells की संख्या हमेशा power of 2 होनी चाहिए।

Number of Cells	Valid Group?
1	Yes
2	Yes
4	Yes
8	Yes
16	Yes
3	No
5	No
6	No

Rules for Grouping

• Groups में cells की संख्या 1, 2, 4, 8, 16... होनी चाहिए।
• Grouping जितना संभव हो उतना बड़ा होना चाहिए।
• सामान्यतः बड़े groups अधिक variables को eliminate करते हैं।
• केवल adjacent cells को group किया जाता है।
• Diagonal cells adjacent नहीं माने जाते।
• K-Map की opposite edges भी adjacent मानी जाती हैं।
• एक cell को आवश्यकता होने पर एक से अधिक groups में शामिल किया जा सकता है।
• सभी आवश्यक 1s को groups में cover करने का प्रयास किया जाता है।

Adjacency in K-Map

K-Map में केवल horizontally और vertically adjacent cells को directly adjacent माना जाता है। Diagonal cells adjacent नहीं होते।

एक महत्वपूर्ण विशेषता यह है कि K-Map की first और last rows तथा first और last columns भी adjacent मानी जाती हैं। इसे wrap-around adjacency कहते हैं।

Minimization using SOP

यदि Boolean function को SOP form में minimize करना है, तो K-Map में उन cells में 1 भरा जाता है जिनके corresponding minterms function में उपस्थित हैं। फिर adjacent 1s के groups बनाए जाते हैं।

उदाहरण:

F(A,B) = Σm(1,3)

2-variable K-Map में m₁ और m₃ पर 1 रखा जाएगा।

A \ B	0	1
0	0	1
1	0	1

दोनों 1s का group बनाया जा सकता है। इस group में B की value हमेशा 1 है जबकि A बदल रहा है। इसलिए A eliminate हो जाता है।

F = B

Step-by-Step Example of SOP Minimization

मान लीजिए:

F(A,B,C) = Σm(1,3,5,7)

3-variable K-Map में minterms 1, 3, 5 और 7 पर 1 रखा जाएगा।

AB \ C	0	1
00	0	1
01	0	1
11	0	1
10	0	1

चारों 1s का एक group बनाया जा सकता है। इस group में A और B दोनों बदल रहे हैं, जबकि C = 1 रहता है। इसलिए A और B eliminate हो जाते हैं।

F = C

Minimization using POS

यदि Boolean function को POS form में minimize करना है, तो K-Map में output 0 वाली cells को group किया जाता है।

अर्थात्:

Example of POS Minimization

मान लीजिए:

F(A,B) = ΠM(0,2)

Output 0 वाली cells m₀ और m₂ होंगी।

A \ B	0	1
0	0	1
1	0	1

दोनों 0s का group बनाने पर B = 0 constant रहता है। POS grouping में constant 0 variable normal form में आता है। इसलिए:

F = B

SOP Grouping Rules

SOP minimization में हम 1s को group करते हैं। यदि किसी variable की value पूरे group में:

• 1 रहती है → variable normal form में आएगा।
• 0 रहती है → variable complemented form में आएगा।
• बदलती रहती है → variable eliminate हो जाएगा।

उदाहरण:

A = 1 → A
A = 0 → A'
A changes → A is eliminated

POS Grouping Rules

POS minimization में हम 0s को group करते हैं। यदि किसी variable की value पूरे group में:

• 0 रहती है → variable normal form में आएगा।
• 1 रहती है → variable complemented form में आएगा।
• बदलती रहती है → variable eliminate हो जाएगा।

Prime Implicant

K-Map में ऐसा group जिसे और बड़ा नहीं किया जा सकता, उसे सामान्यतः Prime Implicant कहा जाता है।

यदि कोई prime implicant ऐसा essential term है जो किसी 1-cell को cover करने के लिए आवश्यक है और वह cell किसी दूसरे suitable group से cover नहीं होती, तो उसे Essential Prime Implicant कहा जाता है।

Essential Prime Implicant

यदि किसी minterm को cover करने वाला केवल एक ही prime implicant है, तो वह Essential Prime Implicant होता है। ऐसे groups को solution में अवश्य शामिल किया जाता है।

Don't Care Conditions

कुछ Boolean functions में कुछ input combinations ऐसे हो सकते हैं जिनके output की आवश्यकता नहीं होती। इन्हें Don't Care Conditions कहा जाता है और सामान्यतः X से represent किया जाता है।

Don't-care cells को आवश्यकता के अनुसार 1 की तरह grouping में शामिल किया जा सकता है या ignore किया जा सकता है। इसका उद्देश्य expression को और अधिक simplify करना होता है।

K-Map Minimization Procedure

K-Map से Boolean expression minimize करने के लिए सामान्यतः निम्न steps follow किए जाते हैं:

1. Boolean function या truth table को identify करें।
2. Variables की संख्या के अनुसार K-Map बनाएं।
3. K-Map में Gray Code ordering का उपयोग करें।
4. SOP के लिए output 1 वाली cells में 1 भरें।
5. POS के लिए output 0 वाली cells में 0 भरें।
6. Adjacent cells के सबसे बड़े possible groups बनाएं।
7. हर group में constant variables identify करें।
8. Changing variables को eliminate करें।
9. सभी आवश्यक groups के terms को combine करें।
10. Final minimized Boolean expression प्राप्त करें।

Example: Complete K-Map Minimization

दिया गया function:

F(A,B,C) = Σm(1,3,5,7)

Step 1: 3-variable K-Map बनाएं।

AB \ C	0	1
00	0	1
01	0	1
11	0	1
10	0	1

Step 2: सभी चार 1s का एक group बनाएं।

Step 3: Group में A और B दोनों बदल रहे हैं। केवल C = 1 constant है।

इसलिए:

F = C

K-Map and Boolean Algebra

K-Map और Boolean Algebra दोनों का उद्देश्य Boolean expressions को simplify करना है। उदाहरण के लिए Boolean Algebra में:

AB + AB' = A(B + B')
        = A(1)
        = A

K-Map में भी corresponding cells को group करके यही simplified result प्राप्त किया जा सकता है।

K-Map and Digital Circuits

Boolean expression को minimize करने से उसके corresponding logic circuit में gates और inputs की संख्या कम हो सकती है। इससे circuit सरल, कम महंगा और अधिक efficient बनाया जा सकता है।

Important Points

• Karnaugh Map को short form में K-Map कहा जाता है।
• K-Map Boolean expressions को simplify करने की graphical technique है।
• n variables के लिए K-Map में 2ⁿ cells होते हैं।
• K-Map में Gray Code ordering का उपयोग किया जाता है।
• Gray Code में adjacent combinations में केवल एक bit बदलता है।
• SOP minimization में 1s को group किया जाता है।
• POS minimization में 0s को group किया जाता है।
• Groups की size हमेशा power of 2 होनी चाहिए।
• Valid group sizes 1, 2, 4, 8, 16 आदि हैं।
• Diagonal cells को adjacent नहीं माना जाता।
• First और last rows/columns wrap-around के कारण adjacent हो सकती हैं।
• बड़े groups सामान्यतः अधिक variables eliminate करते हैं।
• एक cell को आवश्यकता होने पर multiple groups में शामिल किया जा सकता है।
• Don't-care conditions को X से represent किया जाता है।
• Prime implicant ऐसा group है जिसे और बड़ा नहीं किया जा सकता।
• Essential prime implicant solution में आवश्यक group होता है।

Board Focus

Board Important Questions

Very Short Answer Questions

Q1. K-Map का full form क्या है?

Answer: Karnaugh Map.

Q2. K-Map का उपयोग किसलिए किया जाता है?

Answer: Boolean expressions को minimize करने के लिए।

Q3. दो variables के K-Map में कितने cells होते हैं?

Answer: 4.

Q4. तीन variables के K-Map में कितने cells होते हैं?

Answer: 8.

Q5. चार variables के K-Map में कितने cells होते हैं?

Answer: 16.

Q6. K-Map में किस type की coding का उपयोग किया जाता है?

Answer: Gray Code.

Q7. SOP minimization में किसे group किया जाता है?

Answer: 1s.

Q8. POS minimization में किसे group किया जाता है?

Answer: 0s.

Q9. K-Map में valid group sizes कौन-कौन से हैं?

Answer: 1, 2, 4, 8, 16 आदि।

Q10. K-Map में diagonal cells adjacent होती हैं या नहीं?

Answer: नहीं।

Short Answer Questions

Q11. Karnaugh Map क्या है?

Answer: Karnaugh Map एक graphical technique है जिसका उपयोग Boolean expressions को simplify और minimize करने के लिए किया जाता है।

Q12. K-Map में Gray Code का उपयोग क्यों किया जाता है?

Answer: Gray Code में adjacent combinations में केवल एक variable बदलता है, जिससे adjacent cells को combine करके variables eliminate करना आसान होता है।

Q13. K-Map में group की size कैसी होनी चाहिए?

Answer: Group की size हमेशा 2 की power होनी चाहिए, जैसे 1, 2, 4, 8, 16 आदि।

Q14. SOP और POS minimization में क्या अंतर है?

Answer: SOP minimization में 1s को group किया जाता है, जबकि POS minimization में 0s को group किया जाता है।

Q15. K-Map में wrap-around adjacency क्या है?

Answer: K-Map में first और last rows तथा first और last columns को भी adjacent माना जा सकता है।

Q16. Don't-care condition क्या है?

Answer: ऐसा input combination जिसका output महत्वपूर्ण नहीं होता, Don't-care condition कहलाता है और इसे X से represent किया जाता है।

Q17. Prime Implicant क्या है?

Answer: K-Map का ऐसा group जिसे और बड़ा नहीं किया जा सकता, Prime Implicant कहलाता है।

Long Answer Questions

Q18. K-Map द्वारा Boolean expression को minimize करने की प्रक्रिया समझाइए।

Answer: सबसे पहले variables की संख्या के अनुसार K-Map तैयार किया जाता है। SOP के लिए output 1 वाली cells में 1 और POS के लिए output 0 वाली cells में 0 भरा जाता है। इसके बाद adjacent cells के सबसे बड़े possible groups बनाए जाते हैं। प्रत्येक group में constant variables को identify करके changing variables को eliminate किया जाता है। अंत में सभी simplified terms को combine करके minimized Boolean expression प्राप्त किया जाता है।

Q19. निम्न function को K-Map द्वारा minimize कीजिए:

F(A,B,C) = Σm(1,3,5,7)

Answer:

AB \ C	0	1
00	0	1
01	0	1
11	0	1
10	0	1

चारों 1s का एक group बनाया जाता है। इस group में केवल C constant है और C = 1 है। इसलिए:

F = C

Q20. SOP और POS minimization के rules लिखिए।

Answer:

Feature	SOP	POS
Group	1s	0s
Basic Form	Product Terms का OR	Sum Terms का AND
Constant 1 variable	Normal form	Variable eliminated
Constant 0 variable	Complemented form	Normal form
Changing variable	Eliminated	Eliminated

Practice Questions

1. Karnaugh Map क्या है?
2. K-Map का उपयोग क्यों किया जाता है?
3. n variables के K-Map में कितने cells होते हैं?
4. 2-variable K-Map बनाइए।
5. 3-variable K-Map बनाइए।
6. 4-variable K-Map बनाइए।
7. Gray Code क्या है?
8. K-Map में Gray Code का उपयोग क्यों किया जाता है?
9. SOP minimization क्या है?
10. POS minimization क्या है?
11. SOP में किन cells को group किया जाता है?
12. POS में किन cells को group किया जाता है?
13. K-Map में valid group sizes लिखिए।
14. Diagonal cells को adjacent क्यों नहीं माना जाता?
15. Wrap-around adjacency क्या है?
16. Prime Implicant क्या है?
17. Essential Prime Implicant क्या है?
18. Don't-care condition क्या है?
19. दिए गए minterms से SOP को K-Map द्वारा minimize कीजिए।
20. दिए गए maxterms से POS को K-Map द्वारा minimize कीजिए।

Quick Revision

• K-Map: Boolean expression minimization की graphical technique.
• 2 variables: 4 cells.
• 3 variables: 8 cells.
• 4 variables: 16 cells.
• Ordering: Gray Code.
• SOP: Group 1s.
• POS: Group 0s.
• Group size: Power of 2.
• Diagonal: Not adjacent.
• Edges: Wrap-around adjacency possible.
• Don't Care: X.
• Prime Implicant: Maximum possible group.