Digital Logic
The foundation of every digital system. Combinations of logic gates implement arithmetic, decision-making, memory, and control. From a single AND gate to a billion-transistor CPU, it is all built from the same primitives.
Why It Matters
Understanding gates, truth tables, and flip-flops lets you read datasheets for logic ICs, design glue logic between components, implement state machines in MCU firmware or HDL, and reason about timing. Every register, counter, and bus interface in an embedded system is digital logic.
How It Works
Basic Gates and Truth Tables
AND (A . B) OR (A + B) NOT (A')
A B | Y A B | Y A | Y
0 0 | 0 0 0 | 0 0 | 1
0 1 | 0 0 1 | 1 1 | 0
1 0 | 0 1 0 | 1
1 1 | 1 1 1 | 1
NAND (NOT AND) NOR (NOT OR) XOR (A ^ B)
A B | Y A B | Y A B | Y
0 0 | 1 0 0 | 1 0 0 | 0
0 1 | 1 0 1 | 0 0 1 | 1
1 0 | 1 1 0 | 0 1 0 | 1
1 1 | 0 1 1 | 0 1 1 | 0
NAND and NOR are universal gates — any logic function can be built from NAND alone (or NOR alone). In practice, NAND is preferred because CMOS NAND gates are faster and smaller than CMOS NOR gates.
De Morgan’s Laws
The key identities for simplifying logic:
NOT(A AND B) = (NOT A) OR (NOT B) NAND = OR of inverted inputs
NOT(A OR B) = (NOT A) AND (NOT B) NOR = AND of inverted inputs
In notation:
(A . B)' = A' + B'
(A + B)' = A' . B'
Practical use: if you only have NAND gates, apply De Morgan’s to convert any expression into NAND-only form.
Combinational Logic
Output depends only on current inputs. No memory, no clock.
Multiplexer (MUX): selects one of N inputs based on select lines.
2:1 MUX:
A ──┐
MUX──── Y = S' . A + S . B
B ──┘
S
4:1 MUX uses 2 select lines (S1, S0), chooses from 4 inputs.
An N-input MUX can implement any N-variable boolean function by wiring the inputs to 0 or 1 appropriately.
Decoder: N inputs to 2^N outputs, exactly one active at a time. Used for address decoding (select one of several memory chips based on address bits) and 7-segment display drivers.
Adder: half adder (2 bits, no carry in), full adder (2 bits + carry in). Chain N full adders for an N-bit ripple-carry adder. This is the core of the ALU.
Half adder:
Sum = A XOR B
Carry = A AND B
Full adder:
Sum = A XOR B XOR Cin
Carry = (A AND B) OR (Cin AND (A XOR B))
Sequential Logic
Output depends on current inputs AND previous state. Requires a clock signal. Has memory.
SR Flip-Flop (Set-Reset): two cross-coupled NAND or NOR gates. S=1 sets Q=1, R=1 resets Q=0. S=R=1 is forbidden (undefined output).
D Flip-Flop (Data): captures input D on the rising (or falling) clock edge. The workhorse of digital design.
D ──┤D Q├──── Q (follows D, but only updates on clock edge)
| |
CLK ──┤> Q'├──── Q' (complement)
JK Flip-Flop: like SR but with the S=R=1 case defined as “toggle.” J=K=1 flips the output. More flexible than D but less common in modern designs.
Shift Register
A chain of D flip-flops. Data shifts one position per clock edge.
Serial in → [D0] → [D1] → [D2] → [D3] → Serial out
↑ ↑ ↑ ↑
CLK CLK CLK CLK
Uses:
- Serial to parallel conversion (read serial data, read all bits in parallel)
- Parallel to serial conversion (load parallel, shift out serially)
- Driving many outputs from few MCU pins (74HC595 — 8-bit shift register with output latch, chainable)
Counter
Flip-flops configured to count clock edges.
Binary up-counter (3-bit): 000 → 001 → 010 → 011 → 100 → 101 → 110 → 111 → 000
Ripple counter: each flip-flop clocks the next (simple, but slow due to propagation delay). Synchronous counter: all flip-flops share the same clock (faster, preferred).
Practical: 74HC Series ICs
Discrete logic ICs for prototyping and glue logic. 74HC family runs on 2-6V, compatible with 3.3V and 5V systems.
| Part | Function | Pins |
|---|---|---|
| 74HC00 | Quad 2-input NAND | 14 |
| 74HC04 | Hex inverter (6x NOT) | 14 |
| 74HC08 | Quad 2-input AND | 14 |
| 74HC32 | Quad 2-input OR | 14 |
| 74HC86 | Quad 2-input XOR | 14 |
| 74HC138 | 3-to-8 decoder | 16 |
| 74HC151 | 8:1 multiplexer | 16 |
| 74HC595 | 8-bit shift register (serial in, parallel out) | 16 |
| 74HC74 | Dual D flip-flop | 14 |
| 74HC161 | 4-bit synchronous counter | 16 |
These are useful for level shifting, bus buffering, address decoding, and expanding MCU I/O. For complex logic, use an MCU or programmable logic instead.
FPGA vs CPLD
When discrete ICs are too many and an MCU is too slow or not parallel enough:
CPLD (Complex Programmable Logic Device): small (tens to hundreds of logic elements), non-volatile (keeps config on power-off), deterministic timing. Good for glue logic replacement and simple state machines.
FPGA (Field-Programmable Gate Array): large (thousands to millions of logic elements), volatile (needs configuration on boot from flash), massive parallelism. Used for high-speed DSP, protocol implementations, and custom hardware accelerators. Programmed in Verilog or VHDL.
Calculation Example
# Build a truth table and simplify
# Function: alarm sounds when (door_open AND NOT armed) OR panic_button
# D = door_open, A = armed, P = panic_button
# Y = D . A' + P
truth_table = []
for d in (0, 1):
for a in (0, 1):
for p in (0, 1):
y = (d and not a) or p
truth_table.append((d, a, p, int(y)))
# D A P | Y
# 0 0 0 | 0
# 0 0 1 | 1
# 0 1 0 | 0
# 0 1 1 | 1
# 1 0 0 | 1 <- door open, not armed
# 1 0 1 | 1
# 1 1 0 | 0 <- door open, but armed (no alarm from door)
# 1 1 1 | 1 <- panic overrides
# Implement with 74HC gates:
# 1x 74HC04 (NOT gate for A')
# 1x 74HC08 (AND gate for D . A')
# 1x 74HC32 (OR gate for result + P)
# Total: 3 ICs, or 1 NAND IC using De Morgan's transform
# 74HC595 shift register: expand 3 MCU pins to 8 outputs
# SPI-like interface: data, clock, latch
n_outputs = 24 # need 24 LEDs
chips_needed = 24 // 8 # 3 x 74HC595 chained
mcu_pins_used = 3 # data, clock, latch (same 3 pins for any chain length)Related
- Transistors as Switches — gates are built from transistor pairs
- How Computers Execute Code — CPU is gates all the way down
- Microcontroller Architecture — MCU peripherals are digital logic blocks
- Signal Integrity — fast edges from CMOS outputs cause SI issues