Combinational Logic

# Combinational Logic

## CS 315 Computer Architecture

---

## Learning Objectives

- Distinguish **combinational** vs **sequential** logic
- Read and draw AND, OR, NOT gates and truth tables
- Translate a word problem into a **truth table**
- Apply **sum-of-products** to build a Boolean equation
- Design a **1-bit full adder** from grade-school addition
- Compose eight full adders into an **8-bit ripple-carry adder**
- Explain why composition beats a brute-force truth table

---

## Two Kinds of Digital Circuits

<div class="mermaid">
flowchart TD
    A[Digital Circuits] --> B[Combinational Logic]
    A --> C[Sequential Logic]
    B --> B1["Acyclic — no feedback"]
    B --> B2["Output depends ONLY on current inputs"]
    B --> B3["No memory / no state"]
    C --> C1["Has cycles / feedback"]
    C --> C2["Output depends on inputs AND stored state"]
    C --> C3["Registers, counters, flip-flops"]
</div>

---

## Combinational vs Sequential

| Property | Combinational | Sequential |
|----------|--------------|------------|
| Feedback loops | No | Yes |
| Memory / state | None | Stores bits |
| Output depends on | Current inputs only | Inputs + past state |
| Examples | Adder, MUX, decoder | Register, counter |

<div class="info-box">
Today is entirely about <strong>combinational</strong> logic.
</div>

---

## Voltage Abstraction

| Logic value | Voltage (idealized) | Name |
|-------------|---------------------|------|
| `1` | ~high (e.g. 3.3 V) | high / true / asserted |
| `0` | ~low (e.g. 0 V) | low / false / deasserted |

- Wires carry one of two levels
- Gates abstract transistors into logic operations
- Components abstract gates into building blocks
- **Hierarchical abstraction** makes CPU design tractable

---

## The Three Primitive Gates

Every combinational function can be built from just **AND**, **OR**, and **NOT**.

| Operation | C code | Boolean | Truth |
|-----------|--------|---------|-------|
| AND | `a & b` | `a · b` | `1` only when all inputs are `1` |
| OR | `a \| b` | `a + b` | `1` when any input is `1` |
| NOT | `~a` | `ā` | Inverts the input |

A **bubble** on a gate pin means "invert that signal."

---

## AND Gate Truth Table

Output `1` only when **all** inputs are `1`

| a | b | r = a · b |
|---|---|-----------|
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | **1** |

---

## OR Gate Truth Table

Output `1` when **any** input is `1`

| a | b | r = a + b |
|---|---|-----------|
| 0 | 0 | 0 |
| 0 | 1 | **1** |
| 1 | 0 | **1** |
| 1 | 1 | **1** |

---

## NOT Gate and Wiring Conventions

**NOT (inverter):** output is the opposite of the input

| a | r = ā |
|---|-------|
| 0 | **1** |
| 1 | **0** |

**Wiring convention — dots matter:**

```text
   │                  │
───┼───   (no dot)  ──●───   (dot present)
   │                  │
 NOT connected     CONNECTED (junction)
```

<div class="highlight-box">
Crossing wires without a dot are <strong>not</strong> connected. A dot means wires join.
</div>

---

## Composing Gates into Circuits

Gates wire together left-to-right (inputs left, outputs right):

<div class="mermaid">
flowchart LR
    a((a)) --> AND1[AND]
    b((b)) --> AND1
    c((c)) --> AND2[AND]
    d((d)) --> AND2
    AND1 --> OR1[OR]
    AND2 --> OR1
    OR1 --> r((r))
</div>

**Equation:** `r = (a · b) + (c · d)`

A completed subcircuit becomes a **black box** — hide internals, reuse freely.

---

## The Sum-of-Products Method

A three-step recipe: specification → truth table → circuit

<div class="mermaid">
flowchart LR
    A["1. Build truth table"] --> B["2. Find rows where output = 1"]
    B --> C["3. AND each row (product), OR all rows (sum)"]
    C --> D["Draw circuit"]
</div>

- Each **product term** is `1` for exactly one input combination
- The final **OR** fires if any of those combinations occurs

---

## Worked Example: Parity Detector

**Goal:** detect whether a 3-bit number has an even or odd count of 1-bits

| n₂ | n₁ | n₀ | # of 1s | even | odd |
|----|----|----|---------|------|-----|
| 0 | 0 | 0 | 0 | **1** | 0 |
| 0 | 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 2 | **1** | 0 |
| 1 | 0 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 2 | **1** | 0 |
| 1 | 1 | 0 | 2 | **1** | 0 |
| 1 | 1 | 1 | 3 | 0 | 1 |

---

## Parity: SoP Equation

`even = 1` in four rows: `000`, `011`, `101`, `110`

```text
even = (n̄₂ · n̄₁ · n̄₀)    ← row 000
     + (n̄₂ · n₁ · n₀)     ← row 011
     + (n₂ · n̄₁ · n₀)     ← row 101
     + (n₂ · n₁ · n̄₀)     ← row 110
```

**Deriving `odd` the easy way:**

```text
odd = even̄
```

<div class="info-box">
Reuse a result rather than re-deriving it — one NOT gate instead of a second 4-term SoP.
</div>

---

## Parity: Circuit

Four 3-input AND gates (bubbles for complemented inputs) feeding a 4-input OR gate:

<div class="mermaid">
flowchart LR
    n2((n2)) --> A1["AND: n̄₂·n̄₁·n̄₀"]
    n1((n1)) --> A1
    n0((n0)) --> A1
    n2 --> A2["AND: n̄₂·n₁·n₀"]
    n1 --> A2
    n0 --> A2
    n2 --> A3["AND: n₂·n̄₁·n₀"]
    n1 --> A3
    n0 --> A3
    n2 --> A4["AND: n₂·n₁·n̄₀"]
    n1 --> A4
    n0 --> A4
    A1 --> OR1[OR]
    A2 --> OR1
    A3 --> OR1
    A4 --> OR1
    OR1 --> r((even))
</div>

---

## Lab 8: max2 — Maximum of Two 2-bit Numbers

Implement in hardware: `r = max(a, b)` where `a`, `b`, `r` are 2-bit values

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

- Inputs: `a1 a0`, `b1 b0` — four inputs total
- Outputs: `r1 r0`
- Truth table: 2⁴ = **16 rows**

<div class="highlight-box">
Write <strong>one SoP equation per output bit</strong>: separate equations for r₁ and r₀.
</div>

---

## max2 Truth Table (abbreviated)

| a₁ | a₀ | b₁ | b₀ | a | b | max | **r₁** | **r₀** |
|----|----|----|----|----|---|-----|--------|--------|
| 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 | 1 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 0 | 2 | 2 | 1 | 0 |
| 0 | 1 | 0 | 1 | 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 2 | 0 | 2 | 1 | 0 |
| 1 | 1 | 1 | 1 | 3 | 3 | 3 | 1 | 1 |

Collect 1-rows for `r₁` separately from 1-rows for `r₀`, then build two SoP equations.

**Naming:** inputs must be `a1`, `a0`, `b1`, `b0`; file must be `max2.dig`.

---

## Building an Adder: Grade-School Binary

Addition works column by column with carry:

```text
  carries: 1 1
              0 1 1   (a = 3)
            + 0 0 1   (b = 1)
            -------
            1 0 0     (= 4)
```

Each column: two operand bits + carry-in → sum bit + carry-out

This is exactly what one **1-bit adder** must do.

---

## Half Adder vs Full Adder

| | Half Adder | Full Adder |
|-|-----------|-----------|
| Inputs | a, b | a, b, cin |
| Outputs | sum, cout | sum, cout |
| Carry-in? | No | **Yes** |
| Chainable? | No | **Yes** |

<div class="info-box">
A <strong>full adder</strong> is the universal building block — it handles carry-in so units can be chained for multi-bit addition.
</div>

---

## Full Adder Truth Table

| 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** inputs are `1` (majority)

---

## Full Adder: SoP Equations

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

Equivalent simplified forms: `sum = a ^ b ^ cin` (XOR),  `cout = (a·b) + (a·cin) + (b·cin)` (majority)

Save as `1-bit-full-adder.dig` with inputs `a`, `b`, `cin` and outputs `sum`, `cout`.

---

## Full Adder Circuit

<div class="mermaid">
flowchart LR
    a((a)) --> SUM["SoP for sum\n(4 AND terms → OR)"]
    b((b)) --> SUM
    cin((cin)) --> SUM
    SUM --> s((sum))
    a --> COUT["SoP for cout\n(4 AND terms → OR)"]
    b --> COUT
    cin --> COUT
    COUT --> co((cout))
</div>

---

## Why Not One Giant Truth Table?

An 8-bit adder has: `cin` (1) + `a` (8) + `b` (8) = **17 inputs**

```text
2¹⁷ = 131,072 rows   ✗   Completely infeasible
```

<div class="highlight-box">
<strong>The right answer is composition.</strong> Solve the 1-bit problem once, then chain copies of it.
</div>

| Approach | Rows / Effort | Feasible? |
|----------|--------------|-----------|
| Flat SoP for 8-bit adder | 2¹⁷ = 131,072 | No |
| Chain 8 full adders | 8 × (2³ = 8 rows) | Yes |

Effort grows **linearly** with composition, not exponentially.

---

## The 8-bit Ripple-Carry Adder

Chain eight full adders: each `cout` feeds the next `cin`

<div class="mermaid">
flowchart LR
    cin((cin=0)) --> FA0[FA 0]
    a0((a0)) --> FA0
    b0((b0)) --> FA0
    FA0 --> s0((sum0))
    FA0 -- carry --> FA1[FA 1]
    a1((a1)) --> FA1
    b1((b1)) --> FA1
    FA1 --> s1((sum1))
    FA1 -- carry --> dots(("..."))
    dots -- carry --> FA7[FA 7]
    a7((a7)) --> FA7
    b7((b7)) --> FA7
    FA7 --> s7((sum7))
    FA7 -- carry --> cout((cout))
</div>

---

## Splitters and Mergers

Bridges between 8-bit buses and single-bit adder pins:

```text
     splitter                        merger
a ─8─▶ ║ ─▶ a0            sum0 ─▶ ║
       ║ ─▶ a1            sum1 ─▶ ║ ─8─▶ sum
       ⋮                    ⋮     ║
       ║ ─▶ a7            sum7 ─▶ ║
```

- **Splitter**: 8-bit bus → 8 individual wires
- **Merger**: 8 individual wires → 8-bit bus

Save the complete design as `8-bit-ripple-carry-adder.dig` with inputs `a`, `b`, `cin` and outputs `sum`, `cout`.

---

## Propagation Delay

The carry must ripple through all eight full adders before outputs are valid.

<div class="mermaid">
flowchart LR
    FA0[FA 0] -- "carry (slow)" --> FA1[FA 1]
    FA1 -- carry --> FA2[FA 2]
    FA2 -- "..." --> FA7[FA 7]
    FA7 --> cout((cout valid last))
</div>

- Delay grows **linearly** with bit width in ripple-carry
- An 8-bit adder is ~8× slower than a 1-bit adder
- Faster designs (carry-lookahead) exist but are more complex

---

## Subtraction Reuses the Adder

In two's complement: `a - b = a + (~b) + 1`

```text
To subtract:  invert b  AND  set cin = 1
```

**Example: 5 − 3**
```text
a  = 00000101  (5)
~b = 11111100  (~3)
cin = 1
─────────────
   1 00000010  → sum = 2, discard carry-out ✓
```

<div class="info-box">
An ALU can <strong>share one adder</strong> for both add and subtract — just invert b and toggle cin.
</div>

---

## Abstraction Scales

Once the 8-bit adder works, it becomes a black box:

```text
Two 8-bit adders  →  16-bit adder
Four 8-bit adders →  32-bit adder
...
```

The same hierarchical composition principle scales from individual transistors all the way up to a full CPU's ALU.

---

## Key Concepts Reference

| Concept | Definition |
|---------|------------|
| **Combinational logic** | Acyclic, stateless; output = pure function of inputs |
| **Sum-of-products** | OR (sum) of AND terms (products), one per 1-row |
| **Product term** | AND of all inputs, complemented where row has `0` |
| **Half adder** | Adds a, b → sum, cout (no carry-in) |
| **Full adder** | Adds a, b, cin → sum, cout (chainable) |
| **Ripple-carry adder** | N full adders chained, each cout → next cin |
| **Propagation delay** | Time for outputs to settle; grows linearly in ripple-carry |
| **Splitter / merger** | Splits a bus into bits or merges bits into a bus |

---

## Summary

1. **Combinational logic is stateless and acyclic** — outputs depend only on current inputs

2. **Three primitive gates** (AND, OR, NOT) are sufficient for any combinational function

3. **Sum-of-products**: build truth table → find 1-rows → one AND term per row → OR them all

4. **One SoP equation per output bit** — max2 needs separate equations for r₁ and r₀

5. **Full adder** (a, b, cin → sum, cout) is the chainable building block for addition

6. **Brute force fails** (2¹⁷ rows for 8-bit adder); **composition wins** — chain 8 full adders

7. **Subtraction reuses the adder**: invert b and set cin = 1 (two's complement trick)