K-Map (Karnaugh Map)

In this tutorial, you will learn the fundamentals of Karnaugh maps (K-maps), including their definition and looping techniques. You will explore how to write K-maps for different variables, understand minimization rules for both Sum of Products (SOP) and Product of Sums (POS) forms, and discuss the advantages and disadvantages of K-maps. Additionally, you will examine variable-entered maps and the types of implicants related to K-map simplification.

Contents:

  1. What is the Karnaugh map?
  2. Looping in K-maps
  3. Advantages of Looping in K-map
  4. Steps to Write the K-map
  5. Making Groups in K-maps
  6. 2-Variable K-Map
  7. 3-Variable K-Map
  8. 4-Variable K-Map
  9. Need for Minimization
  10. Minimization Rules for K-map in SOP Form
  11. Minimization Rules for K-map in POS Form
  12. Advantages and Disadvantages of K-maps
  13. Variable-Entered Map
  14. Implicants and its Types

What is the Karnaugh Map?

The Karnaugh map (K-map) is a visual method for simplifying Boolean functions. It arranges the truth table of a Boolean function in a grid where the cells are organized according to Gray code, meaning only one bit changes between adjacent cells.

Maurice Karnaugh, an American physicist, invented the K-map in 1953. It helps minimize Boolean expressions by grouping adjacent cells with similar values, allowing simplification through patterns of 1s and 0s.

In a K-map:

  • Minterms (1s) represent where the function is true and Maxterms (0s) represent where the function is false.
  • “Don’t care” conditions (x) can be treated as either 1 or 0 to aid in simplification.

advertisement
advertisement

Looping in K-maps

  • Looping is the process of combining cells in a K-map to get the simplified terms for the output expression.
  • For an SOP expression looping is done by combining cells that contain 1s. For a POS expression looping is done by combining cells that contain 0s.
  • For looping, groups are made up of 2, 4, 8, 16 and so on. Groups are also made by folding K-map over its edges. Groups with the highest number of cells of 1s (for SOP) or 0s (for POS) are prioritized first.

Advantages of Looping in K-map

The following diagram explains a 2-variable K-map.

2-variable K-map
  • The advantage of looping is that it can eliminate the variables those appear in both their true and complemented forms inside the loop.
  • Looping a pair of 1s eliminates one variable. Looping a quad of 1s eliminates two variables and looping an octet of 1s eliminates three variables.
  • In this K-map, looping has been done with a pair of adjacent 1s. Here B is the variable that is present in both complemented and uncomplemented forms.
  • So, after removing B, only one variable is left in its complement form i.e. A’
    So, F(A, B) = A’.

Steps to Write the K-map

Here are the steps to write the K-map for n variable function.

  • For any n-variable, draw a grid of 2n cells. For example, draw a 2×2 cell for 2 variables, 4×2 cell for 3-variables, 4×4 cells for 4 variables.
  • Write the input-variable combinations vertically and horizontally for the grid in a unit-distance changing manner. For example, AB is written as 00, 01, 11, 10 as the input sequence.
  • Fill in 1’s and 0’s according to the given function as maxterms or minterms.
  • If minterms are considered, make groups of 2, 4, and 8 adjacent 1s giving more priority to higher groups. The groups should be made in such a manner that all the minterms are covered at least once.
  • If maxterms are considered, make groups of 2, 4, and 8 adjacent 0s giving more priority to higher groups. The groups should be made in such a manner that all the maxterms are covered at least once. Any redundancy in a grouping should be avoided.
  • Write the Boolean expression for each of the formed groups. Include only those variables in the term which are not changing in the entire group horizontally or vertically.
  • If the expression is to be written in SOP, take the non-changing variable in normal form if it is equal to 1 else complemented if it is equal to 0.
  • Diagonally cells cannot be grouped. They need to be adjacent to each other to be grouped. If a don’t care condition is present, it can be included in grouping if it helps in forming a group with an unpaired minterm.

Making Groups in K-maps

The procedure for making groups in K-map is shown below: –

  • For a 2-variable function, the minterms can be m0, m1, m2, and m3. They can be grouped as m0m1, m0m2, m1m3, m2m3 or they can be grouped as a quad. The groups are shown in the figure below.
    Grouping in 2-variables
  • For a 3-variable function, the minterms can be m0, m1, m2, m3, m4, m5, m6, m7. They can be grouped as an octet, quads, or pairs. Here are some of these groups shown in the figure.
    Grouping in 3-variables

    As shown in the figure, m3 comes after m2 and m7 comes after m5 as we are following the gray-code format.

  • For a 4-variable function, the minterms can be m0, m1, m2,m3, m4, m5, m6, m7, m8, m9, m10, m11, m12, m13, m14, m15. They can be grouped as hextet, octets, quads, or pairs. Here are some of the groups shown in the figure.
Grouping in 4-variables

From the figure,

  • Notice that the cells have been arranged in gray-code format, and thus the minterms need to be filled in that order only.
  • The higher order of groups is to be given more priority.
  • The corner elements may also be grouped as the first row and the last row are adjacent in a rotational manner. Similarly, first column and last column elements may also be grouped.

2-Variable K-Map

For 2 variables A and B, we make a 2×2 cell with A on the vertical column and B on the horizontal column. Here is an example of 2-variable K-map for the function, f(A,B) = Σm(1,2,3).

advertisement
2-Variable K-Map

From the figure,

  • Expression for the horizontal pair: – A is not changing in the box but B is changing from 0 to 1. Therefore, we get A as A=1.
  • Expression for the vertical pair: – B is not changing but A changes from 0 to 1 so we get B as B=1.
  • Thus, the minimized overall expression for the K-map in SOP form is A + B.

3-Variable K-Map

For 3 variables A, B, C we make an 8×2 cell with A on the vertical column and BC on the horizontal column. Here is an example of 3-variable K-map for the function, f(A,B,C) = Σm(1,3,4,5,6,7). Note that BC is written as: – 00 01 11 10 in gray-code format.

3-variable K-map

From the figure,

  • In the octet, both A and B are changing from 0 to 1, Only C is unchanged, so we get C as C=1 from the octet.
  • In the pair, A and B remain constant, so we get AB’ as A is 1 and B is 0.
  • So, we get the minimized expression in the SOP Form as AB’ + C.

advertisement

4-Variable K-Map

For 4 variables A, B, C we make a 4×4 cell with AB on the vertical column and CD on the horizontal column. Here is an example of 4-variable K-map for the function, f(A, B, C, D) = Σm(1, 3, 4, 6, 7, 8, 10, 11, 14, 15).

4-variable K-map

From the figure,

  • There are two quads and three pairs. The expression for m1, m3 pair is A’B’D, for pair m4, m6 is A’BD’, for pair m8, m10 is AB’D’.
  • For the quad having m7, m8, m14, m15 is BC and for the quad having m14, m15, m10, m11 is AC.
  • Thus, the overall minimized expression is A’B’D + A’BD’ + AB’D’ + AC + BC in the SOP form.

Need for Minimization

Any function needs to be reduced into the lowest possible number of terms so that we can implement the function using less hardware. Using laws of Boolean algebra, any function can be reduced into its minimal form but this process is time taking.

Thus, a quicker way to develop the minimal expression for a function is by using,

  • The K-map reduction technique
  • The Quine-McCluskey minimization technique

The k-map technique is used when 2-5 variables are involved, above that, we use the quine-McCluskey technique of minimization.

Minimization Rules for K-map in SOP Form

The rules of minimization in a K-map for an SOP form are explained below:

  • Construct a suitable K-map and place 1s in the cells corresponding to the 1s in the truth table. Fill the rest of the cells with 0s.
  • Make groups of 2n number of cells where n = 0, 1, 2, 3……. and cells in each group should not contain any cell with 0.
  • Groups should be made as large as possible even if they overlap but use the minimum number of loops to group all the cells with 1s.
  • Groups can be made vertically and horizontally but not diagonally. Each group represents a term in the simplified Boolean expression. Larger the group, the smaller the term.
  • These terms can be obtained by combining the coordinates of the binary variables of the cells after applying the looping property. These terms are the product terms.
  • Now, take the OR sum of all the product terms obtained. This will be the simplified SOP Boolean expression.

Minimization Rules for K-map in POS Form

The rules of minimization in a K-map for a POS form are explained below:

  • Construct a suitable K-map for maxterms and place 0s in those cells corresponding to the 0s in the truth table. Fill the rest of the cells with 1s.
  • Make groups for looping of the cells, same as the SOP form but only with 0s. Grouping of 0s will provide us the sum terms.
  • Now, multiply all the sum terms that are obtained from the looping. This will be the simplified POS Boolean expression.

Advantages and Disadvantages of K-maps

The advantages and disadvantages of K-maps are explained below:

Advantages:

  • A K-map provides the simplest and shortest formula to express the logic of a truth table. Thus, minimizing the implementation cost.
  • It takes very little time to provide the simplified logical expression of a truth table or an SOP or POS expression upto 5 variables without using Boolean theorems and laws.

Disadvantages:

  • It is not suitable when the number of variables used in the K-map exceeds 5 because the K-map method uses maps which is difficult to design when the number of input variables increases.

Variable-Entered Map

A variable-entered map (VEM) is a type of Karnaugh map where some cells are filled with variables instead of just 0s and 1s. This approach reduces the number of variable combinations needed to create the K-map, effectively decreasing its size. By using variables in certain cells, a VEM simplifies the representation of more complex functions, making it easier to analyze and minimize Boolean expressions.

The following diagram explains a variable-entered map involving three variables.

A Variable-Entered Map
    The following steps should be followed to solve the variable-entered map:

  • Step1: Convert it into its truth table form.
    B C F
    0 0 1
    0 1 0
    1 0 A’
    1 1 A’
  • Step-2: Develop the truth table including all the variables and obtain the output in terms of 0s and 1s.
    A B C F
    0 0 0 1
    0 0 1 0
    0 1 0 1
    0 1 1 1
    1 0 0 1
    1 0 1 0
    1 1 0 0
    1 1 1 0
  • Step-3: Draw its corresponding K-map involving all the variables and solve the K-map.
    3-variable K-map
  • Step-4: Obtain the Boolean expression from the K-map and this will be the simplified expression of the variable-entered map.
  • So, the simplified SOP expression of the variable-entered map is F = A’B + B’C’.

Implicants and its Types

In any n-variable function, a minterm or a maxterm is known as an implicant. Such a function can have a maximum of 2n-1 implicants. We have two types of implicants known as prime implicants and essential prime implicants.

  • Prime Implicants: All the possible pairs which can be formed from the K-map are known as prime implicants.
  • Essential Prime Implicant: Those pairs of prime implicants are known as essential prime implicants that contain at least one such element which cannot be covered by any other prime implicant.

Key Points to Remember

Here are the key points to remember in “K-Map Method”.

  • The Karnaugh map (K-map) is a visual tool for simplifying Boolean functions, organizing truth table values in a grid based on Gray code.
  • Looping in K-maps involves combining adjacent cells (for SOP) with 1s or (for POS) with 0s to simplify the output expression. Groups of sizes like 2, 4, 8, or 16 are used, with priority given to larger groups.
  • K-maps are essential for minimizing Boolean expressions efficiently, allowing for reduced hardware requirements.
  • Groups in K-maps can overlap, but cells must be adjacent (not diagonal). Grouping “don’t care” conditions can aid in simplification.
  • K-maps can be constructed for 2, 3, and 4 variables, with specific configurations for each (e.g., 2-variable K-map is 2×2, 3-variable is 4×2).
  • K-maps can simplify expressions in both Sum of Products (SOP) and Product of Sums (POS) forms, each having distinct grouping rules.
  • Variable-entered maps (VEM) use variables in some cells, reducing the size of the K-map and simplifying the representation of complex functions.
  • Minterms or maxterms in a K-map are known as implicants, with prime implicants being all possible groupings and essential prime implicants being those that cannot be covered by others.
  • K-maps become complex and less practical when dealing with more than 5 variables, where alternative methods like the Quine-McCluskey technique are preferred.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.