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.

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

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.