The Karnaugh Map Boolean Algebraic Simplification ...

The K-map method of solving the logical expressions is referred to as the graphical technique of simplifying Boolean expressions. K-maps are also referred ... NetworkSites: Latest News TechnicalArticles Latest Projects Education Latest News TechnicalArticles MarketInsights Education LogIn Join Login JoinAAC Orsigninwith Facebook Google LinkedIn GitHub     0:00 / 0:00 Podcast Latest Subscribe Google Spotify Apple iHeartRadio Stitcher Pandora TuneIn Menu Articles Latest News Projects TechnicalArticles IndustryArticles IndustryWhitePapers Forums Latest HardwareDesign Embedded&Programming Education Math&Science Community Education Textbooks VideoLectures&Tutorials Worksheets IndustryWebinars VirtualWorkshops Tools Calculators PartSearch TestEquipmentDatabase BomTool ICDesignCenter Videos Latest NewProducts VideoTutorials On-DemandWebinars TechChats VirtualWorkshops Datasheets Giveaways Industry Tech Days Podcast Connectwithus NetworkSites: TechnicalArticle TheKarnaughMapBooleanAlgebraicSimplificationTechnique JoinourEngineeringCommunity!Sign-inwith: 2 Home TechnicalArticles TheKarnaughMapBooleanAlgebraicSimplificationTechnique TechnicalArticle TheKarnaughMapBooleanAlgebraicSimplificationTechnique June24,2016bySnehaH.L. LearnabouttheKarnaughmap(K-map)techniqueforBooleanalgebraicsimplification.Whatadvantagesanddisadvantagesdotheyhave? ThisarticleprovidesinsightintotheKarnaughmap(K-map)Booleanalgebraicsimplificationtechniqueviaafewexamples.ItalsoincludesabriefnoteontheadvantagesandthedisadvantagesofK-maps.Introduction Digitalelectronicsdealswiththediscrete-valueddigitalsignals.Ingeneral,anyelectronicsystembasedonthedigitallogicusesbinarynotation(zerosandones)torepresentthestatesofthevariablesinvolvedinit.Thus,Booleanalgebraicsimplificationisanintegralpartofthedesignandanalysisofadigitalelectronicsystem. AlthoughBooleanalgebraiclawsandDeMorgan'stheoremscanbeusedtoachievetheobjective,theprocessbecomestediousanderror-proneasthenumberofvariablesinvolvedincreases.Thisnecessitatestheuseofasuitable,relatively-simplesimplificationtechniquelikethatofKarnaughmap(K-map),introducedbyMauriceKarnaughin1953.   ATypicalK-Map TheK-mapmethodofsolvingthelogicalexpressionsisreferredtoasthegraphicaltechniqueofsimplifyingBooleanexpressions.K-mapsarealsoreferredtoas2DtruthtablesaseachK-mapisnothingbutadifferentformatofrepresentingthevaluespresentinaone-dimensionaltruthtable. K-mapsbasicallydeal withthetechniqueofinsertingthevaluesoftheoutputvariableincellswithinarectangleorsquaregridaccordingtoadefinitepattern.ThenumberofcellsintheK-mapisdeterminedbythenumberofinputvariables andismathematicallyexpressedastworaisedtothepowerofthe numberofinputvariables,i.e.,2n,wherethenumberofinputvariablesis n. Thus,tosimplifyalogicalexpressionwithtwoinputs,werequireaK-mapwith4(=22)cells.Afour-inputlogicalexpressionwouldleadtoa16(=24)celled-K-map,andsoon.GrayCoding Further,eachcellwithinaK-maphasadefiniteplace-valuewhichisobtainedbyusinganencodingtechniqueknownasGraycode. Thespecialtyofthiscodeisthefactthattheadjacentcodevaluesdifferonlybyasinglebit.Thatis, ifthegivencode-wordis01,thenthepreviousandthenextcode-wordscanbe11or00,inanyorder,butcannotbe10inanycase. InK-maps,therowsandthecolumnsofthetableuse Graycode-labelingwhichinturnrepresentthevaluesofthecorrespondinginputvariables.ThismeansthateachK-mapcellcanbeaddressedusingauniqueGrayCode-Word. Theseconceptsarefurtheremphasizedbyatypical16-celledK-mapshowninFigure1,whichcanbeusedtosimplifyalogicalexpressioncomprisingof4-variables(A,B,CandDmentionedatitstop-leftcorner).   Figure1:AtypicalbutemptyKarnaughmapwith16cells   HeretherowsandthecolumnsoftheK-maparelabeledusing2-bitGraycode,showninthefigure,whichassignsadefiniteaddressforeachofitscells. Forexample,thegreycoloredcelloftheK-mapshowncanbeaddressedusingthecode-word"0101"whichisequivalentto5indecimal(shownas thegreennumber inthefigure)andcorrespondstotheinputvariablecombinationA̅BC̅DorA+B̅+C+D̅,dependingonwhethertheinput–outputrelationshipisexpressedinSOP(sumofproducts)formorPOS(productofsums)form,respectively. Similarly,AB̅CDorA̅+B+C̅+D̅referstotheGraycode-wordof"1011",equivalentto11indecimal(again,showningreeninthefigure),whichinturnmeansthatweareaddressingthepink-coloredK-mapcellinthefigure.K-MapSimplificationTechnique Withthis generalideaof K-maps,letusnowmoveontotheprocedureemployedindesigninganoptimal(intermsofthenumberofgatesusedtorealizethelogic)digitalsystem.We'llstartwithagivenproblemstatement.   Example1: Designadigitalsystemwhoseoutputisdefinedaslogicallylowifthe4-bitinputbinarynumberisamultipleof3;otherwise,theoutputwillbelogicallyhigh.Theoutputisdefinedifandonlyiftheinputbinarynumberisgreaterthan2.    Step1:TruthTable/CanonicalExpressionLeadingtoMin-orMax-Terms Thefirststepindesigninganydigitalsystemistohaveaclearideaofthevariablesinvolvedintheprocess,alongwiththeirstate-values.Further,dependingontheproblemstatement,wehavetoarriveatthenumberofoutputvariablesandtheirvaluesforeachandeverycombinationoftheinputliterals,whichcanbeconvenientlyrepresentedintheformofatruthtable. Inthegivenexample: Numberofinputvariables=4,whichwewillcallA,B,CandD. Numberofoutputvariables=1, whichwewillcallY where      Y=Don'tCare, iftheinputnumberis lessthan3(orangeentriesinthetruthtable)      Y=0,iftheinputnumberisanintegralmultipleof3 (greenentriesinthetruthtable)      Y=1,iftheinputnumberisnotanintegralmultipleof3(blueentriesinthetruthtable)   Table1   Notethat,inadditiontotheinputandoutputcolumns,thetruthtablealsohasacolumnwhichgivesthedecimalequivalentoftheinputbinarycombination,whichmakesiteasyforustoarriveatthemintermormaxtermexpansionforthegivenproblem.Thusforthegivenexample, Mintermexpansionwillbe ∑m(4,5,7,8,10,11,13,14)+∑d(0,1,2) Maxtermexpansionwillbe∏M(3,6,9,12,15)· ∏D(0,1,2) However,sometimesthelogicalexpressionwhichistobesimplifiedmightbedirectlygivenintermsofSOPorPOSforms.Inthiscase,therequirementforthetruthtablecanbeoverlookedprovidedthatweexpressthegivenexpressioninitscanonicalform,fromwhichthecorrespondingmintermsormaxtermscanbeobtained.Step2:SelectandPopulateK-Map FromStep1,weknowthenumberofinputvariablesinvolvedinthelogicalexpressionfromwhichsizeoftheK-maprequiredwillbedecided.Further,wealsoknowthenumberofsuchK-mapsrequiredtodesignthedesiredsystemasthenumberofoutputvariableswouldalsobeknowndefinitely.Thismeansthat,fortheexampleconsidered,werequireasingle(duetooneoutputvariable)K-mapwith16cells(astherearefour inputvariables). Next,wehave tofilltheK-mapcellswithoneforeachminterm,zeroforeachmaxterm,andXforDon'tCareterms.Theprocedureistoberepeatedforeverysingleoutputvariable.Henceforthisexample,weget theK-mapasshowninFigure2.   Figure2: Acompletelyfilled4-variableK-map​Step3:FormtheGroups K-mapsimplificationcanalsobereferredtoasthe"simplificationbygrouping"techniqueasitsolelyreliesontheformationofclusters.Thatis, themainaimoftheentireprocessistogathertogetherasmany ones(forSOPsolution)orzeros(forPOSsolution)underone roofforeachoftheoutputvariablesintheproblemstated.However,whiledoingso wehave tostrictlyabidebycertainrulesandregulations: Theprocesshastobeinitiatedbygroupingthebitswhichlieinadjacentcellssuchthatthegroupformedcontainsthemaximumnumberofselectedbits.Thismeansthatforan n-variableK-mapwith2ncells,trytogroupfor2ncellsfirst,thenfor2n-1cells,nextfor2n-2cells,andsoonuntilthe“group”containsonly20cells, i.e.,isolatedbits(ifany).Notethatthenumberofcellsinthegroupmustbeequaltoanintegerpowerto2,i.e.,1,2,4,8.... The proceduremust beappliedforalladjacentcellsoftheK-map,evenwhentheyappeartobenotadjacent—thetoprowisconsideredtobeadjacenttothebottomrowandtherightmostcolumnisconsideredtobeadjacenttotheleftmostcolumn,asiftheK-mapwrapsaroundfromtoptobottomandrighttoleft.For example, Group1ofSOPformsolutioninTable1. A bitappearinginonegroupcanberepeatedinanothergroup providedthatthisleadstotheincreaseintheresultinggroup-size.Forexample,cell5isrepeatedinbothGroup3aswellas4inSOPformsolutionofTable1 asitresultsintheformationofagroupwithtwo cellsinsteadofagroupwithjustonecell. Don’tCareconditionsaretobeconsideredforthegroupingactivityifandonlyiftheyhelpinobtainingalargergroup.Otherwise, theyaretobeneglected.HeretheDon'tCaretermsinthecells0and1areconsideredtocreateGroup2ofSOP solutionformasitresultsinagroupwithfour cellsinsteadofjusttwo.     SOPFormSolution  POSFormSolution Numberof groupshaving 16cells 0 0 Numberof groupshaving 8cells  0 0 Numberof groupshaving4cells(BlueEnclosuresinFigure3) 2 Group1(Cells0,2,8,10) 1 Group1(Cells0,1,2,3)  Group2(Cells0,1,4,5) Numberof groupshaving2cells(OrangeEnclosuresinFigure3) 4 Group3(Cells5,7) Group4(Cells5,13) 2 Group2(Cells1,9) Group5(Cells10,11) Group6(Cells10,14) Group3(Cells2,6) Numberof groupshaving1cell(GreenEnclosuresinFigure3) 0 2 Group4(Cell12) Group5(Cell15) Table1   Hencefortheexampleconsidered,theK-mapshowingthegroupscanbeobtainedasgivenbyFigure3 whoseinformationissummarizedinTable1.   Figure3: K-mapsgroupedfor(a)SOPsolutionand(b)POSsolutionStep4:SimplifiedLogicalExpression  Foreachoftheresulting groups,wehavetoobtainthecorrespondinglogicalexpressionintermsoftheinput-variables.ThiscanbedonebyexpressingthebitswhicharecommonamongsttheGraycode-wordswhichrepresentthecellscontainedwithintheconsideredgroup.Anotherwaytodescribetheprocessofobtainingthesimplifiedlogicalexpressionforagroupistoeliminatethevariable(s)forwhichthecorrespondingbitsappearwithinthegroupasboth0and1. Finally,allthesegroup-wiselogicalexpressionsneedtobecombinedappropriatelytoformthesimplifiedBooleanequationfortheoutputvariable. Thesameproceduremustberepeatedforeveryoutputvariableofthegivenproblem. Forinstance,intheexampleconsidered,thelogicaltermforGroup2ofSOPformsolutionisobtainedasA̅C̅.Thisisduetothefactthatthisgrouphas0asthecommonGraycode-wordbitbothalongitsrowsaswellasitscolumns, highlightedinFigure4(a).Thisgivesus theliteralsA̅andC̅. Similarly,inthecaseofGroup1ofPOSformsolution,wecanobtainthelogicalexpressionasA+B.Thisis because thegrouphasthecommonGraycode-wordsas0,0alongitsrowonly(nocode-wordbitsarecommonalongitscolumns)whichcorrespondtotheinputvariablesAandB.   Figure4: K-mapsimplificationtechniquefor(a)SOPsolutionand(b)POSsolution   Followingthissameprocess,wecanobtainthelogicaltermscorrespondingto eachofthegroupstofinallyformthelogicalexpressionfor theparticularoutput,asshownbyTable2.   SOPFormSolution POSFormSolution Groups LogicalExpression Groups LogicalExpression Group1 B̅D̅ Group1 A+B Group2 A̅C̅ Group2 B+C+D̅ Group3 A̅BD Group3 A+C̅+D Group4 BC̅D Group4 A̅+B̅+C+D Group5 AB̅C Group5 A̅+B̅+C̅+D̅ Group6 ACD̅     Thus,Y= B̅D̅+A̅C̅+ A̅BD+ BC̅D+ AB̅C+ ACD̅ Thus,Y=(A+B)(B+C+D̅)(A+C̅+D)(A̅+B̅+C+D)(A̅+B̅+C̅+D̅) Table2Step5:SystemDesign Havingobtainedthesimplifiedlogicalexpression,wecandecideonthetypeandthenumberofgatesrequiredtorealizetheexpectedlogicforeveryoutputbit,whichfurtherresultsinthecompletedesignofthedesiredsystem. Thus,thedigital systemcorrespondingtoSOPandPOSformsofsolution for thegivenexamplecanbedesignedusingthebasicgateslike NOT, AND,and OR asshownbyFigure5(a)and 5(b).   Figure5: Digitalsystemcorrespondingto(a)SOPformofsolutionand(b)POSformofsolution   Nowthatwe'veanalyzedeachstepforExample1,let'spracticeby applyingthemtotwomoreexamples.Example2: Designafulladderbyobtainingthesimplified expressionsforthesumandcarryoutputsinPOSform.   Step1:  Numberofinputvariables=3 Numberofoutputvariables=2   Inputs DecimalEquivalent Outputs A B Ci S Co 0 0 0 0 0 0 0 0 1 1 1 0 0 1 0 2 1 0 0 1 1 3 0 1 1 0 0 4 1 0 1 0 1 5 0 1 1 1 0 6 0 1 1 1 1 7 1 1 Table3   MaxtermexpansionforS= ∏M (0,3,5,6) MaxtermexpansionforCo = ∏M (0,1,2,4)   Steps2 and3: NumberofK-mapsrequired=2 EachK-mapshouldhave8cellsinit. Thusweget:   Figure6: K-mapsimplificationforfulladder(a)sumoutputand(b)carryoutput     SumOutput,S CarryOutput,Co Groupswith8cells Nil Nil Groupswith4cells Nil Nil Groupswith2cells (OrangeEnclosuresinFigure6) Nil 3 Group1(Cells0,1) Group2(Cells0,2) Group3(Cells0,4)   Groupswith1cell (GreenEnclosuresinFigure6) 4 Group1(Cell0) Group2(Cell3) Nil Group3(Cell5) Group4(Cell6) Table4Step4:   Groups SumOutput,S CarryOutput,Co Group1 A+B+ Ci A+B Group2 A+B̅+C̅i A+Ci Group3 A̅+B+C̅i B+Ci Group4 A̅+B̅+Ci     S=(A+B+ Ci)(A+ B̅+C̅i)(A̅+B+C̅i)(A̅+B̅+Ci) Co =(A+B)(A+Ci)(B+Ci) Table5   Step5: Thedigitalsystemdesignedtorealizethefulladderintermsofsumandcarryoutputs(inPOSform)isshownbyFigure7:   Figure7: FulladdercircuitExample3:  SimplifytheBooleanexpressionf(A,B,C,D,E)=∑m (0,3,4,7,8,12,14,16,19,20,23,24,26,28)   Step1:  Numberofinputvariables=5 Numberofoutputvariables=1 Mintermexpansionoftheoutputisgivenas f (A,B,C,D,E)= ∑m (0,3,4,7,8,12,14,16,19,20,23,24,26,28)   Steps2,3,and4: NumberofK-mapsrequired=1 EachK-mapshouldhave32 cellsinit. Thusweget:   Figure8: Grouped32-cellK-map   NumberofGroupswith32cells Nil NumberofGroupswith16cells Nil NumberofGroupswith8cells(OrangeEnclosuresinFigure8) 1 Group1(Cells0,4,8,12,16,20,24,28) D̅E̅ NumberofGroupswith4cells(BlueEnclosuresinFigure8) 1 Group2(Cells3,7,19,23) B̅DE NumberofGroupswith2cells  Nil NumberofGroupswith1cell(GreenEnclosuresinFigure8) 2 Group3(Cell14) A̅BCDE̅ Group4(Cell26) ABC̅DE̅ Thus, f (A,B,C,D,E)= D̅E̅+ B̅DE+ A̅BCDE̅+ ABC̅DE̅ Table6   Step5: Thedigitalsystemcorrespondingtothefunctiongivenisobtainedasshownin Figure9:   Figure9: 5-variableK-mapforthefunctionshowninExample3AdvantagesofK-Maps TheK-mapsimplificationtechniqueissimplerandlesserror-pronecomparedtothemethodofsolvingthelogicalexpressionsusingBooleanlaws. ItpreventstheneedtoremembereachandeveryBooleanalgebraictheorem. Itinvolvesfewerstepsthanthealgebraicminimizationtechniquetoarriveatasimplifiedexpression. K-mapsimplificationtechniquealwaysresultsinminimumexpressionifcarriedoutproperly.   DisadvantagesofK-Maps Asthenumberofvariablesinthelogicalexpressionincreases,theK-mapsimplificationprocessbecomescomplicated. TheminimumlogicalexpressionarrivedatbyusingtheK-mapsimplificationproceduremayormaynotbeuniquedependingonthechoicesmadewhileformingthegroups.Forexample,fortheoutputvariableYshownbytheK-mapin Figure10,wecanobtaintwodifferent,butaccurate logicalexpressions.Thevariationinthesolutionobtainedisobservedinthe thirdterm,whichmaybeeither B̅C̅or AC̅(highlightedinFigure10).Thisdifference depends onwhetheronechoosestogroupthecells(0,4)or(4,6)toformatwo-celledgroupinordertocovertheone foundintheK-mapcellnumbered4.   Figure10: K-mapwithanon-uniquesolutionConclusion Havinganalyzedthestructure ofK-maps,wemayarriveattheconclusionthattheK-mapsimplificationprocessisaneffectivereductiontechniquewhendealing withlogicalexpressionswhichcontainaroundthreetosixinputvariables. RelatedContent HalfBridgeandGateDriveMeasurementsandTechniques 10-FoldBatteryLifeImprovementTechniquesforEmergingAssetTracking/IoTApplications BooleanIdentities SimplifyingPowerICDesigns:3CompaniesTacklePowerConversionSystems LearnAdvancedPowerManagementandSensorDesignTechniquesforEmergingPortableMedicalApplications LearnMoreAbout: booleanalgebra karnaughmaps k-mapsimplification k-maprules k-mapadvantages k-mapdisadvantages Comments 2Comments Logintocomment RajeshN July09,2016 Veryinterestingdetaileddiscussion. Like. Reply ci139 July11,2016 Analternativefortheinputs.noOf()bitmemory-inprogramming-suchmayturnoutmoreoptimalsolutionthancomplexnestedcomparisonstatementsas:address=sourcebits,data=no.ofbitsrequiredforoutput—(whichhowevermakesthecodedifficulttobegraspedatdebuggingstage)—iintendedtousesuchforsystemstate/statusbitsderived/triggeredevt.-sanddidusesuchinoutputformatfilter...longago Like. Reply Loadmorecomments YouMayAlsoLike Beamforming:FundamentalstoImplementation byAvnet IBMResearcherRevealsDetailsonQuantumEntanglementForging byIngridFadelli ResearchersCollabWithIntel,Googleon“EnergyProcessingUnit” byArjunNijhawan Roundup:NewEvalBoardsRevIoTTimetoMarket byNicholasSt.John TeamUpBlastsLoRaWANIntoSpaceforSatelliteIoTConnectivity byJakeHertz WelcomeBack Don'thaveanAACaccount?Createonenow. Forgotyourpassword?Clickhere. SignIn Stayloggedin Orsigninwith Facebook Google Linkedin GitHub Continuetosite QUOTEOF THEDAY “ ” -