Simplifying Boolean Expression using K Map

Minterm Solution of K Map

The following are the steps to obtain simplified minterm solution using K-map. Step 1: Initiate Express the given expression in its canonical form Step 2: Populate the K-map Enter the value of 'one' for each product-term into the K-map cell, while filling others with zeros. Step 3: Form Groups
  1. Consider the consecutive 'ones' in the K-map cells and group them (green boxes).
  2. Each group should contain the largest number of 'ones' and no blank cell.
  3. The number of 'ones' in a group must be a power of 2 i.e. a group can contain
  4. Grouping has to be carried-on in decreasing order meaning, one has to try to group for 8 (octet) first, then for 4 (quad), followed by 2 and lastly for 1 (isolated 'ones').
  5. Grouping is to done either horizontally or vertically or interms of squares or rectangles. Diagonal grouping of 'ones' is not permitted.
  6. The same element(s) may repeat in multiple groups only if this increases the size of the group.
  7. The elements around the edges of the table are considered to be adjacent and can be grouped together.
  8. Don’t care conditions are to be considered only if they aid in increasing the group-size (else neglected).
Step 4: Obtain Boolean Expression for Each Group
Express each group interms of input variables by looking at the common variables seen in cell-labelling. For example in the figure shown below there are two groups with two and one number of 'ones' in them (Group 1 and Group 2, respectively). All the 'ones' in the Group 1 of the K-map are present in the row for which A = 0. Thus they contain the variable A̅. Further these two 'ones' are present in adjacent columns which have only B term in common as indicated by the pink arrow in the figure.

Hence the next term is B. This yields the product term corresponding to this group as A̅B. Similarly the 'one' in the Group 2 of the K-map is present in the row for which A = 1. Further the variables corresponding to its column are B̅C̅. Thus one gets the overall product-term for this group as AB̅C̅. Step 5: Obtain Boolean Expression for the Output The product-terms obtained for individual groups are to be combined to form sum-of-product (SOP) form which yields the overall simplified Boolean expression. This means that for the K-map shown in Step 4, the overall simplified output expression is A few more examples elaborating K-map simplification process are shown below.

Maxterm Solution of K Map

The method to be followed in order to obtain simplified maxterm solution using K-map is similar to that for minterm solution except minor changes listed below.
  1. K-map cells are to be populated by 'zeros' for each sum-term of the expression instead of 'ones'.
  2. Grouping is to be carried-on for 'zeros' and not for 'ones'.
  3. Boolean expressions for each group are to be expressed as sum-terms and not as product-terms.
  4. Sum-terms of all individual groups are to be combined to obtain the overall simplified Boolean expression in product-of-sums (POS) form.

Closely Related Articles Digital ElectronicsBoolean Algebra Theorems and Laws of Boolean AlgebraDe Morgan Theorem and Demorgans LawsTruth Tables for Digital LogicBinary Arithmetic Binary AdditionBinary SubtractionBinary DivisionExcess 3 Code Addition and SubtractionK Map or Karnaugh MapSwitching Algebra or Boolean AlgebraBinary MultiplicationParallel SubtractorMore Related Articles Binary Adder Half and Full AdderBinary SubstractorSeven Segment DisplayBinary to Gray Code Converter and Grey to Binary Code ConverterBinary to BCD Code ConverterAnalog to Digital ConverterDigital Encoder or Binary EncoderBinary DecoderBasic Digital CounterDigital ComparatorBCD to Seven Segment DecoderParallel AdderParallel Adder or SubtractorMultiplexerDemultiplexer555 Timer and 555 Timer WorkingOR Operation | Logical OR OperationAND Operation | Logical AND OperationLogical OR GateLogical AND GateNOT GateUniversal Gate | NAND and NOR Gate as Universal GateNAND GateDiode and Transistor NAND Gate or DTL NAND Gate and NAND Gate ICsX OR Gate and X NOR GateTransistor Transistor Logic or TTLNOR GateFan out of Logic GatesINHIBIT GateNMOS Logic and PMOS LogicSchmitt GatesLogic Families Significance and Types of Logic FamiliesBinary Number System | Binary to Decimal and Decimal to Binary ConversionBinary to Decimal and Decimal to Binary ConversionBCD or Binary Coded Decimal | BCD Conversion Addition SubtractionBinary to Octal and Octal to Binary ConversionOctal to Decimal and Decimal to Octal ConversionBinary to Hexadecimal and Hex to Binary ConversionHexadecimal to Decimal and Decimal to Hexadecimal ConversionGray Code | Binary to Gray Code and that to Binary ConversionOctal Number SystemDigital Logic Gates2′s Complement1′s ComplementASCII CodeHamming Code2s Complement ArithmeticError Detection and Correction Codes9s complement and 10s complement | SubtractionSome Common Applications of Logic GatesKeyboard EncoderAlphanumeric codes | ASCII code | EBCDIC code | UNICODELatches and Flip FlopsS R Flip Flop S R LatchActive Low S R Latch and Flip FlopGated S R Latches or Clocked S R Flip FlopsD Flip Flop or D LatchJ K Flip FlopMaster Slave Flip FlopRead Only Memory | ROMProgrammable Logic DevicesProgrammable Array LogicApplication of Flip FlopsShift RegistersBuffer Register and Controlled Buffer RegisterData Transfer in Shift RegistersSerial In Serial Out (SISO) Shift RegisterSerial in Parallel Out (SIPO) Shift RegisterParallel in Serial Out (PISO) Shift RegisterParallel in Parallel Out (PIPO) Shift RegisterUniversal Shift RegistersBidirectional Shift RegisterDynamic Shift RegisterApplications of Shift RegistersUninterruptible Power Supply | UPSConversion of Flip FlopsNew Articles Electrical and Electronics Engineering BooksWater MeterAir MeterDigital PotentiometersBasic Construction of Wind Turbine