From WikiChip
Editing karnaugh map
Warning: You are not logged in. Your IP address will be publicly visible if you make any edits. If you log in or create an account, your edits will be attributed to your username, along with other benefits.
The edit can be undone.
Please check the comparison below to verify that this is what you want to do, and then save the changes below to finish undoing the edit.
This page supports semantic in-text annotations (e.g. "[[Is specified as::World Heritage Site]]") to build structured and queryable content provided by Semantic MediaWiki. For a comprehensive description on how to use annotations or the #ask parser function, please have a look at the getting started, in-text annotation, or inline queries help pages.
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> | ||
− | ''' | + | '''Marnaugh 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]]. |
== Map Construction == | == Map Construction == | ||
Line 111: | Line 114: | ||
\end{align} | \end{align} | ||
</math> | </math> | ||
− | Each minterm in the equation is | + | 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. |
[[File:kmap example color coded (expression).svg|400px]] | [[File:kmap example color coded (expression).svg|400px]] | ||
=== from truth table === | === 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. | 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]] | [[File:kmap example color coded (table).svg|400px]] | ||
==Simplification== | ==Simplification== | ||
Line 121: | Line 123: | ||
#finding largest groups of 1s | #finding largest groups of 1s | ||
#generating an equation from the identified groups | #generating an equation from the identified groups | ||
− | + | === finding 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]]'''. | 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== |
− | + | A group consists of one or more cells of 1s that are adjacent to one another. I.e. cells must be alongside, above or below one another. Groups may overlap but may not go diagonally. | |
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |