K-Map (Karnaugh Map) Method

In this tutorial, you will learn about the K-map method used in Boolean algebra. You will learn how to write K-maps for two, three, four variable functions.

Contents:

  1. The need for minimization
  2. What is the Karnaugh Map?
  3. Steps to write the K-Map
  4. Making Groups in K-Map
  5. 2-Variable K-Map
  6. 3-Variable K-Map
  7. 4-Variable K-Map
  8. Implicants and its Types

The 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.

advertisement
advertisement

What is the Karnaugh map?

Karnaugh map or k-map is the grid format representation of the truth table of a function, where the cells are arranged according to gray code and there is a unit distance relation between any two adjacent cells. This means between any two adjacent cells, only one-bit changes.

The cells of a K-map are filled with 0, 1 and don’t cares (x) according to the function. The function can be minimized either by using the minterms (1) or the maxterms (0).

  • If the function is written with the help of minterms, we fill 1 for the mentioned minterm cells and 0 in the rest cells.
  • If the function is written with the help of maxterms, we fill 0 for the mentioned maxterm cells and 1 for the rest cells.
  • If a don’t care condition is mentioned, it can be taken either as 1 or 0 or left if not needed.

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.
advertisement

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).

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
advertisement

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.

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.

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”.

  • K-map is a minimization technique used in Boolean Algebra to find out the minimized values of expressions in a quicker manner.
  • K-map follows the gray-code format to arrange its cells of minterms and maxterms.
  • Only adjacent cells can be grouped in a k-map.
  • When we form groups of 2, 4, 8 they are known as pair, quad, and octet, respectively.
  • Don’t care values in a k-map can be used to form pairs, quads, or octets if required.
  • For any group, we write down its expression in terms of the variables which aren’t changing in the entire group both vertically and horizontally.
  • Prime implicants for a function are the maximum possible number of groups that can be formed from its K-map.
  • Essential prime implicants are those groups that contain at least one minterm which is not covered by any other prime implicant.

If you find any mistake above, kindly email to [email protected]

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.