Karnaugh Map

KARNAUGH MAP

• The “Karnaugh map” is a graphical method which provides a systematic method for simplifying and manipulating the Boolean expressions or to convert a truth table to its corresponding logic circuit in a simple, orderly process.
• In this technique, the information contained in a truth table or available in SOP or POS form is represented on K-map.
• Although this technique may be used for any number of variables, it is generally used up to 6-variables beyond which it becomes very cumbersome.
• In n-variable K-map there are 2n cells.
• “Gray code” has been used for the identification of cells.

 Three-variable K-map

• Four cells
• Four minterms (maxterms)

Three-variable K-map

• Eight cells
• Eight minterms (maxterms)

Four-variable K-map

• Sixteen cells
• Sixteen minterms (maxterms)

Implicant

Implicant is a product/sum term in sum of product (SOP) for which the function output must be 1 or sum/maxterm term in product of sum (POS) of a boolean function.

Prime Implicant

A prime Implicant is a smallest possible sum/product term of the given function, removing any one of the literal from which is not possible. All possible groups formed in K-map are prime implicants.

Example: Number of prime implicants = 3

Essential Prime Implicant (EPI)

• Essential Prime Implicant are those prime implicants which cover atleast one minterm in SOP or atleast one maxterm in POS that can’t be covered by any other prime implicant.
• Essential Prime Implicants (EPI) are those prime implicants which always appear in final solution.

Example: Number of Essential Prime Implicants (EPI) = 2.

Redundant Prime Implicants (RPI)

• The prime implicants for which each of its minterm/maxterm is covered by some essential prime implicants are redundant prime implicants (RPI).
• Redundant Prime Implicants (RPI) never appears in final solution.

Example: Redundant Prime Implicant (RPI) = BC

Selective Prime Implicants (SPI)

The prime implicants which are neither essential nor redundant prime implicants are called selective prime implicants. These are also known as non-essential prime implicants.
They may or may not appear in final solution.

Example: Number of selective prime implicants = 2.