Editing karnaugh 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>
\begin{align}
f(a,b,c) =& AB+AC+BC \\
         =& \sum m(3,5,6,7) \\
f^\prime(a,b,c) =& \prod M(0,1,2,4)
\end{align}
</math>
</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 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).

{| style="width: 500px; text-align: center"
! 1-Variable K-map !! 2-Variables K-map
|-
| [[File:kmap (no labels) (1 var).svg|125px]] || [[File:kmap (no labels) (2 vars).svg|150px]]
|-
! 3-Variables K-map !! 4-Variables K-map
|-
| [[File:kmap (no labels) (3 vars).svg|200px]] || [[File:kmap (no labels) (4 vars).svg|200px]]
|}

=== 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 <math>00, 01, 11, 10</math>. Note how 11 and 10 were switched so that only one value is different.

{| class="wikita2ble" style="text-align: center"
! style="width: 300px; height: 50px;" | Numerically !! style="width: 300px;" | Variables
|-
! colspan="2" style="height: 35px;" | 1-Variable K-map
|-
|-
| [[File:kmap (1 var).svg|100px]] || [[File:kmap (labels) (1 var).svg|100px]]
|-
! colspan="2" style="height: 35px;" | 2-Variables K-map
|-
| [[File:kmap (2 vars).svg|125px]] || [[File:kmap (labels) (2 vars).svg|125px]]
|-
! colspan="2" style="height: 35px;" | 3-Variables K-map
|-
| [[File:kmap (3 vars).svg|200px]] || [[File:kmap (labels) (3 vars).svg|200px]]
|-
! colspan="2" style="height: 35px;" | 4-Variables K-map
|-
| [[File:kmap (4 vars).svg|200px]] || [[File:kmap (labels) (4 vars).svg|200px]]
|}

=== Map Cell Numbering ===
{| class="wikitable" style="float: right;"
! colspan="3" | Inputs || colspan="2" | [[Minterm]]s || colspan="2" | [[Maxterm]]s
|-
! A !! B !!   !! [[Minterm]]s !! Index !! [[Maxterm]]s !! Index
|-
| 0 || 0 || || <math>\bar A \bar B</math> || <math>m_0</math> || <math>A+B</math> || <math>M_0</math>
|-
| 0 || 1 || || <math>\bar A B</math> || <math>m_1</math> || <math>A+\bar B</math> || <math>M_1</math>
|-
| 1 || 0 || || <math>A \bar B</math> || <math>m_2</math> || <math>\bar A+B</math> || <math>M_2</math>
|-
| 1 || 1 || || <math>AB</math> || <math>m_3</math> || <math>\bar A + \bar B</math> || <math>M_3</math>
|-
! A !! B !! C !! [[Minterm]]s !! Index !! [[Maxterm]]s !! Index
|-
| 0 || 0 || 0 || <math>\bar A \bar B \bar C</math> || <math>m_0</math> || <math>A+B+C</math> || <math>M_0</math>
|-
| 0 || 0 || 1 || <math>\bar A \bar B C</math> || <math>m_1</math> || <math>A+B+\bar C</math> || <math>M_1</math>
|-
| 0 || 1 || 0 || <math>\bar AB \bar C</math> || <math>m_2</math> || <math>A+\bar B + C</math> || <math>M_2</math>
|-
| 0 || 1 || 1 || <math>\bar A BC</math> || <math>m_3</math> || <math>A+\bar B+\bar C</math> || <math>M_3</math>
|-
| 1 || 0 || 0 || <math>A \bar B \bar C</math> || <math>m_4</math> || <math>\bar A+B+C</math> || <math>M_4</math>
|-
| 1 || 0 || 1 || <math>A \bar B C</math> || <math>m_5</math> || <math>\bar A+B+\bar C</math> || <math>M_5</math>
|-
| 1 || 1 || 0 || <math>AB \bar C</math> || <math>m_6</math> || <math>A+B+\bar C</math> || <math>M_6</math>
|-
| 1 || 1 || 1 || <math>ABC</math> || <math>m_7</math> || <math>\bar A+\bar B+\bar C</math> || <math>M_7</math>
|}
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 [[minterm]]s and [[maxterm]]s. Cell numbering are usually written in one of the cell corners.

{| style="width: 500px; text-align: center"
! 1-Variable K-map !! 2-Variables K-map
|-
| [[File:kmap (numbering) (1 var).svg|125px]] || [[File:kmap (numbering) (2 vars).svg|150px]]
|-
! 3-Variables K-map !! 4-Variables K-map
|-
| [[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. 
[[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)
* Groups consists of one or more cells of 1s only - i.e. no cells of 0s
* Every cell of 1 must be in at lest one group
* Overlapping groups are allowed
* Wrapping around is allowed
* Groups can be made of cells that are adjacent to one another. I.e. cells must be alongside, above or below one another
* Groups may not go diagonally
* Groups should be large as possible.