# Lab: Introduction to Digital Design ## CS 315 Computer Architecture --- ## Where We Are We've worked *top-down*: C → RISC-V assembly → machine code → hardware. **Today we open the hardware black box.** <div class="mermaid"> flowchart TD A["C source"] --> B["RISC-V assembly"] B --> C["Machine code (bits)"] C --> D["Processor (hardware)"] D --> E["Digital logic circuits"] E --> F["Gates: NOT / AND / OR / XOR"] F --> G["Wires & voltages"] </div> --- ## Learning Objectives - Explain how analog voltage becomes digital 0/1 - Identify the four basic gates and their truth tables - Map between C operators, Boolean algebra, and formal logic - Install and run the **Digital** schematic editor - Build and simulate combinational circuits - Apply **sum-of-products** to convert truth tables to circuits - Use **abstraction** (subcircuits) and **buses** to scale designs --- ## Lab 08 Deliverables | Part | Circuit | File | |------|---------|------| | 1 | Warm-up: gates + LEDs | (ungraded) | | 2 | 2-bit max-of-two | `max2.dig` | | 3 | 1-bit full adder | `1-bit-full-adder.dig` | | 4 | 8-bit ripple-carry adder | `8-bit-ripple-carry-adder.dig` | <div class="info-box"> File names must match exactly — the autograder checks them by name. </div> --- ## Analog to Digital: The Key Abstraction A real wire carries a continuously varying voltage (0V–5V). We pick **two thresholds** and ignore everything in between: | Voltage | Meaning | |---------|---------| | Above high threshold | Logic **1** | | Below low threshold | Logic **0** | | Between thresholds | Undefined (avoid!) | <div class="highlight-box"> This single act of rounding — analog → digital — is the first and most important abstraction of the entire unit. </div> --- ## In Digital's Simulator The wire colors make the abstraction visible: - **Green wire** = logic 1 - **Dark green wire** = logic 0 - **Red LED** = output is 1 - **Black LED** = output is 0 You toggle a switch and watch Boolean algebra light up. --- ## The Four Basic Gates | Gate | C code | Boolean | Formal | |------|--------|---------|--------| | AND | `a & b` | `a · b` | `a ∧ b` | | OR | `a \| b` | `a + b` | `a ∨ b` | | NOT | `~a` | `ā` | `¬a` | | XOR | `a ^ b` | `a ⊕ b` | `a ⊕ b` | <div class="info-box"> Boolean OR uses <code>+</code> notation, but <strong>1 + 1 = 1</strong> here — it is not numeric addition. </div> --- ## Truth Tables: AND and OR <div class="two-column"> <div> **AND** — both inputs must be 1 | a | b | a·b | |---|---|-----| | 0 | 0 | 0 | | 0 | 1 | 0 | | 1 | 0 | 0 | | 1 | 1 | **1** | </div> <div> **OR** — at least one input is 1 | a | b | a+b | |---|---|-----| | 0 | 0 | 0 | | 0 | 1 | **1** | | 1 | 0 | **1** | | 1 | 1 | **1** | </div> </div> --- ## Truth Tables: NOT and XOR <div class="two-column"> <div> **NOT** — output is the inverse | a | ā | |---|---| | 0 | **1** | | 1 | **0** | </div> <div> **XOR** — inputs must differ | a | b | a⊕b | |---|---|-----| | 0 | 0 | 0 | | 0 | 1 | **1** | | 1 | 0 | **1** | | 1 | 1 | 0 | </div> </div> <div class="highlight-box"> XOR = OR except when both inputs are 1. This makes XOR the single-bit <em>sum</em> of a + b. </div> --- ## Gate Universality - **NAND** (NOT-AND) is *universal*: every gate can be built from NANDs alone - This is the foundation of "NAND to Tetris" - In this course we build directly from AND / OR / NOT / XOR for clarity <div class="info-box"> A complete computer can be assembled from a single gate type. We aim to build a working RISC-V processor from a small set of gates by end of term. </div> --- ## Combining Gates: Sum-of-Products Circuit Wire two AND gates into an OR gate: ```text r = (a · b) + (c · d) ``` <div class="mermaid"> flowchart LR a((a)) --> AND1["AND"] b((b)) --> AND1 c((c)) --> AND2["AND"] d((d)) --> AND2 AND1 -->|"a·b"| OR1["OR"] AND2 -->|"c·d"| OR1 OR1 --> r((r)) </div> Trace: `a=0,b=1,c=1,d=1` → `0 + 1 = 1` --- ## Combinational Logic Circuits where output depends **only on current inputs** (no memory of the past) are called **combinational**. - Every circuit in today's lab is combinational - Memory elements (flip-flops, registers) come later in the processor unit <div class="info-box"> Combinational logic is stateless — the same inputs always produce the same outputs. </div> --- ## Sum-of-Products: The Recipe **From any truth table to a correct Boolean equation:** <div class="mermaid"> flowchart TD TT["Write the full truth table"] --> R1["Keep rows where output = 1"] R1 --> P["Write one AND term per row\n(use variable if 1, complement if 0)"] P --> S["OR all the AND terms together"] S --> EQ["Boolean equation → circuit"] </div> --- ## Sum-of-Products: Example Reconstruct XOR using SOP — `f = 1` when inputs differ: | a | b | f | |---|---|---| | 0 | 0 | 0 | | 0 | 1 | **1** | | 1 | 0 | **1** | | 1 | 1 | 0 | - Row `a=0, b=1` → product term: `ā · b` - Row `a=1, b=0` → product term: `a · b̄` **Result:** `f = (ā · b) + (a · b̄)` — exactly XOR! --- ## Abstraction and Buses Two ideas that let designs scale beyond a handful of gates: **Abstraction (subcircuits)** - Package a verified circuit as a named, reusable black box - Like calling a function in C — hide the internals, expose the interface - In Digital: save as `.dig`, then place as a component in another circuit **Buses** - One drawn wire carrying many bits (annotated `/8` for 8-bit width) - Keeps multi-bit designs readable instead of dozens of parallel wires --- ## Bus Example: 8-Bit Adder <div class="mermaid"> flowchart LR subgraph Inside["Inside (hidden by abstraction)"] FA0["FA bit0"] -->|c0| FA1["FA bit1"] FA1 -->|c1| FA2["... bit2-6 ..."] FA2 -->|c6| FA7["FA bit7"] end A["a [8-bit bus]"] --> Inside B["b [8-bit bus]"] --> Inside Inside --> R["sum [8-bit bus]"] Inside --> cout((cout)) </div> From the outside: just `sum = a + b`. The eight full adders are invisible. --- ## Installing Digital Digital is a Java application — run it on your **host OS** (macOS, Windows, Linux). ```bash # Check Java is installed java -version # macOS (Homebrew) brew install openjdk # Ubuntu / WSL sudo apt-get update && sudo apt-get install -y default-jdk # Download Digital.jar from GitHub releases, then: java -jar Digital.jar ``` <div class="highlight-box"> Windows users: run the Digital GUI as a normal Windows app, but use <strong>WSL Ubuntu</strong> for the autograder. </div> --- ## Common Setup Issues | Symptom | Cause | Fix | |---------|-------|-----| | `java: command not found` | No JDK or not on PATH | Install OpenJDK; reopen shell | | Autograder can't find `.dig` files | GUI on host, tests in WSL | Save files under `/mnt/c/...` | | Wrong Java version errors | Old or mismatched JDK | Install current `default-jdk` | | Windows path confusion | Mixing `C:\` and `/mnt/c` | Keep repo in one place | --- ## Setting Up the Autograder ```bash # 1. Install uv (Python tool runner) curl -LsSf https://astral.sh/uv/install.sh | sh # 2. Reopen shell so uv is on PATH, then verify uv --version # 3. Clone your Lab08 repo git clone <your-lab08-repo-url> cd lab08 # 4. Create config.toml pointing to Digital.jar # 5. Run the tests uv run <autograder-command> ``` <div class="info-box"> Run from inside the cloned <code>lab08</code> folder. File names must match exactly (e.g., <code>max2.dig</code>). </div> --- ## Part 1: Warm-Up Circuit (Ungraded) Build a circuit with inputs `A` and `B` driving four LEDs: 1. Place two **Input** components, label them `A` and `B` 2. Place a NOT, AND, OR, and XOR gate 3. Place four **LED** output components 4. Wire `A` and `B` to each gate's inputs (NOT takes only `A`) 5. Connect each gate's output to its LED 6. Click **Simulate**, toggle `A` and `B`, verify the truth tables <div class="highlight-box"> Green wire = 1, dark green = 0. Red LED = output 1, black LED = output 0. </div> --- ## Part 2: max2 — 2-Bit Maximum Implement in pure combinational logic: ```c r = (a > b) ? a : b; // a, b, r are 2-bit values (0–3) ``` - Inputs: `a1 a0 b1 b0` (four 1-bit pins) - Outputs: `r1 r0` (two 1-bit pins) - Truth table: `2⁴ = 16` rows - Apply SOP separately to the `r1` column and the `r0` column - Save as **exactly** `max2.dig` --- ## Part 2: max2 Truth Table (excerpt) | a1 a0 | a | b1 b0 | b | max | r1 r0 | |-------|---|-------|---|-----|-------| | 0 0 | 0 | 0 1 | 1 | 1 | 0 1 | | 0 1 | 1 | 1 0 | 2 | 2 | 1 0 | | 1 0 | 2 | 0 1 | 1 | 2 | 1 0 | | 1 1 | 3 | 1 0 | 2 | 3 | 1 1 | Derive `r1` and `r0` equations separately using SOP, then build in Digital. --- ## Part 3: 1-Bit Full Adder A **full adder** adds `a`, `b`, and carry-in `cin`, producing `sum` and `cout`. | 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 | `sum` = 1 when an **odd** number of inputs are 1. `cout` = 1 when **two or more** are 1. --- ## Full Adder: SOP Equations Applying sum-of-products to the truth table: ```text sum = (ā·b̄·cin) + (ā·b·c̄in) + (a·b̄·c̄in) + (a·b·cin) cout = (ā·b·cin) + (a·b̄·cin) + (a·b·c̄in) + (a·b·cin) ``` **Shortcut (equivalent, fewer gates):** ```c int sum = a ^ b ^ cin; int cout = (a & b) | (cin & (a ^ b)); ``` <div class="info-box"> Either form passes the autograder. SOP is always correct; the XOR/majority form is more compact. </div> --- ## Full Adder: Structure <div class="mermaid"> flowchart LR a((a)) --> SUM["sum logic\n(a XOR b XOR cin)"] b((b)) --> SUM cin((cin)) --> SUM a --> COUT["cout logic\n(majority vote)"] b --> COUT cin((cin)) --> COUT SUM --> s((sum)) COUT --> co((cout)) </div> Save as **exactly** `1-bit-full-adder.dig` with pins labeled `a`, `b`, `cin`, `sum`, `cout`. --- ## Part 4: 8-Bit Ripple-Carry Adder Chain **eight full adders**: each `cout` becomes the next `cin`. <div class="mermaid"> flowchart LR cin((cin)) --> FA0["FA bit0"] FA0 -->|c0| FA1["FA bit1"] FA1 -->|c1| FA2["FA bit2"] FA2 -->|"c2..c6"| FA7["FA bit7"] FA7 --> cout((cout)) FA0 & FA1 & FA2 & FA7 --> SUM["sum [8-bit bus]"] </div> - Place `1-bit-full-adder.dig` as a subcircuit — **eight copies** - Use buses and splitters to connect 8-bit inputs `a`, `b` - Save as **exactly** `8-bit-ripple-carry-adder.dig` --- ## Why "Ripple-Carry"? The carry **ripples** from bit 0 to bit 7 in sequence. - Bit 0's `cout` → bit 1's `cin` - Bit 1's `cout` → bit 2's `cin` - ...and so on up to bit 7 <div class="highlight-box"> This is abstraction in action: build one small verified component (full adder), then reuse it eight times via subcircuits and buses to build something powerful. </div> --- ## Why Use Full Adders for All 8 Bits? - Bits 1–7 each receive a carry-in from the adder below — they must add **three** bits (`a_i`, `b_i`, `cin_i`) - A half adder only adds two bits; using one would drop the rippling carry - Bit 0 could theoretically use a half adder (no carry below it) - In practice: use a full adder for every bit to accept an external `cin` and reuse one identical component — cleaner abstraction --- ## Key Concepts | Concept | Definition | |---------|------------| | Combinational logic | Output depends only on current inputs | | Sum-of-products | AND per true row, OR'd together | | Abstraction | Reusable named subcircuit (like a function) | | Bus | One wire carrying many bits (`/8` = 8-bit) | | Full adder | Adds a, b, cin → sum, cout | | Ripple-carry | Full adders chained cout→cin | --- ## Summary 1. **Analog → digital**: threshold classification turns voltages into clean 0/1 values 2. **Four gates**: NOT, AND, OR, XOR — three notations (C, Boolean, formal), small truth tables 3. **Sum-of-products**: keep rows where output = 1, write one AND term per row, OR together — always correct 4. **Abstraction + buses**: package verified circuits as reusable subcircuits; draw multi-bit signals as a single annotated wire 5. **Full adder**: `sum = a⊕b⊕cin`, `cout = (a·b)+(cin·(a⊕b))` — the keystone component 6. **8-bit adder = 8 full adders chained** via cout→cin — the whole arc of the lab in one circuit