A Karnaugh map provides a pictorial method of grouping together expressions with common factors and therefore eliminating unwanted variables. The Karnaugh map can also be described as a special arrangement of a truth table.

**KARNAUGH MAPS **

Maurice Karnaugh, a telecommunications engineer, developed the
Karnaugh map at Bell Labs in 1953 while designing digital logic based telephone
switching circuits. Karnaugh maps reduce logic functions more quickly and
easily compared to Boolean algebra.

A Karnaugh
map provides a pictorial method of grouping together expressions with
common factors and therefore eliminating unwanted variables. The
Karnaugh map can also be described as a
special arrangement of a truth table.

**Construction
of a Karnaugh Map**

1. Each
square containing a ‗1‘ must be consideredstonce,at leaalthough it can be
considered as often as desired.

2. The
objective should be to account for all the marked squares in the minimum number
of groups.

3. The
number of squares in a group must always be a power of 2, i.e. groups can have
1, 2, 4_ 8, 16, squares.

4. Each
group should be as large as possible, which means that a square should not be
accounted for by itself if it can be accounted for by a group of two squares; a
group of two squares should not be made if the
involved squares can be included in a group of four squares and so on.

5. 'Don‘t care‘ entries can be used in accountinglof-squares1foralto make optimum groups.
They are marked ‗X‘ in the rrespondingco squares.
It is, however, not necessary to account for
all 'don‘t care‘ entries. Only such entries that can be
used to advantage should be used.

The diagram below illustrates the correspondence between the Karnaugh map and the truth table for the general case of a two variable problem.

The values inside the squares are copied from the output
column of the truth table, therefore there is one square in the map for every
row in the truth table. Around the edge of the Karnaugh map are the values of
the two input variable. A is along the top and B is down the left hand side.
The diagram below explains this:

The values around the edge of the map can be thought of as
coordinates. So as an example, the square on the top right hand corner of the
map in the above diagram has coordinates A=1 and B=0. This square corresponds
to the row in the truth table where A=1 and B=0 and F=1. Note that the value in
the F column represents a particular function to which the Karnaugh map
corresponds.

**Two variable K-map**

There are four minterms for two variables: hence, the map
consists of four squares, one for each minterm. In any K-Map, each square
represents a minterm. Adjacent squares always differ by just one literal (So
that the unifying theorem may apply: X + X' = 1). For the 2-variable case
(e.g.: variables X, Y), the map can be drawn as below. Two variable map is the
one which has got only two variables as input.

**Example- Carry and Sum of a half adder**

In this example we have the truth table as input, and we have
two output functions. Generally we may have n output functions for m input variables.
Since we have two output functions, we need to draw two k-maps (i.e. one for
each function). Truth table of 1 bit adder is shown below. Draw the k-map for
Carry and Sum as shown below.

**Grouping/Circling K-maps**

The power of K-maps is in
minimizing the terms, K-maps can be minimized with the help of grouping the
terms to form single terms. When forming groups of squares, observe/consider
the following:

•
Every square containing 1 must be considered at
least once.

•
A square containing 1 can be included in as many
groups as desired.

•
A group must be as large as possible.

•
If a square containing 1 cannot be placed in a
group, then leave it out to include in final expression.

•
The number of squares in a group must be equal to
2 .i.e. 2,4,8,.

• The map
is considered to be folded or spherical, therefore squares at the end of a row
or column are treated as adjacent squares.

• The
simplified logic expression obtained from a K-map is not always unique.
Groupings can be made in different ways.

•
Before drawing a K-map the logic expression must
be in canonical form.

**Example (1)- X'Y+XY: **In this
example we have the equation as input, and we have one output function.** **Draw
the k-map for function F with marking 1 for X'Y and XY position. Now combine
two 1's as shown in figure to form the single term. As you can see X and X' get
canceled and only Y remains

**Example (2)- X'Y+XY+XY' :**In this
example we have the equation as input, and we have one output** **function.
Draw the k-map for function F with marking 1 for X'Y, XY and XY position. Now
combine two 1's as shown in figure to form the two single terms.

**F = X + Y**

**3-Variable K-Map**

There are 8 minterms for 3 variables (X, Y, Z). Therefore,
there are 8 cells in a 3-variable K-map. One important thing to note is that
K-maps follow the gray code sequence, not the binary one. Each cell in a
3-variable K-map has 3 adjacent neighbours. In general, each cell in an
n-variable K-map has n adjacent neighbours.

There is wrap-around in the K-map

•
X'Y'Z' (m0) is adjacent to X'YZ' (m2)

•
XY'Z' (m4) is adjacent to XYZ' (m6)

**4-Variable K-Map: **There are
16 cells in a 4-variable (W, X, Y, Z); K-map as shown in the figure below

**Example (5) **F(W,X,Y,Z) = (1,5,12,13)

**Example (6) **F(W,X,Y,Z) = (4, 5, 10,
11, 14,15)

**5-Variable K-Map**: There are 32 cells in a
5-variable (V, W, X, Y, Z); K-map as shown in the figure** **below.

**Ref: **1)** ****A.P Godse & D.A Godse “Digital Electronics”, Technical publications, Pune, Revised **edition, 2008. Pg.No:2.25-2.70

2) **Morris Mano M. and Michael D. Ciletti, “Digital Design”, IV Edition, Pearson Education **Pg.No:70.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

**Related Topics **

Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.