Karnaugh maps and logic minimisation notes — Unit 2

Before minimizing logic, we must represent it in standard formats. There are two primary forms: Sum of Products (SOP) and Product of Sums (POS).

⇒1.1 Minterms and Maxterms

Consider a function of $n$ binary variables. They can be combined to form $2^n$ unique combinations.

• Minterm (Standard Product): An AND term containing all $n$ variables (either normal or complemented). Example for 3 variables (A, B, C): $A'BC'$. Evaluates to 1 for exactly one row in the truth table. Denoted by lowercase $m_i$.
• Maxterm (Standard Sum): An OR term containing all $n$ variables. Example: $A + B' + C$. Evaluates to 0 for exactly one row in the truth table. Denoted by uppercase $M_i$.

Key Relationship: A Maxterm is the exact complement of its corresponding Minterm. $M_j = (m_j)'$.

⇒2.1 Sum of Products (SOP)

A Boolean expression consisting of the logical sum (OR) of product (AND) terms.
Example: $F = AB' + C'D + A'C$.

Canonical SOP: An SOP where every product term is a Minterm (contains all variables).
Notation: $F(A,B,C) = \Sigma m(1, 4, 5, 6, 7)$

⇒2.2 Product of Sums (POS)

A Boolean expression consisting of the logical product (AND) of sum (OR) terms.
Example: $F = (A + B') \cdot (C' + D)$.

Canonical POS: A POS where every sum term is a Maxterm.
Notation: $F(A,B,C) = \Pi M(0, 2, 3)$

Note: The Minterms of a function are exactly the indices missing from its Maxterms. If a 3-variable function has minterms $\Sigma(1,4,5,6,7)$, its maxterms are $\Pi(0,2,3)$.

Minimizing expressions using Boolean algebra theorems is tedious and prone to human error. The Karnaugh Map (K-Map) is a graphical tool that systematically minimizes expressions up to 5 variables.

⇒3.1 The Principle

A K-Map is an array of cells, where each cell represents a Minterm. The cells are arranged so that physically adjacent cells differ by exactly one variable (Gray code ordering).

Because adjacent cells differ by only one variable, if two adjacent cells contain a '1', they can be combined to eliminate the variable that changes state (e.g., $A'BC + ABC = BC(A' + A) = BC$).

⇒4.1 2-Variable K-Map

For $n=2$ variables (A, B), the map has $2^2 = 4$ cells.
Rows are labeled A (0, 1), Columns are labeled B (0, 1).
Cells represent $m_0, m_1, m_2, m_3$.

⇒4.2 3-Variable K-Map

For $n=3$ variables (A, B, C), the map has $2^3 = 8$ cells (usually drawn as 2 rows, 4 columns).

Row labels (A): `0`, `1`.
Column labels (BC): `00`, `01`, `11`, `10` (Notice the Gray Code sequence!)

Cell indices (Top row): 0, 1, 3, 2
Cell indices (Bottom row): 4, 5, 7, 6

Why Gray Code? It ensures that column 01 and column 11 differ by only one bit (the B bit). If we used standard binary (01 then 10), two bits would change, destroying the logic of spatial adjacency.

For $n=4$ variables (A, B, C, D), the map has $2^4 = 16$ cells (4x4 grid).

Row labels (AB): `00`, `01`, `11`, `10`
Column labels (CD): `00`, `01`, `11`, `10`

⇒5.1 Cell Mapping Index

Mapping truth table row numbers to the 16 cells (Row by Row):

Row 1 (00): `0` `1` `3` `2`
Row 2 (01): `4` `5` `7` `6`
Row 3 (11): `12` `13` `15` `14` <-- Notice row 3 and 4 are swapped due to Gray code
Row 4 (10): `8` `9` `11` `10`

To plot a function given in Canonical SOP, e.g., $F = \Sigma m(0,1,2,5,8,9,10)$, simply place a '1' in the corresponding numbered cells. All other cells get '0'.

The goal is to group adjacent '1's to form the largest possible blocks. The larger the block, the more variables are eliminated.

⇒6.1 Rules for Forming Groups

• Groups must contain $1, 2, 4, 8$, or $16$ cells ($2^k$). You cannot group 3 or 6 cells.
• Groups must be rectangular or square (no diagonals, no L-shapes).
• A group must be as large as mathematically possible.
• Every '1' must be part of at least one group.
• Groups can overlap (a '1' can be used in multiple groups if it helps make larger groups).
• Map Rolling: The left and right edges are considered adjacent (like a cylinder). The top and bottom edges are also adjacent. Therefore, the 4 corners of a 4-variable map form a valid group of 4.

Once the groups are drawn, we extract the minimized SOP terms.

⇒7.1 Extraction Rule

For each group, look at the row and column labels that span the group.

• If a variable remains constant across the entire group (e.g., A is '1' for the whole group), it is included in the term (as $A$).
• If a variable is '0' for the whole group, it is included as its complement ($A'$).
• If a variable changes state within the group (e.g., A is '0' in half the group and '1' in the other half), the variable is eliminated.

The final minimized expression is the logical OR (sum) of the extracted product terms.

Example: A group of 4 cells eliminates 2 variables. A group of 8 cells eliminates 3 variables.

Formal terminology used in minimization algorithms.

• Implicant: Any valid rectangular group of '1's in a K-Map. Any single '1' or valid pairing is an implicant.
• Prime Implicant (PI): A group of '1's that cannot be combined with any other '1's to form a larger valid group. (The largest possible groups you drew).
• Essential Prime Implicant (EPI): A Prime Implicant that contains at least one '1' that is not covered by any other prime implicant. These MUST be included in the final minimized expression.
• Redundant Prime Implicant: A Prime Implicant whose '1's are completely covered by other Essential Prime Implicants. These are discarded to achieve minimization.

In some digital systems, certain input combinations will never occur. For example, in a BCD system, inputs 1010 to 1111 (10 to 15) are invalid. We do not care what the output is for these inputs.

These are called Don't Care conditions, denoted by 'X' or 'd' in the truth table and K-Map. Notation: $F = \Sigma m(0, 1, 2) + d(3, 4)$

⇒9.1 Utilizing Don't Cares in K-Maps

• An 'X' cell can be treated as a '1' if treating it as a '1' helps form a larger group (thus reducing the final expression).
• An 'X' cell can be treated as a '0' and ignored if including it doesn't help form a larger group.
• You are never required to group an 'X'. They are purely optional tools to make other groups larger.

K-Maps can also minimize functions into the POS format (AND of ORs).

⇒10.1 Differences from SOP Minimization

• Instead of grouping the 1s, we plot and group the 0s (which represent the Maxterms).
• When extracting the expression for a group, the rule for variables is inverted:
  - If a variable is constant '0', write it uncomplemented (e.g., $A$).
  - If a variable is constant '1', write it complemented (e.g., $A'$).
• The extracted term is a sum (e.g., $(A + B' + C)$).
• The final expression is the product (AND) of these sum terms.

A hardware circuit built from a minimized SOP expression uses an AND-OR layout (or purely NAND-NAND). A POS expression uses an OR-AND layout (or purely NOR-NOR).

For $n=5$ variables (A, B, C, D, E), a single 2D map becomes visually confusing. We require $2^5 = 32$ cells.

⇒11.1 The 3D Layer Approach

A 5-variable map is drawn as two separate 4-variable maps (each 16 cells).

• Map 1: Corresponds to $A = 0$. Represents minterms $m_0$ to $m_{15}$.
• Map 2: Corresponds to $A = 1$. Represents minterms $m_{16}$ to $m_{31}$.

⇒11.2 Grouping across Maps

Imagine Map 1 is a transparent sheet of glass lying exactly on top of Map 2. You can form 3D groups! A cell in Map 1 is considered adjacent to the exact corresponding cell in Map 2.

If a '1' at $m_0$ in Map 1 is grouped with a '1' at $m_{16}$ in Map 2, the variable A changes state (from 0 to 1) and is eliminated from that term.

K-Maps become practically impossible for humans to use when $n \ge 6$. The Quine-McCluskey method is an algorithmic, tabular approach that can handle any number of variables and is easily programmed into computers.

⇒12.1 Phase 1: Finding Prime Implicants

• 1. List all given minterms and convert them to binary.
• 2. Group the minterms by the number of 1s in their binary representation (Index groups).
• 3. Compare each term in Group $i$ with every term in Group $i+1$. If they differ by exactly one bit, combine them by replacing the differing bit with a dash '-'. (e.g., `0100` and `0101` become `010-`). Place a checkmark next to the terms that combined.
• 4. Repeat this matching process on the new dashed terms until no further combinations are possible.
• 5. Any term left without a checkmark is a Prime Implicant.

⇒13.1 Phase 2: Selecting Essential Prime Implicants

Phase 1 generates all Prime Implicants, but we usually don't need all of them to cover the function.

• 1. Create a table. The rows are the Prime Implicants found in Phase 1. The columns are all the original given minterms.
• 2. Place an 'X' in the cell if a Prime Implicant covers a specific minterm.
• 3. Look for columns that have exactly one 'X'. The Prime Implicant corresponding to that row is an Essential Prime Implicant (EPI).
• 4. Add the EPI to your final equation. Cross out that row, and cross out all columns (minterms) that this EPI covers.
• 5. If there are remaining uncovered minterms, select the minimum number of remaining Prime Implicants needed to cover them (using Petrick's Method if necessary).

Mastery of K-Maps is non-negotiable for passing Digital Logic Design.

⇒14.1 University Exam Checklist

• Convert a given Boolean function into Canonical SOP and Canonical POS form.
• Minimize a 4-variable function using a K-Map. e.g., $F(A,B,C,D) = \Sigma m(0,1,2,4,5,6,8,9,12,13,14)$.
• Minimize a function containing Don't Care conditions.
• Define Prime Implicant and Essential Prime Implicant. Identify them on a drawn K-Map.
• Use the Quine-McCluskey Tabular method to minimize a 4 or 5 variable function.

⇒14.2 Common Mistakes to Avoid

• Forgetting to use Gray code `00, 01, 11, 10` on the K-Map axes.
• Forgetting map rolling (the four corners form a valid group of 4, the top row and bottom row form adjacent groups).
• Grouping 6 cells (only powers of 2 are allowed!).
• Including redundant groups. Always stop grouping when all '1's are covered.