Activity 2.2.4 — Advanced K-Map Techniques & POS Form¶

Learning Objectives¶

By the end of this lesson, students will be able to:

Apply advanced K-map grouping rules including wrapping and corner groups
Choose between multiple valid K-map groupings
Simplify using Product of Sums (POS) form by grouping 0s
Determine when to use SOP vs POS based on the problem
Strategically apply don't care conditions for maximum simplification

Vocabulary¶

Vocabulary (click to expand)

Term	Definition
SOP (Sum of Products)	Expression where product terms (ANDs) are summed (ORed) together: A·B + A·C
POS (Product of Sums)	Expression where sum terms (ORs) are multiplied (ANDed) together: (A + B)·(A + C)
Wrapping Group	A group that wraps around the edge of the K-map (top to bottom, left to right)
Corner Group	A group that uses all four corners of a 4-variable K-map
Don't Care (X)	An input combination that never occurs or doesn't matter; can be treated as 0 or 1

Part 1: Review of K-Map Fundamentals¶

Before diving into advanced techniques, let's review the core K-map simplification process:

Fill K-map from truth table (1s where output = 1)
Group adjacent 1s into rectangles of 1, 2, 4, 8, or 16 cells
Maximize group size, minimize number of groups
Every 1 must be in at least one group
Read each group: variables that change are eliminated; variables that stay constant form the term

Part 2: Advanced Grouping Rules¶

Wrapping Groups¶

K-map edges wrap around! Groups can extend from one edge and continue on the opposite edge.

Example — 3-Variable K-map:

         BC
        00  01  11  10
      +----+----+----+----+
  A=0 | 1  | X  | 1  | 0  |
      +----+----+----+----+
  A=1 | 1  | 1  | 1  | 1  |
      +----+----+----+----+

The left column (00 and 10) wrap around and can group together: they differ only in A, so B'=0 is kept.

Corner Groups¶

In a 4-variable K-map, all four corners can form a single group of 4:

         CD
        00  01  11  10
      +----+----+----+----+
  AB=00| 1  | 0  | 0  | 1  |
      +----+----+----+----+
  01  | 0  | 0  | 0  | 0  |
      +----+----+----+----+
  11  | 0  | 0  | 0  | 0  |
      +----+----+----+----+
  10  | 1  | 0  | 0  | 1  |
      +----+----+----+----+

Group of 4: corners at (0,0), (0,3), (3,0), (3,3) - A changes (0→0→1→1), eliminated - B changes (0→0→1→1), eliminated
- C changes (0→0→0→0), stays as C'=1 - D changes (0→1→1→0), changes, eliminated

Term: C'

Key insight: When grouping by wrapping or corners, the variables that wrap (that change going around the edge) are eliminated — only the non-wrapping variables stay constant.

Part 3: Choosing Between Multiple Valid Groupings¶

Often there are multiple valid ways to group 1s. Use these guidelines:

Grouping Guidelines¶

Maximize group size first: Larger groups eliminate more variables
Minimize number of groups: Fewer groups = simpler expression
Cover all 1s: Every 1 must be in at least one group
Prefer groups of 8 over two groups of 4 (more elimination)
When in doubt, try both and compare resulting expressions

Example: Multiple Solutions¶

K-map:

	CD=00	CD=01	CD=11	CD=10
AB=00	1	0	0	1
AB=01	0	1	1	0
AB=11	0	1	1	0
AB=10	1	0	0	1

Solution 1 (two groups of 4): - Group 1: Left column → B'
- Group 2: Middle two columns, middle two rows → C

Expression: F = B' + C

Solution 2 (four groups of 2): - Various smaller groups give more terms

Better choice: Solution 1 (fewer groups, larger groups)

Key insight: Always check if you can make larger groups — larger groups eliminate more variables and produce simpler expressions.

Part 4: Product of Sums (POS) Form¶

So far, we've been using Sum of Products (SOP) form — grouping 1s and creating product terms.

But there's another approach: Product of Sums (POS) — group 0s instead!

Why Use POS?¶

Sometimes produces a simpler expression
When the truth table has more 1s than 0s, grouping 0s may be easier
Some design requirements specify POS output

How POS Works¶

Group the 0s (instead of 1s)
Read each group the same way (variables that stay constant are kept)
BUT: Each group gives a sum term (OR expression)
Final expression: The product (AND) of all sum terms

Key Difference: SOP vs POS Reading¶

Form	What to Group	Each Group Gives	Final Expression
SOP	1s	Product term (AND)	Sum of products (OR of ANDs)
POS	0s	Sum term (OR)	Product of sums (AND of ORs)

SOP vs POS Reading Detail¶

SOP (grouping 1s): - Variable = 0 in group → variable appears as complemented (A') - Variable = 1 in group → variable appears as true (A) - Read: product terms

POS (grouping 0s): - Variable = 0 in group → variable appears as true (A) - Variable = 1 in group → variable appears as complemented (A') - Read: sum terms, then AND them together

Example: POS Simplification¶

Truth Table:

A	B	Y
0	0	1
0	1	0
1	0	0
1	1	0

SOP approach: Group 1s → m0 → term: A'B' → F = A'B'

POS approach: Group 0s (m1, m2, m3) - m1: A=0, B=1 → A stays (0→true), B changes → sum term: A - Group m1,m2,m3: B=1 for all (stays), A changes → sum term: B'

Wait, let me redo properly:

Group 0s in K-map: | | B=0 | B=1 | |--|-----|-----| | A=0 | 1 | 0 | | A=1 | 0 | 0 |

0s at (0,1) and (1,0), (1,1): - Could group (0,1)+(1,1): B=1 constant → A changes → term: B - Could group (1,0)+(1,1): A=1 constant → B changes → term: A - Could group all three 0s: B=1 for two, A=1 for two...

Actually, let's not group them all: group (0,1)+(1,1) → B=1 → term is B F = B (product of sums with one term = just B)

But SOP gave A'B'. Are they equivalent? Let's check: - B=1: F=1 regardless of A (SOP: A'·1 + A·1 = 1) ✓ - B=0: F=0 regardless of A (SOP: 0+0=0) ✓

YES equivalent! Both simplify to just B!

Key insight: SOP and POS may give different-looking expressions, but they represent the same function. Choose whichever gives the simpler result.

Part 5: Don't Care Conditions (Deep Dive)¶

Don't care conditions (marked X) give you flexibility to treat an input as either 0 or 1.

When to Use Don't Cares¶

Maximize group size: Treat X as 1 when grouping 1s, or as 0 when grouping 0s
Simplify both SOP and POS: Can help simplify whichever form you're using

When NOT to Use Don't Cares¶

Never include an X if it would change the logic function
If grouping 1s gives a simpler result than grouping 0s, but using Xs helps more in POS, use that approach
Some applications require specific output for don't care inputs (then X cannot be used freely)

Strategic Don't Care Use¶

Example with Xs:

K-map: | | CD=00 | CD=01 | CD=11 | CD=10 | |----|-------|-------|-------|-------| | AB=00 | 1 | X | 0 | 1 | | AB=01 | 0 | 0 | 0 | 0 | | AB=11 | 0 | 0 | 0 | 0 | | AB=10 | 1 | X | 0 | 1 |

Without using Xs: Two groups of 2 → F = A'B'D' + AB'D'

Using Xs strategically: - Treat X at (0,1) as 1 → group with top-left 1s: gives B'D' - Treat X at (3,1) as 1 → group with bottom-left 1s: gives B'D' - Now group corners: gives D'

Final: F = B'D' + D' = D'

Much simpler!

Part 6: Converting Between SOP and POS¶

You can mathematically convert between SOP and POS:

SOP to POS Conversion¶

Given F = A·B + A·C

Write as sum of minterms: F = Σm(0, 1, 2, 3) [if applicable]
Find zeros: F' has minterms where original is 0
Express F' as SOP
Complement using De Morgan's: F = (F')'

Quick Method¶

For 2-variable case: - SOP: A·B + A'·B' = (A + B')·(A' + B) - Pattern: Each product term becomes a sum term with inverted variables

Key insight: In general, POS is more useful when there are few 1s in the truth table (easy to group 0s), or when the output needs to be active-LOW.

Part 7: Worked Examples¶

Example 1: Choose SOP or POS¶

Truth Table:

A	B	C	Y
0	0	0	1
0	0	1	1
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	1
1	1	1	1

Analysis: 6 ones, 2 zeros → more 1s, so SOP seems easier.

SOP K-map:

	BC=00	BC=01	BC=11	BC=10
A=0	1	1	0	0
A=1	1	1	1	1

Grouping 1s → can we make a group of 8? Yes! The entire bottom row plus first two cells of top row... Actually let's find best groups: - Group of 4: left two columns → C' → term: C' - Group of 4: bottom row, last two columns → A → term: A - m2 and m3 (the two 0s) might be grouped but wouldn't help

Expression: F = C' + A

Check POS alternative: Group 0s at positions (0,2) and (0,3) - Both have A=0, B=1 - Group gives: A' + B (sum term) - F = A' + B [one sum term = just that expression]

Is C' + A equivalent to A' + B? Let's test: - A=0,B=0,C=0: C'+A = 1+0 = 1; A'+B = 1+0 = 1 ✓ - A=0,B=0,C=1: C'+A = 0+0 = 0; A'+B = 1+0 = 1 ✗

NOT equivalent! Different solutions. Let's verify our SOP truth table: Looking at truth table again: rows with Y=0 are only (0,1,0) and (0,1,1) So output Y = 0 only when A=0, B=1 Therefore Y = 1 when A=1 OR B=0 OR (A=0 AND B=1 would give 0)

Actually, let's find canonical form: Zeros at m2(010), m3(011) So F' = A'B'C + A'BC = A'C(B'+B) = A'C F = (A'C)' = A + C'

So F = A + C'

Checking our SOP result: F = C' + A — SAME! ✓

Key insight: When SOP gives a simple result like A + C', use that! POS would be more complex.

Example 2: POS with Don't Cares¶

Expression: F(A,B,C) = Σm(1,3,5) + d(0,7)

SOP (group 1s): K-map: 1s at m1,m3,m5; Xs at m0,m7

Groups: - Group m1,m3 (using X at m0): A'=1 stays, C=1 stays → A'C - Group m5 (with X at m7): A=1 stays, C=1 stays → AC

F = A'C + AC = C(A' + A) = C

POS (group 0s, using don't cares as 0): 0s at: wait, we have 1s at m1,m3,m5... zeros at m2, m4, m6, plus Xs as 0s at m0, m7

Zeros at m2(010), m4(100), m6(110) - m2: A=0,B=1,C=0 → group: A'+B - m4: A=1,B=0,C=0 → group: A+B' - m6: A=1,B=1,C=0 → group: A+B

These don't group well... F = C from SOP is simpler!

Key insight: Generally use the form (SOP or POS) that gives the simpler expression, but also consider your output hardware requirements.

Practice Problem — Advanced K-Maps¶

Problem 1: For the K-map below, identify: - a) Any wrapping groups - b) Any corner groups - c) The simplified expression

	CD=00	CD=10
AB=00	1	1
AB=01	0	0
AB=11	0	0
AB=10	1	1

Show Solution

a) Wrapping groups: The two 1s in column 1 (AB=00 and AB=10) wrap around — they differ only in A, but B stays 0 in both, so they can group. Actually they form a vertical pair.

b) Corner groups: The four 1s at corners (00,00), (00,10), (10,00), (10,10) can form one group of 4!

c) Corner group analysis: - A changes (0→0→1→1), eliminated - B changes (0→0→1→1), eliminated - C changes (0→0→0→0), stays as C' - D changes (0→1→1→0), eliminated

Term from corners: C'

There are no other 1s to group, so final expression is simply: F = C'

Problem 2: Simplify F(A,B,C,D) = Σm(3,5,6,7,9,11,12,13,14,15) using POS form.

Show Solution

First, note there are 10 ones and 6 zeros. SOP might actually be easier, but let's do POS as requested.

Zeros at minterms: 0,1,2,4,8,10

K-map zeros: - m0: 0000 - m1: 0001
- m2: 0010 - m4: 0100 - m8: 1000 - m10: 1010

Grouping zeros: - m0,m1: A=0,B=0,C=0,D changes → sum: A'+B'+C' = (A+B+C)' - m2 (0010): alone, or could group with something...

Better approach: Let's find SOP first, then convert to POS mathematically.

Actually, let's just simplify zeros directly: - Could try grouping zeros to see if simpler

The zeros are scattered... Let's use SOP approach which should be straightforward: 1s at m3,m5,m6,m7,m9,m11,m12,m13,m14,m15

Most of right half of K-map is 1s: - m3(0011),m2=0: group of 2 with m7,m6 - Actually, let's just find groups: - Right two columns, top two rows: 1s → C=1 → term: C - Bottom three rows, column 1 (01): B=1, C=1 → term: BC - And more...

SOP: F = C + BC + ... simplify = C(1+B) = C

That's it! F = C

Now POS: If F = C, then in POS form: F = C (single term is both sum and product)

Actually C = C, so either form works. The simplest is F = C either way!

Problem 3: For the function with don't cares, determine the simplest SOP expression: F(A,B,C) = Σm(2,5) + d(1,3,4,6,7)

Show Solution

Truth table for K-map: | | BC=00 | BC=01 | BC=11 | BC=10 | |----|-------|-------|-------|-------| | A=0 | 0 | X | X | 1 | | A=1 | X | 1 | X | X |

Group 1s: - m2 (A=0,B=1,C=0): can group with X at m3 or m6 (wrap) — let's see best option - m5 (A=1,B=0,C=1): alone but can use Xs

Try different groupings:

Option 1: Group m2 with X at m3: - A=0 (stays), C=0 (stays), B changes → term: A'C'

Option 2: Group m5 with X at m4: - A=1 (stays), B=0 (stays), C changes → term: AB'

Option 3: Group m5 with X at m6: - A=1 (stays), C=1 (stays), B changes → term: AC

Now let's see about overlapping with Xs: - Can we also include X at m1 or m7 to make bigger groups?

Best result appears to be: - One group of 2: m2 + X(m3) → A'C'
- One group of 2: m5 + X(m4) → AB' OR - One group of 2: m5 + X(m6) → AC (covers m5 already)

Actually let's try max use of Xs: Group m2(010) with m3(011) [X]: A'=0, C=0 → term: A'C' Group m5(101) with m4(100) [X]: A=1, B=0 → term: AB' Group corner Xs could add more...

Let me try: Group all corner Xs (m1,m3,m4,m7) as 1: - They form 2x2 at top-right + bottom-left — gives different terms

Given the choices: F = A'C' + AB' seems simplest Or F = A'C' + AC might work better: let's check coverage - m2 covered by A'C' ✓
- m5 covered by AC ✓

Final: F = A'C' + AC (or could be A'C' + AB')

Actually let's verify by trying to maximize: X at m6(110) could group with m2 via wrap? No.

Simplest: F = C (just one term?) Let's see if that works: - m2: C=0, result would be 0... but F(m2)=1. So no.

Our earlier groups are correct. F = A'C' + AC or A'C' + AB' — both valid.

Summary¶

Advanced K-map techniques include wrapping groups (edge to edge) and corner groups (all four corners of 4-variable map)
When multiple valid groupings exist, choose the one with largest groups and fewest groups
POS (Product of Sums) groups 0s instead of 1s; each group gives a sum term (OR)
POS reading: variable = 0 stays true (not complemented), variable = 1 stays complemented
Don't care conditions (X) can be strategically used to maximize groups in either SOP or POS
Choose SOP or POS based on which produces the simpler expression

Key Reminders¶

Edges of K-maps wrap around — top to bottom, left to right
When reading groups that wrap, variables that wrap (change on wrap) are eliminated
Larger groups are always better — they eliminate more variables
POS: group 0s, read as OR terms, AND them together
Test your simplified expression against the original truth table

Custom activity — adapted from PLTW Digital Electronics