Digital Design

# Digital Design

## CS 631 Systems Foundations — Apr 2, 2026

---

## Today's Agenda

1. Course hierarchy: C/Rust down to gates
2. The SW/HW boundary and the ISA
3. Three ways to design digital circuits
4. Analog → digital
5. AND, OR, NOT — and XOR
6. Sum-of-products methodology
7. Half adder and 1-bit full adder
8. 4-bit ripple-carry adder

---

## Course Hierarchy

<div class="mermaid">
flowchart LR
    A["C / Rust"] --> B["Assembly"] --> C["Machine Code"] --> D["Processor"] --> E["Digital Design"]
    E --> F1["Schematic"]
    E --> F2["Physical"]
    E --> F3["HDLs"]
</div>

Digital design is the bottom of the stack — where the processor is actually built.

---

## SW / HW Boundary

<div class="mermaid">
flowchart LR
    C["Software<br/>C / Rust / ASM"] --> ISA["ISA<br/>RISC-V"] --> DL["Hardware<br/>Digital Logic"]
</div>

<div class="info-box">
The <strong>ISA</strong> is the contract. Software is written to it; any hardware that implements it can run the software.
</div>

---

## Three Ways to Design Digital Circuits

| Approach | What you work with | Tools |
|----------|--------------------|-------|
| **Schematic entry** | Virtual circuits | Digital, Logisim |
| **Physical design** | Real wires, chips, FPGAs | TTL, breadboards |
| **HDLs** | Source code for hardware | Verilog, VHDL (IEEE) |

We'll use **schematic entry** (the Digital simulator) so you can watch truth tables turn into gates.

---

## Analog → Digital

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

Building blocks: **power source**, **wires**, **gates** (devices).

<div class="highlight-box">
Above the high threshold = 1. Below the low threshold = 0. Don't linger in between.
</div>

---

## AND Gate

**Truth table**

| a | b | r |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |

</div>
<div>

**Notation**

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

Output is 1 only when **all** inputs are 1.

</div>
</div>

---

## OR Gate

**Truth table**

| a | b | r |
|---|---|---|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |

</div>
<div>

**Notation**

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

Output is 1 when **any** input is 1 (inclusive OR).

</div>
</div>

---

## NOT Gate

**Truth table**

| a | r |
|---|---|
| 0 | 1 |
| 1 | 0 |

</div>
<div>

**Notation**

| Style | Expression |
|-------|------------|
| C / Rust | `!a` or `~a` |
| Boolean | ā (overbar) |
| Logic | ¬a |

The **bubble** on any gate's input or output means "inverted."

</div>
</div>

---

## XOR — A Common Derived Gate

| a | b | r = a ⊕ b |
|---|---|-----------------|
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |

| Style | Expression |
|-------|------------|
| C / Rust | `a ^ b` |
| Boolean / Logic | a ⊕ b |

Output is 1 when inputs **differ**. Not fundamental — built from AND, OR, NOT — but very common.

---

## Notation Summary

| Operation | C / Rust | Boolean | 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 |

<div class="info-box">
Diagram conventions: <strong>dot</strong> at an intersection = connected wires; <strong>bubble</strong> = inversion; wires crossing without a dot are <em>not</em> connected.
</div>

---

## Example Combinational Circuit

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

<div class="mermaid">
graph LR
    A[a] --> AND1[AND]
    B[b] --> AND1
    C[c] --> AND2[AND]
    D[d] --> AND2
    AND1 --> OR1[OR]
    AND2 --> OR1
    OR1 --> R[r]
</div>

"r equals (a AND b) OR (c AND d)."

---

## Goal: 8-Bit Adder

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

Bottom-up plan:

1. **Half adder**: add two 1-bit values
2. **Full adder**: + carry-in
3. **Ripple-carry adder**: chain full adders

---

## 1-Bit Sum via Sum-of-Products

| a | b | sum |
|---|---|-----|
| 0 | 0 | 0 |
| 0 | 1 | **1** |
| 1 | 0 | **1** |
| 1 | 1 | 0 |

Rows where sum = 1 → product terms:

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

<div class="highlight-box">
This is exactly <strong>XOR</strong>: sum = a ⊕ b. Three gates with SoP, or one gate with XOR — both correct.
</div>

---

## Sum-of-Products Methodology

1. **Define** the function.
2. **Build** a truth table.
3. **Identify** rows with output = 1.
4. **Construct a product term** per row:
   - Keep the variable if input is 1
   - Invert the variable if input is 0
5. **Sum** (OR) all product terms.

Implementation: one AND per product term, a single OR across all of them, NOT gates (bubbles) on the inputs that need inverting.

---

## Drawing SoP Circuits

- **AND** per product term, one **OR** combining them, **bubbles** on inputs to invert.

```
  a ──┬── NOT ──┐
      │         ├─ AND ──┐
  b ──┼─────────┘        │
      │                  ├─ OR ── sum
  a ──┼─────────┐        │
      │         ├─ AND ──┘
  b ──┴── NOT ──┘
```

Always correct — not always minimal. For a 1-bit sum, XOR is shorter.

---

## 1-Bit Full Adder

Inputs: **a, b, cin**. Outputs: **sum, cout**. 2³ = 8 rows:

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

---

## Full Adder — SoP Equations

**sum** (4 rows with sum = 1):

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

**cout** (4 rows with cout = 1):

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

<div class="info-box">
Four 3-input ANDs feed one 4-input OR for sum. Same pattern for cout. Some product terms are shared, so a careful implementation can share gates.
</div>

---

## Full Adder — Sum Output Circuit

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

Inputs pick up NOT-bubbles where the product term has a barred variable.

---

## 4-Bit Ripple-Carry Adder

```
  a3 b3       a2 b2       a1 b1       a0 b0
   │  │        │  │        │  │        │  │
 ┌─┴──┴┐     ┌─┴──┴┐     ┌─┴──┴┐     ┌─┴──┴┐
 │ FA  │◀───│ FA  │◀───│ FA  │◀───│ FA  │◀─ cin0 = 0
 │ b3  │    │ b2  │    │ b1  │    │ b0  │
 └──┬──┘    └──┬──┘    └──┬──┘    └──┬──┘
    │          │          │          │
   s3         s2         s1         s0

cout4 ←── (out of FA3)
```

Carry **ripples** from LSB up. Example: 0101 + 0011 = 1000.

---

## Buses and the 4-Bit Adder Block

**Buses** are multi-bit wires. **Splitters** fan them out; **combiners** pack them back.

<div class="highlight-box">
<strong>Abstraction:</strong> the 4-bit adder is an opaque block. Chain copies to scale to 8, 16, 32, 64 bits.
</div>

</div>
<div>

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

</div>
</div>

---

## What's Next

- **Sequential logic** — circuits with memory and state
- 1-bit memory element → N-bit register (up to 64 bits)
- Register file, ALU, control unit

Reference: <a href="https://github.com/hneemann/Digital">github.com/hneemann/Digital</a>

---

## Key Takeaways

- **ISA** = SW/HW contract; digital = voltages disciplined into 0/1.
- **AND, OR, NOT** are enough; XOR is handy.
- **Sum of products** turns any truth table into a correct circuit.
- Half adder → full adder → 4-bit ripple-carry by composition.
- **Abstraction**: build once, then reuse as an opaque block.