Topic 36 Key Rules
Digital Logic Systems Unit 2: Minimization Techniques
# Unit 2: Minimization Techniques and Logic Gates
Boolean expression minimization is crucial for reducing the hardware complexity (number of gates and inputs) required to implement a logic circuit. This unit covers the Principle of Duality, Canonical/Standard Forms, Karnaugh Maps, and the Quine-McCluskey tabulation method.
---
## 1. Principle of Duality
The **Principle of Duality** states that any algebraic identity in Boolean algebra remains valid if all operators and identity elements are interchanged:
* Replace AND ($\cdot$) with OR ($+$).
* Replace OR ($+$) with AND ($\cdot$).
* Replace $1$ with $0$, and $0$ with $1$.
* **Keep variables unchanged** (do NOT invert them).
*Example:*
- **Original Identity**: $A + A'B = A + B$
- **Dual Identity**: $A \cdot (A' + B) = A \cdot B$
### 1.1 Dual vs. Complement
- **Dual ($F^d$)**: Swap operators ($+ \leftrightarrow \cdot$) and constants ($0 \leftrightarrow 1$). Keep variables $x_i$ as $x_i$.
- **Complement ($F'$)**: Swap operators ($+ \leftrightarrow \cdot$) and constants ($0 \leftrightarrow 1$), **and invert all variables** ($x_i \leftrightarrow x_i'$).
$$F'(x_1, x_2, ..., x_n, +, \cdot, 0, 1) = F^d(x_1', x_2', ..., x_n', \cdot, +, 1, 0)$$
---
## 2. Canonical and Standard Forms
### 2.1 Minterms ($m$) and Maxterms ($M$)
For $n$ Boolean variables, there are $2^n$ unique product combinations (minterms) and $2^n$ unique sum combinations (maxterms).
* **Minterm ($m_i$)**: A product (AND) of all $n$ variables, where a variable is in uncomplemented form if its binary value is $1$, and in complemented form if it is $0$. Minterm evaluates to $1$ for exactly one input combination.
* **Maxterm ($M_i$)**: A sum (OR) of all $n$ variables, where a variable is in uncomplemented form if its binary value is $0$, and in complemented form if it is $1$. Maxterm evaluates to $0$ for exactly one input combination.
$$\text{Relationship: } M_i = (m_i)'$$
*Example for 3 variables ($A, B, C$):*
- Row $3$ (binary $011$):
- Minterm $m_3 = A'BC$
- Maxterm $M_3 = A + B' + C'$
### 2.2 Sum of Products (SOP) vs. Product of Sums (POS)
1. **Sum of Products (SOP)**: Terms are ANDed together, and then these product terms are ORed. Represents the active-high ($1$) outputs of a truth table.
* *Canonical SOP (Standard SOP)*: Every product term contains all variables.
*Example:* $F(A,B,C) = \sum m(1, 4, 7) = A'B'C + AB'C' + ABC$.
2. **Product of Sums (POS)**: Terms are ORed together, and then these sum terms are ANDed. Represents the active-low ($0$) outputs of a truth table.
* *Canonical POS (Standard POS)*: Every sum term contains all variables.
*Example:* $F(A,B,C) = \prod M(0, 2, 3, 5, 6) = (A+B+C)(A+B'+C)(A+B'+C')(A'+B+C')(A'+B'+C)$.
---
## 3. Karnaugh Map (K-Map) Minimization
A K-Map is a visual representation of a truth table. Cell addresses are arranged in **Gray Code** order (e.g., $00, 01, 11, 10$) so that adjacent cells differ by only one variable (unit distance). This allows minimization using the theorem $XY + XY' = X(Y+Y') = X$.
### 3.1 K-Map Structures
#### 3-Variable K-Map (8 cells)
```
BC
A \ 00 01 11 10
+----+----+----+----+
0 | m0 | m1 | m3 | m2 |
+----+----+----+----+
1 | m4 | m5 | m7 | m6 |
+----+----+----+----+
```
#### 4-Variable K-Map (16 cells)
```
CD
AB \ 00 01 11 10
+----+----+----+----+
00 | m0 | m1 | m3 | m2 |
+----+----+----+----+
01 | m4 | m5 | m7 | m6 |
+----+----+----+----+
11 | m12| m13| m15| m14|
+----+----+----+----+
10 | m8 | m9 | m11| m10|
+----+----+----+----+
```
### 3.2 Grouping Rules
1. **Pairs**: Group of $2$ adjacent cells (eliminates $1$ variable).
2. **Quads**: Group of $4$ adjacent cells (eliminates $2$ variables).
3. **Octets**: Group of $8$ adjacent cells (eliminates $3$ variables).
4. **Wrap-around**: Cells on the outer edges (left/right, top/bottom) are adjacent.
5. **Don't Care Conditions ($X$ or $d$)**: Used as $1$ if they help form a larger group (reducing terms); otherwise, they are treated as $0$ and ignored.
### 3.3 Definitions
- **Implicant**: Any individual $1$ (or group of $1$s) on the K-Map.
- **Prime Implicant (PI)**: A group of adjacent cells (size $2^k$) that cannot be combined into a larger group.
- **Essential Prime Implicant (EPI)**: A Prime Implicant that contains at least one $1$ which is not covered by any other Prime Implicant. **Every EPI must be included in the final minimized expression.**
---
## 4. Quine-McCluskey (Tabulation) Method
K-maps become unwieldy for $5$ or more variables. The **Quine-McCluskey (QM) method** is an algorithmic tabular approach that is easily programmed.
### 4.1 Step-by-Step Algorithm
1. **List Minterms**: Convert minterms to binary and group them by the number of $1$s they contain (Index groups).
2. **Compare and Combine**: Compare minterms of index group $G_i$ with $G_{i+1}$. If they differ by exactly one bit position, combine them, replace the differing bit with a dash ($-$), and place a checkmark ($\checkmark$) next to both source terms.
3. **Repeat**: Combine the new terms (comparing those with dashes in the same positions) until no further combinations are possible. Unchecked terms are **Prime Implicants (PI)**.
4. **EPI Selection**: Construct a Prime Implicant Chart.
- Rows = PIs, Columns = Minterms.
- Place an $X$ at the intersection of a row and column if the PI covers that minterm.
- Identify columns with exactly one $X$. The PI corresponding to that row is an **Essential Prime Implicant (EPI)**.
- Include EPIs in the final sum, remove covered minterms, and solve the remaining "simplified" chart (using Petrick's method if cyclic).
### 4.2 Tabulation Example
Let $F(A,B,C,D) = \sum m(0, 1, 2, 8, 10, 11, 14, 15)$.
**Step 1: Group by Number of 1's**
* **Group 0 (0 ones)**: $m_0 \ (0000)$
* **Group 1 (1 ones)**: $m_1 \ (0001)$, $m_2 \ (0010)$, $m_8 \ (1000)$
* **Group 2 (2 ones)**: $m_{10} \ (1010)$
* **Group 3 (3 ones)**: $m_{11} \ (1011)$, $m_{14} \ (1110)$
* **Group 4 (4 ones)**: $m_{15} \ (1111)$
**Step 2: Combine Terms (1st Pass)**
* $(0, 1) \rightarrow 000-$
* $(0, 2) \rightarrow 00-0$
* $(0, 8) \rightarrow -000$
* $(2, 10) \rightarrow -010$
* $(8, 10) \rightarrow 10-0$
* $(10, 11) \rightarrow 101-$
* $(10, 14) \rightarrow 1-10$
* $(11, 15) \rightarrow 1-11$
* $(14, 15) \rightarrow 111-$
**Step 3: Combine Terms (2nd Pass)**
* $(0, 2, 8, 10) \rightarrow -0-0$ (Unchecked terms from first pass: $(0,1) \ (000-)$, $(10, 11) \ (101-)$, $(10, 14) \ (1-10)$, $(11, 15) \ (1-11)$, $(14, 15) \ (111-)$ cannot be matched further with identical dash structures).
* Thus, PIs are:
- $PI_1: -0-0 \rightarrow B'D'$
- $PI_2: 000- \rightarrow A'B'C'$
- $PI_3: 101- \rightarrow AB'C$
- $PI_4: 1-1- \rightarrow AC$ (obtained from combining $(10,11,14,15) \rightarrow 1-1-$)
- $PI_5: 111- \rightarrow ABC$
*Solve the chart to select the minimum set covering all minterms.*
---
## 5. Exam Tips & Common Pitfalls
> [!WARNING]
> - **Redundant Groups in K-Map**: A group is redundant if all its cells are covered by other essential groups. Always identify EPIs first to avoid adding redundant terms.
> - **Don't Care Trap**: You do not have to group all Don't Cares ($X$). Only group them if it expands the group size (e.g., converting a pair to a quad).
> - **Gray Code Adjacency**: Remember that corners ($m_0, m_2, m_8, m_{10}$) are all adjacent in a 4-variable K-map and form a quad that simplifies to $B'D'$.