Karnaugh Maps (K-Maps) for Boolean Simplification: A Practical Guide for Digital Electronics

This lecture on Karnaugh Maps (K-Maps) is authored by Dr. G. S. Virdi, Ex-Chief Scientist, CSIR-Central Electronics Engineering Research Institute (CEERI), Pilani, India. With extensive R&D experience in digital electronics, semiconductor devices design, and fabrication, Dr. Virdi provides a detailed and application-oriented understanding of K-Maps.

K-Maps are an essential tool for simplifying complex Boolean expressions, minimizing logic circuits, and optimizing digital system design. This lecture explains K-Map concepts for 2, 3, 4, and 5 variables, including SOP and POS minimization, adjacency rules, grouping techniques, and handling don’t-care conditions. Practical examples help learners accurately apply K-Maps in combinational logic design.

This lecture is highly beneficial for Engineering and Science students at UG/PG level, academicians, and researchers working in digital logic and VLSI design. It will be uploaded on SlideShare for wider accessibility.

1. The Karnaugh Map (K-Map)
Dr.G.S.Virdi
Ex.ChiefScientist
CSIR -Central Electronics Engineering Research Institute
Pilani-333031,India

2. KarnaughMaps
•Karnaughmaps(K-maps)aregraphicalrepresentationsof
Booleanfunctions.
•Onemapcellcorrespondstoarowinthetruthtable.
•Also,onemapcellcorrespondstoamintermoramaxtermin
theBooleanexpression
•Multiple-cellareasofthemapcorrespondtostandardterms.
•AK-mapprovidesasystematicmethodforsimplifyingBoolean
expressionsand,ifproperlyused,willproducethesimplestSOP
orPOSexpressionpossible,knownastheminimum expression.

3. WhatisK-Map
•It’ssimilartotruthtable;insteadofbeingorganized
(i/pando/p)intocolumnsandrows,theK-mapisan
arrayofcellsinwhicheachcellrepresentsabinary
valueoftheinputvariables.
•Thecellsarearrangedinawaysothatsimplification
ofagivenexpressionissimplyamatterofproperly
groupingthecells.
•K-mapscanbeusedforexpressions with2,3,4,and
5variables.

4. Two-VariableMap
1
0
0 1
x
2
x
1
0
m
0
1
m
1
2
m
2
3
m
3
orderingofvariablesisIMPORTANTforf(x
1,x
2),x
1is
therow,x
2isthecolumn.
Cell0representsx
1’x
2’;Cell1representsx
1’x
2;etc.If
amintermispresentinthefunction,thena1is
placedinthecorrespondingcell.
1
0
10
x
1
x
2
0
m
0
2
m
2
1
m
1
3
m
3
OR

5. Two-VariableMap
•AnytwoadjacentcellsinthemapdifferbyONLYonevariable,
whichappearscomplementedinonecelland
uncomplementedintheother.
•Example:
m
0(=x
1’x
2’)isadjacenttom
1(=x
1’x
2)andm
2(=x
1x
2’)butNOTm
3
(=x
1x
2)

6. 2-VariableMap--Example
•f(x
1,x
2)=x
1’x
2’+x
1’x
2+x
1x
2’
=m
0+m
1+m
2
=x
1’+x
2’
•1splacedinK-mapforspecifiedmintermsm
0,
m
1,m
2
•Groupingof1sallowssimplification
•What(simpler)functionisrepresentedbyeach
dashedrectangle?
–x
1’=m
0+m
1
–x
2’=m
0+m
2
•Herem
0coveredtwice
1
0
1
x
x
10
2
0 1
11
2
1
3
0

7. The3VariableK-Map
•Thereare8cellsasshown:
0 1
C
AB
00
01
11
10
ABCABC
ABCABC
ABCABC
ABCABC

8. Example3var.k-map
M
_
in
_
im
_
iz
_
et
_
hef
_
ollowingequationusing k-map
y=ABC+ABC+ABC+ABC
_____
ABC=000=0
_
ABC=101=5
ABC=010=2
ABC=111=7
Usingthisfillthek-map
•Grouping–here2groupsof21’s
Ispossible

9. ForuppergroupAandCare
constantsandBisvarying.
NeglectB.AandCbothare0.
__
HenceoutputofthisgroupisAC
•ForuppergroupAandCare
constantsandBisvarying.
NeglectB.AandCbothare0.
HenceoutputofthisgroupisAC
ThusoutputYisgivenby,
_ _
Y=AC+AC
=A
⃝.
B

10. 00 01 11 10
CD
AB
00
01
11
10
ABCD ABCD ABCD ABCD
ABCD ABCD ABCD ABCD
ABCD ABCD ABCD ABCD
ABCD ABCD ABCD ABCD
The4-VariableK-Map

11. 00011110
CD
AB
00
01
11
10
CellAdjacency

12. •Solvethegiven
k-map
•StepI-grouping
•StepII-outputof
eachgroup
•StepIII-finaloutput
Hereansweris,
___
Y=CD+BC+BD

13. K-MapSOPMinimization
•TheK-MapisusedforsimplifyingBooleanexpressionstotheir
minimalform.
•AminimizedSOPexpressioncontainsthefewestpossible
termswithfewestpossiblevariablesperterm.
•Generally,aminimumSOPexpressioncanbeimplemented
withfewerlogicgatesthanastandardexpression.

14. Grouping
Rulesofgrouping-
1’s&0’scan
notbegrouped
diagonal1’scan
notbegrouped

15. Elementsinagroupshouldbe2
n

16. Minimum
Groups
shouldbe
formed
Forabove
rulegroup
Overlapping
isapplicable

18. MappingaStandardSOPExpression
•ForanSOPexpressionin standardform:
–A1isplacedontheK-mapforeach producttermintheexpression.
–Each1isplacedinacell correspondingtothevalueofa
productterm.
–Example:fortheproductterm,
a1goesinthe101cellona3-
C
0 1
AB
00
01
11
10
ABCABC
ABCABC
ABCABC
ABCABC
variablemap.ABC

19. C
AB
00
01
11
10
MappingaStandardSOPExpression
The expression:
ABCABCABCABC
000 001 110 100
0 1
1 1
1
1
ABCDABCDABCDABCDABCDABCDABCD
ABCABCABC
ABCABCABCABC
Practice:

20. Three-VariableK-Maps
f(0,4)BC f(4,5)AB f(0,1,4,5)B f(0,1,2,3)A
0
1
BC
A
00011110
1000
1000
0
1
BC
A
00011110
0000
1100
0
1
BC
A
00011110
1111
0000
0
1
BC
A
00011110
1100
1100
f(0,4)AC f(4,6)AC f(0,2)AC f(0,2,4,6)C
0
1
BC
A
00011110
0110
0000
0
1
BC
A
00011110
0000
1001
0
1
BC
A
00011110
1001
1001
0
1
BC
A
00011110
1001
0000

21. Four-VariableK-Maps
f(0,8)BCD
f(5,13)BCD f(13,15)ABD f(4,6)ABD
f(2,3,6,7)AC f(4,6,12,14)BD f(2,3,10,11)BC f(0,2,8,10)BD
CD
00011110
AB
00
01
11
10
1000
0000
0000
1000
CD
00011110
AB
000000
010100
110100
100000
CD
00011110
AB
000000
010000
110110
100000
CD
00011110
AB
00
01
11
10
0000
1001
0000
0000
CD
00011110
AB
000011
010011
110000
100000
CD
00011110
AB
00
01
11
10
0000
1001
1001
0000
CD
00011110
AB
00
01
11
10
0011
0000
0000
0011
CD
00011110
AB
00
01
11
10
1001
0000
0000
1001

22. Four-VariableK-Maps
CD
00011110
AB
CD
00011110
AB
CD
00011110
000000 000010 00
011111 010010 01
110000 110010 11
100000 100010 10
AB
1010
0101
1010
0101
CD
00011110
AB
00
01
11
10
0101
1010
0101
1010
CD
00011110
AB
000110
010110
110110
100110
CD
00011110
AB
00
01
11
10
1001
1001
1001
1001
CD
00011110
AB
000000
011111
111111
100000
CD
00011110
AB
00
01
11
10
1111
0000
0000
1111
f(4,5,6,7)AB f(3,7,11,15)CD
f(0,3,5,6,9,10,12,15)
fABCD
f(1,2,4,7,8,11,13,14)
fABCD
f(1,3,5,7,9,11,13,15)
fD
f(0,2,4,6,8,10,12,14)
fD
f(4,5,6,7,12,13,14,15)
fB
f(0,1,2,3,8,9,10,11)
fB

23. DeterminingtheMinimumSOPExpressionfromtheMap
CD
AB
00011110
00 11
011111
111111
10 1
AC
B
ACD
BACACD

24. DeterminingtheMinimumSOPExpressionfromtheMap
ABBCABC
C
AB
0 1
1
1
1 1
00
01
11
10
0 1
C
AB
00
01
11
10
1 1
1
1
1 1
BACAC

25. MappingDirectlyfromaTruthTable
I/P O/P
ABCX
0001
0010
0100
0110
1001
1010
1101
1111
C
0 1
AB
00
01
11
10
1
1
1
1

26. Don’tCareConditions
•Adon’tcarecondition,markedby(X)inthetruth
table,indicatesaconditionwherethedesigndoesn’t
careiftheoutputisa(0)ora(1).
•Adon’tcareconditioncanbetreatedasa(0)ora(1)
inaK-Map.
•Treatingadon’tcareasa(0)meansthatyoudonot
needtogroupit.
•Treatingadon’tcareasa(1)allowsyoutomakea
groupinglarger,resultinginasimplertermintheSOP
equation.

27. SomeYouGroup,SomeYouDon’t
0
X
1 0
0 0
X 0
CVC
AB
AB
AB
AB
AC
Thisdon’t careconditionwastreatedasa(1).
Thisallowedthegroupingofasingleoneto
becomeagroupingoftwo,resultinginasimpler
term.
Therewasnoadvantageintreatingthis
don’tcareconditionasa(1),thusitwas
treatedasa(0)andnotgrouped.

28. Example
Solution:
FRTRS
4
R S T U F
4
0 0 0 0 X
0 0 0 1 0
0 0 1 0 1
0 0 1 1 X
0 1 0 0 0
0 1 0 1 X
0 1 1 0 X
0 1 1 1 1
1 0 0 0 1
1 0 0 1 1
1 0 1 0 1
1 0 1 1 X
1 1 0 0 X
1 1 0 1 0
1 1 1 0 0
1 1 1 1 0
X 0 X 1
0 X 1 X
X 0 0 0
1 1 X 1
RS
RS
RS
RS
V
TUTUTUTU
RT
RS

29. IMPLEMENTATIONOFK-MAPS
-Insomelogiccircuits,theoutputresponses
forsomeinputconditionsaredon’t care
whethertheyare1or0.
x d 1
InK-maps,don’t-careconditionsarerepresented
byd’sinthecorrespondingcells.
Don’t-careconditionsareusefulinminimizing
thelogicfunctionsusingK-map.
-Canbeconsideredeither1or0
-Thusincreasesthechancesofmergingcellsintothelargercells
-->Reducethenumberofvariablesintheproductterms
yz x’
1dd1
yz’
x
y
z
F

30. K-MapPOSMinimization
•Theapproachesaremuchthesame(asSOP)exceptthatwith
POSexpression,0srepresentingthestandardsumtermsare
placedontheK-mapinsteadof1s.

31. C
0 1
AB
00
01
11
10
MappingaStandardPOSExpression
The expression:
(ABC)(ABC)(ABC)(ABC)
000 010 110 101
0
0
0
0

32. K-mapSimplificationofPOSExpression
(ABC)(ABC)(ABC)(ABC)(ABC)
0 1
C
AB
00
01
11
10 AB
0 0
0 0
0
AC
BC
A
1
11
A(BC)
ABAC

33. -Sum-of-IMPLEMENTATIONOFK-MAPS
ProductsForm-
LogicfunctionrepresentedbyaKarnaughmap
canbeimplementedintheformofnot-AND-OR
Acelloracollectionoftheadjacent1-cellscan
berealizedbyanANDgate,withsomeinversion oftheinputvariables.
y
x’
y’
z’
x’
y
z’
x
y
z’
1 1
x 1
z
F(x,y,z)=(0,2,6)
1 1
1
x’
z’
y
z’

x’
y
x
y
z’
x’
y’
z’
F
x
z
y
z
F
notAND OR
z’


34. -Product-of-IMPLEMENTATIONOFK-MAPS
SumsForm-
LogicfunctionrepresentedbyaKarnaughmap
canbeimplementedintheformofI-OR-AND
Ifweimplement aKarnaughmapusing0-cells,
thecomplement ofF,i.e.,F’,canbeobtained.
Thus,bycomplementingF’usingDeMorgan’s
theoremFcanbeobtained
F(x,y,z)=(0,2,6)
x
y
zx
y’
z
F’=xy’+z
F=(xy’)z’
=(x’+y)z’
x
y
z
F
IOR AND
001 1
0001

35. Designofcombinationaldigitalcircuits
•Stepstodesignacombinationaldigitalcircuit:
–Fromtheproblemstatementderivethetruthtable
–Fromthetruthtablederivetheunsimplifiedlogic
expression
–Simplifythelogicexpression
–Fromthesimplifiedexpressiondrawthelogiccircuit

36. Example:Designa3-input(A,B,C)digitalcircuitthatwillgiveatits
output(X)alogic1onlyifthebinarynumberformedattheinputhasmoreones
thanzeros.
XACABBC
A
Inputs
BC
Output
X
0000 0
1001 0
2010 0
3011 1
4100 0
5101 1
6110 1
7111 1
BC
0
1
00011110
A
0010
0111
A B C
X
X(3,5,6,7)

37. X ACABABC
A B C
X
X(2,3,4,5,6,7,8,9)A
Inputs
BCD
Output
X
00000 0
10001 0
20010 1
30011 1
40100 1
50101 1
60110 1
70111 1
81000 1
91001 1
101010 0
111011 0
121100 0
131101 0
141110 0
151111 0
D
CD
00011110
AB
000011
011111
110000
101100
X
Same
Example:Designa4-input(A,B,C,D)digitalcircuitthatwill
giveatitsoutput(X)alogic1onlyifthebinarynumber
formedattheinputisbetween2and9(including).