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 –
- 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
- Draw the K-map.
- Find all prime implicants, starting with the largest rectangles.
- Identify all essential prime implicants.
- If minterms remain uncovered, cover them with prime implicants that:
- cover the most squares,
- are as few as possible,
- overlap as little as possible.
- 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
EPIs: (bottom half), (four corners), (rows 00/10 × columns 11/10). They cover every 1, so
Exercise –
( = wraps top↔bottom.)
Exercise – (Several Minimal Solutions)
- 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 –
Exercise –
Exercise –
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 .
| Group | Squares | Term | Literals |
|---|---|---|---|
| 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 .
- Mark the empty squares with 0 and group the 0s → simplified SoP of .
- Apply the generalized De Morgan law to → PoS of .
Example –
Exercise –
⚠️ 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 – 0100 | 0101 – 1001 | 1010 – 1111 | |
|---|---|---|---|
| 0 | 1 | X |
| Without don’t-cares | With don’t-cares | |
|---|---|---|
| SoP | ||
Exercise – PoS with Don’t-Cares:
- Group the 0s (using X where helpful) →
- De Morgan →
⚠️ 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 .