The K-Map, Boolean Algebraic Simplification Technique

The Karnaugh Map Boolean Algebraic Simplification Technique

The Karnaugh map (K-map) is introduced by Maurice Karnaugh in 1953.The simplification of the Karnaugh map (K-map) Boolean algebraic technique with some examples. It also includes a brief note on the advantages and the limitations of K-maps.

Introduction

Digital electronics deals with the discrete-valued digital signals. In general, any electronic system based on the digital logic uses binary numbers (0's and 1's) to represent the states of the variables involved in it. Thus, Boolean algebraic simplification is an integral part of the design and analysis of a digital electronic system.Although Boolean algebraic laws and DeMorgan's theorems can be used to achieve the objective, here the process becomes complicated when the number of variables involved increases. So, Karnaugh map (K-map) is introduced .

           A Typical K-MapThe K-map method of solving the logical expressions is referred to as the graphical technique of simplifying Boolean expressions. K-maps are also referred to as 2D truth tables as each K-map is nothing but a different format of representing the values present in a one-dimensional truth table.K-maps basically deal with the technique of inserting the values of the output variable in cells within a rectangle or square grid according to a definite pattern. 

        The number of cells in the K-map is determined by the number of input variables and is mathematically expressed as two raised to the power of the number of input variables, i.e., 2n, where the number of input variables is n.Thus, to simplify a logical expression with two inputs, we require a K-map with 4 (=22) cells. A four-input logical expression would lead to a 16 (=24) celled-K-map, and so on. 

          Further, each cell within a K-map has a definite place-value which is obtained by using an encoding technique known as Gray code.The specialty of this code is the fact that the adjacent code values differ only by a single bit. That is, if the given code-word is 01, then the previous and the next code-words can be 11 or 00, in any order, but cannot be 10 in any case.In K-maps, the rows and the columns of the table use Gray code-labeling which in turn represent the values of the corresponding input variables. This means that each K-map cell can be addressed using a unique Gray Code-Word.These concepts are further emphasized by a typical 16-celled K-map shown in Figure 1, which can be used to simplify a logical expression comprising of 4-variables (A, B, C and D mentioned at its top-left corner). 

Figure 1: A typical but empty Karnaugh map with 16 cells 

Here the rows and the columns of the K-map are labeled using 2-bit Gray code, shown in the figure, which assigns a definite address for each of its cells.For example, the grey colored cell of the K-map shown can be addressed using the code-word "0101" which is equivalent to 5 in decimal (shown as the green number in the figure) and corresponds to the input variable combination A̅BC̅D or A+B̅+C+D̅, depending on whether the input–output relationship is expressed in SOP (sum of products) form or POS (product of sums) form, respectively.Similarly, AB̅CD or A̅+B+C̅+D̅ refers to the Gray code-word of "1011", equivalent to 11 in decimal.

It is always desirable to simplify a given Boolean function (as either a Boolean expression or a Truth Table) so that the hardware for realizing the function will be minimized in terms of the number of logic gates and the number of inputs to these gates necessary for representing the function.

Deduction method could be used to apply various axioms and theorems to the given expression so that a simpler form can be derived.

Example :

AB+AB' = A(B+B') = A.1 =A

ABC + ABC'= AB(C+C') = AB.1 = AB

A function can be more systematically simplified by Karnaugh Map.Two variables

Consider Example A above: 

This is the logic behind the combination of neighboring squares in the Karnaugh map:
f(A,B) = A'B + AB' +AB = A + B

Three variables

Example B above has 3 variables: 
f(A,B,C) = A'BC' + A'BC + A'B'C + ABC

and the corresponding truth table is 

Either of the two Karnaugh maps can be used:

The function can be represented by the OR of the three resulting terms: 
f = A'B + A'C + BC

On the other hand, given an Boolean expression, you should be able to obtain the truth table if needed. For each term in the given expression, represent each variable by 0 if it is negated, or 1 otherwise. If a variable is missing in a term (don't care), two terms corresponding to both 0 and 1 of the missing variable are represented. For example, as  is missing in  above, it represents two minterms 010 and 011 in the truth table which should be marked by 1. All minterms not represented by any of the terms in the expression remain to be 0. The repeated terms need to be combined.

 Conclusion Having analyzed the structure of K-maps, we may arrive at the conclusion that the K-map simplification process is an effective reduction technique when dealing with logical expressions which contain around three to six input variables.