Digital Design¶

Overview¶

This lecture shifts the course from software-side RISC-V emulation down to the hardware foundations that make a processor work. We map out the course hierarchy from C/Rust code all the way down to digital logic, and we introduce the three ways to design digital circuits: schematic entry, physical design, and hardware description languages. We then build up from analog voltages to logical 0s and 1s, cover the three fundamental gates (AND, OR, NOT), and use the sum-of-products methodology to derive circuits from truth tables. We apply these ideas to build a 1-bit half adder, a 1-bit full adder, and a 4-bit ripple-carry adder by composition.

Learning Objectives¶

Place digital design within the course hierarchy from C/Rust down to gates
Explain the ISA as the contract between software and hardware
Describe how analog voltages are disciplined into digital 0s and 1s
Identify and use the three fundamental gates: AND, OR, and NOT
Translate among C/Rust, Boolean algebra, and propositional-logic notation
Apply the sum-of-products methodology to derive a circuit from a truth table
Build and analyze a 1-bit half adder and 1-bit full adder
Compose full adders into a 4-bit ripple-carry adder using buses and splitters

Prerequisites¶

RISC-V Emulation — the software view of a processor
RISC-V Machine Code — binary instruction encoding
Binary numbers and bitwise operations in C and Rust

Course Hierarchy: Software Down to Hardware¶

The Complete Stack¶

Up to this point, the course has worked from C/Rust code down through assembly, machine code, and an emulated RISC-V processor. Digital design is the bottom of that stack — the level at which we actually build the processor out of gates and wires.

flowchart TD
    A["C / Rust Code<br/>(High Level)"] --> B["RISC-V Assembly"]
    B --> C["RISC-V Machine Code<br/>(Emulator)"]
    C --> D["RISC-V Processor"]
    D --> E["Digital Design<br/>(Low Level)"]
    E --> F1["Schematic Entry"]
    E --> F2["Physical Design<br/>(wires, gates)"]
    E --> F3["HDLs<br/>(Verilog, VHDL)"]

    style A fill:#e1f5fe
    style E fill:#fff3e0

Level	Description	Example
C / Rust	High-level programming language	`let sum = a + b;`
Assembly	Human-readable machine instructions	`add a0, a1, a2`
Machine Code	Binary instruction encoding	`0x00c58533`
Processor	Hardware that executes instructions	Register file, ALU, control
Digital Design	Logic gates and circuits	AND, OR, NOT

The Software / Hardware Boundary¶

The Instruction Set Architecture (ISA) — RISC-V in our case — is the contract between software and hardware. Software is written to the ISA specification, and any hardware that implements that specification can run the software.

graph TB
    subgraph "Software (SW)"
        C["C / Rust / ASM"]
    end

    subgraph "Interface"
        ISA["ISA — RISC-V"]
    end

    subgraph "Hardware (HW)"
        DL["Digital Logic"]
    end

    C --> ISA
    ISA --> DL

Three Ways to Do Digital Design¶

Approach	What You Work With	Example Tools
Schematic entry	Virtual circuits in software	Digital, Logisim
Physical design	Real components, wires, breadboards	TTL chips, FPGA dev boards
HDLs	Source code describing hardware	Verilog, VHDL (IEEE)

Verilog and VHDL are the industry standards, but they have steep learning curves. In this lecture and the next, we'll focus on schematic entry using the open-source Digital simulator so we can directly see how truth tables turn into gates and how gates compose into larger circuits.

From Analog to Digital¶

Disciplining Continuous Voltages¶

At the lowest physical level, circuits operate with continuous analog voltages. Digital logic imposes a discipline on those voltages: any voltage above a high threshold is treated as logic 1, and any voltage below a low threshold is treated as logic 0. Voltages in the transition region are not allowed to linger.

 Voltage
    |
 5.00 V  ────────────────────────    logic 1
 4.75 V  - - - - - - - - - - - -     (threshold high)
        |
        |      transition region
        |
 0.25 V  - - - - - - - - - - - -     (threshold low)
 0.00 V  ────────────────────────    logic 0

A typical TTL-style convention uses 0 V and 5 V rails. Modern CMOS logic uses lower voltages (e.g., 3.3 V, 1.8 V) but the idea is identical: pick two threshold bands and call them 0 and 1.

Primitive Building Blocks¶

Digital circuits are built from just three physical things:

Power source — provides the rails (ground and Vcc)
Wires — carry signals between components
Devices → gates — perform logical operations on signals

Fundamental Logic Gates¶

All digital circuits can be built from three fundamental gates: AND, OR, and NOT. Each has a symbol, a truth table, and several equivalent notations.

AND Gate¶

The AND gate outputs 1 only when all inputs are 1.

Symbol:

   a ─┐
      ├─D─── r
   b ─┘

Truth Table:

a	b	r = a AND b
0	0	0
0	1	0
1	0	0
1	1	1

Notation:

Style	Expression
C / Rust	`r = a & b`
Boolean Algebra	r = a · b
Logic	r = a ∧ b

OR Gate¶

The OR gate outputs 1 when any input is 1 (inclusive OR).

Symbol:

   a ─╲
      ╲─D─── r
   b ─╱

Truth Table:

a	b	r = a OR b
0	0	0
0	1	1
1	0	1
1	1	1

Notation:

Style	Expression
C / Rust	`r = a \\| b`
Boolean Algebra	r = a + b
Logic	r = a ∨ b

NOT Gate (Inverter)¶

The NOT gate outputs the opposite of its input. Drawn as a triangle with a small bubble on the output — the bubble is the universal symbol for inversion.

Symbol:

   a ──▷o── r

Truth Table:

a	r = NOT a
0	1
1	0

Notation:

Style	Expression
C / Rust	`r = !a` (or `~a` for bitwise)
Boolean Algebra	r = ā
Logic	r = ¬a

XOR Gate (Exclusive OR)¶

XOR is not fundamental — it can be built from AND, OR, and NOT — but it shows up so often that it earns its own symbol.

a	b	r = a XOR b
0	0	0
0	1	1
1	0	1
1	1	0

Style	Expression
C / Rust	`r = a ^ b`
Boolean Algebra	r = a ⊕ b
Logic	r = a ⊕ b

Key property: XOR outputs 1 when the inputs differ.

Notation Summary¶

Operation	C / Rust	Boolean Algebra	Logic
AND	`a & b`	a · b	a ∧ b
OR	`a \\| b`	a + b	a ∨ b
NOT	`!a` / `~a`	ā	¬a
XOR	`a ^ b`	a ⊕ b	a ⊕ b

Example Combinational Circuit¶

Consider the Boolean expression r = (a · b) + (c · d). It is read as "r equals (a AND b) OR (c AND d)" and translates directly into a three-gate circuit:

graph LR
    A[a] --> AND1[AND]
    B[b] --> AND1
    C[c] --> AND2[AND]
    D[d] --> AND2
    AND1 --> OR1[OR]
    AND2 --> OR1
    OR1 --> R[r]

Diagram conventions worth noting:

A dot at an intersection means the wires are connected (a junction).
A bubble on an input or output means that signal is inverted.
Wires that cross without a dot are not connected.

Building an 8-Bit Adder¶

Our target for the next two lectures is an 8-bit adder:

          8             8
  a ─────/────┐   ┌────/──── b
              │   │
           ┌──┴───┴──┐
           │  8-bit  │
           │  Adder  │
           └────┬────┘
                │ 8
               sum

We'll build this bottom-up:

Half adder: adds two 1-bit values (no carry-in)
Full adder: adds two 1-bit values plus a carry-in
Ripple-carry adder: chains full adders to add N-bit values

Half Adder: Sum of Two 1-Bit Values¶

Start with the simplest case — the sum bit (ignoring carry) when adding two 1-bit values a and b.

a	b	sum
0	0	0
0	1	1
1	0	1
1	1	0

Two rows have output 1. For each of those rows we form a product term — an AND of the input literals, inverting a variable that was 0 — and sum (OR) the products:

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

Verify with a = 0, b = 1:

sum = (ā · b) + (a · b̄)
    = (1 · 1) + (0 · 0)
    = 1 + 0
    = 1  ✓

This pattern — output 1 iff inputs differ — is exactly XOR: sum = a ⊕ b. So we can implement the 1-bit sum with either three gates (two ANDs, one OR, with inverters on the inputs) or a single XOR gate.

Half Adder Circuit¶

Using the sum-of-products realization:

 A ──┬── NOT ──┐
     │         ├─ AND ──┐
     │  B ─────┘        │
     │                  ├─ OR ── sum
     │  A ──────┐       │
     │          ├─ AND ─┘
     └── B ── NOT

A complete half adder also produces a carry-out: cout = a · b (the AND of the inputs — 1 only when both are 1).

The Sum-of-Products Methodology¶

Sum-of-products (SoP) is a systematic recipe that turns any truth table into a circuit built from AND, OR, and NOT gates:

Define your function — what should the circuit compute?
Build a truth table listing every input combination.
Identify the rows where the output is 1.
Construct a product term for each such row: a. Keep the variable as-is if the input is 1. b. Invert the variable if the input is 0.
Sum (OR) all the product terms together.

Implementation pattern in a circuit:

Use AND gates (one per product term) to realize each product.
Feed all product-term outputs into a single OR gate.
Use NOT gates (bubbles) on the inputs that need to be inverted.

Any truth table, no matter how large, can be implemented this way. It is not always the most efficient circuit (the 1-bit sum above collapses to a single XOR), but it is always correct, and that is what we need to get started.

One-Bit Full Adder¶

A full adder adds two 1-bit numbers plus a carry-in, producing a sum bit and a carry-out:

            cin
             │
        ┌────┴─────┐
   a ───┤          ├──── sum
        │  1-bit   │
        │  full    │
   b ───┤  adder   ├──── cout
        └──────────┘

Truth Table¶

There are 2³ = 8 input combinations:

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

SoP Derivation — sum¶

Pick the rows where sum = 1 and form product terms:

a	b	cin	Product Term
0	0	1	ā · b̄ · cin
0	1	0	ā · b · c̄in
1	0	0	a · b̄ · c̄in
1	1	1	a · b · cin

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

SoP Derivation — cout¶

a	b	cin	Product Term
0	1	1	ā · b · cin
1	0	1	a · b̄ · cin
1	1	0	a · b · c̄in
1	1	1	a · b · cin

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

Full Adder Circuit (sum output)¶

The sum output uses four 3-input AND gates, one per product term, feeding into a single 4-input OR gate. Inputs get bubbles (NOT gates) where the product term has a barred variable:

  a  b  cin
  │  │   │
  │  │   │   ā · b̄ · cin
  ├──┼───┤──[AND3]─┐
  │  │   │         │
  │  │   │   ā · b · c̄in
  ├──┼───┤──[AND3]─┤
  │  │   │         ├──[OR4]── sum
  │  │   │   a · b̄ · c̄in    │
  ├──┼───┤──[AND3]─┤         │
  │  │   │         │
  │  │   │   a · b · cin
  └──┴───┴──[AND3]─┘

The cout output is built the same way with its own four product terms. Note that the first and last rows of sum and the last row of cout share the same product a · b · cin, so a careful implementation can share gates.

Ripple-Carry Adder: Composition and Abstraction¶

Chaining 1-Bit Full Adders¶

Once we have a 1-bit full adder, we can build an N-bit adder by composition: line up N full adders, wire each adder's cout into the next adder's cin.

  a3 b3            a2 b2            a1 b1            a0 b0
  │  │             │  │             │  │             │  │
┌─┴──┴───┐       ┌─┴──┴───┐       ┌─┴──┴───┐       ┌─┴──┴───┐
│   FA   │ cin3  │   FA   │ cin2  │   FA   │ cin1  │   FA   │ cin0 = 0
│  bit 3 │◀──────│  bit 2 │◀──────│  bit 1 │◀──────│  bit 0 │◀──
│    cout│       │    cout│       │    cout│       │    cout│
└───┬────┘       └───┬────┘       └───┬────┘       └───┬────┘
    │                │                │                │
   s3               s2               s1               s0
    ▲
    │
  cout4  (final carry-out)

This is a 4-bit ripple-carry adder. The carry "ripples" from the least-significant bit up to the most-significant bit.

A concrete example: a = 0101, b = 0011, cin = 0 → sum = 1000, cout = 0 (i.e., 5 + 3 = 8).

Buses and Splitters¶

Drawing four separate wires for a 4-bit input is tedious, so schematic tools introduce buses: a single thick wire that carries multiple bits. A splitter fans a bus out into its individual bit signals (and a combiner does the reverse). In the diagram above, a and b are 4-bit buses that get split into a3 a2 a1 a0 and b3 b2 b1 b0 before feeding into the four full adders.

The 4-Bit Adder as an Opaque Block¶

Once we've built the 4-bit ripple-carry adder, we can treat it as a single component with two 4-bit inputs, a 1-bit carry-in, a 4-bit sum, and a 1-bit carry-out:

           cin
            │
       ┌────┴─────┐
       │   4-bit  │
  a ═══│  ripple  │═══ s
   4   │   carry  │  4
  b ═══│   adder  │
   4   └─────┬────┘
             │
            cout

This is abstraction: the 4-bit adder hides its internal structure, and we can use it as a black box to build an 8-bit, 16-bit, 32-bit, or 64-bit adder by chaining copies of it. The add instruction in our RISC-V processor will ultimately be implemented using exactly this kind of adder, and the program counter (PC) increment uses an adder too.

What's Next¶

Introduce sequential logic — circuits that have memory and state.
Build a 1-bit memory element, then scale up to an N-bit register (including a 64-bit register).
Move from individual registers toward a register file, ALU, and control unit.
Reference: the Digital simulator is the schematic-entry tool we use in class.

Practice Problems¶

Problem 1 — Truth Table Completion¶

Complete the truth table for the function f = (a · b) + (b̄ · c):

a	b	c	b̄	a·b	b̄·c	f
0	0	0	?	?	?	?
0	0	1	?	?	?	?
0	1	0	?	?	?	?
0	1	1	?	?	?	?
1	0	0	?	?	?	?
1	0	1	?	?	?	?
1	1	0	?	?	?	?
1	1	1	?	?	?	?

Solution

| a | b | c | b̄ | a·b | b̄·c | f | |---|---|---|---|-----|-----|---| | 0 | 0 | 0 | 1 | 0 | 0 | 0 | | 0 | 0 | 1 | 1 | 0 | 1 | 1 | | 0 | 1 | 0 | 0 | 0 | 0 | 0 | | 0 | 1 | 1 | 0 | 0 | 0 | 0 | | 1 | 0 | 0 | 1 | 0 | 0 | 0 | | 1 | 0 | 1 | 1 | 0 | 1 | 1 | | 1 | 1 | 0 | 0 | 1 | 0 | 1 | | 1 | 1 | 1 | 0 | 1 | 0 | 1 |

Problem 2 — Sum of Products¶

Design a circuit that outputs 1 when exactly two of three inputs (a, b, c) are 1.

Solution

**Truth table:** | a | b | c | out | |---|---|---|-----| | 0 | 0 | 0 | 0 | | 0 | 0 | 1 | 0 | | 0 | 1 | 0 | 0 | | 0 | 1 | 1 | 1 | | 1 | 0 | 0 | 0 | | 1 | 0 | 1 | 1 | | 1 | 1 | 0 | 1 | | 1 | 1 | 1 | 0 | **Sum of products:** - Row (0, 1, 1): ā · b · c - Row (1, 0, 1): a · b̄ · c - Row (1, 1, 0): a · b · c̄ **out = (ā · b · c) + (a · b̄ · c) + (a · b · c̄)**

Problem 3 — Full Adder Verification¶

Verify that the full-adder SoP equations produce the correct output for a = 1, b = 1, cin = 0.

Solution

**sum = (ā·b̄·cin) + (ā·b·c̄in) + (a·b̄·c̄in) + (a·b·cin)**

sum = (0·0·0) + (0·1·1) + (1·0·1) + (1·1·0)
    = 0 + 0 + 0 + 0
    = 0 ✓  (1 + 1 + 0 = 10 binary; sum bit = 0)

**cout = (ā·b·cin) + (a·b̄·cin) + (a·b·c̄in) + (a·b·cin)**

cout = (0·1·0) + (1·0·0) + (1·1·1) + (1·1·0)
     = 0 + 0 + 1 + 0
     = 1 ✓  (carry out = 1)

Result: 1 + 1 + 0 = 10 binary → sum = 0, cout = 1. ✓

Problem 4 — Notation Translation¶

Translate the following C/Rust expression to Boolean algebra and logic notation:

r = (a & b) | (~a & c)

Solution

| Notation | Expression | |----------|------------| | C / Rust | `r = (a & b) \| (~a & c)` | | Boolean Algebra | r = (a · b) + (ā · c) | | Logic | r = (a ∧ b) ∨ (¬a ∧ c) |

Key Concepts¶

Concept	Definition
ISA	Instruction Set Architecture — the SW/HW contract (RISC-V here)
Combinational Logic	Outputs depend only on current inputs; no memory
Truth Table	Table listing outputs for every input combination
AND / OR / NOT	The three fundamental gates
XOR	Output 1 when inputs differ; built from AND/OR/NOT
Sum of Products	OR of AND terms — one AND per row where output is 1
Product Term	AND of all input literals for a particular row
Half Adder	Adds two 1-bit values; outputs sum and carry
Full Adder	Adds two 1-bit values plus carry-in; outputs sum and cout
Ripple-Carry Adder	N full adders chained cout → cin
Bus / Splitter	Multi-bit wire / gadget that fans it out to individual bits
Abstraction	Treating a built circuit as an opaque reusable block

Summary¶

The course hierarchy runs from C/Rust down through assembly, machine code, and the processor, and ends at digital logic. The ISA (RISC-V) is the contract between software and hardware.
Digital design can be done three ways: schematic entry (virtual), physical design (real wires and chips), and HDLs (Verilog, VHDL). We use schematic entry in the Digital simulator.
Digital abstracts analog: voltages above a high threshold are logic 1, below a low threshold are logic 0. From there we need just power, wires, and gates.
Three fundamental gates (AND, OR, NOT) suffice to build any combinational circuit. XOR is a common derived gate. Each gate has equivalent representations in C/Rust, Boolean algebra, and propositional logic.
Sum-of-products turns any truth table into a circuit: identify rows with output 1, form a product term per row, OR them together. The method is always correct, even if not always minimal.
Adders demonstrate the method end-to-end: the 1-bit sum collapses to XOR, the full adder combines two 1-bit values with a carry-in, and a 4-bit ripple-carry adder is built by composing four full adders. The 4-bit adder becomes an opaque block that scales up to 8, 16, 32, or 64 bits.

Digital Design¶

Overview¶

Learning Objectives¶

Prerequisites¶

Course Hierarchy: Software Down to Hardware¶

The Complete Stack¶

The Software / Hardware Boundary¶

Three Ways to Do Digital Design¶

From Analog to Digital¶

Disciplining Continuous Voltages¶

Primitive Building Blocks¶

Fundamental Logic Gates¶

AND Gate¶

OR Gate¶

NOT Gate (Inverter)¶

XOR Gate (Exclusive OR)¶

Notation Summary¶

Example Combinational Circuit¶

Building an 8-Bit Adder¶

Half Adder: Sum of Two 1-Bit Values¶

Half Adder Circuit¶

The Sum-of-Products Methodology¶

One-Bit Full Adder¶

Truth Table¶

SoP Derivation — sum¶

SoP Derivation — cout¶

Full Adder Circuit (sum output)¶

Ripple-Carry Adder: Composition and Abstraction¶

Chaining 1-Bit Full Adders¶

Buses and Splitters¶

The 4-Bit Adder as an Opaque Block¶

What's Next¶

Practice Problems¶

Problem 1 — Truth Table Completion¶

Problem 2 — Sum of Products¶

Problem 3 — Full Adder Verification¶

Problem 4 — Notation Translation¶

Key Concepts¶

Summary¶

Further Reading¶