4 min read
On this page

Logic Gates

Logic gates are the physical building blocks of digital circuits. Each gate implements a Boolean function using transistors.

Fundamental Gates

AND Gate

Output is 1 only when all inputs are 1.

Symbol:  A ──┐
             │D──── Y = A·B
         B ──┘

Truth table:
A B | Y
0 0 | 0
0 1 | 0
1 0 | 0
1 1 | 1

OR Gate

Output is 1 when any input is 1.

Symbol:  A ──┐
             │)──── Y = A+B
         B ──┘

Truth table:
A B | Y
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 1

NOT Gate (Inverter)

Flips the input.

Symbol:  A ──▷○──── Y = A'

Truth table:
A | Y
0 | 1
1 | 0

Universal Gates

NAND Gate

NOT-AND. Output is 0 only when all inputs are 1.

Symbol:  A ──┐
             │D○──── Y = (A·B)'
         B ──┘

Truth table:
A B | Y
0 0 | 1
0 1 | 1
1 0 | 1
1 1 | 0

Functionally complete alone. Any Boolean function can be built with only NAND gates:

  • NOT: Connect both inputs together
  • AND: NAND followed by NOT (another NAND)
  • OR: NOT both inputs, then NAND

NAND is the most common gate in CMOS technology because it's naturally efficient to implement.

NOR Gate

NOT-OR. Output is 1 only when all inputs are 0.

Symbol:  A ──┐
             │)○──── Y = (A+B)'
         B ──┘

Truth table:
A B | Y
0 0 | 1
0 1 | 0
1 0 | 0
1 1 | 0

Also functionally complete alone. Apollo Guidance Computer was built entirely from NOR gates.

XOR and XNOR

XOR (Exclusive OR)

Output is 1 when inputs differ.

Symbol:  A ──┐
             │)=──── Y = A⊕B
         B ──┘

Truth table:
A B | Y
0 0 | 0
0 1 | 1
1 0 | 1
1 1 | 0

Properties:

  • A ⊕ 0 = A (identity)
  • A ⊕ 1 = A' (complement)
  • A ⊕ A = 0 (self-inverse)
  • A ⊕ A' = 1
  • Associative and commutative
  • A ⊕ B ⊕ B = A (useful for swapping without temp: a ^= b; b ^= a; a ^= b)

Applications: Parity checking, checksums, encryption (one-time pad), arithmetic (addition without carry), comparators.

XNOR (Equivalence)

Output is 1 when inputs are the same.

Y = (A⊕B)' = A·B + A'·B'

A B | Y
0 0 | 1
0 1 | 0
1 0 | 0
1 1 | 1

Buffers

Buffer

Output equals input. No logic change. Used for signal strengthening.

A ──▷──── Y = A

Tri-State Buffer

Has an enable input. When enabled, output = input. When disabled, output is high impedance (Z) — effectively disconnected.

A ──▷──── Y = A (when EN=1)
   EN      Y = Z (when EN=0)

High impedance (Z): The output is electrically disconnected from the wire. Multiple tri-state buffers can share a single wire (bus) as long as at most one is enabled at a time.

Applications: Shared buses, memory data lines, bidirectional I/O pins.

Gate-Level Implementation

CMOS Technology

CMOS (Complementary Metal-Oxide-Semiconductor) uses pairs of NMOS and PMOS transistors:

  • NMOS: Conducts when gate = 1 (connects to ground)
  • PMOS: Conducts when gate = 0 (connects to VDD)

CMOS Inverter: PMOS on top, NMOS on bottom. Input goes to both gates. Output taken from middle.

NAND in CMOS: 2 PMOS in parallel + 2 NMOS in series. Naturally efficient. NOR in CMOS: 2 PMOS in series + 2 NMOS in parallel.

NAND is faster than NOR in CMOS (NMOS series resistance is lower than PMOS series resistance).

Fan-In

The number of inputs to a gate. High fan-in increases propagation delay (more transistors in series).

Practical limit: 4-8 inputs. For higher fan-in, cascade smaller gates.

Fan-Out

The number of gate inputs driven by one output. Each input adds capacitive load, slowing the driving gate.

Practical limit depends on technology. Insert buffers for high fan-out.

Timing

Propagation Delay (tpd)

Time from input change to output change. Has two components:

  • tpHL: High-to-low delay
  • tpLH: Low-to-high delay

Typically 10-100 ps for modern CMOS.

Contamination Delay (tcd)

Minimum time before output might change. Important for hold time analysis. tcd ≤ tpd.

Rise Time (tr) and Fall Time (tf)

Time for output to transition from 10% to 90% (rise) or 90% to 10% (fall) of VDD.

Timing Diagram

A:  ──┐     ┌──
      └─────┘
B:  ────┐ ┌────
        └─┘
Y:  ──┐   ┌──
      └───┘
      ←tpd→

Critical Path

The longest delay path through a combinational circuit determines the maximum operating frequency:

f_max = 1 / t_critical_path

Power Dissipation

Dynamic Power

P_dynamic = α · C · V² · f
  • α: activity factor (fraction of time the gate switches)
  • C: load capacitance
  • V: supply voltage
  • f: clock frequency

Dominant in modern CMOS. Reducing V is the most effective way to reduce power (quadratic effect).

Static Power (Leakage)

P_static = V · I_leak

Subthreshold leakage current flows even when transistors are "off." Becomes significant at small technology nodes (< 65nm).

Power-Delay Product

PDP = P × t_pd

Measures energy per switching event. Lower is better. A figure of merit for gate efficiency.

Gate Arrays and Standard Cells

Standard Cell Design

Pre-designed gate layouts (inverter, NAND2, NAND3, etc.) placed in rows and connected by routing.

Cell library: Contains optimized implementations of common gates with characterized timing, power, and area.

Gate Array / Sea of Gates

Pre-fabricated arrays of transistors. Only the metal interconnect layers are customized. Faster time-to-market but less optimal.

Applications in CS

  • Processor design: ALUs, control units, decoders built from gates. Critical path determines clock speed.
  • Memory: SRAM cells use cross-coupled inverters. Sense amplifiers use differential gate circuits.
  • FPGA: Lookup tables (LUTs) implement arbitrary Boolean functions. Configuration bits program the function.
  • I/O interfaces: Tri-state buffers for bidirectional data buses. Level shifters use gate circuits.
  • Clock distribution: Buffer trees distribute the clock signal to all flip-flops.
  • Signal integrity: Proper fan-out management, buffer insertion, timing closure.