Karnaugh maps from 2 to 6 variables — pairs, quads, octets, rolling, overlapping, and redundant groups — don’t-care conditions, NOR implementation using 0-grouping, and the Quine-McCluskey tabular method.
🎯 Why Simplify?
The canonical SOP form of a Boolean function has one product term per ‘1’ in the truth table — for 4 variables that can be up to 16 AND gates. A Karnaugh map (K-map) finds the minimal expression by visually identifying adjacent minterms that can be merged to eliminate variables.
Group size
Variables eliminated
Term size remaining
Name
2¹ = 2 cells
1 variable
(n−1) literals
Pair
2² = 4 cells
2 variables
(n−2) literals
Quad
2³ = 8 cells
3 variables
(n−3) literals
Octet
2⁴ = 16 cells
4 variables
(n−4) literals
Hextet
Golden rule. Always form the largest possible groups first. Larger groups = fewer literals = simpler circuit.
2️⃣ 2-Variable K-Map
A 2-variable map has 4 cells (2² = 4 minterms). The column and row headers use Gray code ordering — adjacent cells differ by exactly one variable, enabling valid grouping.
B̄ (0)
B (1)
Ā (0)
m₀
m₁
A (1)
m₂
m₃
Figure 1 — 2-variable K-map layout. Each cell = one minterm. Adjacent cells (horizontally or vertically) differ by exactly one variable — the basis for valid grouping.
3️⃣ 3-Variable K-Map
A 3-variable map has 8 cells. The two-variable axis (BC) uses Gray code: 00, 01, 11, 10 — NOT binary order. This ensures every adjacent pair of cells is logically adjacent (differs by 1 bit). Forgetting this is the most common K-map mistake.
A\BC
00
01
11
10
0
m₀
m₁
m₃
m₂
1
m₄
m₅
m₇
m₆
Figure 2 — 3-variable K-map. BC columns follow Gray code (00→01→11→10), NOT binary order (00→01→10→11). The leftmost and rightmost columns are also adjacent (the map “wraps”).
F = Ā·B̄ + Ā·C + A·B (three pairs covering all five 1s)
4️⃣ 4-Variable K-Map
A 4-variable map has 16 cells. Both axes use Gray code: AB = 00,01,11,10 (rows) and CD = 00,01,11,10 (columns). The map wraps on all four edges.
AB\CD
00
01
11
10
00
0
1
2
3
01
4
5
6
7
11
12
13
14
15
10
8
9
10
11
Figure 3 — 4-variable K-map minterm numbering. Rows and columns both follow Gray code. Note that rows go 00→01→11→10, so rows 0 and 3 (values 0–3 and 8–11) are adjacent — the map wraps top-to-bottom as well as left-to-right.
Example 4.5 — Simplify X(A,B,C,D) = Σ(0,1,2,5,8,10,11,14,15)
Plot 1s in the K-map:
AB\CD
00
01
11
10
00
1
1
0
1
01
0
1
0
0
11
0
0
1
1
10
1
0
1
1
Cells 0,1,2 (row 00, cols 00,01,10) + cell 8 (row 10, col 00) — Rolling quad → Ā·C̄
Figure 4 — Group sizes and their effect. Each doubling of group size eliminates one more variable. A group of all 16 cells in a 4-variable map would give the constant 1.
Reading a group term. After forming a group, identify which variables are constant across all cells in the group — those variables appear in the product term. Variables that change within the group are eliminated. If the constant value is 0, the variable appears complemented; if 1, it appears uncomplemented.
🔁 Rolling and Overlapping Groups
Rolling (wrapping): The K-map is a torus — left and right edges are adjacent, and top and bottom edges are adjacent. Groups may wrap around any edge. The four corner cells of a 4-variable map always form a valid quad.
Overlapping: The same ‘1’ cell can belong to more than one group. This is encouraged — it allows each group to be as large as possible without constraint. A cell shared by two quads is better than having two isolated pairs.
Figure 5 — Rolling (wrapping) examples. Left: the four corner cells (0,2,8,10) form a valid quad because the map wraps both horizontally and vertically — giving term B̄·D̄. Right: the left column (cells 1,5,13,9) forms a column-spanning quad.
🗑️ Redundant Groups
A group is redundant if every one of its ‘1’ cells is already covered by other groups. Redundant groups add unnecessary literals to the final expression and must be removed.
Test for redundancy. A group is redundant if you can remove it and every 1 it contained is still covered by at least one remaining group. Always review your final grouping and drop redundant groups before writing the expression.
📋 Step-by-Step Simplification Procedure
Draw the K-map for n variables. Fill cells: write 1 for minterms in the function, 0 for all others.
Identify and circle the largest possible groups — octets first, then quads, then pairs. Remember rolling and overlapping.
Every 1 must be covered by at least one group. Isolated 1s that don’t fit a larger group are circled alone (trivial group of 1).
Review and remove redundant groups — any group whose 1s are all covered by other groups.
Write one product term per group — include only the variables that are constant across all cells in the group.
OR all product terms to get the minimal SOP expression.
🃏 Don’t-Care Conditions
Some input combinations never occur in a given system — for example, the illegal codes 1010–1111 in a BCD system. These are called don’t-care conditions, marked with φ (or X) in the K-map.
Don’t-care cells can be treated as either 0 or 1 — whichever helps form a larger group. They are included inside groups as 1s to expand groups, but ignored (treated as 0) if they don’t help.
Critical constraint: Never form a group consisting only of φ cells — at least one genuine 1 must be in every group.
Example 4.6 — Simplify F(W,X,Y,Z) = Σ(0,2,3,5,6,8,9) + don’t-cares Σ(10,11,12,13,14,15)
K-map with 1s at 0,2,3,5,6,8,9 and φ at 10-15:
WX\YZ
00
01
11
10
00
1
0
1
1
01
0
1
0
1
11
φ
φ
φ
φ
10
1
1
φ
φ
Large octet using don’t-cares → W̄ (all of rows WX=00 and WX=10 with help from φ row WX=11)
Cells 2,3,6,10,11,14 area → Ȳ·Z̄ pattern
Cell 5 and its don’t-care neighbours → X·Z̄
F = W̄ + Ȳ·Z̄ + X·Z + X·Ȳ + X̄·Ȳ·Z (NAND-gate implementation shown in textbook Fig 4.25)
🔲 NOR Implementation — Grouping the 0s
To implement a function using NOR gates only, you need the function in POS (Product of Sums) form. The K-map gives POS directly when you group the 0s (and don’t-cares) instead of the 1s.
The rules for grouping 0s are identical to grouping 1s. However, the product term is written as a maxterm:
If a variable is 0 (constant) across all cells in the group → write it uncomplemented in the maxterm.
If a variable is 1 (constant) → write it complemented in the maxterm.
The final POS expression is the AND of all maxterms, and is directly implemented with NOR gates using De Morgan’s law: Ā·B̄ = NOR(A,B)
Example 4.7 — NOR implementation of F(A,B,C,D) = Π(0,1,4,5,8,12,14,15) + don’t-cares(9,11,13)
Group the 0s in the K-map (0s at: 0,1,4,5,8,12,14,15; φ at: 9,11,13):
AB\CD
00
01
11
10
00
0
0
1
1
01
0
0
1
1
11
0
φ
φ
0
10
0
φ
φ
0
0-quad at cols 00,01 → variable C is 0, D changes → maxterm: (A+B) no wait — CD=00,01 means C=0 constant; A,B vary → (C) is 0-constant → maxterm contributes C
0-pair at corners of cols 00 and 10, rows 11 and 10 → A=1 constant → maxterm Ā
F = (A+B)·C → NOR implementation: NOR(NOR(A,B), NOR(C,C))
5️⃣ 5- and 6-Variable Maps
For 5 variables (A,B,C,D,E): the map splits into two 4-variable blocks — one for Ā and one for A. A pair, quad or octet can span both blocks if the positions are identical in both maps (mirror images). Diagonal blocks are never adjacent.
For 6 variables (A,B,C,D,E,F): four 4-variable blocks for combinations ĀB̄, ĀB, AB, AB̄. Groups across adjacent blocks follow the same mirror-image rule.
Practical note. 5- and 6-variable K-maps are difficult to draw and verify by eye. For functions of 5+ variables, the Quine-McCluskey tabular method (next section) is more reliable and easily computerised.
🗂️ Quine-McCluskey Tabular Method
Developed by Quine and improved by McCluskey, the Q-M method finds prime implicants algorithmically — making it suitable for any number of variables and easy to automate in software (used internally by EDA tools).
Steps
List all minterms in binary. Group them by the count of 1-bits.
Compare adjacent groups: combine any two minterms from consecutive groups that differ by exactly one bit. Mark the differing position with a dash (−). Check off (√) any minterm that gets combined.
Repeat: combine the new terms again — two terms combine if they have dashes in the same position(s) and differ by one more bit. Continue until no further combinations are possible.
Prime implicants are all unchecked terms — those that could not be combined further.
Build a prime implicant chart: rows = prime implicants, columns = original minterms. Mark which minterms each PI covers. Select the minimum set of PIs that covers all minterms.
Example 4.11 — Q-M Method: F(A,B,C,D,E) = Σ(0,2,3,4,6,7,8,11,12,13,16,18,19,20,22,23,24,27,28,29)
Step 1: Group by 1-count
Group (# of 1s)
Minterm
Binary (ABCDE)
Combined?
0
0
00000
√
1
2
00010
√
4
00100
√
8
01000
√
16
10000
√
2
3
00011
√
6
00110
√
12
01100
√
18
10010
√
20
10100
√
24
11000
√
Step 2: First combinations (sample)
Minterms
Binary
Prime Implicant?
0,2
000-0
0,4
00-00
0,8
0-000
0,16
-0000
2,3
0001-
2,6
00-10
4,6
001-0
…
…
Final result after all stages:
F = D̄·Ē + B̄·D̄ + B̄·C̄·D̄ + C̄·D̄·Ē (same result as 5-variable K-map Example 4.9)
Q-M vs K-map. K-maps are visual and fast for ≤4 variables but difficult beyond that. Q-M works for any number of variables and is systematic — it guarantees finding the minimal expression. Modern EDA tools use variants of Q-M (ESPRESSO algorithm) internally.
📋 Quick Reference
Topic
Key Rule
K-map axis order
Gray code (00→01→11→10), NOT binary order
Pair
2 adjacent 1s → eliminates 1 variable
Quad
4 adjacent 1s (power of 2) → eliminates 2 variables
Octet
8 adjacent 1s → eliminates 3 variables
Rolling
Left/right edges wrap; top/bottom edges wrap; four corners form a quad
Overlapping
Same 1 can be in multiple groups — always preferred to enlarge groups
Redundant group
All its 1s already covered by other groups — remove it
Don’t-care (φ)
Use as 1 inside a group if it makes the group larger; treat as 0 otherwise; never form a group of only φ cells
NOR implementation
Group the 0s (and φ) → get POS form → variables constant at 1 are complemented in the maxterm
Reading a group term
Only variables constant across all cells in the group appear; complemented if value = 0, uncomplemented if value = 1
Q-M Method
Group minterms by 1-count → combine pairs differing by 1 bit (mark −) → repeat → unchecked terms = prime implicants → cover all minterms with minimum PIs
5-var K-map
Two 4-var blocks (Ā and A); groups span blocks only if positions are mirror images
Coming next — DE-05: Combinational Switching Circuits — the design methodology applied to Half Adder, Full Adder, Parallel Binary Adder, BCD Adder, Excess-3 Adder, and the 2’s Complement Adder/Subtractor.