Source

Adapted from my own handwritten and hand-typed notes from Year 1 to Year 3 of my EEE degree

Definitions

Key terms:

  • implicant: any valid group of 1s on the K-map, i.e. any product term that implies the function
  • prime implicant (PI): an implicant that cannot be combined into a larger group, i.e. a group covering the largest possible block of adjacent squares
  • essential prime implicant (EPI): a prime implicant that covers at least one minterm that no other prime implicant covers

A function is covered when every 1 square is inside at least one group. The same map can be covered in many ways, so a function can be written in many equivalent SOP forms.

A prime implicant may contain 1, 2, 4, 8 or even 16 minterms.

Minimized Function

A minimized logic function contains:

  • all essential prime implicants (these must appear)
  • the fewest extra prime implicants needed to cover the remaining 1s

When there is a choice of extra prime implicants, there can be several different but equally minimal answers.

Procedure

Steps:

  • mark every prime implicant (largest possible groups)
  • find 1s covered by only one PI, those PIs are essential
  • add the cheapest PIs that cover what is left
  • write one product term per group and OR them

Worked Example

:

00011110
01110
10011
  • is only in (covers ), so is essential
  • is only in (covers ), so is essential
  • is still uncovered and can go in either or , both prime, neither essential

A common mistake is to circle as a pair inside a bigger possible group, or to keep a group that is fully covered by other groups. Both give a correct but non-minimal answer.

Undefined input rows make bigger groups possible, see Don't-Care Conditions.