Karnaugh map


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". (Pronunciation confirmed by a phone call to Polytechnic University, NJ, the school where he taught until recently. Paul E. Black 18 Dec 2000)

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 implemented 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

More information

A primer on Karnaugh maps motivated by minimizing logic. Dean Johnson's 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 20 April 2022.
HTML page formatted Wed Apr 20 09:32:15 2022.

Cite this as:
Sandeep Kumar Shukla, "Karnaugh map", in Dictionary of Algorithms and Data Structures [online], Paul E. Black, ed. 20 April 2022. (accessed TODAY) Available from: