From WikiChip
Difference between revisions of "karnaugh map"

(→‎Map Cell Numbering: +images +table)
Line 13: Line 13:
 
'''Marnaugh Map''' ('''K-map''') is a graphical tool that provides a simple and straightforward method of [[logic minimization|minimizing]] [[Boolean algebra|Boolean expressions]]. The K-map method was introduced in 1953 by [[Maurice Karnaugh]] as an enhancement to [[Veitch diagram]].
 
'''Marnaugh Map''' ('''K-map''') is a graphical tool that provides a simple and straightforward method of [[logic minimization|minimizing]] [[Boolean algebra|Boolean expressions]]. The K-map method was introduced in 1953 by [[Maurice Karnaugh]] as an enhancement to [[Veitch diagram]].
  
−
== Format ==
+
== Map Construction ==
 
=== Map Formats ===
 
=== Map Formats ===
 
A K-map is a square or rectangle divided into a number of smaller squares called '''cells'''. Each cell on the K-Map corresponds directly to a line in a [[truth table]]. There are always <math>2^n</math> cells in a K-Map where <math>n</math> is the number of variables in the {{ba|function}}. Below are the usual formats for 1-4 variable k-maps (larges k-maps are discussed later on).
 
A K-map is a square or rectangle divided into a number of smaller squares called '''cells'''. Each cell on the K-Map corresponds directly to a line in a [[truth table]]. There are always <math>2^n</math> cells in a K-Map where <math>n</math> is the number of variables in the {{ba|function}}. Below are the usual formats for 1-4 variable k-maps (larges k-maps are discussed later on).
Line 94: Line 94:
 
| [[File:kmap (numbering) (3 vars).svg|200px]] || [[File:kmap (numbering) (4 vars).svg|200px]]
 
| [[File:kmap (numbering) (3 vars).svg|200px]] || [[File:kmap (numbering) (4 vars).svg|200px]]
 
|}
 
|}
 +
 +
== Populating a K-map==
 +
Populating a K-map can be done with a [[boolean algebra|Boolean expression]] or a [[truth table]].
 +
=== from Boolean expression ===
 +
Because each cell on the K-map represents a particular [[minterm]] (or [[maxterm]]). Converting the desired [[Boolean function]] into [[sum of minterms]] form can help considerably.
 +
 +
Consider the following [[Boolean function]].
 +
::<math>f(A,B,C) = \bar A C + B(A+C)</math>
 +
To make it easier to transfer the data to a K-map, the equation can be manipulated a bit so that it's in [[sum of minterms]] canonical form.
 +
::<math>
 +
\begin{align}
 +
f(A,B,C) =& \bar A C + B(A+C) \\
 +
        =& AB + \bar AC + BC && \mbox{By Distributive Axiom} \\
 +
        =& AB(C+\bar C) + \bar AC(B+\bar B) + BC(A+\bar A) && \because (X+\bar X) = 1 \mbox{ By Inverse Axiom} \\
 +
        =& ABC+AB\bar C+ \bar ACB + \bar AC\bar B + BCA + BC \bar A && \mbox{ By Distributive Axiom} \\
 +
        =& ABC+AB\bar C+ \bar ABC + \bar A\bar BC + ABC + \bar ABC && \mbox{ By Commutative Axiom} \\
 +
        =& ABC+AB\bar C+ \bar ABC + \bar A\bar BC && \mbox{ By Idempotent Law} \\
 +
        =& m_7 + m_6 + m_3 + m_1
 +
\end{align}
 +
</math>
 +
Each minterm in the equation is than transferred into the K-map where each variable in the minterm represents a 1 and each complemented variable represents a 0.
 +
=== from truth table ===
 +
Transferring the data from a [[truth table]] to a K-map is slightly more straightforward since each cell corresponds directly to each row in the table. A cell on the K-map is labeled 1 when the row they represent in the truth table results in a 1; otherwise the cell is labeled 0. Often times if the cell is 0, the 0 itself is simply omitted and is understood to mean that.

Revision as of 10:34, 10 December 2015

3-input MAJ gate kmap.svg
3-input MAJ gate
Equation StartLayout 1st Row 1st Column f left-parenthesis a comma b comma c right-parenthesis equals 2nd Column upper A upper B plus upper A upper C plus upper B upper C 2nd Row 1st Column equals 2nd Column sigma-summation m left-parenthesis 3 comma 5 comma 6 comma 7 right-parenthesis 3rd Row 1st Column f prime left-parenthesis a comma b comma c right-parenthesis equals 2nd Column product upper M left-parenthesis 0 comma 1 comma 2 comma 4 right-parenthesis EndLayout

Marnaugh Map (K-map) is a graphical tool that provides a simple and straightforward method of minimizing Boolean expressions. The K-map method was introduced in 1953 by Maurice Karnaugh as an enhancement to Veitch diagram.

Map Construction

Map Formats

A K-map is a square or rectangle divided into a number of smaller squares called cells. Each cell on the K-Map corresponds directly to a line in a truth table. There are always Equation 2 Superscript n cells in a K-Map where Equation n is the number of variables in the function. Below are the usual formats for 1-4 variable k-maps (larges k-maps are discussed later on).

1-Variable K-map 2-Variables K-map
kmap (no labels) (1 var).svg kmap (no labels) (2 vars).svg
3-Variables K-map 4-Variables K-map
kmap (no labels) (3 vars).svg kmap (no labels) (4 vars).svg

Map Labeling

The coordinates of the cells in a K-map are the input value combinations from the truth table. There are a number of common ways to label a K-map. The two most common methods are numerically and by variables and their complements. There are advantages to both. Regardless of which way you choose, the coordinates of two adjacent cells differ by only one variable - i.e. only one 0 can switch to a 1 and vice versa between two adjacent cells. For example, consider a function with 2 variables, the order by which you list them would be Equation 00 comma 01 comma 11 comma 10 . Note how 11 and 10 were switched so that only one value is different.

Numerically Variables
1-Variable K-map
kmap (1 var).svg kmap (labels) (1 var).svg
2-Variables K-map
kmap (2 vars).svg kmap (labels) (2 vars).svg
3-Variables K-map
kmap (3 vars).svg kmap (labels) (3 vars).svg
4-Variables K-map
kmap (4 vars).svg kmap (labels) (4 vars).svg

Map Cell Numbering

Inputs Minterms Maxterms
A B Minterms Index Maxterms Index
0 0 Equation upper A overbar upper B overbar Equation m 0 Equation upper A plus upper B Equation upper M 0
0 1 Equation upper A overbar upper B Equation m 1 Equation upper A plus upper B overbar Equation upper M 1
1 0 Equation upper A upper B overbar Equation m 2 Equation upper A overbar plus upper B Equation upper M 2
1 1 Equation upper A upper B Equation m 3 Equation upper A overbar plus upper B overbar Equation upper M 3
A B C Minterms Index Maxterms Index
0 0 0 Equation upper A overbar upper B overbar upper C overbar Equation m 0 Equation upper A plus upper B plus upper C Equation upper M 0
0 0 1 Equation upper A overbar upper B overbar upper C Equation m 1 Equation upper A plus upper B plus upper C overbar Equation upper M 1
0 1 0 Equation upper A overbar upper B upper C overbar Equation m 2 Equation upper A plus upper B overbar plus upper C Equation upper M 2
0 1 1 Equation upper A overbar upper B upper C Equation m 3 Equation upper A plus upper B overbar plus upper C overbar Equation upper M 3
1 0 0 Equation upper A upper B overbar upper C overbar Equation m 4 Equation upper A overbar plus upper B plus upper C Equation upper M 4
1 0 1 Equation upper A upper B overbar upper C Equation m 5 Equation upper A overbar plus upper B plus upper C overbar Equation upper M 5
1 1 0 Equation upper A upper B upper C overbar Equation m 6 Equation upper A plus upper B plus upper C overbar Equation upper M 6
1 1 1 Equation upper A upper B upper C Equation m 7 Equation upper A overbar plus upper B overbar plus upper C overbar Equation upper M 7

Sometimes the individual cells are numbered in accordance with their minterm and maxterm indices. Strictly speaking this is unnecessary, but it may be useful in various situations when working with minterms and maxterms. Cell numbering are usually written in one of the cell corners.

1-Variable K-map 2-Variables K-map
kmap (numbering) (1 var).svg kmap (numbering) (2 vars).svg
3-Variables K-map 4-Variables K-map
kmap (numbering) (3 vars).svg kmap (numbering) (4 vars).svg

Populating a K-map

Populating a K-map can be done with a Boolean expression or a truth table.

from Boolean expression

Because each cell on the K-map represents a particular minterm (or maxterm). Converting the desired Boolean function into sum of minterms form can help considerably.

Consider the following Boolean function.

Equation f left-parenthesis upper A comma upper B comma upper C right-parenthesis equals upper A overbar upper C plus upper B left-parenthesis upper A plus upper C right-parenthesis

To make it easier to transfer the data to a K-map, the equation can be manipulated a bit so that it's in sum of minterms canonical form.

Equation StartLayout 1st Row 1st Column f left-parenthesis upper A comma upper B comma upper C right-parenthesis equals 2nd Column upper A overbar upper C plus upper B left-parenthesis upper A plus upper C right-parenthesis 2nd Row 1st Column equals 2nd Column upper A upper B plus upper A overbar upper C plus upper B upper C 3rd Column Blank 4th Column By Distributive Axiom 3rd Row 1st Column equals 2nd Column upper A upper B left-parenthesis upper C plus upper C overbar right-parenthesis plus upper A overbar upper C left-parenthesis upper B plus upper B overbar right-parenthesis plus upper B upper C left-parenthesis upper A plus upper A overbar right-parenthesis 3rd Column Blank 4th Column because left-parenthesis upper X plus upper X overbar right-parenthesis equals 1 By Inverse Axiom 4th Row 1st Column equals 2nd Column upper A upper B upper C plus upper A upper B upper C overbar plus upper A overbar upper C upper B plus upper A overbar upper C upper B overbar plus upper B upper C upper A plus upper B upper C upper A overbar 3rd Column Blank 4th Column By Distributive Axiom 5th Row 1st Column equals 2nd Column upper A upper B upper C plus upper A upper B upper C overbar plus upper A overbar upper B upper C plus upper A overbar upper B overbar upper C plus upper A upper B upper C plus upper A overbar upper B upper C 3rd Column Blank 4th Column By Commutative Axiom 6th Row 1st Column equals 2nd Column upper A upper B upper C plus upper A upper B upper C overbar plus upper A overbar upper B upper C plus upper A overbar upper B overbar upper C 3rd Column Blank 4th Column By Idempotent Law 7th Row 1st Column equals 2nd Column m 7 plus m 6 plus m 3 plus m 1 EndLayout

Each minterm in the equation is than transferred into the K-map where each variable in the minterm represents a 1 and each complemented variable represents a 0.

from truth table

Transferring the data from a truth table to a K-map is slightly more straightforward since each cell corresponds directly to each row in the table. A cell on the K-map is labeled 1 when the row they represent in the truth table results in a 1; otherwise the cell is labeled 0. Often times if the cell is 0, the 0 itself is simply omitted and is understood to mean that.

Retrieved from "https://en.wikichip.org/w/index.php?title=karnaugh_map&oldid=13011"