Skip to content

Minimization

Short Notes

Minimization involves reducing the number of gates and inputs required to implement a Boolean function, primarily using K-Maps.

Key Terms

  • Implicant: Any individual minterm or group of minterms (powers of 2) in a K-Map.
  • Prime Implicant (PI): An implicant that cannot be combined with another implicant to form a larger group.
  • Essential Prime Implicant (EPI): A PI that covers at least one minterm that is not covered by any other PI.
  • Don't Care (\(X\)): Conditions where the output value does not matter. Used to enlarge PI groups but don't need to be covered.

Key Theories & Formulas

1. Prime Implicant Determination

  • Every cell in the K-Map representing a '1' must be covered.
  • Every EPI must be part of the final minimized expression.
  • Other PIs are chosen to cover any remaining '1's using the minimum number of PIs.

2. NAND-NAND and NOR-NOR Realization

  • SOP form is implemented using NAND-NAND logic.
  • POS form is implemented using NOR-NOR logic.

Example Problems

Problem: Given \(f(A,B,C,D) = \sum m(0, 1, 5, 7, 8, 10, 14, 15)\). Find the number of PIs and EPIs.

  1. Map Groups:
    • Group 1: (0, 8) \(\implies \overline{B}\overline{C}\overline{D}\)
    • Group 2: (0, 1) \(\implies \overline{A}\overline{B}\overline{C}\)
    • Group 3: (5, 7) \(\implies \overline{A}BD\)
    • Group 4: (7, 15) \(\implies BCD\)
    • Group 5: (14, 15) \(\implies ABC\)
    • Group 6: (10, 14) \(\implies AC\overline{D}\)
    • Group 7: (8, 10) \(\implies A\overline{B}\overline{D}\)
  2. Analysis: All are PIs because none can be expanded.
  3. Essential check: Minterm 1 is only in Group 2. Minterm 5 only in Group 3. Result: Analysis depends on specific overlaps. In this case, there are usually several non-essential PIs that create multiple minimal solutions.

Hardest GATE Questions

Topic: Implicant Overlap and Minimum NAND Gate Requirement Tricky Question (GATE 2012): For a function \(f\), if the number of PIs is 5, can the number of EPIs be 6?

  • Analysis: No. By definition, every EPI is a PI. Therefore, \(EPI \le PI\).
  • The "Trap": Sometimes students count "Redundant PIs" as a separate category or double-count minterms during POS vs SOP comparison.
  • Real Complexity: Finding the absolute minimum number of 2-input NAND gates for an expression like \(A\overline{B} + \overline{A}BC\).
  • Simplify Expression.
  • Map to NAND (Bubble push).
  • Look for common sub-expressions to reuse gates. Note: Often, the minimized Boolean expression doesn't lead directly to the fewest gates if sub-expressions aren't reused

References