L14: Circuit Synthesis#

From expressions to gates.

Objective
Practice usage of theorems 5-17 of Boolean algebra.

Before the Lecture#

Required Textbook Reading:

Review 2.6 (Synthesis using AND, OR, and NOT gates)
Review 2.7 (NAND and NOR Logic Networks)
2.8 (Design Examples)

Optional Supplemental Instruction:

Circuit Synthesis Overview#

Circuit synthesis is the process of taking a Boolean function and converting it into a physical circuit implementation. This is a fundamental skill in digital design, as it bridges the gap between abstract logic and real hardware.

Key Concepts#

1. From Truth Tables to Expressions

The first step in circuit synthesis is to convert a truth table or Boolean specification into an algebraic expression. Two standard forms are commonly used:

Sum of Products (SOP): Also called disjunctive normal form. Each minterm where the output is 1 is AND’ed together, then all terms are OR’ed.
Product of Sums (POS): Also called conjunctive normal form. Each maxterm where the output is 0 is OR’ed together, then all terms are AND’ed.

2. Simplification Using Boolean Algebra

Once you have an expression, Boolean algebra theorems 5-17 help reduce the circuit complexity:

Theorem 5-9: Basic identities and complements
Theorem 10-12: Commutative, associative, and distributive laws
Theorem 13-17: De Morgan’s laws, consensus, and absorption

The goal is to minimize the number of gates and literals needed, reducing cost, power consumption, and propagation delay.

3. Gate-Level Implementation

After simplification, choose appropriate gate implementations:

AND, OR, NOT gates: Direct implementation of simplified expressions
NAND gates: Universal gates; any circuit can be built using only NAND gates
NOR gates: Also universal; any circuit can be built using only NOR gates

NAND and NOR implementations are often preferred in practice due to manufacturing efficiency and easier transistor-level realization.

Example Synthesis Process#

Start with a specification (e.g., truth table)
Write the initial Boolean expression (SOP or POS)
Apply theorems to simplify
Convert to target gate family if needed
Draw the final circuit schematic
Verify using simulation or manual checking

Common Pitfalls#

Forgetting to apply all simplification opportunities
Not considering fan-in/fan-out limitations of gates
Failing to verify the final circuit matches the original specification

Discussion & Practice
As a class, let’s walk through the examples in 2.7.