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 nomenclature
The Karnaugh map was invented in 1953 by Maurice Karnaugh, a telecommunications engineer at Bell Labs.
Usage in boolean logic
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.
Properties
A mapping of minterms on a Karnaugh map. The arrows indicate which squares can be thought of as "switched" (rather than being in a normal sequential order).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 ones 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 ones, that person can produce a term of a sum of products 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 compliment of the variable, while 0 means the variable non-complimented.
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.
Example
Consider the following function1:
f(A, B, C, D) = E(4, 8, 9, 10, 11, 12, 14, 15)
The values inside E tell us which rows have output 1.
This function has this truth table:
A B C D f
0. 0 0 0 0 0
1. 0 0 0 1 0
2. 0 0 1 0 0
3. 0 0 1 1 0
4. 0 1 0 0 1
5. 0 1 0 1 0
6. 0 1 1 0 0
7. 0 1 1 1 0
8. 1 0 0 0 1
9. 1 0 0 1 1
10. 1 0 1 0 1
11. 1 0 1 1 1
12. 1 1 0 0 1
13. 1 1 0 1 0
14. 1 1 1 0 1
15. 1 1 1 1 1
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.