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 which cover the inputs where the expression is true give a minimum implementation.

See also Venn diagram.

Note: 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

Implementation

(Java)

More information

An interactive quiz.

Go to the Algorithms, Data Structures, and Problems home page.

If you have suggestions, corrections, or comments, please get in touch with Paul E. Black ([email protected]).

Entry modified Thu Jun 1 14:42:37 2000.
HTML page formatted Thu Jul 6 09:52:24 2000.

This page's URL is http://hissa.nist.gov/dads/HTML/karnaughmap.html