// Karnaugh Maps

In 1953, Maurice Karnaugh invented a form of logic diagram called a Karnaugh Map, which provides an alternative technique for representing Boolean functions:

A	B	F
0	0	0
0	1	0
1	0	0
1	1	1

	A'B'	A'B	AB	AB'
			√

---

The Karnaugh Map comprises a box for every line in the truth table.The binary values above the boxes are those associated with the a and b inputs. The Karnaugh Map's input values must be ordered such that the values for adjacent columns vary only by one bit: for example, 00₂,01₂,11₂,10₂. This ordering is known as a Gray Code, and it is a key factor in the way in which Karnaugh Maps work.

The y column in the truth table shows all the 0 and 1 values associated with the gate's output. Similarly, all of the output values could be entered into the Karnaugh Map's boxes.However, for reasons of clarity, it is common for only a single set of values to be used, either 1's or √'s.

Similar maps can be constructed for 3-input and 4-input functions. In the case of a 4-input map, the values associated with the c and d inputs must also be orderes as a gray Code, they must be ordered in such a way that the values for adjacent rows vary by only a single bit.

3 inputs    A'B' A'B AB AB' C' C

z4-inputs    A'B' A'B AB AB' C'D' C'D CD CD'

// Minimization Using Karnaugh Maps

Karnaugh Maps are useful in the simplification and minimization of Boolean functions.

The input values associated with each row and column in the map differ by only one bit, any pair of horizontally or vertically adjacent boxes corresponds to the minterms that differ by only a single variable. Such pairs of minterms can be grouped together and the variable that differs can be discarded:

// Grouping Minterms

In the case of a 3-input Karnaugh Map, any two horizontally or vertically adjacent minterms each composed of three variables, can be combined to form a new product term composed of only two variables. Similarly, in the case of a 4-input map, any two adjacent minterms, each composed of four variables, can be combined to form a new product term composed of only three variables. Additionally the √s associated with the minterms can be used to form multiple groups:

---

Groupings can also be formed from four adjacent minterms, in which case two redundant variables can be discarded.

In fact, any group of 2ⁿ adjacent minterms can be gathered together where n is a positive integer.

Karnaugh Map values are ordered so that the values associated with adjacent rows and columns differ by only a single bit. One result of this ordering is that the top and bottom rows are also separated by only a single bit (think of rolling the map into a cylinder such that the top and bottom edged touch or the right and left edges touch).