4.2 3-Variable and 4-Variable K-Map Minimization

Back to Digital Logic Notes

📚Module 04: Simplification of Boolean Expressions & K-MapsTopic 4.2⏱️16 min read

🎯High-Yield For:University Semester Exams • Hardware Engineering Rounds • Foundational Computing

💡 Core Intuition: Land Consolidation & Boundary Removal

Imagine an urban planner tasked with zoning a new city block divided into individual $1 \times 1$ meter plots of land:

🍳 The Everyday Analogy: Merging Plots into Superblocks

• Individual Plots (Unminimized Minterms): If every land owner builds a standalone perimeter fence around their tiny $1 \times 1$ plot, the block becomes a maze of costly walls, gates, and redundant boundaries.
• Consolidation into Superblocks (K-Map Grouping): The city permits developers to merge adjacent plots to build commercial superblocks. However, municipal bylaws enforce strict geometric constraints:
  • You can only consolidate plots in binary powers of 2: 1, 2, 4, 8, or 16 plots. You cannot zone a 3-plot or 6-plot superblock.
  • Plots must form a contiguous rectangle or square.
  • Every internal fence knocked down between merged plots saves construction material and wiring costs.

A 2-plot merger (Pair) knocks down 1 internal wall. A 4-plot merger (Quad) eliminates 4 boundaries. An 8-plot merger (Octet) clears almost the entire city block. In digital electronics, every boundary knocked down in a K-map grouping permanently removes an entire physical transistor input from your circuit!

💻 Bridging to Computer Science

In digital design:

1. Every cell containing a 1 on a Karnaugh map is a single minterm containing all $n$ literals.
2. Grouping adjacent cells into binary subcubes ($2^k$) applies the fundamental Boolean absorption identity $AX + A\bar{X} = A$.
3. Merging $2^k$ cells eliminates exactly $k$ independent variables, producing an optimized product term with only $(n - k)$ literals.

Maximizing group sizes and minimizing the total count of groups directly yields the absolute minimum number of logic gates and inputs required to realize the function in silicon.

---

📑Table of Contents

• 📏 The 4 Golden Rules of K-Map Subcube Grouping
• 🧮 The Subcube Variable Elimination Theorem
  • Subcube Hierarchy & Literal Savings Table
• 🔄 Step-by-Step SOP Minimization Algorithm
• 🛡️ Step-by-Step POS Minimization Algorithm
• 🏭 Real-World Production Context: ALU Multiplexer Tree Minimization
• 📐 Numerical Applications & Worked Examples
  • Example 1: 3-Variable SOP Minimization with Overlapping Groups
  • Example 2: 4-Variable SOP Minimization with Corner and Edge Quads
  • Example 3: 4-Variable POS Minimization (Grouping 0s)
• 🎯 Exam & Interview Pitfall Check

---

📏 The 4 Golden Rules of K-Map Subcube Grouping

To guarantee that a grouped K-map produces a valid, minimal Boolean expression, every grouping (called a subcube) must strictly obey four geometric and algebraic laws:

2️⃣

Rule 1: Powers of Two

Size Constraint

• A subcube MUST contain exactly 2ᵏ cells: 1, 2, 4, 8, or 16 cells.
• Groups of 3, 5, 6, 7, 10, or 12 cells are STRICTLY FORBIDDEN.
• Only powers of 2 provide symmetric complement cancellation (X + X' = 1).

Key Abstractions / Calls

Size ∈ {1, 2, 4, 8, 16}

📐

Rule 2: Rectangular Geometry

Shape Constraint

• Groups must be rectangular or square (1x1, 1x2, 2x1, 2x2, 1x4, 4x1, 2x4, 4x4).
• L-shaped, T-shaped, diagonal, or cross-shaped groups are invalid.
• Rectangles include toroidal wrap-arounds across map edges and corners.

Key Abstractions / Calls

Rows × Cols = 2ᵏ

🎯

Rule 3: Maximal Subcube Size

Optimization Rule

• Always make groups as LARGE as possible.
• An octet (8 cells) is strictly superior to two quads (4 cells each).
• A quad (4 cells) is strictly superior to two pairs (2 cells each).
• Larger groups eliminate more literals, reducing gate fan-in.

Key Abstractions / Calls

Max(2ᵏ) → Min(Literals)

✂️

Rule 4: Redundancy Elimination

Pruning Rule

• Every 1 must be covered by at least one group.
• Overlapping is allowed and encouraged to enlarge groups.
• However, if all 1s in a group are already covered by other essential groups, that group is REDUNDANT and must be pruned.

Key Abstractions / Calls

Prune Subsets

---

🧮 The Subcube Variable Elimination Theorem

📐Theorem 4.2: Variable Elimination in K-Map Subcubestheorem

In an $n$-variable Karnaugh map, grouping $2^k$ adjacent cells together into a valid subcube eliminates exactly $k$ variables, resulting in a simplified product term containing strictly:

$$\text{Literal Count} = n - k$$

where:

• $n = \text{total number of system variables}$.
• $k = \log_2(\text{number of cells in the subcube})$.

🔍Derivation: Algebraic Proof of the Variable Elimination Theoremproof

Let an $n$-variable system have a subcube of $2^k$ minterms. By definition of Gray code adjacency, across these $2^k$ cells:

1. Exactly $(n - k)$ variables remain constant across all cells (either fixed at 0 or fixed at 1).
2. Exactly $k$ variables undergo all possible $2^k$ binary permutations of 0s and 1s.

Factoring out the $(n - k)$ constant literals into a common product term $P$:

$$F_{\text{subcube}} = P \cdot \sum_{j=0}^{2^k - 1} m_j(y_1, y_2, \dots, y_k)$$

Because the sum of all $2^k$ canonical minterms of $k$ variables equals logic 1 (Tautology Law):

$$\sum_{j=0}^{2^k - 1} m_j(y_1, \dots, y_k) = 1$$

Therefore:

$$F_{\text{subcube}} = P \cdot 1 = P \quad \blacksquare$$

The resulting term $P$ contains exactly $(n - k)$ literals.

Subcube Hierarchy & Literal Savings Table

Subcube Name	Number of Cells ($2^k$)	Variables Eliminated ($k$)	Resulting Term Size in 3-Var Map ($3 - k$)	Resulting Term Size in 4-Var Map ($4 - k$)
Single	$2^0 = 1$	$0$	3 literals (e.g., $A\bar{B}C$)	4 literals (e.g., $A\bar{B}C\bar{D}$)
Pair	$2^1 = 2$	$1$	2 literals (e.g., $AB$)	3 literals (e.g., $AB\bar{C}$)
Quad	$2^2 = 4$	$2$	1 literal (e.g., $A$)	2 literals (e.g., $AC$)
Octet	$2^3 = 8$	$3$	0 literals (Logic 1)	1 literal (e.g., $B$)
Hexadecet	$2^4 = 16$	$4$	—	0 literals (Logic 1)

---

🔄 Step-by-Step SOP Minimization Algorithm

Architecture Flow

The 4-Stage Systematic K-Map Minimization Workflow

Standard procedural algorithm for guaranteed minimal Sum-of-Products expressions

📍Stage 1

Plot & Identify Singles

Place a 1 in each minterm cell and identify isolated 1s with zero adjacent neighbors.

→

Check Neighbors

📦Stage 2

Form Maximal Subcubes

Prioritize 1s with unique neighbors. Expand into maximal Octets (8), Quads (4), or Pairs (2).

→

Cover All 1s

✂️Stage 3

Prune Redundant Loops

Inspect each group: if all its 1s are already covered by other chosen groups, discard it completely.

→

Minimal Cover

⚡Stage 4

Extract Minimized SOP

Read constant variables for each surviving group and combine them using logical OR (+).

🗺️

Visual 4-Variable K-Map Subcube Inspector

Hover or tap group pills below to inspect subcube coverage on the toroidal grid

4-Var SOP Toroidal Grid

CD ➔ ⬇ AB	00CD	01CD	11CD	10CD
00AB	m01	m10	m30	m21
01AB	m40	m51	m71	m60
11AB	m120	m131	m151	m140
10AB	m81	m90	m110	m101

Subcube Groups & Prime ImplicantsHover or tap to inspect group coverage

Minimized Boolean Expression:F = BD + B'D'

---

🛡️ Step-by-Step POS Minimization Algorithm

When minimizing Product of Sums (POS), the logic is dual:

SOP Minimization vs. POS Minimization on K-Maps

Contrasting the procedural mechanics between grouping 1s and grouping 0s

SOP Minimization

Sum of Products (∑ m)

➕

Dominant Architecture / DomainActive-HIGH Output Logic

• •Plot 1s for all minterm indices.
• •Form maximal subcubes covering all 1s.
• •Extract common literals: Variable = 1 → uncomplemented (A), Variable = 0 → complemented (A').
• •Form product terms and combine them with OR (+).

"Target the peaks: F = ∑(Product Terms)"

POS Minimization

Product of Sums (∏ M)

✖️

Dominant Architecture / DomainActive-LOW Output Logic

• •Plot 0s for all maxterm indices.
• •Form maximal subcubes covering all 0s.
• •Extract common literals: Variable = 0 → uncomplemented (A), Variable = 1 → complemented (A').
• •Form sum terms and combine them with AND (·).

"Target the troughs: F = ∏(Sum Terms)"

---

🏭 Real-World Production Context: ALU Multiplexer Tree Minimization

In high-performance microprocessors (such as AMD Zen 4 and Intel Core architectures), the Arithmetic Logic Unit (ALU) execution datapath must complete operations in under a single clock cycle ($\sim 200\text{ picoseconds}$ at $5\text{ GHz}$).

Architecture Flow

ALU Control Path Latency Optimization via K-Map Minimization

Transforming multi-level logic into shallow, high-speed execution stages

🔢Decode

Opcode Control

Binary opcode bits dispatched from the processor pipeline.

→

K-Map

⚡Decoder

Shallow Gate Array

Quad grouping reduces 4-input gates to fast 2-input gates.

→

Assert

🔀MUX Tree

Function Selector

Routes datapath to ADD, SUB, or XOR without stall cycles.

→

1-Cycle

🎯Core

Register Writeback

Critical path latency drops from 4 down to 2 gate delays.

1. Gate Delay Reduction: A standard 4-input AND gate has higher capacitive input load and slower propagation delay than a 2-input AND gate. By grouping 4 cells into a Quad, the synthesis compiler eliminates 2 literals, transforming a slow 4-input gate into a fast 2-input gate.
2. Dynamic Power Savings: In CMOS circuits, power is consumed during voltage switching: $P_{\text{dynamic}} = \alpha C V_{DD}^2 f$. Minimizing redundant product terms reduces parasitic wire capacitance $C$ and switching activity $\alpha$, directly cooling the silicon die.

---

📐 Numerical Applications & Worked Examples

Example 1: 3-Variable SOP Minimization with Overlapping Groups

Problem Statement:
Minimize the 3-variable Boolean switching function using a Karnaugh map:

$$F(A, B, C) = \sum m(1, 2, 3, 5, 7)$$

Identify all groups formed, verify redundancy, and write the simplified minimal SOP equation.

Step-by-Step Solution:

1. Plot the 3-Variable K-Map & Identify Groups:

🗺️

3-Variable K-Map Minimization (Example 1)

Hover or tap group pills below to inspect the Quad {m1, m3, m5, m7} and Pair {m2, m3}

3-Var SOP Toroidal Grid

BC ➔ ⬇ A	00BC	01BC	11BC	10BC
0A	m00	m11	m31	m21
1A	m40	m51	m71	m60

Subcube Groups & Prime ImplicantsHover or tap to inspect group coverage

Minimized Boolean Expression:F = C + A'B

2. Identify Groups:

   • Group 1 (Quad of 4 cells): Notice the entire column $01$ and column $11$ are filled with 1s: $\text{Cells } \{m_1, m_3, m_5, m_7\}$
     • Across rows: $A$ varies from $0 \to 1$ (eliminated).
     • Across columns: $B$ varies from $0 \to 1$ (eliminated), while $C = 1$ is constant.
     • Term for Group 1 $= C$.
   • Group 2 (Pair of 2 cells): Inspect minterm $m_2$ at row 0, col 10 (010).
     • Cell $m_2$ is isolated vertically (below it is 0).
     • Horizontally, its only neighbor is cell $m_3$ (011).
     • We form a Pair: $\{m_2, m_3\}$.
     • Across row: $A = 0$ ($\bar{A}$) is constant.
     • Across cols $11$ and $10$: $B = 1$ is constant, while $C$ varies from $1 \to 0$ (eliminated).
     • Term for Group 2 $= \bar{A}B$.

3. Check for Redundant Groups:

   • Minterm $m_2$ is covered only by Group 2 $\implies$ Group 2 is mandatory.
   • Minterms $m_5, m_7$ are covered only by Group 1 $\implies$ Group 1 is mandatory.
   • Both groups are essential. Zero redundant groups exist.

4. Final Minimized Expression:

$$F(A, B, C) = C + \bar{A}B$$

Initial canonical cost: 5 product terms with 3 literals each = 15 literals.
Minimized cost: 1 single literal + 1 two-literal term = 3 literals (80% silicon area reduction!).

---

Example 2: 4-Variable SOP Minimization with Corner and Edge Quads

Problem Statement:
Minimize the 4-variable Boolean function:

$$F(A, B, C, D) = \sum m(0, 2, 5, 7, 8, 10, 13, 15)$$

Step-by-Step Solution:

1. Plot the 4-Variable K-Map & Identify Groups:

🗺️

4-Variable Disjoint Quads Minimization (Example 2)

Hover or tap group pills below to highlight the Central Quad {m5, m7, m13, m15} and Four-Corner Quad {m0, m2, m8, m10}

4-Var SOP Toroidal Grid

CD ➔ ⬇ AB	00CD	01CD	11CD	10CD
00AB	m01	m10	m30	m21
01AB	m40	m51	m71	m60
11AB	m120	m131	m151	m140
10AB	m81	m90	m110	m101

Subcube Groups & Prime ImplicantsHover or tap to inspect group coverage

Minimized Boolean Expression:F = BD + B'D'

2. Identify Geometric Patterns:

   • Pattern 1: The Central Quad (4 cells):
     • Cells $\{m_5, m_7, m_{13}, m_{15}\}$ form a contiguous $2 \times 2$ block in the center!
     • Across rows $01$ ($\bar{A}B$) and $11$ ($AB$): $A$ changes ($0 \to 1$), while $B = 1$ is constant.
     • Across columns $01$ ($\bar{C}D$) and $11$ ($CD$): $C$ changes ($0 \to 1$), while $D = 1$ is constant.
     • Term $= BD$.
   • Pattern 2: The Four Corners Quad (4 cells):
     • Cells $\{m_0, m_2, m_8, m_{10}\}$ occupy the four extreme corners of the toroidal grid!
     • Across top row $00$ and bottom row $10$: $A$ changes ($0 \to 1$), while $\bar{B}$ ($B = 0$) is constant.
     • Across left column $00$ and right column $10$: $C$ changes ($0 \to 1$), while $\bar{D}$ ($D = 0$) is constant.
     • Term $= \bar{B}\bar{D}$.

3. Check Coverage:

   • All 8 minterms are completely covered by these two disjoint Quads.
   • Neither group is redundant.

4. Final Minimized Expression:

$$F(A, B, C, D) = BD + \bar{B}\bar{D}$$

Observation: Notice that $BD + \bar{B}\bar{D} = B \odot D$ (an XNOR gate between $B$ and $D$). Variables $A$ and $C$ were entirely redundant!

---

Example 3: 4-Variable POS Minimization (Grouping 0s)

Problem Statement:
Find the minimal Product of Sums (POS) expression for the switching function:

$$F(A, B, C, D) = \prod M(0, 1, 4, 5, 8, 9, 12, 13)$$

Step-by-Step Solution:

1. Plot the 4-Variable POS K-Map (Entering 0s):

🗺️

4-Variable POS K-Map Minimization (Example 3)

Hover or tap the Octet group pill below to see columns 00 and 01 merge, eliminating variables A, B, and D

4-Var POS Toroidal Grid

CD ➔ ⬇ AB	00CD	01CD	11CD	10CD
00AB	M00	M10	M31	M21
01AB	M40	M50	M71	M61
11AB	M120	M130	M151	M141
10AB	M80	M90	M111	M101

Subcube Groups & Prime ImplicantsHover or tap to inspect group coverage

Minimized Boolean Expression:F = C

2. Identify Grouping Structure:

   • Inspect the plotted 0s: columns 00 and 01 are completely filled with 0s across all 4 rows!
   • This forms a massive Octet of 8 cells: $\text{Cells } \{M_0, M_1, M_4, M_5, M_8, M_9, M_{12}, M_{13}\}$
   • By the Variable Elimination Theorem, an octet ($2^3 = 8$) eliminates $k = 3$ variables from a 4-variable system, leaving strictly $4 - 3 = \mathbf{1\text{ literal}}$.

3. Extract the Minimal Sum Term:

   • Across all 4 rows ($00, 01, 11, 10$): both variables $A$ and $B$ take on all combinations of 0 and 1 $\implies$ $A$ and $B$ are completely eliminated!
   • Across columns $CD = 00$ and $CD = 01$:
     • Variable $D$ changes from $0 \to 1$ $\implies$ $D$ is eliminated.
     • Variable $C = 0$ remains constant across all 8 cells.
   • In POS convention, a variable with value 0 corresponds to its uncomplemented form ($C$).

4. Final Minimized POS Expression:

$$F(A, B, C, D) = C$$

An expression originally requiring eight 4-variable OR gates reduces down to a single bare wire carrying signal $C$!

---

🎯 Exam & Interview Pitfall Check

Core Conceptual Questions

• Why does grouping an Octet (8 cells) provide double the hardware savings of two Quads (4 cells each)?
  Two independent Quads generate two distinct 2-literal product terms (e.g., $AB + CD$), requiring two 2-input AND gates plus a 2-input OR gate (total: 3 logic gates and 6 transistor inputs).
  In contrast, an Octet merges all 8 cells into a single 1-literal term (e.g., $A$), completely eliminating the AND gates and the OR gate. An Octet eliminates $3$ variables, whereas a Quad eliminates only $2$.

• How can you mathematically detect if a group in a K-map is completely redundant?
  A group is redundant if and only if every single minterm (1) contained inside that group is also a member of at least one other selected group. To test for redundancy, temporarily remove the group. If every 1 on the map is still covered by the remaining groups, the removed group was redundant and must be permanently discarded.

Common Interview Traps

• Trap: Forgetting that wrap-around columns 1 and 4 are adjacent.
  Candidates frequently circle minterm $m_4$ (0100) and minterm $m_6$ (0110) as two separate isolated 1s, overlooking that column $00$ and column $10$ are horizontally adjacent across the cylinder seam. They form a Pair ($B\bar{D}$), saving a literal and a gate.

• Trap: Inverting variables when formulating POS sum terms.
  A very common error is using SOP rules when reading POS groups. In SOP, $A = 0$ is $\bar{A}$. In POS, $A = 0$ is uncomplemented $A$, and $A = 1$ is complemented $\bar{A}$. Writing $\bar{C}$ instead of $C$ for a cell with $C = 0$ in a POS map inverts the entire logic circuit!

---

🗺️View Complete Digital Logic Roadmap & Syllabus

← Previous Topic4.1 Karnaugh Map Foundations & Gray Code AdjacencyNext Topic →4.3 Implicants, Prime Implicants & Don't Care Conditions