Karnaugh map (K — map)

Boolean Expression:

Boolean expressions can be simplified by using two methods. One is known as the Karnaugh map (K—map) method, and the other is known as the Quine—McCluskey (Q—M) tabular method.

Karnaugh map (K—map):

· K-map is a very important method used for the simplification of Boolean expressions. It follows a systematic approach that utilizes a graphical method to obtain the simplified Boolean expression.

· Proper use of this method simplified the Boolean expression to minimal such that the expression can not be minimized further. It contains four or less number of variables (or literals) with their complements.

· As much as the Boolean expression gets reduced. It helps in getting a simple, less expensive and smaller circuit.

· Modified Veitched diagram is also known as K-Map. K-Map is based on Gray code. Implementation of Gray Code from Binary code to Gray Code.

Implementation of Gray code:

· When there are two variables, then Gray code-

· In this table, the conversion of Binary to gray code is implemented in the following way. The most significant bit (MSB) is the same in Gray code, and the next bit from the left side is changed based on the XOR condition. It means for the same operation like 1,1 or 0,0 it gives the output as 0, and for 0,1 or 1,0 it give output as 1.

So, in Gray code, the first bit is the same as in binary, and the next bit is changed as per the XOR condition. That is why Gray code follows this pattern. (00, 01, 10, 11).

· When there are 3 variables, then the Gray code-

· In this table, the conversion of Binary to gray code is implemented in the following way. The most significant bit (MSB) is the same in gray code and the next two bits from left side are changing based on the XOR condition. It means for the same operation like 1,1 or 0,0 it gives the output as 0 and for 0,1 or 1,0 it gives the output as 1.

· So, in Gray code the first bit is the same as in binary and the next two bits are changing as per XOR condition. That is why, Gray code follows this pattern. (000, 001, 011, 010, 110, 111, 101, 100).

Important Points:

· Gray code is also known as Unity Hamming distance code.

· It is also known as Cyclic code.

· It is also known as Reflecting code. As the first bit if hidden is same in binary and the next bit changed like the characters changed in a mirror.

Here, it reflected like a mirror.

Two Variable K — map:

· For two variable K — map two lines are drawn; A and B two variables are taken one at horizontal and the other at vertical.

· The complement of variable is followed by ltself in horizontal line and vertical line. The variable for 0 takes (Bar sign) with it as shown in fig.

· work as 0 and 1 if variable are taken instead of 0 and 1. So, f(A,B)-

Here, K — map show four squares represented by four minterms m0, m1, m2, and m3 where m0 is 00, m1 is 01, m2 is 10, and m3 is 11.

Three Variable K — map:

· Three Variable combination gives 2³=8 combination of values in K-Map from (0,1,2,3,4,5,6,7).

· For three variables two adjacent variables are taken on either side (horizontal line) of the K — map and the remaining one variable on (vertical line) on the other side.

· Let A, B and C are the three variables, the two variables (BC) will have four combinations on horizontal side. Single variable A is taken on vertical side and have 2 combination.

· on the other side as shown in figure. So, f(A,B,C) is-

Four Variable K — map:

· Four Variable combination gives 2⁴=16 combination of values in K-Map from (0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15).

· For four variables two adjacent variables are taken on either side (horizontal line) of the K — map and the remaining one variable on (vertical line) on the other side.

· Let A, B, C and D are the four variables, the two variables (CD) will have four combinations on horizontal side, the two variable AB is taken on vertical side and have 4 combination. So, f(A,B,C,D) is-

· If a Boolean function of three variables or four variables is given, the 1s entry in the K—map is done for those combinations which are present in the given expression and for the other combinations 0s entry are made.