Elijah's Notes

Combinational Logic

3 min read

Purpose

Pin down what makes a circuit combinational, and collect the tools for turning a truth table into a small boolean expression. Smaller expressions mean fewer transistors and less delay, so minimization is where most of this note goes.

Combinational vs. sequential

The output of combinational logic depends only on the current input. There is no feedback, so the circuit holds no state. Multiplexers, decoders, and adders all work this way. Sequential logic adds feedback, so its output depends on the current input and on stored state. See Sequential Logic for that side.

Representation

The same logic can be written as text, a circuit, a truth table, or an equation. Take a car’s warning lights. The door is ajar if the driver door is open or the passenger door is open:

DoorAjar = DriverDoorOpen OR PassengerDoorOpen

The seat belt light is on if the driver’s belt is unfastened, or if a passenger is present with their belt unfastened:

SeatBeltLight = (NOT DriverSeatBeltFastened) OR (NOT PassengerSeatBeltFastened AND PassengerPresent)

The same expression drawn as a gate network:

flowchart LR
    dsb["DriverSeatBeltFastened"] --> n1["NOT"]
    psb["PassengerSeatBeltFastened"] --> n2["NOT"]
    n2 --> a1["AND"]
    pp["PassengerPresent"] --> a1
    n1 --> o1["OR"]
    a1 --> o1
    o1 --> out["SeatBeltLight"]

    style dsb fill:#e3f2fd,stroke:#1565c0
    style psb fill:#e3f2fd,stroke:#1565c0
    style pp fill:#e3f2fd,stroke:#1565c0
    style out fill:#e8f5e9,stroke:#2e7d32

Truth table to boolean expression

Sum of products: for each row where the output is 1, AND the inputs together, complementing any input that is 0 in that row. OR all of those product terms.

Product of sums: for each row where the output is 0, OR the inputs together, complementing any input that is 1 in that row. AND all of those sum terms.

Pick the form from the truth table

Sum of products generates one term per 1 in the output column, and product of sums one term per 0. When the output is mostly 0s, SOP starts smaller; when it is mostly 1s, POS does. Both minimize to equivalent logic, so start from the shorter one.

Boolean identities

IdentityDescription
A + 0 = AIdentity
A + A = AIdempotent
A + 1 = 1Annihilation
A + A' = 1Complement
A + B = B + ACommutative
A + (B + C) = (A + B) + CAssociative
A(B + C) = AB + ACDistributive
A + AB = AAbsorption

Logic minimization

Reducing complexity at the gate level buys smaller and faster hardware. The things worth counting:

  • Number of gates. Fewer gates means less area.
  • Number of literals (gate inputs). Fewer literals means less wiring.
  • Number of levels. Fewer levels means a shorter critical path and fewer dependencies.
  • Types of gates. Some gates cost fewer transistors than others.

Simpler boolean expressions generally map to smaller transistor networks, which means smaller circuit delays. CMOS transistor counts per gate, from lecture:

TypeCMOS transistors required
NOT2
AND6
OR6
NAND4
NOR4
XOR8
XNOR8

NAND and NOR are universal gates. You can build every other gate type from just one of them. For example, AND is a NAND followed by an inverter, and the inverter itself is a NAND with both inputs tied together. The table above also explains why NAND-based implementations are attractive, since NAND costs 4 transistors while AND costs 6.

DeMorgan’s law

In a circuit, the general rule for applying DeMorgan’s law to an AND or OR gate with some inverted terminals is to swap the gate type (AND becomes OR, OR becomes AND) and toggle the inversion on every terminal, so inverted points become plain and plain points become inverted.

Graph View