# Karnaugh map

(algorithm)

**Definition:**
A method for minimizing a *boolean expression*, usually aided by a rectangular map of the value of the expression for all possible input values. Input values are arranged in a *Gray code*. Maximal rectangular groups that cover the inputs where the expression is true give a minimum implementation.

**Also known as** Veitch diagram, KV diagram.

**Aggregate child** (... is a part of or used in me.)

*Gray code*.

**See also**
*Venn diagram*.

*Note:
"Karnaugh" is pronounced "car-no". *

*
** In the example, "*" means "don't care", that is, it doesn't matter what the function value is for those inputs. This expression may be realized as AB' + AD + BC'D + B'CD'. Some expressions may be implemented more compactly by grouping the zeros, possibly including "don't care" cells, and negating the final output. The positive implementation is smaller for this expression.*

Author: SKS

## Implementation

(Java) applet demonstrating minimization.
## More information

A primer on Karnaugh maps motivated by minimizing logic. An interactive quiz.

**Maurice Karnaugh**, *The Map Method for Synthesis of Combinational Logic Circuits*, Trans. AIEE. pt I, 72(9):593-599, November 1953.

Go to the
Dictionary of Algorithms and Data
Structures home page.

If you have suggestions, corrections, or comments, please get in touch
with Paul Black.

Entry modified 6 May 2019.

HTML page formatted Mon May 6 10:22:33 2019.

Cite this as:

Sandeep Kumar Shukla, "Karnaugh map", in
*Dictionary of Algorithms and Data Structures* [online], Paul E. Black, ed. 6 May 2019. (accessed TODAY)
Available from: https://www.nist.gov/dads/HTML/karnaughmap.html