Lab: Introduction to Digital Design¶

Overview¶

This is a hands-on lab session that opens the digital design unit of the course. After weeks of writing C and RISC-V assembly, we now drop below the instruction set to ask a new question: how is a processor actually built out of physical components? The answer starts with the idea that a continuous, analog electrical signal can be abstracted into a clean binary 0 or 1, and that a tiny set of logic gates (NOT, AND, OR, XOR) is enough to compute anything. In this session we install and configure the Digital schematic editor, review Boolean algebra and truth tables, build our first circuits by placing gates and wiring inputs to outputs, and learn the two ideas that let designs scale: abstraction (packaging a circuit as a reusable subcircuit) and buses (carrying many bits on one wire). The work here is the direct on-ramp to Lab 08, whose deliverables are a max-of-two circuit, a 1-bit full adder, and an 8-bit ripple-carry adder.

Learning Objectives¶

Explain how an analog voltage is turned into a digital 0/1 value using high/low thresholds
Identify the four basic gates (NOT, AND, OR, XOR) and write their truth tables
Map between the three notations for the same operation: C operators, Boolean algebra, and formal logic
Install, configure, and run the Digital schematic editor on your host OS
Build a combinational circuit in Digital by placing inputs, gates, and outputs, then simulate it
Use sum-of-products to turn a truth table into a Boolean equation and then a circuit
Apply abstraction by packaging a circuit as a reusable subcircuit, and use buses to carry multi-bit signals
Set up the autograder and run the Lab 08 test suite on your machine

Prerequisites¶

Boolean / bitwise operators in C: &, |, ~, ^ (CS 315 C review and key concepts)
Binary representation of small integers (0–3 in 2 bits, 0–255 in 8 bits) and two's complement
A working shell on your host OS (macOS Terminal, Linux, or WSL Ubuntu on Windows)
Java (an OpenJDK runtime) installed, since Digital is a Java application
Familiarity with git clone for fetching the lab repository

1. Where Digital Design Fits¶

So far this course has worked top-down: C compiles to RISC-V assembly, assembly assembles to machine code, and machine code is just bits. We always treated "the hardware" as a black box that executes those bits. Starting now we open that box.

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 (analog)"]

    style D fill:#f9f,stroke:#333,stroke-width:2px
    style E fill:#f9f,stroke:#333,stroke-width:2px
    style F fill:#f9f,stroke:#333,stroke-width:2px

In a typical engineering program, digital design can span two full semesters. Here we condense the essentials into a few weeks with one concrete goal in mind: build a working RISC-V processor from a small set of gates by the end of the term. A remarkable fact underpins the whole unit — a complete computer can be assembled from a handful of gate types. The book The Elements of Computing Systems (popularly "NAND to Tetris") builds an entire machine starting from a single gate. We will not be quite that minimalist, but the spirit is identical: start from primitives, then abstract upward.

We will use the Digital application (by H. Neemann) for schematic entry, simulation, and verification: https://github.com/hneemann/Digital. A web-based alternative, Phil Peterson's "Golden Gates," was also mentioned in class. The Digital interface looks a little dated, but it does exactly what the course needs and runs anywhere Java does.

2. Analog to Digital: The Core Abstraction¶

A real wire carries a continuously varying voltage — an analog signal. The trick that makes all of digital logic possible is to stop caring about the exact voltage and instead classify it into just two categories.

Consider a wire that can swing between 0V and 5V. We pick two thresholds. Any voltage above the high threshold is read as logic 1 (high); any voltage below the low threshold is read as logic 0 (low). The undefined band in between is something a good design avoids settling in.

 5V  ──────────────────────────●●●●●●●   ┐
                          ●●●                │ read as 1
     · · · · · · · · ●● · · · · · · · ·   ┘  (high threshold)
                  ●●
               ●●
            ●●
     · · ●● · · · · · · · · · · · · · · ·     (low threshold)
 0V  ●●─────────────────────────────────  ┐ read as 0
                                          ┘  (low)

The S-shaped curve above is a signal transitioning from low to high. We do not measure where it is exactly; we only ask "is it above the high line, or below the low line?" This single act of rounding — analog → digital — is what we mean by the first and most important abstraction of the unit.

Term	Meaning
Analog	Signal that varies continuously (any voltage 0V–5V)
Digital	Signal constrained to two values, 0 and 1
High / 1	Voltage above the high threshold
Low / 0	Voltage below the low threshold

Once signals are binary, we move up one level of vocabulary: instead of "wires and devices" we talk about gates. A gate is a device that takes one or more binary inputs and produces a binary output according to a fixed rule.

In Digital's simulator, the wire colors encode this abstraction directly: green = 1, dark green = 0. A red LED means the value driving it is 1; a black LED means 0.

3. The Four Basic Gates¶

Three of these you already know as C bitwise operators; the fourth, XOR, shows up constantly in arithmetic. Each gate has three equivalent names depending on the context you're in.

Gate symbols (as drawn in lab)¶

        AND                      OR                       NOT

  a ──┐                   a ──┐                    a ──▷o── r
      │‾‾‾‾D── r              │‾‾‾‾)── r
  b ──┘                   b ──┘
       (flat back,             (curved back,            (triangle with
        round front)            pointed front)           a bubble = invert)

Three notations for the same idea¶

Gate	C code	Boolean algebra	Formal logic
AND	`r = a & b`	`r = a · b`	`r = a ∧ b`
OR	`r = a \\| b`	`r = a + b`	`r = a ∨ b`
NOT	`r = ~a`	`r = ā`	`r = ¬a`
XOR	`r = a ^ b`	`r = a ⊕ b`	`r = a ⊕ b`

A few notes on the Boolean-algebra notation, which is what we will write on paper:

AND is written like multiplication: a · b, or just ab.
OR is written like addition: a + b. (It is not numeric addition — 1 + 1 = 1 here.)
NOT is written as an overbar: ā means "not a."

Truth tables¶

A truth table lists the output for every possible combination of inputs. With two 1-bit inputs there are 2² = 4 rows.

AND — output is 1 only when both inputs are 1:

a	b	r
0	0	0
0	1	0
1	0	0
1	1	1

OR — output is 1 when at least one input is 1:

a	b	r
0	0	0
0	1	1
1	0	1
1	1	1

NOT — one input, output is the opposite:

a	r
0	1
1	0

XOR — output is 1 when the inputs differ:

a	b	r
0	0	0
0	1	1
1	0	1
1	1	0

XOR is "exclusive or": true when exactly one input is true. Notice it is the same as OR except for the 1,1 row. Keep XOR in mind — it is exactly the single-bit sum of an adder, which we build later in this lab.

A note on universality. A single gate type, NAND (NOT-AND), is universal: every other gate can be built from NANDs alone. We mention this because it is the foundation of "NAND to Tetris," but for clarity in this course we build directly from AND / OR / NOT / XOR rather than reducing everything to NAND.

4. Combining Gates into Circuits¶

Gates become useful when you wire them together so that the output of one feeds the input of another. Here is the small two-level circuit drawn in lecture:

  a=0 ──┐
        │‾‾‾D── (a·b)=0 ──┐
  b=1 ──┘                 │‾‾‾)── r = 1
                          │
  c=1 ──┐                 │
        │‾‾‾D── (c·d)=1 ──┘
  d=1 ──┘

Two AND gates feed a single OR gate. The Boolean equation that this circuit implements is read directly off the structure:

r = (a · b) + (c · d)

Let's trace the values shown: a·b = 0·1 = 0, c·d = 1·1 = 1, and 0 + 1 = 1, so r = 1. This pattern — a layer of AND gates feeding one OR gate — is so common it has a name, sum-of-products (Section 6), and it is the recipe we use to turn any truth table into a circuit.

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))

Circuits like this, where the output depends only on the current inputs (no memory of the past), are called combinational logic. Every circuit in this lab is combinational; memory elements come later in the processor unit.

5. Abstraction and Buses: How Designs Scale¶

You could in principle build a whole processor as one enormous flat sheet of gates, but no human could read or debug it. Two ideas make large designs tractable.

Abstraction (subcircuits)¶

Abstraction means hiding the internal gates of a circuit behind a clean box with named inputs and outputs, then reusing that box. Once we build and verify a 1-bit full adder, we never look inside it again — we just drop in eight copies to make an 8-bit adder. In Digital, you save a circuit as a .dig file and then place it inside another circuit as a component, exactly like calling a function in C.

Buses¶

A bus is a single drawn wire that actually carries many bits at once. Instead of drawing eight separate parallel wires for an 8-bit value, you draw one thick wire annotated with the bit width. This is the key to keeping multi-bit designs readable.

The lab goal, drawn as a black box, is an 8-bit adder:

        8                          8
  a ━━━━/━━━━┓                ┏━━━━/━━━━ r
            ┃    ┌───────┐    ┃
            ┗━━━▶│   +   │━━━▶┛
                 │ 8-bit │
            ┏━━━▶│ adder │
        8   ┃    └───────┘
  b ━━━━/━━━━┛
            ▲
            │
           bus  (one wire, /8 = eight bits wide)

The little slash with an 8 on a wire is Digital's notation for "this is a bus of width 8." Inside the box are dozens of gates; from the outside it is just r = a + b. That is abstraction and buses working together.

flowchart LR
    subgraph Inside["Inside the 8-bit adder (hidden by abstraction)"]
        FA0["full adder bit0"] --> FA1["full adder bit1"]
        FA1 --> FA2["... bit2..6 ..."]
        FA2 --> FA7["full adder bit7"]
    end
    A["a [8-bit bus]"] --> Inside
    B["b [8-bit bus]"] --> Inside
    Inside --> R["r [8-bit bus]"]

6. Sum-of-Products: From Truth Table to Circuit¶

This is the single most important procedure in the lab. Given any truth table, sum-of-products (SOP) gives you a guaranteed-correct Boolean equation, which you then drop straight into Digital as gates.

The recipe:

Write the full truth table for the output you want.
Keep only the rows where the output is 1.
For each such row, write one product (AND) term that is true for exactly that input combination: use the variable if its value is 1, and the complemented variable (overbar) if its value is 0.
OR all those product terms together. Done.

Worked example: a 1-of-the-rows function¶

Suppose r = 1 only when a=1, b=0. That single row gives the product term a · b̄ (a is 1 so use a; b is 0 so use b̄). With only one true row, the whole equation is just r = a · b̄.

Why it always works¶

Each product term is 1 for one and only one input combination — it is a "selector" for that exact row. OR-ing the selectors together produces a function that is 1 precisely on the rows you chose and 0 everywhere else. That is the definition of the truth table, so the equation matches it by construction. The cost is that SOP is not necessarily the smallest circuit (minimization is a separate topic), but it is always correct, which is what we need first.

flowchart TD
    TT["Truth table"] --> R1["Pick rows where output = 1"]
    R1 --> P["Write a product (AND) term per row"]
    P --> S["OR the product terms together"]
    S --> EQ["Boolean equation"]
    EQ --> C["AND gates → one OR gate (circuit)"]

7. Installing and Configuring Digital¶

Digital is a Java application, so the first requirement is a Java runtime. You run Digital on your host OS (macOS, Windows, or Linux) — not on a RISC-V VM or BeagleV board — because it is a GUI program.

Step-by-step setup¶

# 1. Make sure Java is installed (OpenJDK is fine). Check the version:
java -version

# 2. If Java is missing, install OpenJDK for your platform:
#    macOS (Homebrew):
brew install openjdk
#    Ubuntu / WSL Ubuntu:
sudo apt-get update && sudo apt-get install -y default-jdk

# 3. Download Digital from the releases page and unzip it:
#    https://github.com/hneemann/Digital/releases
#    Then launch the jar:
java -jar Digital.jar

On macOS you can usually just double-click Digital.jar once Java is installed. On Windows, the smoothest path for the autograder (Section 8) is WSL Ubuntu, but the Digital GUI itself runs as a normal Windows application — you do not have to run the GUI inside WSL.

Common setup mistakes¶

Symptom	Likely cause	Fix
`java: command not found`	No JDK installed, or not on `PATH`	Install OpenJDK; reopen the shell
Digital opens but autograder fails to find it	GUI on host, tests in WSL can't see the `.dig` files	Save `.dig` files where WSL can reach them (e.g. under `/mnt/c/...`)
Wrong Java version errors	Old or mismatched JDK	Install a current `default-jdk` / recent OpenJDK
Windows path confusion	Mixing Windows `C:\` and WSL `/mnt/c` paths	Keep the repo in one place and reference it consistently

Windows users were encouraged to use WSL Ubuntu specifically because it gives a Linux-style shell with easy access to the C: drive (mounted at /mnt/c), which makes the autograder tooling behave the same as on macOS and Linux. June offered to help Windows students through the WSL setup.

8. Setting Up and Running the Autograder¶

Lab 08 is graded by an autograder that drives Digital in a headless mode and checks your .dig circuits against expected truth tables. You need it running on your host OS.

# 1. Install uv (the Python tool runner the autograder uses) and put it on PATH.
#    The official one-liner:
curl -LsSf https://astral.sh/uv/install.sh | sh

# 2. Reopen your shell (or source your profile) so uv is on PATH, then verify:
uv --version

# 3. Clone your Lab08 GitHub repository:
git clone <your-lab08-repo-url>
cd lab08

# 4. Create a config.toml that tells the autograder where your Digital.jar lives.
#    (Exact keys are given in the lab repo; the idea is a path to Digital.jar.)

# 5. Run the autograder tests from inside the lab directory:
uv run <autograder-command>

The two things that trip people up:

uv not on PATH. The installer prints a line to add to your shell profile; if you skip it, uv: command not found. Reopen the terminal after installing.
Running from the wrong directory. The tests expect to find your .dig files in the repository's directory structure. Run from inside the cloned lab08 folder, and make sure files like max2.dig are named exactly as the spec requires.

A simplified bash setup script was provided in class to streamline steps 1–4. If you get stuck, the recommendation was to lean on tooling (including ChatGPT) for OS-specific path and config problems, and to ask Greg or June.

9. Building Your First Circuit in Digital (Lab 08 Part 1)¶

Part 1 is an ungraded warm-up that gets you comfortable with the editor. You build a circuit with two inputs, A and B, that drives four LEDs — one each for NOT, AND, OR, and XOR — so you can see the gates in action.

Procedure¶

Place two inputs. Add two Input components from the toolbar. Double-click each and set its label to A and B. (Labeling matters — the autograder and your own sanity depend on named pins.)
Place four gates. Drop a NOT, an AND, an OR, and an XOR gate onto the canvas, stacked vertically.
Place four LEDs. Add four LED output components to the right of the gates.
Wire it up. Drag wires from A and B to the gate inputs. The NOT gate takes only A. Connect each gate's output to its LED.
Simulate. Click the run/simulate button. Toggle A and B by clicking them and watch the LEDs.

   A ●──┬─────────────────▷o──● LED   (NOT A: red when A=0)
        │
        ├──┐
   B ●──┼──┤‾‾D────────────● LED       (A AND B: red only when both 1)
        │  │
        ├──┤‾‾)────────────● LED       (A OR  B: red when either 1)
        │  │
        └──┤‾‾D)───────────● LED       (A XOR B: red when they differ)

What you should see¶

An LED turns red when its gate outputs 1, and black when it outputs 0.
Wires show green for 1 and dark green for 0 while simulating.
Toggle through all four A,B combinations and confirm each LED matches the truth tables in Section 3.

This is the moment the abstraction becomes real: you toggle two switches and watch Boolean algebra light up.

10. Worked Example: Building the 1-bit Full Adder (Lab 08 Part 3)¶

The full adder is the heart of the lab and the building block of the 8-bit adder. A half adder adds two bits a and b. A full adder also takes a carry-in cin, so it can be chained. It produces a sum bit and a carry-out cout.

The truth table¶

Three 1-bit inputs → 2³ = 8 rows. sum is 1 when an odd number of inputs are 1; cout is 1 when two or more inputs are 1 (a majority).

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-of-products equations¶

Applying the SOP recipe from Section 6 — one product term per row where the output is 1, then OR them together — gives exactly the equations shown in the lab spec:

sum  = (ā · b̄ · cin) + (ā · b · cin̄) + (a · b̄ · cin̄) + (a · b · cin)

cout = (ā · b · cin) + (a · b̄ · cin) + (a · b · cin̄) + (a · b · cin)

Read sum row by row: it picks out the four rows 001, 010, 100, 111 — precisely the rows where an odd number of inputs are 1. cout picks out 011, 101, 110, 111 — the majority rows.

Building it in Digital¶

Add three inputs labeled exactly a, b, and cin.
Add two outputs labeled exactly sum and cout.
For each product term, use a multi-input AND gate; feed it the inputs, running each 0-variable through a NOT gate first.
OR the sum product terms into the sum output; OR the cout product terms into cout.
Save the file as exactly 1-bit-full-adder.dig.

flowchart LR
    a((a)) --> SUM["sum logic (XOR of a,b,cin)"]
    b((b)) --> SUM
    cin((cin)) --> SUM
    a --> COUT["cout logic (majority)"]
    b --> COUT
    cin --> COUT
    SUM --> s((sum))
    COUT --> co((cout))

Shortcut after it works. The SOP sum equation is logically equal to sum = a ⊕ b ⊕ cin, and cout = (a · b) + (cin · (a ⊕ b)). Once your SOP version passes, this XOR/majority form is a much smaller circuit. Either is fine for the grader, but knowing both deepens your understanding.

The C equivalent¶

If it helps to anchor the logic, here is the same full adder as C bit operations:

// 1-bit full adder using C bitwise operators.
// a, b, cin are each 0 or 1. sum and cout are each 0 or 1.
int sum  = a ^ b ^ cin;
int cout = (a & b) | (cin & (a ^ b));

11. Worked Example: max2 (Lab 08 Part 2)¶

Part 2 turns a familiar C if/else into pure combinational logic. The C fragment is:

if (a > b) {
    r = a;
} else {
    r = b;
}

Here a, b, and r are 2-bit values, so each can be 0, 1, 2, or 3. We represent each as two bits: a = (a1, a0), b = (b1, b0), and the result r = (r1, r0). The circuit must output the larger of a and b.

Building the truth table¶

Four inputs (a1 a0 b1 b0) → 2⁴ = 16 rows. For each row, decode a and b, take the max, and encode it back into r1 r0.

a1 a0	a	b1 b0	b	max	r1 r0
0 0	0	0 0	0	0	0 0
0 0	0	0 1	1	1	0 1
0 0	0	1 0	2	2	1 0
0 0	0	1 1	3	3	1 1
0 1	1	0 0	0	1	0 1
0 1	1	0 1	1	1	0 1
0 1	1	1 0	2	2	1 0
0 1	1	1 1	3	3	1 1
1 0	2	0 0	0	2	1 0
1 0	2	0 1	1	2	1 0
1 0	2	1 0	2	2	1 0
1 0	2	1 1	3	3	1 1
1 1	3	0 0	0	3	1 1
1 1	3	0 1	1	3	1 1
1 1	3	1 0	2	3	1 1
1 1	3	1 1	3	3	1 1

Because r has two bits, you write two equations — one for r1 and one for r0 — each derived by applying sum-of-products to its own column. Collect the rows where r1 = 1, write a 4-variable product term for each, and OR them; repeat for r0.

Building it in Digital¶

Add four inputs labeled exactly a1, a0, b1, b0.
Add two outputs labeled r1 and r0.
Apply SOP to the r1 column → AND/NOT/OR gates → r1.
Apply SOP to the r0 column → AND/NOT/OR gates → r0.
Save as exactly max2.dig.

You only need to submit the working circuit — not the truth table or the equations — but you should derive them on paper first so the circuit is correct by construction.

12. Scaling Up: The 8-bit Ripple-Carry Adder (Lab 08 Part 4)¶

Now abstraction pays off. An 8-bit adder is just eight 1-bit full adders chained together: each adder's cout becomes the next adder's cin. The carry "ripples" from the least significant bit to the most significant — hence ripple-carry adder.

   a0 b0   a1 b1   a2 b2          a7 b7
    │  │    │  │    │  │           │  │
  ┌─▼──▼─┐┌─▼──▼─┐┌─▼──▼─┐       ┌─▼──▼─┐
cin│ FA0 ││ FA1 ││ FA2  │ ... → │ FA7  │→ cout
  └──┬───┘└──┬───┘└──┬───┘       └──┬───┘
     │ c0──▶ │ c1──▶ │ c2 ...       │
   sum0    sum1    sum2           sum7

The first full adder takes the external cin. Each subsequent adder takes the previous adder's carry-out. The eight sum bits form the 8-bit result; the last cout is the overall carry-out.

Building it in Digital¶

Place the 1-bit-full-adder.dig you built in Part 3 as a subcircuit — eight copies.
Use buses and splitters to break the 8-bit inputs a and b into individual bits feeding the eight adders, and to merge the eight sum bits back into one 8-bit sum bus.
Wire cout of adder i into cin of adder i+1.
Inputs must be named exactly a, b, cin; outputs sum, cout. Save as exactly 8-bit-ripple-carry-adder.dig.

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 --> s0["sum0"]
    FA1 --> s1["sum1"]
    FA2 --> s2["sum2..6"]
    FA7 --> s7["sum7"]
    s0 --> SUM["sum [8-bit bus]"]
    s1 --> SUM
    s2 --> SUM
    s7 --> SUM

This is the whole arc of the lab in one picture: a tiny verified component (the full adder), reused via abstraction, connected with buses, scales into something useful. That same pattern will eventually give us an ALU and then a processor.

Key Concepts¶

Concept	Definition	Example
Analog signal	Continuously varying voltage	A wire ramping from 0V to 5V
Digital signal	Voltage classified into 0 or 1 by thresholds	Above high line = 1, below low line = 0
Gate	Device computing a fixed Boolean function of binary inputs	AND, OR, NOT, XOR
Truth table	Output listed for every input combination	2 inputs → 4 rows
AND	Output 1 only when all inputs are 1	`r = a · b`
OR	Output 1 when any input is 1	`r = a + b`
NOT	Output is the inverse of the input	`r = ā`
XOR	Output 1 when inputs differ	`r = a ⊕ b`
Sum-of-products	One AND term per true row, OR'd together	`r = (a·b) + (c·d)`
Combinational logic	Output depends only on current inputs (no memory)	An adder
Abstraction	Packaging a circuit as a reusable named box	A full adder used 8 times
Bus	One drawn wire carrying many bits	An 8-bit `/8` wire
Full adder	1-bit adder with carry-in and carry-out	`sum = a⊕b⊕cin`
Ripple-carry adder	Full adders chained `cout`→`cin`	8-bit adder from 8 full adders

Practice Problems¶

Problem 1: Read a circuit¶

Given the circuit r = (a · b) + (c · d) with inputs a=1, b=1, c=0, d=1, what is r?

Click to reveal solution

a · b = 1 · 1 = 1
c · d = 0 · 1 = 0
r = 1 + 0 = 1

`r = 1`. The OR is 1 because at least one of its inputs (the top AND) is 1.

Problem 2: XOR vs OR¶

Fill in the output column for XOR and explain the one row where XOR differs from OR.

a	b	a OR b	a XOR b
0	0	0	?
0	1	1	?
1	0	1	?
1	1	1	?

Click to reveal solution

| a | b | a OR b | a XOR b | |---|---|--------|---------| | 0 | 0 | 0 | 0 | | 0 | 1 | 1 | 1 | | 1 | 0 | 1 | 1 | | 1 | 1 | 1 | **0** | XOR matches OR on every row except `1,1`. OR is "at least one is 1," while XOR is "exactly one is 1," so when *both* inputs are 1, OR gives 1 but XOR gives 0. This is exactly why XOR equals the single-bit *sum* of `a + b`: `1 + 1` is `0` with a carry of `1`.

Problem 3: Sum-of-products from scratch¶

Build the Boolean equation for a function f(a, b) that is 1 only when the inputs differ (i.e. reconstruct XOR using sum-of-products).

Click to reveal solution

The truth table has `f = 1` on rows `a=0,b=1` and `a=1,b=0`. Write one product term per true row:

row a=0,b=1  →  ā · b
row a=1,b=0  →  a · b̄

OR them together:

f = (ā · b) + (a · b̄)

This is the classic SOP expansion of XOR. It uses two NOT gates, two AND gates, and one OR gate.

Problem 4: Carry-out of a full adder¶

For a 1-bit full adder, what is cout when a=1, b=1, cin=0? Use the truth table from Section 10, then verify with the XOR/majority form.

Click to reveal solution

From the truth table, row `a=1, b=1, cin=0` gives `sum=0, cout=1`. Verify with the compact form:

cout = (a & b) | (cin & (a ^ b))
     = (1 & 1) | (0 & (1 ^ 1))
     = 1 | (0 & 0)
     = 1 | 0
     = 1

`cout = 1` because both `a` and `b` are 1 — `1 + 1 = 10` in binary, so the sum bit is 0 and the carry is 1.

Problem 5: Counting rows¶

Lab 08 Part 2 (max2) has four inputs (a1 a0 b1 b0). How many rows does its truth table have, and why? How many rows would an adder with two 4-bit inputs have?

Click to reveal solution

max2 has `2⁴ = 16` rows — one per combination of the four 1-bit inputs. An adder with two 4-bit inputs plus a carry-in has `4 + 4 + 1 = 9` input bits, so `2⁹ = 512` rows. This is exactly why we do **not** build wide adders from a single truth table — the table explodes. Instead we use **abstraction**: build a 1-bit full adder (8 rows) once and chain copies.

Problem 6: Why ripple-carry needs a full adder, not a half adder¶

In the 8-bit ripple-carry adder, why must bits 1 through 7 use a full adder rather than a half adder? Could bit 0 use a half adder?

Click to reveal solution

Bits 1–7 each receive a **carry-in** from the adder below them, so they must add *three* bits: `a_i`, `b_i`, and the incoming carry. A half adder only adds two bits and has no carry-in, so it cannot account for the rippling carry — using one would drop carries and produce wrong sums. Bit 0 has no carry below it, so in principle it could be a half adder. In practice we use a full adder for every bit anyway: it lets the whole circuit accept an external `cin` (needed for chaining adders or doing subtraction later), and using one identical reusable component for all eight bits is cleaner — abstraction again.

Summary¶

Digital design opens the black box under machine code: a processor is built from gates, gates from wires, and wires carry voltages — but the magic is the analog → digital abstraction that turns a continuous voltage into a clean 0 or 1.
Four gates do everything we need at first: NOT, AND, OR, and XOR. Each has three equivalent notations (C operator, Boolean algebra, formal logic) and a small truth table you should know by heart.
Truth tables specify behavior, and sum-of-products converts them to circuits: keep the rows where the output is 1, write one AND term per row, OR them together — always correct, if not always minimal.
Abstraction and buses are what let designs scale: package a verified circuit as a reusable subcircuit, and draw multi-bit signals as a single bus wire instead of many parallel wires.
Digital is a Java app run on your host OS, and the Lab 08 autograder (driven by uv) must run on that same OS — WSL Ubuntu is the smooth path for Windows. Most setup problems are a missing PATH entry or running tests from the wrong directory.
The 1-bit full adder is the keystone component: it adds a, b, and cin to produce sum and cout, equivalently sum = a ⊕ b ⊕ cin and cout = (a·b) + (cin·(a⊕b)).
The 8-bit ripple-carry adder is eight full adders chained cout→cin, demonstrating the whole arc of the lab: build a small verified block once, then reuse it through abstraction and buses to build something powerful — the same pattern that will carry us all the way to a working processor.

a1 a0	a	b1 b0	b	max	r1 r0
0 0	0	0 0	0	0	0 0
0 0	0	0 1	1	1	0 1
0 0	0	1 0	2	2	1 0
0 0	0	1 1	3	3	1 1
0 1	1	0 0	0	1	0 1
0 1	1	0 1	1	1	0 1
0 1	1	1 0	2	2	1 0
0 1	1	1 1	3	3	1 1
1 0	2	0 0	0	2	1 0
1 0	2	0 1	1	2	1 0
1 0	2	1 0	2	2	1 0
1 0	2	1 1	3	3	1 1
1 1	3	0 0	0	3	1 1
1 1	3	0 1	1	3	1 1
1 1	3	1 0	2	3	1 1
1 1	3	1 1	3	3	1 1

a1 a0	a	b1 b0	b	max	r1 r0
0 0	0	0 0	0	0	0 0
0 0	0	0 1	1	1	0 1
0 0	0	1 0	2	2	1 0
0 0	0	1 1	3	3	1 1
0 1	1	0 0	0	1	0 1
0 1	1	0 1	1	1	0 1
0 1	1	1 0	2	2	1 0
0 1	1	1 1	3	3	1 1
1 0	2	0 0	0	2	1 0
1 0	2	0 1	1	2	1 0
1 0	2	1 0	2	2	1 0
1 0	2	1 1	3	3	1 1
1 1	3	0 0	0	3	1 1
1 1	3	0 1	1	3	1 1
1 1	3	1 0	2	3	1 1
1 1	3	1 1	3	3	1 1

Lab: Introduction to Digital Design¶

Overview¶

Learning Objectives¶

Prerequisites¶

1. Where Digital Design Fits¶

2. Analog to Digital: The Core Abstraction¶

3. The Four Basic Gates¶

Gate symbols (as drawn in lab)¶

Three notations for the same idea¶

Truth tables¶

4. Combining Gates into Circuits¶

5. Abstraction and Buses: How Designs Scale¶

Abstraction (subcircuits)¶

Buses¶

6. Sum-of-Products: From Truth Table to Circuit¶

Worked example: a 1-of-the-rows function¶

Why it always works¶

7. Installing and Configuring Digital¶

Step-by-step setup¶

Common setup mistakes¶

8. Setting Up and Running the Autograder¶

9. Building Your First Circuit in Digital (Lab 08 Part 1)¶

Procedure¶

What you should see¶

10. Worked Example: Building the 1-bit Full Adder (Lab 08 Part 3)¶

The truth table¶

Sum-of-products equations¶

Building it in Digital¶

The C equivalent¶

11. Worked Example: max2 (Lab 08 Part 2)¶

Building the truth table¶

Building it in Digital¶

12. Scaling Up: The 8-bit Ripple-Carry Adder (Lab 08 Part 4)¶

Building it in Digital¶

Key Concepts¶

Practice Problems¶

Problem 1: Read a circuit¶

Problem 2: XOR vs OR¶

Problem 3: Sum-of-products from scratch¶

Problem 4: Carry-out of a full adder¶

Problem 5: Counting rows¶

Problem 6: Why ripple-carry needs a full adder, not a half adder¶

Further Reading¶

Summary¶

a1 a0	a	b1 b0	b	max	r1 r0
0 0	0	0 0	0	0	0 0
0 0	0	0 1	1	1	0 1
0 0	0	1 0	2	2	1 0
0 0	0	1 1	3	3	1 1
0 1	1	0 0	0	1	0 1
0 1	1	0 1	1	1	0 1
0 1	1	1 0	2	2	1 0
0 1	1	1 1	3	3	1 1
1 0	2	0 0	0	2	1 0
1 0	2	0 1	1	2	1 0
1 0	2	1 0	2	2	1 0
1 0	2	1 1	3	3	1 1
1 1	3	0 0	0	3	1 1
1 1	3	0 1	1	3	1 1
1 1	3	1 0	2	3	1 1
1 1	3	1 1	3	3	1 1