The Karnaugh map, also known as a Veitch diagram (K-map or KV-map for short), is a tool to facilitate management of Boolean algebraic expressions.
History and nomenclature
The Karnaugh map was invented in 1953 by Maurice Karnaugh, a telecommunications engineer at Bell Labs.
Usage in binary math
Normally, extensive calculations are required to obtain the minimal expression of a Boolean function, but one can use a Karnaugh map instead.
Problem solving uses
- Karnaugh maps make use of the human brain's excellent pattern-matching capability to decide which terms should be combined to get the simplest expression.
- K-maps permit the rapid identification and elimination of potential race hazards, something that boolean equations alone cannot do.
- A Karnaugh map is an excellent aid for simplification of up to six variables, but with more variables it becomes hard even for our brain to discern optimal patterns.
Karnaugh maps also help teach about Boolean functions and minimization.
Example
Consider the following function:
- f(A, B, C, D) = E(4, 8, 9, 10, 11, 12, 14, 15)
This function has this truth table:
A B C D f |
The input variables can be combined in 16 different ways, so our Karnaugh map has to have 16 positions. The most convenient way to arrange this is in a 4x4 grid.
The binary digits in the map represent the function's output for any given combination of inputs. We write 0 in the upper leftmost corner of the map because f = 0 when A = 0, B = 0, C = 1, D = 0. Similarly we mark the bottom right corner as 1 because A = 1, B = 0, C = 0, D = 0 gives f = 1. Note that the values are ordered in a gray code, so that precisely one variable flips between any pair of adjacent cells.
After the Karnaugh map has been constructed our next task is to find the minimal terms to use in the final expression. These terms are found by encircling groups of 1's in the map. The encirclings must be rectangular karnaugh map and must have an area that is a positive power of two (i.e. 2, 4, 8, …). The rectangles should be as large as possible without containing any 0's. The optimal encirclings in this map are marked by the green, red and blue lines.
For each of these encirclings we find those variables that have the same state in each of the fields in the encircling. For the first encircling (the red one) karnaugh map sum of the product we find that:
- The variable A maintains the same state (1) in the whole encircling, therefore it should be included in the term for the red encircling.
- Variable B does not maintain the same state (it shifts from 1 to 0), and should therefore be excluded.
- C does not change.
- D changes.
Thus the first term in the Boolean expression is AC.
For the green encircling we see that A and B maintain the same state, but C and D changes. B is 0 and has to be negated before it can be included. Thus the second term is AB'.
In the same way, the blue rectangle gives the term BC'D' and so the whole expression is: AC + AB′+ BC′D′.
The grid is toroidally connected, which means that the rectangles can wrap around edges, so ABD′ is a valid term, although not part of the minimal set.
The inverse of a function is solved in the same way by encircling the 0's instead.
In a Karnaugh map with n variables, a Boolean term mentioning k of them will have a corresponding rectangle of area 2n-k.
Multiprocessor systems
In a multiprocessor computer with 64 processors, contiguous processors could be optimally placed following a three dimensional 4x4 Karnaugh cube. Every processor /node coordinates are their Karnaugh coordinates and the whole set is a hypercube with six dimensions. The difference between the coordinates of any two physically contiguous processors is always one bit.
Race hazards
Karnaugh maps are useful for detecting and eliminating race hazards.
- In the above example, a potential race condition exists when C and D are both 0, A is a 1, and B changes from a 0 to a 1 (moving from the green state to the blue 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. This is very easy to spot using a Karnaugh map, because a race condition may exist when moving between any pair of adjacent, but disjointed, regions circled on the map.
Further examples
- A harder possible glitch to spot is if D was 0 and A and B were both 1, with C changing from 0 to 1. In this case the glitch wraps around from the bottom of the map to the top of the map.
Whether these glitches do occur depends on the physical nature of the implementation, and whether we need to worry about it depends on the application.
In this case, an additional term of +AD' would eliminate the potential race hazard, bridging between the green and blue output states or blue and red output states.
The term is redundant in terms of the static logic of the system, but such redundant terms are often needed to assure race-free dynamic performance.
When not to use K-maps
For expressions having more than four variables, the Quine-McCluskey algorithm, also called the method of prime implicants, should be used.
This algorithm uses a deterministic approach to simplification of boolean expressions. Thus, following the steps of this alternate algorithm ensures that the simplest expression can be found.
- This alternate algorithm is especially useful for creating software programs that simplify any given boolean expression.
See also
- list of Boolean algebra topics
- Venn diagram
- Quine-McCluskey algorithm
External links
- Karnaugh Maps 101
- Open source Karnaugh Maps minimization software
- Commercial software advertisement for Karnaugh Minimizer
References
- Maurice Karnaugh, The Map Method for Synthesis of Combinational Logic Circuits, Trans. AIEE. part I, 72(9):593-599, November 1953.
Electronics Topics
The field of electronics is the study and use of systems that operate by controlling the flow of electrons or other electrically charged particles in devices such as thermionic valves and semiconductors. The design and construction of electronic circuits to solve practical problems is part of the fields of electronic engineering, and the hardware design side of computer engineering. The study of new semiconductor devices and their technology is sometimes considered as a branch of physics.
# - A | B | Co - Cz | C - Cm | D
Em - F | E - El | G - H | I - K | L - Ma
