Reference topics: 6.004 ยท independent study notes, not affiliated

Computation Structures

Introduces the design of digital systems from logic gates to complete processors. Covers combinational and sequential logic, finite-state machines, instruction-set architectures, pipelines, caches, and virtual memory.

8Lectures
2Assignments
2Exams
1hDuration
1

From Electrons to Logic Gates

Overview Bridge analog to digital design. Key ideas MOSFETs as switches; CMOS as logic. Digital signal is a voltage range. Noise margins make it reliable. Worked example 3.3V logic high might be...

โฑ 1 min read

Overview

Bridge analog to digital design.

Key ideas

  • MOSFETs as switches; CMOS as logic.
  • Digital signal is a voltage range.
  • Noise margins make it reliable.

Worked example

3.3V logic high might be 2.4-3.3V. Above 2.0V is 1.

Common pitfalls

  • Assuming exact voltages.

Why it matters

Ladder: transistors -> gates -> modules -> processor.

2

Combinational Logic and Boolean Algebra

Overview Boole algebra is the math of digital logic. Key ideas AND, OR, NOT, XOR, NAND, NOR. Truth tables. Karnaugh maps. Worked example Simplify A_NOT_B + A_B_NOT + AB to A + B. Common pitfalls ...

โฑ 1 min read

Overview

Boole algebra is the math of digital logic.

Key ideas

  • AND, OR, NOT, XOR, NAND, NOR.
  • Truth tables.
  • Karnaugh maps.

Worked example

Simplify A_NOT_B + A_B_NOT + AB to A + B.

Common pitfalls

  • Ignoring dont-cares.

Why it matters

Fewer gates is not always faster.

3

Sequential Logic and Flip-Flops

Overview Storage requires feedback. Key ideas Latch: level-sensitive. Flip-flop: edge-triggered. Setup and hold times. Worked example D flip-flop stores one bit on rising edge. Common pitfalls ...

โฑ 1 min read

Overview

Storage requires feedback.

Key ideas

  • Latch: level-sensitive.
  • Flip-flop: edge-triggered.
  • Setup and hold times.

Worked example

D flip-flop stores one bit on rising edge.

Common pitfalls

  • Ignoring setup/hold violations.

Why it matters

Synchronous design makes timing tractable.

4

Finite State Machines

Overview States, inputs, transitions, outputs. Key ideas Moore: output = f(state). Mealy: output = f(state, input). Any FSM can be built from flip-flops and gates. Worked example Traffic light states...

โฑ 1 min read

Overview

States, inputs, transitions, outputs.

Key ideas

  • Moore: output = f(state).
  • Mealy: output = f(state, input).
  • Any FSM can be built from flip-flops and gates.

Worked example

Traffic light states red/yellow/green with timer transitions.

Common pitfalls

  • Missing transitions.

Why it matters

Traffic lights, protocols, and CPU control units.

5

Instruction Set Architectures

Overview The ISA is the contract between hardware and software. Key ideas Registers, memory, PC. RISC vs CISC. Beta ISA is a clean RISC for teaching. Worked example To add two numbers: load, add,...

โฑ 1 min read

Overview

The ISA is the contract between hardware and software.

Key ideas

  • Registers, memory, PC.
  • RISC vs CISC.
  • Beta ISA is a clean RISC for teaching.

Worked example

To add two numbers: load, add, store.

Common pitfalls

  • Assuming complex ISAs are faster.

Why it matters

Compilers target an ISA; OSes save and restore its state.

6

Pipelining

Overview Execute instructions in parallel by overlapping stages. Key ideas Five stages: fetch, decode, execute, memory, write-back. Hazards: data, control, structural. Forwarding handles most. Worked...

โฑ 1 min read

Overview

Execute instructions in parallel by overlapping stages.

Key ideas

  • Five stages: fetch, decode, execute, memory, write-back.
  • Hazards: data, control, structural.
  • Forwarding handles most.

Worked example

Ideal CPI = 1.

Common pitfalls

  • Forgetting pipeline fill/drain.

Why it matters

Ideal speedup 5x, real workloads 3-4x.

7

Caches and Memory Hierarchy

Overview CPU speed grows faster than memory speed. Key ideas Temporal and spatial locality. Direct-mapped, set-associative, fully associative. Write-through vs write-back. Worked example Good...

โฑ 1 min read

Overview

CPU speed grows faster than memory speed.

Key ideas

  • Temporal and spatial locality.
  • Direct-mapped, set-associative, fully associative.
  • Write-through vs write-back.

Worked example

Good locality runs several times faster on identical hardware.

Common pitfalls

  • Ignoring cache-line effects.

Why it matters

Programming for locality is highest-leverage.

8

Virtual Memory

Overview Private, contiguous address space per process. Key ideas Pages, page tables, TLB. Page faults load from disk. Protection falls out of translation. Worked example Two processes both use...

โฑ 1 min read

Overview

Private, contiguous address space per process.

Key ideas

  • Pages, page tables, TLB.
  • Page faults load from disk.
  • Protection falls out of translation.

Worked example

Two processes both use virtual 0x1000, mapped differently.

Common pitfalls

  • Forgetting TLB is a cache.

Why it matters

On 64-bit, VM is more about protection.

๐Ÿ“ Boolean Logic

Q1. Simplify A'B + AB' + AB.

Show Solution

A + B.

๐Ÿ“ FSM Design

Q1. Detect sequence 1011.

Show Solution

4 states S0-S3.

๐ŸŽฏ Midterm Exam

Q1. 2-bit counter with D flip-flops.

Show Solution

Next-state logic for 00->01->10->11.

๐ŸŽฏ Final Exam

Q1. 5-stage pipeline speedup.

Show Solution

Ideal ~5x, reduced by hazards.