K-Map or Karnaugh Map is a graphical representation of input conditions similar to truth table. It is an array of cells which helps in logical simplification or minimization of Boolean expression. This post will discuss about Karnaugh Map (K-Map), simplification of Boolean expression, Minterm, Maxterm, its applications, advantages and disadvantages.

What is K-Map (Karnaugh Map)

Karnaugh Map is a two-dimensional graphical representation of the input and output conditions which can minimize the Boolean expression involving 2, 3, 4 and 5 variables. In other words, it is used to remove redundant operations in a Boolean function. It is named after Maurice Karnaugh, an American mathematician and physicist, who developed K- Map at Harvard Computation Laboratory.

Maurice Karnaugh

Fig. 1 – Maurice Karnaugh, Founder of Karnaugh Map

Fig. 2 below shows an example of Karnaugh Map with two variables and each square is called a ‘cell’. Four cells are numbered (0, 1, 2, 3). K-Map having n-variable has 2n cells where in each cell corresponds to the truth table value. The cells are designated with a value that corresponds to truth-table row. The cells are arranged such that the adjacent cells differ by only one bit position.

K-Map

Fig. 2 – Example of Karnaugh Map (K-Map)

What is Minterm and Maxterm

Let us understand the meaning of Minterm and Maxterm in this section as it helps in the simplification of Boolean expression using K- Map.

Minterm

Minterm of ‘n’ variables is a product of ‘n’ variables which appear exactly once in True or Complemented form.

Example: Minterms of 3 variables(X,Y,Z) = Each Minterm = 1 for only one combination of values of the variables it represents otherwise 0. Identifying the Minterms from the K-map is equivalent to reading equations in Sum-of-Minterms or Sum-of-Products (SOP) form, directly from the truth table.

 

Minterms for Three Variables (1)

Fig. 3 – Minterms for Three Variables

Maxterm

Maxterm of ‘n’ variables is a sum of ‘n’ variables which appear exactly once in True or Complemented form.

Example: Maxterm of 3 variables (X,Y,Z)= Each Maxterm = 0 for only one combination of values of the variables it represents otherwise the value is 1. Hence Boolean function could be expressed algebraically from a given truth table by identifying the logical product of all the Maxterms that produce 0 in the function. This expression is called as Product of Maxterms or Product-of-Sums (POS)

Maxterms for Three Variables (1)

Fig. 4 – Maxterms for Three Variables

Simplification of Boolean Expression Using K-Map (Karnaugh Map)

Simplification of Boolean expression using K- Map requires grouping of 1’s. Grouping of 1’s should follow certain rules:

  • Groups should have 2, 4, 8 one’s (1’s).
  • Identification of Minterms or Maxterms is necessary.
  • Grouping is done horizontally, vertically but never diagonally.
  • Multiple groups using repeated 1’s can be done.

This can be better explained with an example using 3 variables as shown below:

image

image

Two groups are formed: Group 1 is marked in Blue Color and the other group in Red Color. The groups are listed below.

clip_image001

The variables that are remaining are OR’ed (Logical Addition) to obtain the reduced Boolean expression.

image

Applications of Karnaugh Map (K-Map) 

The applications include:

  • They are used in design and implementation of Digital Circuits
  • K- Maps are used in the simplification of Half- Adder and Full- Adder circuits

Advantages of K-Map 

The advantages include:

  • The most economical and simplified circuit can be built using K-Maps.
  • Using K-Maps, logical operation is fast.
  • Deriving at the simplest expression helps in reduction of instructions in software applications.
  • It is more efficient than any other simplification techniques of Boolean algebra.

Disadvantages of K-Map

K-Maps depend on the variables in an expression and hence the simplification process becomes complex with the increase in variables

Also Read:
Logic Gates - Types, Working Principle, Application, Advantage
pH Measurement – Working Principle, Applications and Advantages
Hamming Codes – How it Works, Application, Advantages & Disadvantages