Karnaugh map

Uses your system voice; voice and rate in settings.

Snapshot

≈ 12 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

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 as a refinement of Edward W. Veitch's 1952 Veitch chart, which itself was a rediscovery of Allan Marquand's 1881 logical diagram or Marquand diagram. They are also known as Marquand–Veitch diagrams, Karnaugh–Veitch (KV) maps, and (rarely) Svoboda charts. 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.

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 as a refinement of Edward W. Veitch's 1952 Veitch chart, which itself was a rediscovery of Allan Marquand's 1881 logical diagram or Marquand diagram. They are also known as Marquand–Veitch diagrams, Karnaugh–Veitch (KV) maps, and (rarely) Svoboda charts. 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.

Example

Karnaugh maps are used to facilitate the simplification of Boolean algebra functions. For example, consider the Boolean function described by the following truth table. Following are two different notations describing the same function in unsimplified Boolean algebra, using the Boolean variables , , , and their inverses. f(A, B, C, D) = \sum_{}m_i, i \in \{6, 8, 9, 10, 11, 12, 13, 14\} where m_i are the minterms to map (i.e., rows that have output 1 in the truth table). f(A, B, C, D) = \prod_{}M_i, i \in \{0, 1, 2, 3, 4, 5, 7, 15\} where M_i are the maxterms to map (i.e., rows that have output 0 in the truth table).

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 × 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.

Solution

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, should be included. D changes, so it is excluded. Thus the first minterm in the Boolean sum-of-products expression is . 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 . Note that it is acceptable that the green grouping overlaps with the red one. In the same way, the blue grouping gives the term . The solutions of each grouping are combined: the normal form of the circuit is A\overline{C} + A\overline{B} + BC\overline{D} . Thus the Karnaugh map has guided a simplification of \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} It would also have been possible to derive this simplification by carefully applying the 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. The three terms to cover the inverse are all shown with grey boxes with different colored borders: : : : This yields the inverse: \overline{f(A,B,C,D)} = \overline{A}\,\overline{B} + \overline{A}\,\overline{C} + BCD Through the use of De Morgan's laws, the product of sums can be determined: \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}

Don't cares

Karnaugh maps also allow easier minimizations of functions whose truth tables include "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: f(A,B,C,D) = A + BC\overline{D} Note that the first term is just , not . 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: \overline{f(A,B,C,D)} = \overline{A}\,\overline{B} + \overline{A}\,\overline{C} + \overline{A}D Through the use of De Morgan's laws, the product of sums can be determined: \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}

Race hazards

Elimination

Karnaugh maps are useful for detecting and eliminating race conditions. 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 above, a potential race condition exists when both C and D are 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. 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 A\overline{D} 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 redundant in terms of the static logic of the system, but such redundant, or consensus terms, are often needed to assure race-free dynamic performance. Similarly, an additional term of \overline{A}D 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 \left(A + \overline{D}\right) .

2-variable map examples

The following are all the possible 2-variable, 2 × 2 Karnaugh maps. Listed with each is the minterms as a function of \sum m() and the race hazard free (see 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. 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

Related graphical methods

Related graphical minimization methods include: Marquand diagram (1881) by Allan Marquand (1853–1924) Veitch chart (1952) by Edward W. Veitch (1924–2013) Svoboda chart (1956) by Antonín Svoboda (1907–1980) 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, 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

References

Further reading

(146 pages) (282 pages with 14 animations) K-Map troubleshoot

Text derived from https://en.wikipedia.org/w/index.php?oldid=1362915698 under CC BY-SA 4.0; modifications have been made.

Sources cited in this revision

8 named source(s) extracted from the cited revision. A source with no author is shown by its publication; nothing is invented.