Karnaugh Map

Author

Eric W. Weisstein
April 19, 2011

This notebook downloaded from http://mathworld.wolfram.com/notebooks/Algebra/KarnaughMap.nb.

For more information, see Eric's MathWorld entry http://mathworld.wolfram.com/KarnaughMap.html.

©2011 Wolfram Research, Inc. except for portions noted otherwise

Text

The Karnaugh map is a device used to quickly eliminate redundant operations in a Boolean Function. The easiest to read Karnaugh maps are those drawn for a function in the form of a complete product or “sum of products,” where the latter name also implies the use of · and + for the AND and OR operators. In a typical truth table for such a function, the inputs are enumerated using 0 for False and 1 for true, and ordered as a counting sequence when read as positive binary integers. Below is such a truth table for a function of four variables.

γ[exp_]:=Graphics[Text[exp],ImageSize->{18,18}];
z=γ[0];o=γ[1];b=γ[""];
δ[exp_]:=Graphics[Text[exp],ImageSize->{48,18}];

Build the truth table

tbl=Part[Table[IntegerDigits[n,2,4],{n,0,15}]];

Do[AppendTo[Part[tbl,i] ,Part[Table[v,{v,{0,0,1,1,0,0,1,1,1,0,0,0,1,1,0,0}}],i]],{i,1,16}];

tbl=Insert[tbl,{γ[(Subscript[x, 3])],γ[(Subscript[x, 2])],γ[(Subscript[x, 1])],γ[(Subscript[x, 0])],γ["f"]},1];

Do[AppendTo[Part[tbl,i],Part[{b,b,b,δ["(Overscript[(Subscript[x, 3]), ¯]) (Overscript[(Subscript[x, 2]) , ¯])(Subscript[x, 1]) (Overscript[(Subscript[x, 0]), ¯])"],δ["(Overscript[(Subscript[x, 3]), ¯]) (Overscript[(Subscript[x, 2]) , ¯])(Subscript[x, 1]) (Subscript[x, 0])"],b,b,δ["(Overscript[(Subscript[x, 3]), ¯]) (Subscript[x, 2])(Subscript[x, 1]) (Overscript[(Subscript[x, 0]), ¯])"],δ["(Overscript[(Subscript[x, 3]), ¯]) (Subscript[x, 2])(Subscript[x, 1]) (Subscript[x, 0])"],δ["(Subscript[x, 3]) (Overscript[(Subscript[x, 2]) , ¯])(Overscript[(Subscript[x, 1]), ¯])(OverBar[(Subscript[x, 0])]) "],b,b,b,δ["(Subscript[x, 3]) (Subscript[x, 2])(Overscript[(Subscript[x, 1]), ¯]) (Overscript[(Subscript[x, 0]), ¯])"],δ["(Subscript[x, 3]) (Subscript[x, 2])(Overscript[(Subscript[x, 1]), ¯]) (Subscript[x, 0])"],b,b},i]],{i,1,17}]

GraphicsGrid[tbl]

({{(Subscript[x, 1]), (Subscript[x, 2]), (Subscript[x, 3]), (Subscript[x, 4]), , f, , }, {0, 0, 0, 0, , 0, , }, {0, 0, 0, 1, , 0, , }, {0, 0, 1, 0, , 1, , (Overscript[(Subscript[x, 1]), ¯]) (Overscript[(Subscript[x, 2]) , ¯])(Subscript[x, 3]) (Overscript[(Subscript[x, 4]), ¯])}, {0, 0, 1, 1, , 1, , (Overscript[(Subscript[x, 1]), ¯]) (Overscript[(Subscript[x, 2]) , ¯])(Subscript[x, 3]) (Subscript[x, 4])}, {0, 1, 0, 0, , 0, , }, {0, 1, 0, 1, , 0, , }, {0, 1, 1, 0, , 1, , (Overscript[(Subscript[x, 1]), ¯]) (Subscript[x, 2])(Subscript[x, 3]) (Overscript[(Subscript[x, 4]), ¯])}, {0, 1, 1, 1, , 1, , (Overscript[(Subscript[x, 1]), ¯]) (Subscript[x, 2])(Subscript[x, 3]) (Subscript[x, 4])}, {1, 0, 0, 0, , 1, , (Subscript[x, 1]) (Overscript[(Subscript[x, 2]) , ¯])(Overscript[(Subscript[x, 3]), ¯]) (Overscript[(Subscript[x, 4]), ¯])}, {1, 0, 0, 1, , 0, , }, {1, 0, 1, 0, , 0, , }, {1, 0, 1, 1, , 0, , }, {1, 1, 0, 0, , 1, , (Subscript[x, 1]) (Subscript[x, 2])(Overscript[(Subscript[x, 3]), ¯]) (Overscript[(Subscript[x, 4]), ¯])}, {1, 1, 0, 1, , 1, , (Subscript[x, 1]) (Subscript[x, 2])(Overscript[(Subscript[x, 3]), ¯]) (Subscript[x, 4])}, {1, 1, 1, 0, , 0, , }, {1, 1, 1, 1, , 0, , }})

For those rows in the table where the function value is 1, or True, a logical expression called a minterm is shown. The minterms use the overbar notation to mean NOT. When all seven minterms are accumulated,

f((Subscript[x, 1]),(Subscript[x, 2]),(Subscript[x, 3]),(Subscript[x, 4]))=(Overscript[(Subscript[x, 1]), ¯]) (Overscript[(Subscript[x, 2]) , ¯])(Subscript[x, 3]) (Overscript[(Subscript[x, 4]), ¯])+(Overscript[(Subscript[x, 1]), ¯]) (Overscript[(Subscript[x, 2]) , ¯])(Subscript[x, 3]) (Subscript[x, 4])+(Overscript[(Subscript[x, 1]), ¯]) (Subscript[x, 2])(Subscript[x, 3]) (Overscript[(Subscript[x, 4]), ¯])+(Overscript[(Subscript[x, 1]), ¯]) (Subscript[x, 2])(Subscript[x, 3]) (Subscript[x, 4])+(Subscript[x, 1]) (Overscript[(Subscript[x, 2]) , ¯])(Overscript[(Subscript[x, 3]), ¯]) (Overscript[(Subscript[x, 4]), ¯])+(Subscript[x, 1]) (Subscript[x, 2])(Overscript[(Subscript[x, 3]), ¯]) (Overscript[(Subscript[x, 4]), ¯])+(Subscript[x, 1]) (Subscript[x, 2])(Overscript[(Subscript[x, 3]), ¯]) (Subscript[x, 4])

the function is realized. This realization is not optimal, and a Karnaugh map can be used to reduce it. 

A Karnaugh map for the function is shown below. It is a two dimensional layout of the truth table. Each dimension spans an adjacent, though not necessarily so, pair of variables. Instead of a counting sequence, the variables’ sequence is in Gray Code, so that between each pair of adjacent cells (in rows or columns) only a single variable changes state.

kmap=GraphicsGrid[
{{b,γ["(Subscript[x, 1]) (Subscript[x, 0])"],SpanFromLeft,SpanFromLeft,SpanFromLeft,SpanFromLeft,SpanFromLeft,b,b,b,b},
{b,b,γ["00"],γ["01"],γ["11"],γ["10"],b,b,b,b,b},
{γ[ "(Subscript[x, 3]) (Subscript[x, 2])"],     γ["00"]     ,z,z,o,o,b,γ["(OverBar[(Subscript[x, 3])])(OverBar[(Subscript[x, 2])])(Subscript[x, 1])(Subscript[x, 0])+(OverBar[(Subscript[x, 3])])(OverBar[(Subscript[x, 2])])(Subscript[x, 1])(OverBar[(Subscript[x, 0])])=(OverBar[(Subscript[x, 3])])(OverBar[(Subscript[x, 2])])(Subscript[x, 1])"],SpanFromLeft,SpanFromLeft,SpanFromLeft},{SpanFromAbove,   γ["01"]     ,z,z,o,z,b,γ["(OverBar[(Subscript[x, 3])])(OverBar[(Subscript[x, 2])])(Subscript[x, 1])(Subscript[x, 0])+(OverBar[(Subscript[x, 3])])(Subscript[x, 2])(Subscript[x, 1])(Subscript[x, 0])=(OverBar[(Subscript[x, 3])])(Subscript[x, 1])(Subscript[x, 0])"],SpanFromLeft,SpanFromLeft,SpanFromLeft},{SpanFromAbove,       γ["11"]       ,o,o,z,z,b,γ["(Subscript[x, 3])(Subscript[x, 2])(OverBar[(Subscript[x, 1])])(OverBar[(Subscript[x, 0])])+(Subscript[x, 3])(Subscript[x, 2])(OverBar[(Subscript[x, 1])])(Subscript[x, 0])+(Subscript[x, 3])(OverBar[(Subscript[x, 2])])(OverBar[(Subscript[x, 1])])(OverBar[(Subscript[x, 0])])+(Subscript[x, 3])(OverBar[(Subscript[x, 2])])(OverBar[(Subscript[x, 1])])(Subscript[x, 0])=(Subscript[x, 3])(OverBar[(Subscript[x, 1])])"],SpanFromLeft,SpanFromLeft,SpanFromLeft},{SpanFromAbove,            γ["10"]            ,o,o,z,z,b,b,b,b,b}},
Frame->{False,False,Flatten[Table[Table[{j,k}->j>2&&k>2,{j,6}],{k,6}]]},Spacings->Scaled[.3],ImageSize->{768,384}];

On the map, neighboring cells where the function value is 1 are grouped together with loops. Each loop represents minterms which can be reduced. Those variables which change within a loop can be eliminated. The validity of this, using the uppermost expression as an example, can be shown algebraically.

({{(Subscript[x, 1])·(Subscript[x, 2])·(Overscript[(Subscript[x, 3]), ¯])·(Overscript[(Subscript[x, 4]), ¯])+(Subscript[x, 1])·(Overscript[(Subscript[x, 2]), ¯])·(Overscript[(Subscript[x, 3]), ¯])·(Overscript[(Subscript[x, 4]), ¯])}, {=(Subscript[x, 2])·((Subscript[x, 1])·(Overscript[(Subscript[x, 3]), ¯])·(Overscript[(Subscript[x, 4]), ¯]))+(Overscript[(Subscript[x, 2]), ¯])·((Subscript[x, 1])·(Overscript[(Subscript[x, 3]), ¯])·(Overscript[(Subscript[x, 4]), ¯]))}, {=((Subscript[x, 2])+(Overscript[(Subscript[x, 2]), ¯]))·((Subscript[x, 1])·(Overscript[(Subscript[x, 3]), ¯])·(Overscript[(Subscript[x, 4]), ¯]))}, {=(Subscript[x, 1])·(Overscript[(Subscript[x, 3]), ¯])·(Overscript[(Subscript[x, 4]), ¯])}})

Loops can also be drawn wrapping around rows and/or columns, because the Karnaugh map (up to four variables) is really the surface of a torus.

Graphic

kmg=;
kmg=SetAlphaChannel[kmg,.8];
torus=ParametricPlot3D[{Cos[u] (3+Cos[v]),Sin[u] (3+Cos[v]),Sin[v]},{u,0,2 π},{v,0,2 π},TextureCoordinateFunction->({2 #4,#5}&),PlotStyle->Directive[Opacity[.7],Specularity[White,50],Texture[kmg]],Axes->False,Lighting->"Neutral",Mesh->None,Boxed->False];

Show[torus,Method->{"ShrinkWrap"->True}]

bt[n_,k_]:=If[BitGet[n,k]==1,Subscript[x,k],OverBar[Subscript[x,k]]];

cell[n_]:=Table[bt[n,k],{k,{3,2,1,0}}];

kmg=Rasterize[Grid[Map[cell,Table[BitOr[BitShiftLeft[i,2],j],{i,{0,1,3,2}},{j,{0,1,3,2}}],{2}],Frame->All,Spacings->{2,3}],ImageSize->{{1536},{1536}}];

torus=ParametricPlot3D[{Cos[u] (2+Cos[v]),Sin[u] (2+Cos[v]),Sin[v]},{u,0,2 π},{v,0,2 π},TextureCoordinateFunction->({2 #4,#5}&),PlotStyle->Directive[Opacity[.85],Specularity[White,20],Texture[kmg]],Axes->False,Lighting->"Neutral",Mesh->None,Boxed->False];

Show[torus,Method->{"ShrinkWrap"->True}]

Karnaugh maps such as in the above example can be similarly drawn for 2 (Degenerate) or 3 variables. They can be employed for more than 4 variables (e.g., 5 variables by overlaying two 4 variable maps), but visualization becomes a much greater chore than algebra.

There are other logic design and minimization methods based on the Karnaugh map, such as for using NAND operators instead of AND and OR.

References

Booth, T. \titleisbn {Digital Networks and Computer Systems.} {0471088404} New York, United States : John Wiley and Sons, p. 64,125-136, 1971.\par

Muroga, S. \titleisbn {Logic Design and Switching Theory.} {0471044180} New York, United States : John Wiley and Sons, p.87-90,281-297, 1979.\par