1. Implicants

Definition – Implicant

An implicant is a rectangle of 1-squares on a K-map whose size is a power of 2 (1, 2, 4, 8, 16).

Definition – Prime Implicant (PI)

A prime implicant is an implicant not fully contained in any other implicant (it cannot be enlarged).

Definition – Essential Prime Implicant (EPI)

An essential prime implicant is a prime implicant that covers at least one 1 that no other prime implicant covers. Every EPI must appear in the minimal SoP.

flowchart LR
    I["Implicants<br/>(any valid rectangle of 1s)"] --> P["Prime implicants<br/>(maximal rectangles)"]
    P --> E["Essential PIs<br/>(only cover for some 1)"]

Example –

ABCD0001111000011110011132415176112131511418911110All prime implicantsABCD0001111000011110011132415176112131511418911110F = A’C’ + ACD + BCD’

  • Implicants: 0 of 8 squares, 1 of 4 squares (), 8 of 2 squares, 8 single squares.
  • Prime implicants (left map): one 4-square PI , and four 2-square PIs: , , , . The 2-square implicants inside (e.g. ) are not prime.
  • Essential PIs: (only cover for 0, 1, 5) and (only cover for 11). , , are not essential — each of their 1s is also covered by another PI.

2. SoP Optimization Algorithm

  1. Draw the K-map.
  2. Find all prime implicants, starting with the largest rectangles.
  3. Identify all essential prime implicants.
  4. If minterms remain uncovered, cover them with prime implicants that:
    • cover the most squares,
    • are as few as possible,
    • overlap as little as possible.
  5. Write the optimized SoP (OR of the chosen implicants).
flowchart TD
    A["1. Draw K-map"] --> B["2. All PIs<br/>(largest first)"]
    B --> C["3. Pick all EPIs"]
    C --> D{"All 1s<br/>covered?"}
    D -- No --> E["4. Add PIs: big, few,<br/>little overlap"]
    E --> D
    D -- Yes --> F["5. Write SoP"]

Example – Finishing

After the EPIs and , minterms 6 and 14 are left. The single PI covers both:

(right-hand map above)

Exercise – EPIs of

ABCD0001111000011110011312145761211311511418191111101F = A + B’D’ + B’C

EPIs: (bottom half), (four corners), (rows 00/10 × columns 11/10). They cover every 1, so

Exercise –

ABCD00011110000111100113124151716112131151481911110F = A’B + A’CD + AC’D + B’C’D’

( = wraps top↔bottom.)

Exercise – (Several Minimal Solutions)

ABCD00011110000111100113121415716121131151141891110F = AB + BC’D’ + A’B’D’ + A’CD

  • Only EPI: (row 11).
  • Remaining 0, 2, 3, 4, 7 can be covered in several equally cheap ways:

⚠️ The minimal SoP is not unique. Any cover with the same cost is a correct answer.

Exercise –

XYZ000111100101113214157161F = Z’ + X’Y’ + XY

Exercise –

ABCD000111100001111001132141517161121311511481911101F = BD + A’B + B’D’

Exercise –

ABCD0001111000011110013124151716121311511418911110G = A’BC’ + A’CD + ABC + AC’D

is a 4-square prime implicant, but not essential: each of its 1s is already covered by the four EPIs. Adding it would only increase the cost.

⚠️ Don’t automatically take the biggest group. A big PI whose squares are all covered by EPIs is redundant.


3. 5-Variable K-Maps

A 5-variable map has 32 squares, drawn as two 4-variable maps: one for , one for (rows , columns , both in Gray code).

  • Each square has 5 neighbours: 4 in its own map + the square in the same position in the other map.
  • Implicants inside one map are chosen as usual.
  • An implicant spanning both maps covers squares as squares at the same positions in each map, and loses the variable .

A = 0BCDE00011110000111100132457161211311514891110A = 1BCDE000111100001111016171918120212312228293130242527261

GroupSquaresTermLiterals
2 (map )4
2 (both maps, same spot)4
2 (map , wraps)4

General rule: 2 squares → 4 literals, 4 squares → 3 literals (e.g. , ), 8 squares → 2 literals (e.g. , ), 16 squares → 1 literal (e.g. , ).


4. PoS Optimization

Method – Group the 0s

In the K-map of , the 1s are the minterms of and the empty squares (0s) are the minterms of .

  1. Mark the empty squares with 0 and group the 0s → simplified SoP of .
  2. Apply the generalized De Morgan law to → PoS of .

Example –

ABCD000111100001111001103021415171611201311511408190110101F’ = B’D + ABD’

Exercise –

ABCD000111100001111001113020415170611201301511418090111100F’ = AC’ + A’CD + B’CD’

⚠️ When complementing into , every literal flips and AND ↔ OR: the term in becomes the sum in .


5. Don’t-Care Conditions

Motivation

A function with a 4-bit BCD input only ever sees the codes 0 – 9; the six combinations 10 – 15 never occur, so the output there is unspecified.

Definitions

  • An incompletely specified function has unspecified outputs for some inputs.
  • A don’t-care minterm is an input combination whose output value doesn’t matter. Writing 1 would force , writing 0 would force , so it is marked X.
  • Notation: .

Rule – Using X in a K-Map

Treat each X as 1 if that makes a group bigger, otherwise as 0. X squares never need to be covered on their own.

Example – “BCD ≥ 5”

for BCD codes , for , for : .

0000 – 01000101 – 10011010 – 1111
01X

ABCD00011110000111100132451716112X13X15X14X819111X10Xno X used: G = 12ABCD00011110000111100132451716112X13X15X14X819111X10XX used: F = A + BD + BC, G = 7

Without don’t-caresWith don’t-cares
SoP

Exercise – PoS with Don’t-Cares:

  1. Group the 0s (using X where helpful) →
  2. De Morgan →

ABCD0001111000011110001X31204X50706X1211311511418091111100F’ = B’D’ + A’B → F = (B+D)(A+B’)

⚠️ An X can be used as 1 in the SoP of and as 0 in the SoP of (or vice versa) — each grouping decides independently. The two resulting expressions may therefore differ on the don’t-care inputs, which is fine.


Exercises: in the slides — find PIs/EPIs; minimize , , , , , ; PoS of ; PoS with don’t-cares .