View source for Karnaugh map

{{Expand German|Karnaugh-Veitch-Diagramm|date=February 2018|topic=sci}}
{{short description|Graphical method to simplify Boolean expressions}}
{{Use dmy dates|date=April 2019|cs1-dates=y}}
{{Use list-defined references|date=January 2022}}
{{anchor|1|2|3|4|5|6|7|8}}<!-- parked anchors for redirects -->

[[File:Karnaugh Map Ex Improved Shading.png|thumb|right|An example Karnaugh map.  Note: Every rectangle encloses 2, 4 or 8 trues or 1's.  Also, the yellows rectangle wraps off the top and encloses the two bottom right cells.]]

A '''Karnaugh map''' ('''KM''' or '''K-map''') is a diagram that can be used to simplify a [[Boolean algebra]] expression. [[Maurice Karnaugh]] introduced the technique in 1953<ref name="Karnaugh_1953"/><ref name="Curtis_1962"/> as a refinement of [[Edward W. Veitch]]'s 1952 '''Veitch chart''',<ref name="Veitch_1952"/><ref name="Brown_2012"/> which itself was a rediscovery of [[Allan Marquand]]'s 1881 ''logical diagram''<ref name="Marquand_1881"/><ref name="Gardner_1958"/> or '''Marquand diagram'''.<ref name="Brown_2012"/> They are also known as '''Marquand–Veitch diagrams''',<ref name="Brown_2012"/> '''Karnaugh–Veitch (KV) maps''', and (rarely) '''Svoboda charts'''.<ref name="Klir_1972"/> An early advance in the history of [[formal logic]] methodology, Karnaugh maps remain relevant in the digital age, especially in the fields of [[logical circuit]] design and [[digital engineering]].<ref name="Brown_2012"/>

== Definition ==
A Karnaugh map reduces the need for extensive calculations by taking advantage of humans' pattern-recognition capability.<ref name="Karnaugh_1953"/> It also permits the rapid identification and elimination of potential [[race condition]]s.{{clarification needed|date=July 2023}}

The required Boolean results are transferred from a [[truth table]] onto a two-dimensional grid where, in Karnaugh maps, the cells are ordered in [[Gray code]],<ref name="Wakerly_1994"/><ref name="Brown_2012"/> and each cell position represents one combination of input conditions. Cells are also known as minterms, while each cell value represents the corresponding output value of the Boolean function. Optimal groups of 1s or 0s are identified, which represent the terms of a [[Canonical form (Boolean algebra)|canonical form]] of the logic in the original truth table.<ref name="Belton_1998"/> These terms can be used to write a minimal Boolean expression representing the required logic.

Karnaugh maps are used to simplify real-world logic requirements so that they can be implemented using the minimal number of [[logic gates]]. A [[sum-of-products expression]] (SOP) can always be implemented using [[AND gate]]s feeding into an [[OR gate]], and a [[product-of-sums expression]] (POS) leads to OR gates feeding an AND gate. The POS expression gives a complement of the function (if F is the function so its complement will be F').<ref name="Dodge_2016"/> Karnaugh maps can also be used to simplify logic expressions in software design. Boolean conditions, as used for example in [[Conditional (programming)|conditional statements]], can get very complicated, which makes the code difficult to read and to maintain. Once minimised, canonical sum-of-products and product-of-sums expressions can be implemented directly using AND and OR logic operators.<ref name="Cook_2012"/>

==Example==
Karnaugh maps are used to facilitate the simplification of [[Boolean algebra (logic)|Boolean algebra]] functions. For example, consider the Boolean function described by the following [[truth table]].

{| class="wikitable" style="text-align: center"
|+ Truth table of a function
|-
! &nbsp; !! ''A'' !! ''B'' !! ''C'' !! ''D'' !! {{tmath|f(A, B, C, D)}}
|-
! scope="row" |  0
| 0 || 0 || 0 || 0 || 0
|-
! scope="row" |  1
| 0 || 0 || 0 || 1 || 0
|-
! scope="row" |  2
| 0 || 0 || 1 || 0 || 0
|-
! scope="row" |  3
| 0 || 0 || 1 || 1 || 0
|-
! scope="row" |  4
| 0 || 1 || 0 || 0 || 0
|-
! scope="row" |  5
| 0 || 1 || 0 || 1 || 0
|-
! scope="row" |  6
| 0 || 1 || 1 || 0 || 1
|-
! scope="row" |  7
| 0 || 1 || 1 || 1 || 0
|-
! scope="row" |  8
| 1 || 0 || 0 || 0 || 1
|-
! scope="row" |  9
| 1 || 0 || 0 || 1 || 1
|-
! scope="row" | 10
| 1 || 0 || 1 || 0 || 1
|-
! scope="row" | 11
| 1 || 0 || 1 || 1 || 1
|-
! scope="row" | 12
| 1 || 1 || 0 || 0 || 1
|-
! scope="row" | 13
| 1 || 1 || 0 || 1 || 1
|-
! scope="row" | 14
| 1 || 1 || 1 || 0 || 1
|-
! scope="column" | 15
| 1 || 1 || 1 || 1 || 0
|}

Following are two different notations describing the same function in unsimplified Boolean algebra, using the Boolean variables {{mvar|A}}, {{mvar|B}}, {{mvar|C}}, {{mvar|D}} and their inverses.
* <math>f(A, B, C, D) = \sum_{}m_i, i \in \{6, 8, 9, 10, 11, 12, 13, 14\}</math> where <math>m_i</math> are the [[minterms]] to map (i.e., rows that have output 1 in the truth table).
* <math>f(A, B, C, D) = \prod_{}M_i, i \in \{0, 1, 2, 3, 4, 5, 7, 15\}</math> where <math>M_i</math> are the [[maxterms]] to map (i.e., rows that have output 0 in the truth table).

[[File:karnaugh_map_torus.svg|left|thumb|K-map drawn on a torus, and in a plane. The dot-marked cells are adjacent.]]
[[File:K-map minterms A.svg|thumb|right|K-map construction. Instead of the output values (the rightmost values in the truth table), this diagram shows a decimal representation of the input ABCD (the leftmost values in the truth table), therefore it is not a Karnaugh map.]]
[[File: Torus from rectangle.gif|thumb|right|In three dimensions, one can bend a rectangle into a torus.]]

=== {{Anchor|Karnaugh map}}Construction ===
In the example above, the four input variables can be combined in 16 different ways, so the truth table has 16 rows, and the Karnaugh map has 16 positions. The Karnaugh map is therefore arranged in a 4&nbsp;×&nbsp;4 grid.

The row and column indices (shown across the top and down the left side of the Karnaugh map) are ordered in [[Gray code]] rather than binary numerical order. Gray code ensures that only one variable changes between each pair of adjacent cells. Each cell of the completed Karnaugh map contains a binary digit representing the function's output for that combination of inputs.

=== Grouping ===
After the Karnaugh map has been constructed, it is used to find one of the simplest possible forms — a [[Canonical form (Boolean algebra)|canonical form]] — for the information in the truth table. Adjacent 1s in the Karnaugh map represent opportunities to simplify the expression. The minterms ('minimal terms') for the final expression are found by encircling groups of 1s in the map. Minterm groups must be rectangular and must have an area that is a power of two (i.e., 1,&nbsp;2,&nbsp;4,&nbsp;8...). Minterm rectangles should be as large as possible without containing any 0s. Groups may overlap in order to make each one larger. The optimal groupings in the example below are marked by the green, red and blue lines, and the red and green groups overlap. The red group is a 2&nbsp;×&nbsp;2 square, the green group is a 4&nbsp;×&nbsp;1 rectangle, and the overlap area is indicated in brown.

The cells are often denoted by a shorthand which describes the logical value of the inputs that the cell covers. For example, {{mvar|AD}} would mean a cell which covers the 2x2 area where {{mvar|A}} and {{mvar|D}} are true, i.e. the cells numbered 13, 9, 15, 11 in the diagram above. On the other hand, {{mvar|A}}{{overline|{{mvar|D}}}} would mean the cells where {{mvar|A}} is true and {{mvar|D}} is false (that is, {{overline|{{mvar|D}}}} is true).

The grid is [[torus|toroidally]] connected, which means that rectangular groups can wrap across the edges (see picture). Cells on the extreme right are actually 'adjacent' to those on the far left, in the sense that the corresponding input values only differ by one bit; similarly, so are those at the very top and those at the bottom. Therefore, {{mvar|A}}{{overline|{{mvar|D}}}} can be a valid term—it includes cells 12 and 8 at the top, and wraps to the bottom to include cells 10 and 14—as is {{overline|{{mvar|B}}}}{{overline|{{mvar|D}}}}, which includes the four corners.

===Solution===
[[File:K-map 6,8,9,10,11,12,13,14.svg|thumb|Diagram showing two K-maps. The K-map for the function f(A, B, C, D) is shown as colored rectangles which correspond to minterms. The brown region is an overlap of the red 2×2 square and the green 4×1 rectangle. The K-map for the inverse of f is shown as gray rectangles, which correspond to maxterms.]]

Once the Karnaugh map has been constructed and the adjacent 1s linked by rectangular and square boxes, the algebraic minterms can be found by examining which variables stay the same within each box.

For the red grouping:
* ''A'' is the same and is equal to 1 throughout the box, therefore it should be included in the algebraic representation of the red minterm.
* ''B'' does not maintain the same state (it shifts from 1 to 0), and should therefore be excluded.
* ''C'' does not change. It is always 0, so its complement, NOT-C, should be included. Thus, {{overline|{{mvar|C}}}} should be included.
* ''D'' changes, so it is excluded.

Thus the first minterm in the Boolean sum-of-products expression is {{mvar|A}}{{overline|{{mvar|C}}}}.

For the green grouping, ''A'' and ''B'' maintain the same state, while ''C'' and ''D'' change. ''B'' is 0 and has to be negated before it can be included. The second term is therefore {{mvar|A}}{{overline|{{mvar|B}}}}. Note that it is acceptable that the green grouping overlaps with the red one.

In the same way, the blue grouping gives the term {{mvar|BC}}{{overline|{{mvar|D}}}}.

The solutions of each grouping are combined: the normal form of the circuit is <math>A\overline{C} + A\overline{B} + BC\overline{D}</math>.

Thus the Karnaugh map has guided a simplification of
:<math>\begin{align}
              f(A, B, C, D) = {} &\overline{A}BC\overline{D} + A\overline{B}\,\overline{C}\,\overline{D} + A\overline{B}\,\overline{C}D + A\overline{B}C\overline{D} + {}\\
                                 &A\overline{B}CD + AB\overline{C}\,\overline{D} + AB\overline{C}D + ABC\overline{D}\\
                            = {} &A\overline{C} + A\overline{B} + BC\overline{D}
\end{align}</math>

It would also have been possible to derive this simplification by carefully applying the [[Boolean algebra (logic)#Axiomatizing Boolean algebra|axioms of Boolean algebra]], but the time it takes to do that grows exponentially with the number of terms.

===Inverse===
The inverse of a function is solved in the same way by grouping the 0s instead.<ref group="nb" name="NB_NotNeg"/>

The three terms to cover the inverse are all shown with grey boxes with different colored borders:
* {{font color|#5E200E|brown}}: {{overline|{{mvar|A}}}} {{overline|{{mvar|B}}}}
* {{font color|#926700|gold}}: {{overline|{{mvar|A}}}} {{overline|{{mvar|C}}}}
* {{font color|#064483|blue}}: {{mvar|BCD}}

This yields the inverse:
:<math>\overline{f(A,B,C,D)} = \overline{A}\,\overline{B} + \overline{A}\,\overline{C} + BCD</math>

Through the use of [[De Morgan's laws]], the [[product of sums]] can be determined:
:<math>\begin{align}
 f(A,B,C,D) &= \overline{\overline{f(A,B,C,D)}} \\
            &= \overline{\overline{A}\,\overline{B} + \overline{A}\,\overline{C} + BCD} \\
            &= \left(\overline{\overline{A}\,\overline{B}}\right) \left(\overline{\overline{A}\,\overline{C}}\right) \left(\overline{BCD}\right) \\
            &= \left(A + B\right)\left(A + C\right)\left(\overline{B} + \overline{C} + \overline{D}\right)
\end{align}</math>

===Don't cares===
[[File:K-map 6,8,9,10,11,12,13,14 don't care.svg|thumb|The value of {{tmath|f(A,B,C,D)}} for ''ABCD'' = 1111 is replaced by a "don't care". This removes the green term completely and allows the red term to be larger. It also allows blue inverse term to shift and become larger]]

Karnaugh maps also allow easier minimizations of functions whose truth tables include "[[Don't-care (logic)|don't care]]" conditions. A "don't care" condition is a combination of inputs for which the designer doesn't care what the output is. Therefore, "don't care" conditions can either be included in or excluded from any rectangular group, whichever makes it larger. They are usually indicated on the map with a dash or X.

The example on the right is the same as the example above but with the value of ''f''(1,1,1,1) replaced by a "don't care". This allows the red term to expand all the way down and, thus, removes the green term completely.

This yields the new minimum equation:
:<math>f(A,B,C,D) = A + BC\overline{D}</math>

Note that the first term is just {{mvar|A}}, not {{mvar|A}}{{overline|{{mvar|C}}}}. In this case, the don't care has dropped a term (the green rectangle); simplified another (the red one); and removed the race hazard (removing the yellow term as shown in the following section on race hazards).

The inverse case is simplified as follows:
:<math>\overline{f(A,B,C,D)} = \overline{A}\,\overline{B} + \overline{A}\,\overline{C} + \overline{A}D</math>

Through the use of [[De Morgan's laws]], the [[product of sums]] can be determined:
:<math>\begin{align}
 f(A,B,C,D) &= \overline{\overline{f(A,B,C,D)}} \\
            &= \overline{\overline{A}\,\overline{B} + \overline{A}\,\overline{C} + \overline{A}\,D} \\
            &= \left(\overline{\overline{A}\,\overline{B}}\right) \left(\overline{\overline{A}\,\overline{C}}\right) \left(\overline{\overline{A}\,D}\right) \\
            &= \left(A + B\right)\left(A + C\right)\left(A +\overline{D}\right)
\end{align}</math>

==Race hazards==
===Elimination===
Karnaugh maps are useful for detecting and eliminating [[race condition]]s. Race hazards are very easy to spot using a Karnaugh map, because a race condition may exist when moving between any pair of adjacent, but disjoint, regions circumscribed on the map. However, because of the nature of Gray coding, ''adjacent'' has a special definition explained above – we're in fact moving on a torus, rather than a rectangle, wrapping around the top, bottom, and the sides.
* In the example [[#Solution|above]], a potential race condition exists when ''C'' is 1 and ''D'' is 0, ''A'' is 1, and ''B'' changes from 1 to 0 (moving from the blue state to the green state). For this case, the output is defined to remain unchanged at 1, but because this transition is not covered by a specific term in the equation, a potential for a ''glitch'' (a momentary transition of the output to 0) exists.
* There is a second potential glitch in the same example that is more difficult to spot: when ''D'' is 0 and ''A'' and ''B'' are both 1, with C changing from 1 to 0 (moving from the blue state to the red state). In this case the glitch wraps around from the top of the map to the bottom.

[[File:K-map 6,8,9,10,11,12,13,14.svg|thumb|Race hazards are present in this diagram.]]
[[File:K-map 6,8,9,10,11,12,13,14 anti-race.svg|thumb|Above diagram with consensus terms added to avoid race hazards.]]

Whether glitches will actually occur depends on the physical nature of the implementation, and whether we need to worry about it depends on the application. In clocked logic, it is enough that the logic settles on the desired value in time to meet the timing deadline. In our example, we are not considering clocked logic.

In our case, an additional term of <math>A\overline{D}</math> would eliminate the potential race hazard, bridging between the green and blue output states or blue and red output states: this is shown as the yellow region (which wraps around from the bottom to the top of the right half) in the adjacent diagram.

The term is [[logic redundancy|redundant]] in terms of the static logic of the system, but such redundant, or [[consensus theorem|consensus terms]], are often needed to assure race-free dynamic performance.

Similarly, an additional term of <math>\overline{A}D</math> must be added to the inverse to eliminate another potential race hazard. Applying De Morgan's laws creates another product of sums expression for ''f'', but with a new factor of <math>\left(A + \overline{D}\right)</math>.

===2-variable map examples===
The following are all the possible 2-variable, 2&nbsp;×&nbsp;2 Karnaugh maps. Listed with each is the minterms as a function of <math display="inline">\sum m()</math> and the race hazard free (''see [[#Race hazards|previous section]]'') minimum equation. A minterm is defined as an expression that gives the most minimal form of expression of the mapped variables. All possible horizontal and vertical interconnected blocks can be formed. These blocks must be of the size of the powers of 2 (1, 2, 4, 8, 16, 32, ...). These expressions create a minimal logical mapping of the minimal logic variable expressions for the binary expressions to be mapped. Here are all the blocks with one field.

A block can be continued across the bottom, top, left, or right of the chart. That can even wrap beyond the edge of the chart for variable minimization. This is because each logic variable corresponds to each vertical column and horizontal row. A visualization of the k-map can be considered cylindrical. The fields at edges on the left and right are adjacent, and the top and bottom are adjacent. K-Maps for four variables must be depicted as a donut or torus shape. The four corners of the square drawn by the k-map are adjacent. Still more complex maps are needed for 5 variables and more.
<gallery perrow="5">
File:K-map 2x2 none.svg | Σ''m''(0); ''K'' = 0
File:K-map 2x2 1.svg | Σ''m''(1); ''K'' = ''A''′''B''′
File:K-map 2x2 2.svg | Σ''m''(2); ''K'' = ''AB''′
File:K-map 2x2 3.svg | Σ''m''(3); ''K'' = ''A''′''B''
File:K-map 2x2 4.svg | Σ''m''(4); ''K'' = ''AB''
File:K-map 2x2 1,2.svg | Σ''m''(1,2); ''K'' = ''B''′
File:K-map 2x2 1,3.svg | Σ''m''(1,3); ''K'' = ''A''′
File:K-map 2x2 1,4.svg | Σ''m''(1,4); ''K'' = ''A''′''B''′ + ''AB''
File:K-map 2x2 2,3.svg | Σ''m''(2,3); ''K'' = ''AB''′ + ''A''′''B''
File:K-map 2x2 2,4.svg | Σ''m''(2,4); ''K'' = ''A''
File:K-map 2x2 3,4.svg | Σ''m''(3,4); ''K'' = ''B''
File:K-map 2x2 1,2,3.svg | Σ''m''(1,2,3); ''K'' = ''A''' + ''B''′
File:K-map 2x2 1,2,4.svg | Σ''m''(1,2,4); ''K'' = ''A'' + ''B''′
File:K-map 2x2 1,3,4.svg | Σ''m''(1,3,4); ''K'' = ''A''′ + ''B''
File:K-map 2x2 2,3,4.svg | Σ''m''(2,3,4); ''K'' = ''A'' + ''B''
File:K-map 2x2 1,2,3,4.svg | Σ''m''(1,2,3,4); ''K'' = 1
</gallery>

=={{anchor|Marquand|Veitch|Svoboda|Mahoney|RKM|MEV|VEKM|VEM|MRM}}Related graphical methods==
{{Further|Logic optimization#Graphical methods}}

Related graphical minimization methods include:
* ''Marquand diagram'' (1881) by [[Allan Marquand]] (1853–1924)<ref name="Marquand_1881"/><ref name="Gardner_1958"/><ref name="Brown_2012"/><!-- a precursor to Karnaugh maps, needs to be covered explicitly inhere or in a separate article - until then parked here for completeness -->
* ''Veitch chart'' (1952) by [[Edward W. Veitch]] (1924–2013)<ref name="Veitch_1952"/><ref name="Brown_2012"/><!-- a precursor to Karnaugh maps, needs to be covered explicitly inhere or in a separate article -  until then parked here for completeness -->
* ''Svoboda chart'' (1956) by [[Antonín Svoboda (computer scientist)|Antonín Svoboda]] (1907–1980)<ref name="Klir_1972"/><!-- basically an application of Veitch charts -->
* ''[[Mahoney map]]'' (''M-map'', ''designation numbers'', 1963) by Matthew V. Mahoney (a reflection-symmetrical extension of Karnaugh maps for larger numbers of inputs)
* ''[[Reduced Karnaugh map]]'' (RKM) techniques (from 1969) like ''infrequent variables'', ''map-entered variables'' (MEV), ''variable-entered map'' (VEM) or ''variable-entered Karnaugh map'' (VEKM) by G. W. Schultz, [[Tom Osborne (engineer)|Thomas E. Osborne]], Christopher R. Clare, J. Robert Burgoon, Larry L. Dornhoff, William I. Fletcher, Ali M. Rushdi and others (several successive Karnaugh map extensions based on variable inputs for a larger numbers of inputs)
* ''[[Minterm-ring map]]'' (MRM, 1990) by Thomas R. McCalla (a three-dimensional extension of Karnaugh maps for larger numbers of inputs)

==See also==
* [[Algebraic normal form]] (ANF)
* [[Binary decision diagram]] (BDD), a data structure that is a compressed representation of a Boolean function
* [[Espresso heuristic logic minimizer]]
* [[List of Boolean algebra topics]]
* [[Logic optimization]]
* [[Punnett square]] (1905), a similar diagram in biology
* [[Quine–McCluskey algorithm]]
* [[Reed–Muller expansion]]
* [[Venn diagram]] (1880)
* [[Zhegalkin polynomial]]

== Notes ==
{{Reflist|group="nb"|refs=
<ref group="nb" name="NB_NotNeg">This should not be confused with the negation of the result of the previously found function.</ref>
}}

==References==
{{reflist|refs=
<ref name="Curtis_1962">{{cite book |title=A new approach to the design of switching circuits |author-first=Herbert Allen |author-last=Curtis |publisher=[[D. van Nostrand Company, Inc.]] |date=1962 |location=Princeton, New Jersey, USA |edition=1 |series=The Bell Laboratories Series |s2cid=57068910 |oclc=1036797958 |isbn=0-44201794-4 |id={{ISBN|978-0-44201794-1}}. ark:/13960/t56d6st0q <!-- |ia=newapproachtodes00curt -->}} (viii+635 pages) (NB. This book was reprinted by Chin Jih in 1969.)</ref>
<ref name="Karnaugh_1953">{{cite journal |author-last=Karnaugh |author-first=Maurice |author-link=Maurice Karnaugh |title=The Map Method for Synthesis of Combinational Logic Circuits |journal=[[Transactions of the American Institute of Electrical Engineers, Part I: Communication and Electronics]] |volume=72 |issue=5 |pages=593–599 |date=November 1953 |orig-date=1953-04-23, 1953-03-17 |id=Paper 53-217 |doi=10.1109/TCE.1953.6371932 |url=http://philectrosophy.com/documents/The%20Map%20Method%20For%20Synthesis%20of.pdf |access-date=2017-04-16 |url-status=dead |archive-url=https://web.archive.org/web/20170416232229/http://philectrosophy.com/documents/The%20Map%20Method%20For%20Synthesis%20of.pdf |archive-date=2017-04-16}} (NB. Also contains a short review by [[Samuel H. Caldwell]].)</ref>
<ref name="Brown_2012">{{cite book |title=Boolean Reasoning - The Logic of Boolean Equations |author-first=Frank Markham |author-last=Brown |edition=<!-- 2012 -->reissue of 2nd |publisher=[[Dover Publications, Inc.]] |location=Mineola, New York |date=2012 |orig-date=2003, 1990 |isbn=978-0-486-42785-0}} [<!-- 1st edition -->http://www2.fiit.stuba.sk/~kvasnicka/Free%20books/Brown_Boolean%20Reasoning.pdf<!-- https://web.archive.org/web/20170416231752/http://www2.fiit.stuba.sk/~kvasnicka/Free%20books/Brown_Boolean%20Reasoning.pdf -->]</ref>
<ref name="Wakerly_1994">{{cite book |title=Digital Design: Principles & Practices |author-last=Wakerly |author-first=John F. |date=1994 |publisher=[[Prentice Hall]] |location=New Jersey, USA |isbn=0-13-211459-3 |pages=48–49, 222}} (NB. The two page sections taken together say that K-maps are labeled with [[Gray code]]. The first section says that they are labeled with a code that changes only one bit between entries and the second section says that such a code is called Gray code.)</ref>
<ref name="Belton_1998">{{cite web |author-first=David |author-last=Belton |date=April 1998 |url=http://www.ee.surrey.ac.uk/Projects/Labview/minimisation/karrules.html |title=Karnaugh Maps – Rules of Simplification |access-date=2009-05-30 |url-status=live |archive-url=https://web.archive.org/web/20170418140519/http://www.ee.surrey.ac.uk/Projects/Labview/minimisation/karrules.html |archive-date=2017-04-18}}</ref>
<ref name="Dodge_2016">{{cite web |title=Simplifying Logic Circuits with Karnaugh Maps |author-first=Nathan B. |author-last=Dodge |date=September 2015 |publisher=[[The University of Texas at Dallas]], [[Erik Jonsson School of Engineering and Computer Science]] |url=http://www.utdallas.edu/~dodge/EE2310/lec5.pdf |access-date=2017-04-18 |url-status=live |archive-url=https://web.archive.org/web/20170418140824/https://www.utdallas.edu/~dodge/EE2310/lec5.pdf |archive-date=2017-04-18}}</ref>
<ref name="Cook_2012">{{cite web |author-last=Cook |author-first=Aaron |title=Using Karnaugh Maps to Simplify Code |publisher=Quantum Rarity |url=http://www.quantumrarity.com/archives/255 |access-date=2012-10-07 |url-status=live |archive-url=https://web.archive.org/web/20170418141624/http://www.quantumrarity.com/archives/255 |archive-date=2017-04-18}}</ref>
<ref name="Marquand_1881">{{cite journal |title=XXXIII: On Logical Diagrams for ''n'' terms |author-first=Allan |author-last=Marquand |author-link=Allan Marquand |journal=[[The London, Edinburgh, and Dublin Philosophical Magazine and Journal of Science]] |issue=75 |series=5 |date=1881 |volume=12 |doi=10.1080/14786448108627104 |pages=266–270 |url=http://www.tandfonline.com/doi/abs/10.1080/14786448108627104 |access-date=2017-05-15}} (NB. Quite many secondary sources erroneously cite this work as "A logical diagram for ''n'' terms" or "On a logical diagram for ''n'' terms".)</ref>
<ref name="Veitch_1952">{{cite book |author-last=Veitch |author-first=Edward Westbrook |title=Proceedings of the 1952 ACM national meeting (Pittsburgh) on - ACM '52 |chapter=A chart method for simplifying truth functions |author-link=Edward W. Veitch |location=New York, USA |publisher=[[Association for Computing Machinery]]  |pages=127–133 |date=1952-05-03 |orig-year=1952-05-02 |doi=10.1145/609784.609801|s2cid=17284651 }}</ref>
<ref name="Klir_1972">{{cite book |title=Introduction to the Methodology of Switching Circuits |chapter=Reference Notations to Chapter 2 |author-first=George Jiří |author-last=Klir |author-link=George Jiří Klir |edition=1 |date=May 1972 |lccn=72-181095 |isbn=0-442-24463-0 |id=C4463-000-3 |publisher=Litton Educational Publishing, Inc. / [[D. van Nostrand Company]] |location=Binghamton, New York, USA |page=84}} (xvi+573+1 pages)</ref>
<ref name="Gardner_1958">{{cite book |title=Logic Machines and Diagrams |chapter=6. Marquand's Machine and Others |author-first=Martin |author-last=Gardner |author-link=Martin Gardner |publisher=[[McGraw-Hill Book Company, Inc.]] |publication-place=New York, USA |date=1958 |edition=1 |isbn=1-11784984-8 |id=ark:/13960/t5cc1sj6b |lccn=58-6683 |pages=104–116 |url=https://archive.org/details/logicmachinesdia227gard}} (x+157 pages)</ref>
}}

==Further reading==
* {{cite book |author-last=Katz |author-first=Randy Howard |author-link=Randy Katz |title=Contemporary Logic Design |orig-date=1994 |publisher=[[The Benjamin/Cummings Publishing Company]] |isbn=0-8053-2703-7 |pages=[https://archive.org/details/contemporarylogi00katz/page/70 70–85] |date=1998 |volume=26 |issue=5 |url=https://archive.org/details/contemporarylogi00katz/page/70}}
* {{cite book |author-last=Vingron |author-first=Shimon Peter |title=Switching Theory: Insight Through Predicate Logic |orig-date=2003-11-05 |publisher=[[Springer-Verlag]] |location=Berlin, Heidelberg, New York |isbn=3-540-40343-4 |pages=57–76 |chapter=Karnaugh Maps |date=2004}}
* {{cite book |author-last=Wickes |author-first=William E. |title=Logic Design with Integrated Circuits |chapter=3.5. Veitch Diagrams |url=https://archive.org/details/logicdesignwithi00wick_0 |url-access=registration |date=1968 |publisher=[[John Wiley & Sons]] |location=New York, USA |lccn=68-21185 |pages=[https://archive.org/details/logicdesignwithi00wick_0/page/36 36–49] |quote-page=36 |quote=[…] a refinement of the [[Venn diagram]] in that circles are replaced by squares and arranged in a form of matrix. The Veitch diagram labels the squares with the [[minterm]]s. [[Maurice Karnaugh|Karnaugh]] assigned 1s and 0s to the squares and their labels and deduced the numbering scheme in common use.}}
* {{cite web |title=Reed-Muller Logic |work=Logic 101 |at=Part 3 |author-first=Clive "Max" |author-last=Maxfield |date=2006-11-29 |publisher=[[EE Times]] |url=http://www.eetimes.com/author.asp?section_id=216&doc_id=1274545 |access-date=2017-04-19 |url-status=live |archive-url=https://web.archive.org/web/20170419235904/http://www.eetimes.com/author.asp?section_id=216&doc_id=1274545 |archive-date=2017-04-19}}
* {{cite book |author-last1=Lind |author-first1=Larry Frederick |author-last2=Nelson |author-first2=John Christopher Cunliffe |title=Analysis and Design of Sequential Digital Systems |chapter=Section 2.3 |date=1977 |publisher=[[Macmillan Press]] |isbn=0-33319266-4 |url=https://archive.org/details/AnalysisDesignOfSequentialDigitalSystems/}} (146 pages)
* {{cite journal |author-first=Michel Elizabeth |author-last=Holder |title=A modified Karnaugh map technique |journal=[[IEEE Transactions on Education]] |volume=48 |issue=1 |pages=206–207 |date=March 2005 |orig-date=2005-02-14 |issn=0018-9359 |eissn=1557-9638 |doi=10.1109/TE.2004.832879 |s2cid=25576523 |publisher=[[IEEE]] |bibcode=2005ITEdu..48..206H |url=https://www.researchgate.net/publication/3050984}}
* {{cite book |author-first=Joseph |author-last=Cavanagh |title=Computer Arithmetic and Verilog HDL Fundamentals |publisher=[[CRC Press]] |date=2008 |edition=1}}
* {{cite book |author-first1=Zvi |author-last1=Kohavi |author-first2=Niraj K. |author-last2=Jha |title=Switching and Finite Automata Theory |publisher=[[Cambridge University Press]] |date=2009 |edition=3 |isbn=978-0-521-85748-2}}
* {{cite book |title=KV-Diagramme in der Schaltalgebra - Verknüpfungen, Beweise, Normalformen, schaltalgebraische Umformungen, Anschauungsmodelle, Paradebeispiele |language=de |trans-title=KV diagrams in Boolean algebra - relations, proofs, normal forms, algebraic transformations, illustrative models, typical examples |author-first=Jürgen |author-last=Grund |date=2011 |publisher=viademica Verlag |publication-place=Berlin, Germany |type=e-book |format=Windows/Mac executable or [[Adobe Flash]]-capable browser on CD-ROM |edition=1 |isbn=978-3-939290-08-7 |url=http://www.viademica.de/content/minititel/263.pdf |access-date=2022-11-26 |url-status=live |archive-url=https://web.archive.org/web/20221112172143/http://www.viademica.de/content/minititel/263.pdf |archive-date=2022-11-12}} [http://www.viademica.de/content/buchkatalog/detail.php?id=263<!-- https://web.archive.org/web/20221126095943/http://www.viademica.de/content/buchkatalog/detail.php?id=263 -->] (282 pages with 14 animations)

== External links ==
{{sisterlinks}}
* [http://gandraxa.com/detect_overlapping_subrectangles.xml Detect Overlapping Rectangles], by Herbert Glarner.
* [http://www.sccs.swarthmore.edu/users/06/adem/engin/e15/lab1/ Using Karnaugh maps in practical applications], Circuit design project to control traffic lights.
* [https://www.fullchipdesign.com/kmap2v.htm K-Map Tutorial for 2,3,4 and 5 variables ]
* [http://iris.elf.stuba.sk/JEEEC/data/pdf/07-08_105-08.pdf POCKET–PC BOOLEAN FUNCTION SIMPLIFICATION, Ledion Bitincka — George E. Antoniou]
* [http://www.youtube.com/watch?v=5_dxk2FqEnY K-Map troubleshoot]
* {{cite web|url= https://www.csusm.edu/stemsc/handouts/project2_handouts/cs231_karnaugh_maps.pdf|title= Guide To The K-Map (Karnaugh Map|at= [https://www.csusm.edu/ California State University San Marcos]|access-date= 18 December 2023}}

[[Category:Boolean algebra]]
[[Category:Diagrams]]
[[Category:Electronics optimization]]
[[Category:Logic in computer science]]
{{Diagrams in logic}}