Reference topics: MIT 6.004 · independent study notes, not affiliated

Computation Structures

Digital logic, combinational/sequential circuits, FSM, pipelining, and processor design.

5Lectures
1Assignments
1Exams
40hDuration
1

Digital Abstraction and Boolean Logic

The Digital Abstraction Digital circuits don't exist. Every wire carries an analog voltage that could, in principle, take any value. The digital abstraction is a discipline we impose on top of...

⏱ 50 min read

The Digital Abstraction

Digital circuits don't exist. Every wire carries an analog voltage that could, in principle, take any value. The digital abstraction is a discipline we impose on top of that:

  • Any voltage below V_IL is interpreted as logical 0
  • Any voltage above V_IH is interpreted as logical 1
  • The circuit must produce outputs below V_OL or above V_OH

The gaps V_IL - V_OL and V_OH - V_IH are the noise margins NM_L and NM_H. They let us ignore noise, crosstalk, and process variation as long as the noise stays below the margins.

Why Digital?

Analog circuits amplify, filter, and process continuous signals. Digital circuits are robust, scalable, and programmable. Moore's law exists because digital circuits can shrink to nanometer dimensions while retaining their function. Analog circuits cannot.

Digital is a contract: as long as we honor the voltage thresholds, the circuit works.

Boolean Algebra

Proposed by George Boole (1854). Variables take values in {0, 1}. Operations:

  • AND: A AND B (1 if both are 1)
  • OR: A OR B (1 if either is 1)
  • NOT: inverts

Derived:

  • NAND: NOT (A AND B)
  • NOR: NOT (A OR B)
  • XOR: A XOR B (1 if A != B)

Truth Tables

Every boolean function of n variables is defined by a table with 2^n rows. Example, XOR:

A | B | A XOR B
0 | 0 | 0
0 | 1 | 1
1 | 0 | 1
1 | 1 | 0

Boolean Identities

  • Commutative: A+B = B+A, A·B = B·A
  • Associative: (A+B)+C = A+(B+C)
  • Distributive: A(B+C) = AB + AC
  • Identity: A + 0 = A, A · 1 = A
  • Complement: A + NOT A = 1, A · NOT A = 0
  • Idempotent: A + A = A, A · A = A
  • Absorption: A + AB = A
  • De Morgan: NOT(A+B) = NOT A · NOT B, NOT(A·B) = NOT A + NOT B

De Morgan is the most useful for circuit simplification.

Sum of Products (SOP)

Any boolean function can be written as an OR of AND terms, one per row of the truth table where the output is 1. This is the canonical SOP form.

Example: XOR = (NOT A)·B + A·(NOT B)

Karnaugh Maps

A graphical tool for minimizing boolean expressions. Arrange the truth table in a 2D grid with Gray-coded rows and columns (adjacent cells differ by one bit). Find the largest power-of-2 groups of 1s. Each group becomes one product term.

Example: minimize F(A,B,C) = sum of minterms 1, 3, 5, 7:

  • Group all four cells: F = C
  • Massive simplification.

Logic Gates

Physical implementations of boolean operations:

  • CMOS: complementary pull-up (PMOS) and pull-down (NMOS) networks
  • TTL: bipolar transistors (legacy)
  • Static CMOS is the dominant technology

NAND and NOR are the universal gates - any boolean function can be built from NAND alone (or NOR alone).

Key Takeaways

  • Digital abstraction imposes thresholds for robustness
  • Noise margins enable reliable operation
  • Boolean algebra is the mathematical foundation
  • De Morgan's law is the workhorse for simplification
  • SOP form is canonical but not minimal
  • Karnaugh maps minimize small functions
  • NAND/NOR are universal gates
2

Combinational Logic Design

From Truth Table to Circuit The design flow: 1. Specify the function (truth table or boolean equation) 2. Minimize (algebraic or K-map) 3. Implement with available gates 4. Verify (simulation, timing...

⏱ 50 min read

From Truth Table to Circuit

The design flow:

  1. Specify the function (truth table or boolean equation)
  2. Minimize (algebraic or K-map)
  3. Implement with available gates
  4. Verify (simulation, timing analysis)

Adders

The half adder: sum = A XOR B, carry = A AND B.

The full adder: takes A, B, Cin, produces Sum and Cout:

Sum = A XOR B XOR Cin
Cout = (A AND B) OR (Cin AND (A XOR B))

Cascading N full adders gives an N-bit ripple-carry adder. Carry propagates from LSB to MSB, causing delay proportional to N.

Carry Lookahead

To speed up addition, compute carries in parallel:

g_i = A_i AND B_i (generate)
p_i = A_i XOR B_i (propagate)
C_{i+1} = g_i OR (p_i AND C_i)

Recursively expanding gives all carries in O(log N) depth. Trade-off: more gates, but faster.

Comparators

Equality: XNOR all bit pairs, AND the results.

Magnitude comparison: ripple from MSB. If A_i > B_i and all higher bits equal, then A > B.

Multiplexers (MUX)

A 2:1 MUX selects between two inputs based on a select signal:

Y = S ? B : A
Y = S AND B OR (NOT S AND A)

Wider MUXes: 4:1 selects among 4 inputs with 2 select bits. Tree of 2:1 MUXes.

MUXes implement any function: apply all minterms as inputs and use the truth-table values as select signals.

Decoders

An N-to-2^N decoder: activates exactly one of 2^N outputs based on N select bits. Used for memory addressing, instruction decoding.

Encoders

Reverse of decoder: 2^N inputs to N outputs, giving the index of the active input. Priority encoder handles multiple active inputs by choosing the highest priority.

Tri-State Buffers

Allow multiple drivers on the same wire by enabling only one at a time:

Y = EN ? A : Z

Where Z is high impedance (disconnected). Used for shared buses.

Read-Only Memory (ROM)

A ROM is a lookup table. Address in, data out. Internally, decoder + OR array.

ROMs implement arbitrary combinational functions - handy for complex logic.

Programmable Logic Arrays (PLA)

Have both AND and OR planes that can be programmed. More flexible than ROM.

Used in FPGAs and CPLDs. Modern FPGAs use LUTs (lookup tables) that can implement any 4-6 input function.

Timing

Combinational circuits have propagation delay. The critical path determines the maximum clock frequency. Setup and hold constraints must be satisfied for the downstream flip-flops.

Key Takeaways

  • Design flow: specify, minimize, implement, verify
  • Adders: ripple vs lookahead (speed trade-off)
  • MUXes implement any function
  • Decoders address memories
  • ROMs and PLAs are programmable logic
  • Timing is critical: propagation delay limits clock speed
  • Combinational logic: output depends only on current inputs
3

Sequential Logic and Flip-Flops

Sequential Logic Combinational logic has no memory. Sequential logic has state - the output depends on current AND past inputs. Two types: Synchronous: state changes on a clock edge Asynchronous:...

⏱ 50 min read

Sequential Logic

Combinational logic has no memory. Sequential logic has state - the output depends on current AND past inputs.

Two types:

  • Synchronous: state changes on a clock edge
  • Asynchronous: state changes whenever inputs change

Synchronous is easier to design and verify, and is standard for digital systems.

Latches vs Flip-Flops

SR Latch: set/reset, level-sensitive. Problem: invalid state when both S and R are 1.

D Latch: transparent latch. When Enable = 1, Q follows D. When Enable = 0, Q holds.

D Flip-Flop: edge-triggered. Q only updates on a rising (or falling) clock edge. Two latches in a master-slave configuration.

D flip-flops are the workhorse of synchronous digital design.

Timing Parameters

Setup time t_setup: D must be stable this long before the clock edge.

Hold time t_hold: D must remain stable this long after the clock edge.

Clock-to-Q delay t_cq: Q changes this long after the clock edge.

Maximum clock frequency: limited by t_cq + combinational delay + t_setup.

Registers

N flip-flops with a shared clock form an N-bit register.

Parallel load register: D inputs from combinational logic; Q outputs to next stage.

Shift register: each FF's D comes from the previous FF's Q. Shifts data one bit per clock.

Used for serial-to-parallel conversion, delay lines, sequence generation.

Counters

A counter increments (or decrements) on each clock edge.

Ripple counter: each FF clocks the next. Simple, but accumulates delay.

Synchronous counter: all FFs clocked together. Faster, but more logic.

Johnson counter: ring of FFs with inverted feedback. 2N distinct states.

Ring counter: one-hot circulating through N FFs.

Finite State Machines (FSMs)

An FSM has:

  • States (encoded as bits)
  • Inputs
  • Outputs
  • Transition function
  • Output function

Moore machine: output depends only on state.

Mealy machine: output depends on state AND inputs. Usually fewer states.

FSMs implement protocols, controllers, and algorithms.

Example: Traffic Light Controller

States: RED, GREEN, YELLOW.
Inputs: timer_done.
Outputs: lights (R, Y, G).

Transitions:

  • RED -> GREEN when timer done
  • GREEN -> YELLOW when timer done
  • YELLOW -> RED when timer done

Encode as 2-bit state, implement with D flip-flops and combinational logic.

FSM Design Steps

  1. Draw state diagram
  2. Assign binary codes to states
  3. Derive next-state logic (truth table)
  4. Derive output logic
  5. Minimize
  6. Implement with FFs + combinational logic

Metastability

When a FF's input changes near the clock edge, its output may be undefined for a short time (metastable). Synchronizers (two or three FFs in series) resolve this.

Critical for crossing clock domains.

Key Takeaways

  • Sequential = state + combinational logic
  • D flip-flops are edge-triggered, synchronous
  • Setup and hold times constrain timing
  • Registers, shift registers, counters are building blocks
  • FSMs organize complex control logic
  • Metastability is real - use synchronizers
  • Timing closure is the art of meeting clock constraints
4

Memory and Pipelining

Memory Hierarchy Fast memory is small and expensive; large memory is slow and cheap. We use a hierarchy: Registers: a few bytes, ~1 cycle L1 cache: 32 KB, ~1-4 cycles L2 cache: 256 KB, ~10-20 cycles...

⏱ 50 min read

Memory Hierarchy

Fast memory is small and expensive; large memory is slow and cheap. We use a hierarchy:

  • Registers: a few bytes, ~1 cycle
  • L1 cache: 32 KB, ~1-4 cycles
  • L2 cache: 256 KB, ~10-20 cycles
  • L3 cache: 8 MB, ~30-40 cycles
  • DRAM: GB, ~200 cycles
  • SSD: TB, ~100,000 cycles

Data moves up on demand. Locality determines hit rate.

SRAM

Static RAM: 6 transistors per bit (4 for the cross-coupled inverters, 2 for access). Fast, but large. Used for caches.

Read/write at full clock speed. Retains data while powered.

DRAM

Dynamic RAM: 1 transistor + 1 capacitor per bit. Compact and cheap, but needs periodic refresh (charge leaks).

Slower than SRAM. Used for main memory.

Pipelining

Split a computation into stages, each of which can run independently. Multiple operations are in flight at once.

Classic 5-stage RISC pipeline:

  1. IF - instruction fetch
  2. ID - instruction decode / register read
  3. EX - execute (ALU)
  4. MEM - memory access
  5. WB - write back

Throughput: 1 instruction per cycle (instead of 5).

Pipeline Hazards

Structural hazard: two instructions want the same hardware. Fix: duplicate hardware (e.g., separate I$ and D$).

Data hazard: instruction needs a value that hasn't been written yet. Fix: forwarding (bypass) or stalling.

Control hazard: branch resolution delays fetching. Fix: branch prediction.

Forwarding

The ALU result from one instruction can be forwarded directly to the next without waiting for WB:

add r1, r2, r3 # r1 ready at end of EX
sub r4, r1, r5 # needs r1 at start of EX

Forward from add's EX output to sub's EX input. Eliminates most stalls.

Branch Prediction

Predict taken or not-taken. If wrong, flush the pipeline and restart.

Modern predictors: 2-bit saturating counters, gshare, tournament, TAGE. Accuracy > 95%.

Superscalar

Issue multiple instructions per cycle. Requires:

  • Multiple functional units
  • Register renaming (removes false dependencies)
  • Out-of-order execution

Modern CPUs issue 4-6 instructions per cycle.

Deep Pipelines

More stages = faster clock, but higher penalty on mispredicts.

Pentium 4 had 31 stages - high clock but poor IPC. Modern CPUs use 14-20 stages as a balance.

Key Takeaways

  • Memory hierarchy: small+fast to large+slow
  • SRAM (fast, big) vs DRAM (compact, cheap)
  • Pipelining increases throughput, not latency
  • Hazards: structural, data, control
  • Forwarding and branch prediction key to performance
  • Superscalar and out-of-order push further
  • Balance pipeline depth vs mispredict penalty
5

Instruction Set Architecture

What is an ISA? The Instruction Set Architecture is the contract between hardware and software. It defines: Instructions the CPU can execute Registers available Data types Addressing modes Exceptio...

⏱ 50 min read

What is an ISA?

The Instruction Set Architecture is the contract between hardware and software. It defines:

  • Instructions the CPU can execute
  • Registers available
  • Data types
  • Addressing modes
  • Exceptions and interrupts

Software written for an ISA runs on any microarchitecture implementing it.

RISC vs CISC

RISC (Reduced Instruction Set Computer):

  • Fixed-length instructions
  • Load/store architecture
  • Many registers
  • Simple decoding
  • Compiler does more

CISC (Complex Instruction Set Computer):

  • Variable-length
  • Many operations can access memory
  • Fewer registers
  • Complex decoding
  • Hardware does more

Examples: x86 is CISC. ARM, RISC-V, MIPS are RISC.

Modern x86 CPUs decode CISC into RISC-like micro-ops internally. The boundary is blurry.

RISC-V Basics

RISC-V is a clean, open ISA:

  • 32 general-purpose registers (x0-x31)
  • Fixed 32-bit instructions (with 16-bit compressed variant)
  • Load/store architecture
  • Simple addressing: base + offset

Instruction formats:

  • R-type: register-register (add, sub, and)
  • I-type: register-immediate (addi, lw)
  • S-type: store
  • B-type: branch
  • J-type: jump

Sample Instructions

add x1, x2, x3 # x1 = x2 + x3
addi x1, x2, 10 # x1 = x2 + 10
lw x1, 0(x2) # x1 = memory[x2 + 0]
sw x1, 0(x2) # memory[x2 + 0] = x1
beq x1, x2, label # branch if x1 == x2
jal x1, func # call function

Addressing Modes

  • Immediate: value is in the instruction
  • Register: value is in a register
  • Base + offset: memory[x_reg + imm]
  • PC-relative: for branches and jumps

RISC-V keeps it simple. CISC has many more modes.

Calling Convention

Function call protocol (standardized for RISC-V):

  • Arguments passed in a0-a7
  • Return value in a0
  • Return address in ra
  • Callee-saved: s0-s11 (must restore)
  • Caller-saved: t0-t6 (may be clobbered)
  • Stack pointer in sp

Registers make the compiler's job easier.

Privilege Levels

RISC-V has three:

  • User (U): application code
  • Supervisor (S): OS kernel
  • Machine (M): firmware / hypervisor

Transitions via system calls, exceptions, and interrupts.

Extensions

Base ISA + optional extensions:

  • M: integer multiply/divide
  • A: atomic operations
  • F: single-precision float
  • D: double-precision float
  • C: compressed 16-bit instructions
  • V: vector

This modular design lets designers pick only what they need.

Comparison: ISA vs Microarchitecture

ISA: what the software sees. Stable across generations.

Microarchitecture: how it's implemented. Changes every generation.

Example: x86 has been stable since 1978. The implementation went from 29,000 transistors (8086) to billions (modern).

📝 Problem Set 1: Boolean Logic, FFs, FSMs

Q1. Simplify F(A,B,C) = Σ(0,1,2,3,4,5,6,7) using a K-map.

Show Solution

All cells are 1. So F = 1 (constant 1). Trivial but valid — a common case for ground/power pins.

Q2. Design a D flip-flop-based 4-bit synchronous counter (mod-16). Sketch the logic.

Show Solution

Use 4 D FFs. Next D0 = ¬Q0. Next D1 = Q1 XOR Q0. Next D2 = Q2 XOR (Q0 AND Q1). Next D3 = Q3 XOR (Q0 AND Q1 AND Q2). This is a standard binary ripple-through counter.

Q3. What is metastability? How is it mitigated in a 2-FF synchronizer?

Show Solution

Metastability: FF's output is undefined when its input changes near the clock edge. If a downstream FF samples it, unpredictable values propagate. Fix: 2 (or 3) FFs in series. First FF may go metastable; by the time it settles, the second FF samples it cleanly. MTBF depends on clock frequency and settling time.

🎯 Midterm 1: Logic, FFs, Pipelining

Q1. Design a 2-bit comparator with outputs LT, EQ, GT. Write the boolean equations.

Show Solution

For bits A1A0 and B1B0: EQ = (A1 XNOR B1) AND (A0 XNOR B0). GT = (A1 AND ¬B1) OR (A1 XNOR B1 AND A0 AND ¬B0). LT = ¬GT AND ¬EQ.

Q2. A pipeline has 5 stages. Compute the throughput and latency for 1000 instructions.

Show Solution

Throughput: 1 instruction per cycle at steady state → 1000 cycles total (5-cycle latency filled by 1000 instructions). Latency: 5 cycles per instruction. Total time = 5 + 999 = 1004 cycles ≈ 1000 cycles. Speedup vs non-pipelined (5000 cycles) = 5x.

Q3. Explain the difference between a Moore and Mealy FSM. Which is faster? Which has fewer states?

Show Solution

Moore: output depends only on current state. Mealy: output depends on state AND inputs. Mealy reacts faster (output changes with input, no clock wait). Mealy often has fewer states. Moore is safer (glitch-free outputs on state change).