Logic Minimization

From truth table to optimized circuit - SOP, POS, Quine-McCluskey, and NAND/NOR implementations.

Logic minimization is the process of reducing a Boolean expression to its simplest form before implementing it as a circuit. Starting from a specification, you create a truth table, derive a canonical expression, minimize it using K-maps or algorithms, and then map the result to available gate types. This complete design flow is the core skill of combinational logic design.

Objectives

  • Convert specifications to truth tables and canonical forms
  • Write Sum of Products (SOP) and Product of Sums (POS) canonical expressions
  • Understand minterm (Σ) and maxterm (Π) notation
  • Apply the complete design flow from specification to gate-level circuit
  • Introduction to Quine-McCluskey for more than 4 variables
  • Convert any expression to NAND-only or NOR-only implementation

Key Takeaways

  • SOP (Sum of Products) uses OR of AND terms; POS (Product of Sums) uses AND of OR terms
  • The design flow: specification → truth table → canonical form → minimize → implement → verify
  • K-maps are best for 2-4 variables; Quine-McCluskey handles any number
  • NAND-only: convert SOP to NAND-NAND with double inversion
  • NOR-only: convert POS to NOR-NOR with double inversion
  • Cost metrics include literal count, gate count, and propagation delay
  • Always verify the final circuit against the original truth table

Applications

  • ASIC Design: Logic synthesis tools minimize millions of gates automatically.
  • FPGA Programming: Efficient use of limited LUT resources through minimization.
  • PCB Design: Minimizing IC count reduces cost and board complexity.
  • Embedded Systems: Optimal logic for address decoders, protocol handlers, and control logic.

Practice Problems

Problem 1: Write the SOP canonical form for f(A,B,C) defined by the truth table where f=1 for inputs 001, 010, 110, 111.

Problem 2: Convert the SOP expression f = A·B + C to NAND-only implementation.

Problem 3: A circuit has literal count 8 before minimization and 4 after. What percentage reduction was achieved?

Problem 4: Design a circuit that outputs 1 when a 3-bit binary input is a prime number (2,3,5,7). Use the complete design flow.

Problem 5: What is the maximum number of prime implicants for a 3-variable function?