Latest revision |
Your text |
Line 1: |
Line 1: |
| {{title|Karnaugh Map (K-map)}} | | {{title|Karnaugh Map (K-map)}} |
− | <div style="float: right; text-align: center; margin: 20px; width: 250px">[[File:3-input MAJ gate kmap.svg|200px]]<br />3-input [[MAJ]] gate<br /><math> | + | <div style="float: right; text-align: center; margin: 20px; width: 250px"> |
| + | [[File:3-input MAJ gate kmap.svg|200px]]<br /> |
| + | 3-input [[MAJ]] gate<br /> |
| + | <math> |
| \begin{align} | | \begin{align} |
| f(a,b,c) =& AB+AC+BC \\ | | f(a,b,c) =& AB+AC+BC \\ |
| =& \sum m(3,5,6,7) \\ | | =& \sum m(3,5,6,7) \\ |
− | f(a,b,c) =& \prod M(0,1,2,4) | + | f^\prime(a,b,c) =& \prod M(0,1,2,4) |
| \end{align} | | \end{align} |
| </math> | | </math> |
| </div> | | </div> |
− | '''Karnaugh Map''' ('''K-map''') (pronounced ''car-no 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]]. |
| | | |
− | == Map Construction == | + | == Format == |
| === 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 91: |
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 then transferred into the K-map where each variable in the minterm represents a 1 and each complemented variable represents a 0.
| |
− | [[File:kmap example color coded (expression).svg|400px]]
| |
− | === 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.
| |
− |
| |
− | [[File:kmap example color coded (table).svg|400px]]
| |
− | ==Simplification==
| |
− | Generating simplified equations for a Karnaugh map involves two simple steps:
| |
− | #finding largest groups of 1s
| |
− | #generating an equation from the identified groups
| |
− | [[File:kmap terms.svg|400px|right]]
| |
− | ===Groups===
| |
− | An '''[[implicant]]''' is the individual product term in the [[sum of product]] expression. On a K-map implicants are represented as one or more adjacent cells of 1s. A '''group''' is a loose term for the enclosure containing adjacent squares of 1s. When a group contains the most adjacent 1 cells it possibly can, it is called a '''[[prime implicant]]'''. When a group encloses cells of 1s that are not shared with any other group, it is called an '''[[essential prime implicant]]'''. Likewise, when a group encloses cells of 1s that are all shared with other groups, it is called a '''[[non-essential prime implicant]]'''.
| |
− | ====Rules====
| |
− | When grouping implicants together, there is a set of rules that must be followed:
| |
− | * Groups are made of power of 2 number of cells (e.g. 1, 2, 4, 8, 16)
| |
− | ::[[File:kmap rules - powers of 2.svg|400px]]
| |
− | * Groups consists of one or more cells of 1s only - i.e. no cells of 0s
| |
− | ::[[File:kmap rules - only 1s.svg|400px]]
| |
− | * Every cell of 1 must be in at lest one group
| |
− | ::[[File:kmap rules - no leftout cells.svg|400px]]
| |
− | * Overlapping groups are allowed
| |
− | ::[[File:kmap rules - overlapping allowed.svg|400px]]
| |
− | * Wrapping around is allowed
| |
− | ::[[File:kmap rules - wrapping around.svg|400px]]
| |
− | * Groups can be made of cells that are adjacent to one another. I.e. cells must be alongside, above or below one another
| |
− | ::[[File:kmap rules - adjacent cells.svg|400px]]
| |
− | * Groups may not go diagonally
| |
− | ::[[File:kmap rules - no diagonals.svg|400px]]
| |
− | * Groups should be large as possible.
| |
− | ::[[File:kmap rules - largest groups.svg|400px]]
| |
− | ===Simplified Equation===
| |
− | After all the maximum groups have been marked in the K-map, a simplified Boolean expression may be obtained by ORing together the individual expressions for each of the groups. The expression for a group is the variables or the complement of the variables that do not change between cells.
| |
− |
| |
− | [[File:kmap example 1.svg|left|150px]]
| |
− | For example, consider the example to the left. This Karnaugh map has a single group that covers both <math>B = 0</math> and <math>B = 1</math>. Because <math>B</math> changes, it is dropped from our expression, living us with just <math>A = 1</math>. Therefore the Boolean expression for this K-map is simply <math>f(A,B) = \sum m(2,3) = A</math>.
| |
− |
| |
− | [[File:kmap example 2.svg|right|100px]]
| |
− | The Karnaugh map on the right on the other hand has two groups. One group spans both <math>B = 0</math> and <math>B = 1</math> and another that spans <math>A = 0</math> and <math>A = 1</math>. In the expression for the group that spans vertically, <math>B</math> changes yielding the expression <math>A</math>. Likewise in the expression that spans horizontally, <math>A</math> changes, yielding the expression <math>B</math>. The simplified equation for this K-map is the ORing of all the individual term - <math>f(A,B) = \sum m(1,2,3) = A+B</math>.
| |
− |
| |
− |
| |
− | [[File:kmap example 3.svg|left|200px]]
| |
− | In this K-map, cells 0 and 4 are considered adjacent as well as cells 3 and 7. For the group involving cells 0 and 4, <math>A</math> changes, therefore it is dropped from the expression. Because <math>B</math> is always 0 and <math>C</math> is always 0 as well, the equation for that group is <math>\bar B \bar C</math>. For the second group involving cells 3 and 7, <math>A</math> changes once again. In this group <math>B</math> is always 1 and <math>C</math> is always 1 as well. The equation for this group is <math>BC</math>. The final simplified equation for this K-map is the ORing of all the terms - <math>f(A,B,C) = \sum m(0,3,4,7) = \bar B \bar C + BC</math>.
| |
− | {{clear}}
| |
− | == Don't cares ==
| |
− | {{further|don't care}}
| |
− | {| class="wikitable" style="float: right; text-align: center;"
| |
− | ! A !! B !! C !! Q
| |
− | |-
| |
− | | 0 || 0 || 0 || {{X}}
| |
− | |-
| |
− | | 0 || 0 || 1 || {{X}}
| |
− | |-
| |
− | | 0 || 1 || 0 || 0
| |
− | |-
| |
− | | 0 || 1 || 1 || 0
| |
− | |-
| |
− | | 1 || 0 || 0 || 1
| |
− | |-
| |
− | | 1 || 0 || 1 || 1
| |
− | |-
| |
− | | 1 || 1 || 0 || 0
| |
− | |-
| |
− | | 1 || 1 || 1 || 1
| |
− | |}
| |
− | [[Incompletely specified function]] are functions with combination of inputs that should never occur. Those unspecified [[minterm]]s are called [[don't care]] values. Don't care values open opportunities for further simplification of the Boolean expression. When it comes to Karnaugh maps, don't care values, which are represented with ''X'''s are considered either a 0 or 1, whichever results in the biggest group - i.e. the simplest expression.
| |
− |
| |
− | [[File:kmap (don't care example).svg|left|200px]]
| |
− | The [[truth table]] to the Karnaugh map below is on the right and represents an [[incompletely specified function]]. Note the don't care values for two of the outputs. I.e. <math>f(0,0,0)</math> and <math>f(0,0,1)</math> should never happen. In this example, the two don't care values can be used to make the 2-cell group be a 4-cell group allowing us to eliminate a whole variable: <math>A</math>. The Boolean expression is therefore <math>f(a,b,c) = \bar B + AC</math>.
| |
− | {{clear}}
| |
− |
| |
− | == Product of Sum (PoS)==
| |
− | [[File:kmap pos example.svg|200px|right]]
| |
− | While usually used to generate sum of products, Karnaugh maps can be used to generate [[product of sum]] just as easily by applying the same rules we designed above, but for 0 cells instead. Remember that when working with [[maxterm]]s instead of [[minterm]]s, when a variable is 1, it is complemented instead of when it's 0.
| |
− |
| |
− | For example consider the K-map on the right. In this case the 0 cells are grouped. The Boolean function for this Karnaugh map is
| |
− | ::<math>f(A,B,C) = \prod M(2,6,1,3) = (\bar B+C)(A+\bar C)</math>.
| |
− | {{clear}}
| |
− | == Hazard analysis ==
| |
− | {{empty section}}
| |
− |
| |
− | == Larger Karnaugh Maps==
| |
− | {{empty section}}
| |
− | === 5-variable K-map===
| |
− | {{empty section}}
| |
− |
| |
− | === 6-variable K-map===
| |
− | {{empty section}}
| |
− |
| |
− | == Examples ==
| |
− | {{empty section}}
| |
− |
| |
− | == See also ==
| |
− | * [[Boolean algebra]]
| |