NIST

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