Karnaugh

Karnaugh, in the context of digital logic, most often refers to the Karnaugh map, a visual method for simplifying Boolean expressions. The Karnaugh map is named after Maurice Karnaugh, an American physicist and engineer who introduced the technique at Bell Labs in the early 1950s.

A Karnaugh map translates a Boolean function of n variables into a two-dimensional grid with 2^n cells. The cells correspond to the minterms (input combinations). The grid is arranged in Gray code order so that adjacent cells differ by only one variable. Common instantiations are 2-variable maps (2x2), 3-variable maps (2x4), and 4-variable maps (4x4).

To minimize, one marks the cells corresponding to outputs of 1 (and optionally marks don't-care terms). Groups of 1s are formed into the largest possible rectangles whose side lengths are powers of two (1, 2, 4, etc.) and which wrap around the edges. Each group yields a product term by dropping the variables that stay constant within the group. The final minimized sum of products is the OR of these terms. Don’t-care terms can be included in groups to achieve larger rectangles and simpler expressions; otherwise, groups may be reduced.

Limitations and scope: The Karnaugh map is intuitive and effective for functions with up to about four variables; for larger functions or more complex designs, algorithmic methods such as the Quine–McCluskey procedure are typically used. Karnaugh maps remain widely taught in introductory digital logic and are used in circuit design and debugging.

See also: Karnaugh map, Boolean algebra, Gray code, Quine–McCluskey algorithm.