Digital Logic Components

# Digital Logic Components

## CS 315 Computer Architecture

---

## Where We Are

<div class="mermaid">
flowchart LR
    G["Gates\nAND/OR/NOT/XOR"] --> SOP["Sum-of-Products\n(truth table to circuit)"]
    SOP --> ADD["Ripple-Carry Adder"]
    ADD --> COMP["Components\nComparators / MUXes / ALU"]
    COMP --> SEQ["Sequential Logic\nclock + state"]
    style COMP fill:#e8f5e9,stroke:#00543c,stroke-width:2px
</div>

**Today**: circuits as reusable components, MUXes, the ALU, subtraction, and a preview of sequential logic

---

## Two Flavors of Logic

| | Combinational | Sequential |
|---|---|---|
| **Output depends on** | Current inputs only | Inputs **and** stored state |
| **Structure** | DAG (no feedback) | Feedback loop + clock |
| **Examples** | Adder, comparator, MUX, ALU | Register, counter, PC |

<div class="info-box">
Everything before today was combinational. Sequential logic is how circuits <strong>remember</strong> and compute over time.
</div>

---

## The 1-Bit Comparator: Truth Table

Does `a == b`? With one bit each, equality holds when both bits match.

| a | b | eq? |
|---|---|-----|
| 0 | 0 | **1** |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | **1** |

Sum-of-products:

```text
eq = (a' . b') + (a . b)
```

---

## 1-Bit Comparator = XNOR

Compare XOR with XNOR (NOT-XOR):

| a | b | XOR | XNOR | eq? |
|---|---|-----|------|-----|
| 0 | 0 | 0 | **1** | **1** |
| 0 | 1 | 1 | 0 | 0 |
| 1 | 0 | 1 | 0 | 0 |
| 1 | 1 | 0 | **1** | **1** |

<div class="highlight-box">
XOR is 1 when bits <em>differ</em>. XNOR is 1 when bits are the <em>same</em>.<br>
A 1-bit comparator is just a single <strong>XNOR gate</strong>.
</div>

---

## Abstraction: Circuit as a Component

The central skill — collapse a working circuit into a reusable **box** with named ports.

| Software | Hardware |
|----------|----------|
| Function signature | Component ports (inputs/outputs) |
| Function body | Gate-level circuit inside the box |
| Calling the function | Wiring up an instance |
| Reusing a function | Instantiating multiple copies |

<div class="mermaid">
flowchart LR
    subgraph Box["1-bit comparator (black box)"]
        direction LR
        IN1["a"] --> C[" "]
        IN2["b"] --> C
        C --> OUT["eq"]
    end
</div>

---

## 2-Bit Comparator: Compose + Split + AND

Two numbers are equal **iff every bit position is equal**.

<div class="mermaid">
flowchart TD
    A2["a (2-bit)"] --> SP1["splitter"]
    B2["b (2-bit)"] --> SP2["splitter"]
    SP1 -->|"a[1]"| CMP1["1-bit cmp"]
    SP2 -->|"b[1]"| CMP1
    SP1 -->|"a[0]"| CMP0["1-bit cmp"]
    SP2 -->|"b[0]"| CMP0
    CMP1 -->|"eq1"| AND["AND"]
    CMP0 -->|"eq0"| AND
    AND --> EQ["eq"]
</div>

- **Split** each 2-bit input into individual bits
- Feed corresponding bits to **1-bit comparators**
- **AND** the results — equal only if *all* positions match

---

## Why AND? Why Not OR?

```text
101 == 101  ->  all bits match  ->  AND = 1  (equal)
100 =/= 101  ->  bit 0 differs  ->  AND = 0  (not equal)
```

<div class="highlight-box">
Equality is <strong>conjunctive</strong>: one mismatched bit anywhere forces the result to "not equal."<br>
OR would report equal if <em>any</em> bit matched — that's wrong.
</div>

---

## Scaling Up: 8-Bit Comparator

**Divide-and-conquer in hardware**: split into two 4-bit halves, AND the results.

<div class="mermaid">
flowchart TD
    C8["8-bit comparator"] --> C4H["4-bit cmp (high nibble)"]
    C8 --> C4L["4-bit cmp (low nibble)"]
    C4H --> C1H["1-bit cmp x4"]
    C4L --> C1L["1-bit cmp x4"]
    C4H -->|"eq_hi"| AND8(["AND"])
    C4L -->|"eq_lo"| AND8
    AND8 --> EQ["eq"]
</div>

An N-bit comparator splits into two (N/2)-bit comparators. Leaves are XNOR gates.

---

## Comparator in C

The hardware bit-by-bit AND maps directly to code:

```c
#include <stdint.h>
#include <stdbool.h>

// Mirrors the hardware: XNOR each bit, AND-reduce
bool eq8(uint8_t a, uint8_t b) {
    bool eq = true;
    for (int i = 0; i < 8; i++) {
        int abit = (a >> i) & 1;
        int bbit = (b >> i) & 1;
        eq = eq && (abit == bbit);   // XNOR of the two bits
    }
    return eq;
    // In real code: return a == b;
}
```

**Project 5 use**: compare instruction `opcode` fields against constants like the R-type opcode or the end-of-program marker `0xC0001073`.

---

## The Multiplexor (MUX)

A MUX is a hardware `?:` / `switch`: select signal `s` chooses which input routes to output.

```text
         s
         |1
     +---+---+
a --1| 0     |
     |       |--1-- r
b --1| 1     |
     +-------+
```

- `s = 0` → `r = a`
- `s = 1` → `r = b`

<div class="info-box">
A MUX <strong>selects</strong> a value — it does not compute one.
</div>

---

## Wider Data: 32-Bit MUX

The select stays **1 bit**; the data buses grow to 32 bits.

```text
         s
         |1
     +---+---+
a -32| 0     |
     |       |--32-- r
b -32| 1     |
     +-------+
```

Internally: 32 independent 1-bit MUXes sharing one select line.

---

## More Inputs: 4-Input MUX

With 4 data inputs, need **2 select bits** (`s1 s0`):

| s1 | s0 | r |
|----|----|---|
| 0 | 0 | a |
| 0 | 1 | b |
| 1 | 0 | c |
| 1 | 1 | d |

<div class="highlight-box">
An <strong>N-input MUX</strong> needs <strong>ceil(log2 N)</strong> select bits.<br>
2 inputs → 1 select  |  4 inputs → 2 select  |  8 inputs → 3 select
</div>

---

## MUX in C

```c
// 2-input MUX
uint32_t mux2(uint32_t a, uint32_t b, int s) {
    return s ? b : a;       // s==0 -> a, s==1 -> b
}

// 4-input MUX (2-bit select)
uint32_t mux4(uint32_t a, uint32_t b,
              uint32_t c, uint32_t d, int s) {
    switch (s & 0x3) {
        case 0: return a;
        case 1: return b;
        case 2: return c;
        default: return d;
    }
}
```

---

## Implementing a MUX from a Truth Table

1-bit, 2-input MUX — sum-of-products (4 rows where `r = 1`):

```text
r = (a' . b  . s )   <- a=0,b=1,s=1
  + (a  . b' . s')   <- a=1,b=0,s=0
  + (a  . b  . s')   <- a=1,b=1,s=0
  + (a  . b  . s )   <- a=1,b=1,s=1
```

Simplifies to the clean two-gate form:

```text
r = (a AND NOT s) OR (b AND s)
```

- Top AND passes `a` only when `s = 0`
- Bottom AND passes `b` only when `s = 1`
- Exactly one AND is "live" at a time

---

## Building a 4-Input MUX: Two Options

| | Option 1: Flat SOP | Option 2: MUX Tree |
|---|---|---|
| **Built from** | AND/OR/NOT gates | smaller 2-input MUXes |
| **Levels** | 2 (fast, wide) | 2 MUX stages |
| **Reuse** | none | reuses 2-input MUX |

<div class="mermaid">
flowchart LR
    subgraph Tree["Option 2: MUX Tree"]
        a --> M1["MUX\ns0"]
        b --> M1
        c --> M2["MUX\ns0"]
        d --> M2
        M1 --> M3["MUX\ns1"]
        M2 --> M3
        M3 --> r
    end
</div>

Option 2 embodies today's theme: **reuse a smaller component**.

---

## The ALU: MUXes in Action

Run **all** operations in parallel; MUX the desired result out.

<div class="mermaid">
flowchart LR
    A["A (64)"] --> ADD["+"]
    A --> SUB["-"]
    A --> MUL["x"]
    B["B (64)"] --> ADD
    B --> SUB
    B --> MUL
    ADD --> MUX["MUX\n(wide)"]
    SUB --> MUX
    MUL --> MUX
    S["S\nALUop"] --> MUX
    MUX --> R["r (64)"]
</div>

- Operands fan out to **every** functional unit
- All units compute simultaneously (combinational — nothing stops them)
- Select `S` passes **exactly one** result through

---

## ALU Details

**Project 6 ALU operations:**
- Add
- Subtract
- Multiply
- Shift left logical
- Shift right logical

Selected by a **3-bit `ALUop`**

</div>
<div>

**Key properties:**
- Fully **combinational** — no clock, no state
- Unused results are computed but ignored
- Simple and fast for single-cycle design

</div>
</div>

<div class="info-box">
The "waste" of computing all operations simultaneously is the price of simplicity. Real processors use the same pattern.
</div>

---

## Subtraction from Addition

We have an adder. Subtraction comes free via **two's complement**:

```text
A - B  =  A + (-B)  =  A + (NOT B) + 1
```

To negate `B` in two's complement:
1. **Invert** all bits (one NOT gate per bit)
2. **Add 1** — absorbed into carry-in `Cin = 1`

---

## 8-Bit Subtractor Circuit

```text
Cin = 1  (the "+1" of two's complement)
  |
  v
a[0] ---+
b[0]--NOT--| FA |--> s[0]
           |Cout|--+
                   | (carry ripples up)
a[1] ---+          |
b[1]--NOT--| FA |<-+--> s[1]
           |Cout|--+
              ...
a[7] ---+          |
b[7]--NOT--| FA |<-+--> s[7]
```

Result: `s = A + (NOT B) + 1 = A - B`

---

## Subtraction in C

```c
#include <stdint.h>

int8_t sub8(int8_t a, int8_t b) {
    return a + (~b + 1);   // ~b inverts all bits; +1 completes negation
    // identical to: return a - b;
}
```

Verify: `A=5 (0101)`, `B=3 (0011)`

```text
NOT B = 1100
  0101   (A = 5)
+ 1100   (NOT B)
+    1   (Cin)
-------
 10010  -> drop carry-out -> 0010 = 2  ✓
```

---

## Selectable Add/Subtract

Use a MUX to choose between `B` and `NOT B`:

```text
A ──────────────────────┐
                        [Adder]──── r
B ──[NOT gates]──[MUX]──┘
                  ^
             sub? (0=add, 1=sub)
             also drives Cin
```

- `sub=0`: MUX passes `B`, `Cin=0` → addition
- `sub=1`: MUX passes `NOT B`, `Cin=1` → subtraction

One adder design handles both operations — cornerstone of every ALU.

---

## Sequential Logic: The Two New Ingredients

Everything so far: **combinational** — a DAG, no memory.

To compute *over time* we need **state**:

1. **A clock** — a periodic square wave; each rising edge is a discrete "step"

```text
CLOCK  _|‾|_|‾|_|‾|_|‾|_
        ^ ^ ^ ^   (rising edges)
```

2. **State** — storage elements (registers / flip-flops) that remember a value between ticks

---

## Sequential Circuit Structure

<div class="mermaid">
flowchart LR
    CLK["CLOCK"] --> ST["State\n(register)"]
    IN["inputs"] --> CL["Combinational\nLogic"]
    ST -->|"current state"| CL
    CL -->|"next state\n(feedback)"| ST
    CL --> OUT["outputs"]
</div>

- Each clock tick: state register **latches** new value
- Combinational logic computes **next state** and outputs
- The **feedback loop** is the crucial difference from combinational circuits

---

## Combinational vs Sequential: Key Examples

| Component | Type | Why |
|-----------|------|-----|
| ALU | **Combinational** | Pure function of A, B, ALUop; no clock |
| 8-bit comparator | **Combinational** | `eq` depends only on current `a`, `b` |
| Instruction counter | **Sequential** | Must remember count between clock ticks |
| Processor PC | **Sequential** | Holds address, updates each clock cycle |

<div class="highlight-box">
Rule of thumb: if a circuit needs to <strong>remember</strong> anything across clock ticks, it is sequential.
</div>

---

## Sequential Logic and the Projects

**Project 5 — Static Analyzer:**
- **Comparators** recognize opcode fields
- **Sequential counters** accumulate instruction-type counts
- **Clock + ROM address register** steps through instructions one per tick

**Project 6 — Processor:**
- **PC register** holds state, advances each cycle
- Combinational fetch / decode / execute / writeback logic
- One big sequential machine built from everything in this lecture

---

## Key Concepts Reference

| Concept | One-liner |
|---------|-----------|
| **Combinational logic** | DAG; output = f(current inputs) |
| **Sequential logic** | Clock + state register + feedback loop |
| **1-bit comparator** | XNOR gate |
| **Abstraction** | Circuit → reusable box with named ports |
| **Splitter** | Breaks wide bus into bit ranges |
| **MUX** | Selects one of N inputs via ceil(log2 N) select bits |
| **ALU** | Parallel ops + wide MUX driven by ALUop |
| **Two's complement sub** | `A - B = A + (NOT B) + 1` |
| **State register** | Holds a value between clock ticks |

---

## Summary

1. **Combinational** logic is a DAG (no state); **sequential** adds a clock and state register.

2. A **1-bit comparator** is an XNOR gate; compose them with splitters and AND to make N-bit comparators.

3. **Abstraction** is the key move — collapse any circuit into a reusable box and wire up multiple copies.

4. A **MUX** selects one of N inputs using `ceil(log2 N)` select bits; it is the hardware `?:`.

5. The **ALU** runs all operations in parallel and MUXes the desired result — fully combinational.

6. **Subtraction** comes free from addition: `A - B = A + (NOT B) + 1` (inverters + `Cin = 1`).

7. **Sequential logic** = combinational logic + clocked state register in a feedback loop — the foundation of registers, counters, and the processor PC.