(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. Jack Dillon's interactive practicer (Flash).
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 E. Black.
Entry modified 29 September 2005.
HTML page formatted Mon Sep 11 09:46:04 2006.
Cite this as:
Sandeep Kumar Shukla, "Karnaugh map", in
Dictionary of Algorithms and Data
Structures [online], Paul E. Black, ed.,
U.S. National Institute of
Standards and Technology. 29 September 2005. (accessed TODAY)
Available from: http://www.nist.gov/dads/HTML/karnaughmap.html
