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'$.