What is the purpose of using karnaugh map?

In this article, we will take a look at the Introduction to K-Map (Karnaugh Map) according to the GATE Syllabus for CSE (Computer Science Engineering). Read ahead to learn more.

Table of Contents

In numerous digital circuits and other practical problems, finding expressions that have minimum variables becomes a prerequisite. In such cases, minimisation of Boolean expressions is possible that have 3, 4 variables. It can be done using the Karnaugh map without using any theorems of Boolean algebra. The K-map can easily take two forms, namely, Sum of Product or SOP and Product of Sum or POS, according to what we need in the problem. K-map is a representation that is table-like, but it gives more data than the TRUTH TABLE. Fill a grid of K-map with 1s and 0s, then solve it by creating various groups.

Here are the steps that are used to solve an expression using the K-map method:

1. Select a K-map according to the total number of variables.

2. Identify maxterms or minterms as given in the problem.

3. For SOP, put the 1’s in the blocks of the K-map with respect to the minterms (elsewhere 0’s).

4. For POS, putting 0’s in the blocks of the K-map with respect to the maxterms (elsewhere 1’s).

5. Making rectangular groups that contain the total terms in the power of two, such as 2,4,8 ..(except 1) and trying to cover as many numbers of elements as we can in a single group.

6. From the groups that have been created in step 5, find the product terms and then sum them up for the SOP form.

Z = ∑P, Q, R (1, 3, 6, 7)

From the red group, the product term would be —

P’R

From the green group, the product term would be —

PQ

If we sum these product terms, then we will get this final expression (P’R + PQ)

F (A, B, C, D) = ∑(0, 2, 5, 7, 8, 10, 13, 15)

From the red group, the product term would be —

BD

From the lilac group, the product term would be —

B’D’

If we sum these product terms, then we will get this final expression (BD + B’D’)

F (P, Q, R) = π(0,3,6,7)

From the lilac group, the terms would be

P Q

If we take the complement of these two

P’ Q’

And then sum up them

(P’ + Q’)

From the blue group, the terms would be

B R

When we take the complement of these terms

B’ R’

And then sum them up

(B’ + R’)

From the red group, the terms would be

P’ Q’ R’

If we take the complement of the two terms

P Q R

And then sum them up

(P + Q + R)

If we take the product of these three terms, then we will get this final expression –

(P’ + Q’) (P’ + R’) (P + Q + R)

F (P, Q, R, S) = π (3, 5, 7, 8, 10, 11, 12, 13)

From the blue group, the terms would be

R’ S Q

We take their complement and then sum them

(R + S’+ Q’)

From the purple group, the terms would be

R S P’

We take their complement and then sum them

(R’ + S’+ P) S

From the red group, the terms would be

P R’ S’

We take their complement and then sum them

(P’ + R + S)

From the lilac group, the terms would be

P Q’ R

We take their complement and then sum them

(P’ + Q + R’)

Finally, we will express these in the form of the product –

(R + S’+ Q’).(R’ + S’+A).(P’+ R + S).(P’+ Q + R’)

Pitfall – Always remember that POS ≠ (SOP)’

*Here, the correct form would be (POS of F) = (SOP of F’)’

1. There are a total of ______ cells in a K-map with 4-variable.

a) 8

b) 18

c) 16

d) 12

Answer – (c) 16

2. The don’t care condition could be used in order to simplify the Boolean expressions in the ___________.

a) Latches

b) K-maps

c) Terms

d) Registers

Answer – (b) K-maps

3. Logic gates can be widely used in the _______________ design and are therefore available in the IC form.

a) Digital

b) Sampling

c) Systems

d) Analog

Answer – (a) Digital

4. Entries are also called the _______________ mapping.

a) Boolean

b) K

c) Straight

d) Diagonal

Answer – (d) Diagonal

5. Every product term of the group, a’.b.c’ and a.c, represents the ____________ in that particular group:

a) Sum of Maxterms

b) Sum of Minterms

c) POS

d) Input

Answer – (b) Sum of Minterms

The Karnaugh map (KM or K-map) is a method of simplifying Boolean algebra expressions. Maurice Karnaugh introduced it in 1953 as a refinement of Edward W. Veitch's 1952 Veitch chart, which was a rediscovery of Allan Marquand's 1881 logical diagram aka Marquand diagram but with a focus now set on its utility for switching circuits. Veitch charts are also known as Marquand–Veitch diagrams or, rarely, as Svoboda charts, and Karnaugh maps as Karnaugh–Veitch maps (KV maps).

The Karnaugh map reduces the need for extensive calculations by taking advantage of humans' pattern-recognition capability. It also permits the rapid identification and elimination of potential race conditions.

The required Boolean results are transferred from a truth table onto a two-dimensional grid where, in Karnaugh maps, the cells are ordered in Gray code, and each cell position represents one combination of input conditions. Cells are also known as minterms, while each cell value represents the corresponding output value of the boolean function. Optimal groups of 1s or 0s are identified, which represent the terms of a canonical form of the logic in the original truth table. These terms can be used to write a minimal Boolean expression representing the required logic.

Karnaugh maps are used to simplify real-world logic requirements so that they can be implemented using a minimum number of logic gates. A sum-of-products expression (SOP) can always be implemented using AND gates feeding into an OR gate, and a product-of-sums expression (POS) leads to OR gates feeding an AND gate. The POS expression gives a complement of the function (if F is the function so its complement will be F'). Karnaugh maps can also be used to simplify logic expressions in software design. Boolean conditions, as used for example in conditional statements, can get very complicated, which makes the code difficult to read and to maintain. Once minimised, canonical sum-of-products and product-of-sums expressions can be implemented directly using AND and OR logic operators.

Karnaugh maps are used to facilitate the simplification of Boolean algebra functions. For example, consider the Boolean function described by the following truth table.

Following are two different notations describing the same function in unsimplified Boolean algebra, using the Boolean variables A, B, C, D and their inverses.

In the example above, the four input variables can be combined in 16 different ways, so the truth table has 16 rows, and the Karnaugh map has 16 positions. The Karnaugh map is therefore arranged in a 4 × 4 grid.

The row and column indices (shown across the top and down the left side of the Karnaugh map) are ordered in Gray code rather than binary numerical order. Gray code ensures that only one variable changes between each pair of adjacent cells. Each cell of the completed Karnaugh map contains a binary digit representing the function's output for that combination of inputs.

After the Karnaugh map has been constructed, it is used to find one of the simplest possible forms — a canonical form — for the information in the truth table. Adjacent 1s in the Karnaugh map represent opportunities to simplify the expression. The minterms ('minimal terms') for the final expression are found by encircling groups of 1s in the map. Minterm groups must be rectangular and must have an area that is a power of two (i.e., 1, 2, 4, 8...). Minterm rectangles should be as large as possible without containing any 0s. Groups may overlap in order to make each one larger. The optimal groupings in the example below are marked by the green, red and blue lines, and the red and green groups overlap. The red group is a 2 × 2 square, the green group is a 4 × 1 rectangle, and the overlap area is indicated in brown.

The cells are often denoted by a shorthand which describes the logical value of the inputs that the cell covers. For example, AD would mean a cell which covers the 2x2 area where A and D are true, i.e. the cells numbered 13, 9, 15, 11 in the diagram above. On the other hand, AD would mean the cells where A is true and D is false (that is, D is true).

The grid is toroidally connected, which means that rectangular groups can wrap across the edges (see picture). Cells on the extreme right are actually 'adjacent' to those on the far left, in the sense that the corresponding input values only differ by one bit; similarly, so are those at the very top and those at the bottom. Therefore, AD can be a valid term—it includes cells 12 and 8 at the top, and wraps to the bottom to include cells 10 and 14—as is BD, which includes the four corners.

Once the Karnaugh map has been constructed and the adjacent 1s linked by rectangular and square boxes, the algebraic minterms can be found by examining which variables stay the same within each box.

For the red grouping:

Thus the first minterm in the Boolean sum-of-products expression is AC.

For the green grouping, A and B maintain the same state, while C and D change. B is 0 and has to be negated before it can be included. The second term is therefore AB. Note that it is acceptable that the green grouping overlaps with the red one.

In the same way, the blue grouping gives the term BCD.

The solutions of each grouping are combined: the normal form of the circuit is A C ¯ + A B ¯ + B C D ¯ {\displaystyle A{\overline {C}}+A{\overline {B}}+BC{\overline {D}}} .

Thus the Karnaugh map has guided a simplification of

It would also have been possible to derive this simplification by carefully applying the axioms of Boolean algebra, but the time it takes to do that grows exponentially with the number of terms.

The inverse of a function is solved in the same way by grouping the 0s instead.

The three terms to cover the inverse are all shown with grey boxes with different colored borders:

This yields the inverse:

Through the use of De Morgan's laws, the product of sums can be determined:

Karnaugh maps also allow easier minimizations of functions whose truth tables include "don't care" conditions. A "don't care" condition is a combination of inputs for which the designer doesn't care what the output is. Therefore, "don't care" conditions can either be included in or excluded from any rectangular group, whichever makes it larger. They are usually indicated on the map with a dash or X.

The example on the right is the same as the example above but with the value of f(1,1,1,1) replaced by a "don't care". This allows the red term to expand all the way down and, thus, removes the green term completely.

This yields the new minimum equation:

Note that the first term is just A, not AC. In this case, the don't care has dropped a term (the green rectangle); simplified another (the red one); and removed the race hazard (removing the yellow term as shown in the following section on race hazards).

The inverse case is simplified as follows:

Through the use of De Morgan's laws, the product of sums can be determined:

Karnaugh maps are useful for detecting and eliminating race conditions. Race hazards are very easy to spot using a Karnaugh map, because a race condition may exist when moving between any pair of adjacent, but disjoint, regions circumscribed on the map. However, because of the nature of Gray coding, adjacent has a special definition explained above – we're in fact moving on a torus, rather than a rectangle, wrapping around the top, bottom, and the sides.

Whether glitches will actually occur depends on the physical nature of the implementation, and whether we need to worry about it depends on the application. In clocked logic, it is enough that the logic settles on the desired value in time to meet the timing deadline. In our example, we are not considering clocked logic.

In our case, an additional term of A D ¯ {\displaystyle A{\overline {D}}} would eliminate the potential race hazard, bridging between the green and blue output states or blue and red output states: this is shown as the yellow region (which wraps around from the bottom to the top of the right half) in the adjacent diagram.

The term is redundant in terms of the static logic of the system, but such redundant, or consensus terms, are often needed to assure race-free dynamic performance.

Similarly, an additional term of A ¯ D {\displaystyle {\overline {A}}D} must be added to the inverse to eliminate another potential race hazard. Applying De Morgan's laws creates another product of sums expression for f, but with a new factor of ( A + D ¯ ) {\displaystyle \left(A+{\overline {D}}\right)} .

The following are all the possible 2-variable, 2 × 2 Karnaugh maps. Listed with each is the minterms as a function of ∑ m ( ) {\textstyle \sum m()} and the race hazard free (see previous section) minimum equation. A minterm is defined as an expression that gives the most minimal form of expression of the mapped variables. All possible horizontal and vertical interconnected blocks can be formed. These blocks must be of the size of the powers of 2 (1, 2, 4, 8, 16, 32, ...). These expressions create a minimal logical mapping of the minimal logic variable expressions for the binary expressions to be mapped. Here are all the blocks with one field.

A block can be continued across the bottom, top, left, or right of the chart. That can even wrap beyond the edge of the chart for variable minimization. This is because each logic variable corresponds to each vertical column and horizontal row. A visualization of the k-map can be considered cylindrical. The fields at edges on the left and right are adjacent, and the top and bottom are adjacent. K-Maps for four variables must be depicted as a donut or torus shape. The four corners of the square drawn by the k-map are adjacent. Still more complex maps are needed for 5 variables and more.

Related graphical minimization methods include:

A K arnaugh map (K-map) is a visual method used to simplify the algebraic expressions in Boolean functions without having to resort to complex theorems or equation manipulations.