From Boolean algebra to gate-level design. The mathematical and physical foundation of every digital system ever built.
Boolean Algebra
Boolean algebra, formalized by George Boole in 1854, is the mathematics of binary logic. Every digital circuit is ultimately an implementation of Boolean functions in silicon. Variables take only two values: 0 (false) and 1 (true).
AND
A · B
OR
A + B
NOT
~A
XOR
A ⊕ B
NAND
Universal
Fundamental Operations
AND (conjunction) — written as A·B or AB. Output is 1 only when both inputs are 1. In hardware: series transistors.
OR (disjunction) — written as A+B. Output is 1 when at least one input is 1. In hardware: parallel transistors.
NOT (complement) — written as A' or ~A. Inverts the input. In CMOS: a pMOS/nMOS inverter pair.
XOR (exclusive or) — A xor B = AB' + A'B. Output is 1 when inputs differ. Fundamental to adders and parity.
NAND — NOT-AND. Functionally complete: any Boolean function can be built from NAND gates alone.
NOR — NOT-OR. Also functionally complete. The Apollo Guidance Computer used only NOR gates.
Key Theorems
De Morgan's Laws — (AB)' = A' + B' and (A+B)' = A'B'. Convert between AND/OR by complementing. Critically important for NAND/NOR logic conversion.
Idempotent — A + A = A, A·A = A
Complement — A + A' = 1, A·A' = 0
Absorption — A + AB = A, A(A+B) = A
Distributive — A(B+C) = AB + AC, A+BC = (A+B)(A+C)
Consensus — AB + A'C + BC = AB + A'C (the BC term is redundant)
Shannon's Expansion — f(A,B,...) = A·f(1,B,...) + A'·f(0,B,...). Basis for multiplexer-based implementations and BDDs.
Truth Table
→
K-Map / Quine-McCluskey
→
Minimized SOP/POS
→
Gate-level circuit
Canonical Forms
Sum of Products (SOP) — OR of AND terms (minterms). Each minterm is a product of all variables in true or complemented form. Example: f = A'B'C + AB'C' + ABC.
Product of Sums (POS) — AND of OR terms (maxterms). Dual of SOP. Example: f = (A+B+C)(A'+B+C')(A'+B'+C).
SOP maps directly to a two-level AND-OR circuit; POS maps to OR-AND. Both can be converted to all-NAND or all-NOR.
💡 A computer chip is made of billions of tiny switches called transistors. They only understand ON (1) and OFF (0). Logic gates combine these switches to make decisions — AND means "both must be on," OR means "at least one on," and NOT flips the answer. Every app, game, and video you've ever used runs on just these three ideas!
Truth Tables
A truth table exhaustively lists every possible input combination and the corresponding output. For n inputs, the table has 2^n rows. Truth tables completely specify a combinational function.
Basic Gates
A
B
AND
OR
NAND
NOR
XOR
XNOR
0
0
0
0
1
1
0
1
0
1
0
1
1
0
1
0
1
0
0
1
1
0
1
0
1
1
1
1
0
0
0
1
Full Adder Truth Table
The full adder computes Sum = A XOR B XOR Cin, and Cout = AB + BCin + ACin. It adds three single-bit inputs and produces a sum bit and a carry-out bit.
A
B
Cin
Sum
Cout
0
0
0
0
0
0
0
1
1
0
0
1
0
1
0
0
1
1
0
1
1
0
0
1
0
1
0
1
0
1
1
1
0
0
1
1
1
1
1
1
Don't-Care Conditions
In many real designs, certain input combinations never occur (e.g., BCD digits only go 0-9, leaving 6 unused combinations in a 4-bit encoding). These "don't-care" entries (marked X or d) can be treated as either 0 or 1 during minimization, allowing simpler circuits. Don't-cares are critical for efficient Karnaugh map reduction.
Karnaugh Maps
Maurice Karnaugh introduced K-maps in 1953 as a graphical method for simplifying Boolean functions. They exploit the spatial arrangement of minterms so that adjacent cells differ by exactly one variable — enabling visual identification of simplification opportunities.
How K-Maps Work
Gray code ordering — rows and columns are labeled in Gray code (00, 01, 11, 10) so adjacent cells differ by one bit. This includes wrap-around: the leftmost and rightmost columns are adjacent, as are the top and bottom rows.
Grouping — circle groups of 1s in powers of 2 (1, 2, 4, 8). Each group eliminates variables that change within the group. A group of 2 eliminates one variable; a group of 4 eliminates two.
Prime implicants — make groups as large as possible. An implicant that cannot be further enlarged is a prime implicant. The goal is to cover all 1s with the fewest, largest prime implicants.
Essential prime implicants — a prime implicant that covers at least one minterm not covered by any other prime implicant. These must appear in the minimal solution.
2-Variable K-Map
For f(A,B) = A'B + AB = B, the K-map shows both cells in column B=1 are 1. Grouping those two cells eliminates A, leaving f = B.
4-Variable K-Map
For 4 variables (A, B, C, D), the K-map is a 4x4 grid with 16 cells. Corner grouping is common: the four corners (0000, 0010, 1000, 1010) form a valid group of 4, giving B'D'. K-maps work well up to 5-6 variables; beyond that, use the Quine-McCluskey algorithm or Espresso heuristic minimizer.
Quine-McCluskey Algorithm
A tabular method for exact Boolean minimization. Systematically finds all prime implicants, then solves a covering problem for the minimum set. Guaranteed optimal but exponential time complexity (NP-hard in general). Tools like Espresso (developed at UC Berkeley) use heuristic approaches that produce near-optimal results in practical time.
Logic Gates in Hardware
Logic gates are the physical building blocks of digital circuits. In CMOS technology (Complementary Metal-Oxide-Semiconductor), gates are built from pairs of pMOS and nMOS transistors.
CMOS Gate Implementation
Inverter (NOT) — one pMOS (pull-up) and one nMOS (pull-down). When input is 0, pMOS conducts, output goes to VDD (1). When input is 1, nMOS conducts, output goes to GND (0).
NAND gate — pMOS transistors in parallel (pull-up), nMOS in series (pull-down). Output is low only when all inputs are high. NAND is the natural gate in CMOS because it uses fewer transistors than AND.
NOR gate — pMOS in series, nMOS in parallel. Complementary to NAND. Generally slower due to stacked pMOS (which have lower mobility than nMOS).
Why NAND/NOR dominate — in CMOS, inverted outputs come "free" (the complementary structure naturally inverts). AND and OR gates require an extra inverter stage, adding delay and area. Real standard cell libraries are built primarily from NAND, NOR, and INV cells.
Fan-In and Fan-Out
Fan-in — number of inputs to a gate. High fan-in (e.g., 8-input NAND) means more stacked transistors, increasing delay. Practical limit is 4-5 inputs; larger functions are decomposed.
Fan-out — number of gates driven by one output. Each load adds capacitance, slowing the driving gate. Buffers are inserted when fan-out exceeds the drive strength.
Propagation Delay
The time from input change to stable output. Measured as t_pHL (high-to-low transition) and t_pLH (low-to-high). Total delay through a circuit is the sum of gate delays along the critical path. In modern 5nm processes, inverter delay is approximately 10-15 picoseconds.
Combinational vs Sequential Logic
Combinational Logic
Output depends only on current inputs. No memory, no feedback, no clock. Given the same inputs, a combinational circuit always produces the same outputs (after propagation delay).
Multiplexer (MUX) — selects one of 2^n inputs based on n select lines. A 2:1 MUX implements f = S'A + SB. MUXes can implement any Boolean function: an n-variable function needs a 2^(n-1):1 MUX.
Decoder — converts an n-bit binary code to 2^n output lines, exactly one active. A 3-to-8 decoder activates one of 8 lines. Used for memory address decoding and instruction decoding.
Encoder / Priority Encoder — reverse of decoder. Outputs the binary code of the highest-priority active input. Used in interrupt controllers.
Adders — ripple-carry (simple, slow: O(n) delay), carry-lookahead (fast: O(log n) delay, more area), Kogge-Stone, Brent-Kung, carry-select, carry-skip. The adder is the most critical datapath component.
ALU — Arithmetic Logic Unit. Combines an adder, logic unit, and shifter. Controlled by opcode bits to select operation (add, sub, AND, OR, shift, compare).
Comparator — determines equality or magnitude (A > B, A < B, A = B). Equality is XNOR of corresponding bits, ANDed together.
Sequential Logic
Output depends on current inputs AND stored state. Uses feedback and clock signals. Sequential circuits have memory — they can be in different states even with the same inputs.
SR Latch — the simplest storage element. Two cross-coupled NOR (or NAND) gates. Set and Reset inputs. Forbidden state when both S=R=1 (NOR version). Foundation for all sequential elements.
D Latch — adds a data input and enable signal. When enable is high, output follows input (transparent). When enable goes low, output holds its last value. Problem: transparent during the entire enable-high phase.
D Flip-Flop — edge-triggered (typically rising edge). Built from two D latches in master-slave configuration. Captures input only at the clock edge, eliminating transparency problems. The workhorse of synchronous design.
Registers — a group of D flip-flops sharing a clock. An n-bit register stores n bits. CPU registers (e.g., RISC-V's 32 x 32-bit register file) are arrays of registers with read/write ports.
Counters — sequential circuits that cycle through a sequence. Binary counter, Gray code counter, ring counter, Johnson counter. Used for addresses, timing, and control.
Finite State Machines — Moore (output depends only on state) or Mealy (output depends on state and input). Defined by states, transitions, and outputs. Implemented as flip-flops (state) plus combinational logic (next-state and output functions).
🕒Sequential logic is what gives computers memory! Combinational circuits are like a calculator — put in numbers, get an answer, done. But sequential circuits remember things. A flip-flop is like a tiny Post-it note that stores one bit (0 or 1). Your computer's RAM is millions of these Post-it notes working together!
Standard Cell Design
Standard cell methodology is the dominant approach for ASIC design. A library of pre-characterized logic cells (INV, NAND2, NOR2, DFF, etc.) with fixed heights and variable widths is provided by the foundry. The designer works at the gate level; place-and-route tools handle physical layout.
Drive strength variants — each cell type comes in multiple drive strengths. Stronger cells (bigger transistors) drive more load but use more area and power. The synthesis tool selects the appropriate strength.
Timing — propagation delay, setup time, hold time, clock-to-Q delay. Characterized across PVT (Process, Voltage, Temperature) corners: fast (FF, high V, low T), slow (SS, low V, high T), typical (TT).
Power — dynamic (switching + short-circuit) and static (leakage). Leakage is a major concern in sub-28nm nodes. Multi-Vt (threshold voltage) cells trade speed for leakage: HVT (slow, low leakage), SVT (standard), LVT (fast, high leakage).
Liberty (.lib) files — industry-standard format for timing and power data. Non-linear delay models (NLDM) capture input-slew and output-load dependencies. CCS (Composite Current Source) models are more accurate for advanced nodes.
LEF (Library Exchange Format) — describes the physical dimensions: cell height, width, pin locations, routing blockages. Used by the place-and-route tool.
From RTL to GDSII
Synthesis — converts RTL (Verilog/VHDL) to a gate-level netlist of standard cells. Tools: Synopsys Design Compiler, Cadence Genus, open-source Yosys.
Floorplanning — defines the chip area, places major blocks (memories, IPs), defines power grid, sets I/O pad ring.
Placement — positions every standard cell to minimize wirelength and timing. Global placement then legalization (snapping to rows).
Clock Tree Synthesis (CTS) — builds a balanced distribution network so the clock arrives at all flip-flops simultaneously (minimizing skew).
Routing — connects all cell pins with metal wires. Global routing (channel assignment) then detailed routing (exact tracks). Must satisfy DRC (design rule checks) for the target process.
Sign-off — final timing analysis (STA), power analysis, DRC, LVS (Layout vs Schematic), EM (electromigration), IR-drop analysis. Then GDSII tape-out to the foundry.