(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
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.
If you have suggestions, corrections, or comments, please get in touch with Paul Black.
Entry modified 24 September 2012.
HTML page formatted Mon Feb 2 13:10:39 2015.
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