(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". (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.
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: https://www.nist.gov/dads/HTML/karnaughmap.html