Karnaugh map
From Wikipedia, the free encyclopedia
|
Image:K-map 6,8,9,10,11,12,13,14 anti-race.svg
An example Karnaugh map
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. A Karnaugh map is unique in that only one variable changes value between squares; in other words, the rows and columns are ordered according to the principles of Gray code.
History and nomenclatureThe Karnaugh map was invented in 1952 by Edward W. Veitch and developed further 1953 by Maurice Karnaugh, a telecommunications engineer at Bell Labs. Usage in boolean logicNormally, 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 also help teach about Boolean functions and minimization. Properties
A Karnaugh map may have any number of variables, but usually works best when there are only a few - between 2 and 6 for example. Each variable contributes two possibilities to each possibility of every other variable in the system. Karnaugh maps are organized so that all the possibilities of the system are arranged in a grid form and between two adjacent boxes only one variable can change value. This is what allows it to reduce hazards. When using a Karnaugh map to derive a minimized function, one "covers" the 1s on the map by rectangular "coverings" that contain a number of boxes equal to a power of 2 (for example, 4 boxes in a line, 4 boxes in a square, 8 boxes in a rectangle, etc). Once a person has covered the 1s, a term of a sum of products is produced by finding the variables that do not change throughout the entire covering, and taking a 1 to mean that variable and a 0 as the complement of that variable. Doing this for every covering gives you a matching function. One can also use zeros to derive a minimized function. The procedure is identical to the procedure for ones except that each term is a term in a product of sums - and a 1 means the complement of the variable while 0 means the variable non-complemented. Each square in a Karnaugh map corresponds to a minterm (and maxterm). The picture to the right shows the location of each minterm on the map. A Venn diagram of four sets—labeled A, B, C, and D — is shown to the right that corresponds to the 4-variable K-map of minterms just above it:
Minterm m9 is ABCD=1001 which corresponds to where only sets A & D intersect. Thus, a specific minterm identifies a unique intersection of all four sets. The Venn diagram can include an infinite number of sets and still correspond to the respective Karnaugh maps. With increasing number of sets and variables, both Venn diagram and Karnaugh map increase in complexity to draw and manage. Size of mapIn a Karnaugh map with Failed to parse (Missing texvc executable; please see math/README to configure.): n
variables, a Boolean term mentioning Failed to parse (Missing texvc executable; please see math/README to configure.): k
of them will have a corresponding rectangle of area Failed to parse (Missing texvc executable; please see math/README to configure.): 2^{n-k}
. Common sized maps are of 2 variables which is a 2x2 map; 3 variables which is a 2x4 map; and 4 variables which is a 4x4 map (shown below).
ExampleConsider the following boolean function of four variables (which, in binary, has a maximum number of combinations of 16):
lists the minterms to map (i.e., which rows have output 1 in the truth table). Truth tableUsing the defined minterms, the truth table can be created:
MapThe 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. Image:K-map 6,8,9,10,11,12,13,14.svg
K-map showing minterms and boxes covering the desired minterms
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 Failed to parse (Missing texvc executable; please see math/README to configure.): f=0 when Failed to parse (Missing texvc executable; please see math/README to configure.): A=0 , Failed to parse (Missing texvc executable; please see math/README to configure.): B=0 , Failed to parse (Missing texvc executable; please see math/README to configure.): C=0 , Failed to parse (Missing texvc executable; please see math/README to configure.): D=0 . Similarly we mark the bottom right corner as 1 because Failed to parse (Missing texvc executable; please see math/README to configure.): A=1 , Failed to parse (Missing texvc executable; please see math/README to configure.): B=0 , Failed to parse (Missing texvc executable; please see math/README to configure.): C=1 , Failed to parse (Missing texvc executable; please see math/README to configure.): D=0 gives Failed to parse (Missing texvc executable; please see math/README to configure.): 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 1s in the map. The encirclings must be rectangular and must have an area that is a power of two (i.e. 1, 2, 4, 8, …). The rectangles should be as large as possible without containing any 0s. 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) we find that:
maintains the same state (1) in the whole encircling, therefore it should be included in the term for the red encircling.
does not maintain the same state (it shifts from 1 to 0), and should therefore be excluded.
does not change: it is always 0.
changes. Thus the first term in the Boolean expression is Failed to parse (Missing texvc executable; please see math/README to configure.): A\overline{C} . For the green encircling we see that Failed to parse (Missing texvc executable; please see math/README to configure.): A
and Failed to parse (Missing texvc executable; please see math/README to configure.): B
maintain the same state, but Failed to parse (Missing texvc executable; please see math/README to configure.): C
and Failed to parse (Missing texvc executable; please see math/README to configure.): D
change. Failed to parse (Missing texvc executable; please see math/README to configure.): B
is 0 and has to be negated before it can be included. Thus the second term is Failed to parse (Missing texvc executable; please see math/README to configure.): A\overline{B}
. In the same way, the blue rectangle gives the term Failed to parse (Missing texvc executable; please see math/README to configure.): BC\overline{D}
and so the whole expression is: Failed to parse (Missing texvc executable; please see math/README to configure.): A\overline{C} + A\overline{B} + BC\overline{D}
. Toroidally connectedThe grid is toroidally connected, which means that the rectangles can wrap around edges, so Failed to parse (Missing texvc executable; please see math/README to configure.): A\overline{D} is a valid term, although not part of the minimal set—this covers minterms 8, 10, 12, & 14. Perhaps the hardest-to-visualize wrap-around term is Failed to parse (Missing texvc executable; please see math/README to configure.): \overline{B}\,\overline{D} which covers the four corners—this covers minterms 0, 2, 8, 10. InverseThe inverse of a function is solved in the same way by encircling the 0s instead. The three terms to cover the inverse are all shown with grey boxes with different colored borders:
Don't caresImage:K-map 6,8,9,10,11,12,13,14 don't care.svg
The minterm 15 is dropped and replaced as a don't care, this removes the green term completely but restricts the blue inverse term
Karnaugh maps also allow easy minimizations of functions whose truth tables include "don't care" conditions (that is sets of inputs for which the designer doesn't care what the output is) because "don't care" conditions can be included in a ring to make it larger but do not have to be ringed. They are usually indicated on the map with a hyphen/dash/X in place of the number. The value can be a "0," "1," or the hyphen/dash/X depending on if one can use the "0" or "1" to simplify the KM more. If the "don't cares" don't help you simplify the KM more, then use the hyphen/dash/X. The example to the right is the same above example but with minterm 15 dropped and replaced as 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:
not Failed to parse (Missing texvc executable; please see math/README to configure.): A\overline{C}
. In this case, the don't care has dropped a term (the green); simplified another (the red); and removed the race hazard (the yellow as shown in a following section). Also, since the inverse case no longer has to cover minterm 15, minterm 7 can be covered with Failed to parse (Missing texvc executable; please see math/README to configure.): \left(A + \overline{D}\right)
rather than Failed to parse (Missing texvc executable; please see math/README to configure.): \left(\overline{B} + \overline{C} + \overline{D}\right)
with similar gains.
Race hazardsImage:K-map 6,8,9,10,11,12,13,14 anti-race.svg
Above k-map with the Failed to parse (Missing texvc executable; please see math/README to configure.): A\overline{D} term added to avoid race hazards
Karnaugh maps are useful for detecting and eliminating race hazards. They are 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.
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 Failed to parse (Missing texvc executable; please see math/README to configure.): 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. 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 Failed to parse (Missing texvc executable; please see math/README to configure.): \left(A + \overline{D}\right) must be added to the inverse case to eliminate another potential race hazard. 2 variable mapsThe following are all the possible 2 variable, 2x2 Karnaugh maps. Listed with each is the minterms as a function of Failed to parse (Missing texvc executable; please see math/README to configure.): E() and the race hazard free (see previous section) minimum equation.
Problems with Karnaugh mapsKarnaugh maps generally become more cluttered and hard to interpret when adding more variables. A general rule is that Karnaugh maps work well for up to four variables, and shouldn't be used at all for more than six variables. For expressions with larger numbers of variables, the Quine-McCluskey algorithm can be used. Nowadays in general the minimization process is carried out by computer, for which the Espresso heuristic logic minimizer has become the standard minimization program. SoftwareThere are many software applications to solve K-Map problems. One such free program for Linux and Windows platform is GKMap. See also
External links
ApplicationsReferences
de:Karnaugh-Veitch-Diagramm et:Karnaugh' kaart es:Mapa de Karnaugh fr:Table de Karnaugh gl:Mapa de Karnaugh it:Mappa di Karnaugh he:מפת קרנו hu:Karnaugh-tábla nl:Karnaugh-diagram ja:カルノー図 pl:Metoda Karnaugh pt:Mapa de Karnaugh ro:Diagramă Karnaugh ru:Карта Карно sr:Карноова карта fi:Karnaugh’n kartta sv:Karnaughdiagram vi:Bìa Karnaugh |
