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 24 September 2012.
HTML page formatted Tue May 6 13:48:55 2014.

Cite this as:
Sandeep Kumar Shukla, "Karnaugh map", in Dictionary of Algorithms and Data Structures [online], Vreda Pieterse and Paul E. Black, eds. 24 September 2012. (accessed TODAY) Available from: http://www.nist.gov/dads/HTML/karnaughmap.html