# CS 211 - Lecture 24

## Computer Architecture

### Digital Logic Design

Bernhard Firner

2025-11-25

---

## Topic Intro

* Not enough time to dive deeply into this topic
* So why bother?
  * Give you a sense of "what is happening" when thinking about hardware
* Move some earlier topics from the realm of memorization into the realm of understanding

---

## Types of Logic

* We separate logic into two categories
  * combinational: stateless
  * sequential: has state
* Let's begin with combinational
  * Some of this may be a review

---

## Combinational Logic

* Stateless part of our systems use combinational logic
* Stateless means that something's output only depends upon its current inputs
  * Recall the adder example? This is stateless

---

## Addition

* Addition is done one bit at a time

---

## Handling Carry

* Need to also handle carry in from the previous bit

---

## Ripple Carry Adder

* Just cascade the one bit adders together to an arbitrary precision
* No past state exists in this circuit

---

## Adder

* Let's go back to that adder and describe it with a truth table

<div class="container">
<table>
<tr> <th>Input A</th><th>Input B</th><th>Sum</th><th>Carry</th></tr>
<tr> <td>0</td><td>0</td><td>0</td><td>0</td></tr>
<tr> <td>0</td><td>1</td><td>1</td><td>0</td></tr>
<tr> <td>1</td><td>0</td><td>1</td><td>0</td></tr>
<tr> <td>1</td><td>1</td><td>0</td><td>1</td></tr>
</table>
</div>

* sum = A xor B
* carry = a and b

---

## With Proper Gates

---

## All Gate Symbols

---

## Adder with Carry

* Our adder needs a carry input
* Things are getting complicated already!

</div>
<div class="col">

<div class="container">
<table>
<tr> <th>Input A</th><th>Input B</th><th>Carry In</th><th>Sum</th><th>Carry Out</th></tr>
<tr> <td>0      </td><td>0      </td><td>0       </td><td>0  </td><td>0    </td></tr>
<tr> <td>0      </td><td>0      </td><td>1       </td><td>1  </td><td>0    </td></tr>
<tr> <td>0      </td><td>1      </td><td>0       </td><td>1  </td><td>0    </td></tr>
<tr> <td>0      </td><td>1      </td><td>1       </td><td>0  </td><td>1    </td></tr>
<tr> <td>1      </td><td>0      </td><td>0       </td><td>1  </td><td>0    </td></tr>
<tr> <td>1      </td><td>0      </td><td>1       </td><td>0  </td><td>1    </td></tr>
<tr> <td>1      </td><td>1      </td><td>0       </td><td>0  </td><td>1    </td></tr>
<tr> <td>1      </td><td>1      </td><td>1       </td><td>1  </td><td>1    </td></tr>
</table>
</div>

</div>
</div>

---

## Complexity and Optimization

* We could muddle our way through this
* First represent as an equation
  * $Sum = (C_{in} \land \bar{B} \land \bar{A}) \lor  (B \land \overline{C_{in}} \land \bar{A}) ...$
  * $Sum = (C_{in} \oplus A \oplus B)$
* $\land$ means logical and, $\lor$ is logical or, $\oplus$ is xor, and a line is negation
* Is that minimization obvious?

</div>
<div class="col">

</div>
</div>

---

## Circuit Minimization

* It turns out that circuit minimization is difficult
  * There are some algorithms we could learn
    * Karnough maps, Quine-McCluskey algorithm, etc
  * With limited time, let's just focus on other fundamentals

---

## Easier Ways?

* You may wonder why we need to make this complicated
  * If we just added those 1s directly, we wouldn't need logic gates
    * Except that isn't how voltage works
* The implementation of something else would be even more difficult

---

## Voltage and Logic

* Your computer (and phone and watch, etc) uses two-states
  * Voltage low (or ground)
  * Voltage high (or Vcc)
* This is a fundamental of digital circuits

---

## Digital Vs Analog

* So why not use analog?
  * Can you add Vcc + Vcc and get 2Vcc?
    * No. That's not how voltage works.
  * Maybe if our building blocks were amplifiers, but that would be a tough system to build
* Our fundamental building block is the transistor used as switches

---

## Transistors

* Transistors have 3 terminals, with one terminal acting as a control switch
  * I'm simplifying a lot here, there are other uses and form factors
* One input controls the transistor state
  * Think of it as one switch and two terminals for output levels
* We are actually changing the conductivity of the transistor junction
  * Take a class on transport theory to learn more!

---

## Gates

* We assemble our gates with transistors, so they naturally work with bistate logic
* But it is easier to fabricate systems with a subset of the different logic gates
  * Homogeneity simplifies the hardware design process

---

## Universal Gates

* We do not need the complete set of possible gates to represent all of our digital logic
* The subset of AND, OR, and NOT is sufficient
  * That makes them a "universal set"

---

## Proof

| C      |     B | A     | Out   |
| :----: | :---: | :---: | :---: |
| 0      | 0     | 0     | 1     |
| 0      | 0     | 1     | 0     |
| 0      | 1     | 0     | 1     |
| 0      | 1     | 1     | 0     |
| 1      | 0     | 0     | 0     |
| 1      | 0     | 1     | 0     |
| 1      | 1     | 0     | 1     |
| 1      | 1     | 1     | 0     |

</div>
<div class="col">

* We can write a truth table for any expression
* Let's say we want to express this one
* We can **always** write a truth table as a sum of products
  * AND together the elements of each row with 1 output
  * OR those together to get a possible circuit

</div>
</div>

---

## Proof

</div>
<div class="col">

* Products:
* $\overline{C}~ AND~ \overline{B}~ AND ~\overline{A}$
* $\overline{C}~ AND ~B ~AND ~\overline{A}$
* $C ~AND ~B ~AND ~\overline{A}$
* Sum
  * $\overline{CBA} ~ OR ~\overline{C}B\overline{A} ~ OR ~ CB\overline{A}$
* Often written
  * $\overline{CBA} + \overline{C}B\overline{A} + CB\overline{A}$
* Called the disjunctive normal form

</div>
</div>

---

## Other Options

* But maybe it is easier to fabricate a single type of gate
  * In that case, either NAND or NOR are also universal

---

## Demonstration

* We can simply show that the other gates are representable with NAND and NOR

| x      |     y | NAND  |
| :----: | :---: | :---: |
| 0      | 0     | 1     |
| 0      | 1     | 1     |
| 1      | 0     | 1     |
| 1      | 1     | 0     |

</div>
<div class="col">

| x      |     y | NOR  |
| :----: | :---: | :---: |
| 0      | 0     | 1     |
| 0      | 1     | 0     |
| 1      | 0     | 0     |
| 1      | 1     | 0     |

</div>
</div>

---

## Not Representation

| A      |     A | NAND A|
| :----: | :---: | :---: |
| 0      | 0     | 1     |
| 1      | 1     | 0     |

</div>
<div class="col">

| A      |     A | NOR A |
| :----: | :---: | :---: |
| 0      | 0     | 0     |
| 1      | 1     | 1     |

</div>
</div>

---

## OR Representation

| A      |     B | NAND A   | NAND B   | (NAND A) NAND (NAND B) |
| :----: | :---: | :---:    | :---:    | :---:    |
| 0      | 0     | 1        | 1        | 0        |
| 0      | 1     | 1        | 0        | 1        |
| 1      | 0     | 0        | 1        | 1        |
| 1      | 1     | 0        | 0        | 1        |

</div>
<div class="col">

| A      |     B | A NOR B | NOR(A NOR B) |
| :----: | :---: | :---:   | :---:        |
| 0      | 0     | 1       | 0            |
| 0      | 1     | 0       | 1            |
| 1      | 0     | 0       | 1            |
| 1      | 1     | 0       | 1            |

</div>
</div>

---

## AND Representation

| A      |     B | A NAND B | NAND(A NAND B) |
| :----: | :---: | :---:    | :---:          |
| 0      | 0     | 1        | 0              |
| 0      | 1     | 1        | 0              |
| 1      | 0     | 1        | 0              |
| 1      | 1     | 0        | 1              |

</div>
<div class="col">

| A      |     B | NOR A    | NOR B    | (NOR A) NOR (NOR B) |
| :----: | :---: | :---:    | :---:    | :---:    |
| 0      | 0     | 1        | 1        | 0        |
| 0      | 1     | 1        | 0        | 0        |
| 1      | 0     | 0        | 1        | 0        |
| 1      | 1     | 0        | 0        | 1        |

</div>
</div>

---

## Important Logic

* A few structures tend to repeat
  * ALUs
  * Multiplexers
  * Decoders

---

## Multiplexer

* Just call it a MUX
* Allows us to select one output from several

---

## Using Muxes

* Muxes can select from more inputs
  * For $2^n$ inputs, we need $n$ select inputs
* FPGA (field programmable gate arrays) are programmable hardware
  * They use MUXes as part of their programmable logic, along with look up tables, adders, and a flip-flop
  * Look up tables are also implemented with a MUX
  * "Programming" them means setting all of the control inputs

---

## Logic With A MUX

* We can simply program the truth table
* Let A, B, and C become the control inputs
* We then have 8 hard-coded inputs set to either 0 or 1

</div>
<div class="col">

</div>
</div>

---

## MUX Look Up Table

</div>
<div class="col">

</div>
</div>

---

## FPGAs

* Logic represented by MUXes is slower than using the gates directly
  * e.g. implementing AND with MUXes is a waste
* But it is still faster than a software implementation
* There are a lot of special purpose systems like this
  * Used where there are too many settings for one piece of hardware, but speed is still important
  * reconfigurable wireless radios, for example

---

## Decoder

* A decoder converts $n$ inputs to $2^n$ unique outputs

</div>
</div>

---

## Stacked Decoders

* We can stack multiple decoders together
* Notice that only one output is active at a time

</div>
</div>

---

## Tying Things Together

* Why should you care?
  * A decoder is an excellent way to convert an address to a single selector
  * You might see this in a cache, for example
    * Think about set selection during cache access

---

## Practical Concerns

* Notice how more complex logic requires deeper nesting of gates?
  * It takes actual time for voltage to stabilize
* This is why our systems cannot run infinitely fast
  * Physics is holding us back
* Delays are a combination of propagation delays, and voltage settling times

---

## Next Time

* Hopefully this is helping to make computers feel less abstract
* We'll talk more about time and delays when we cover sequential logic

<!--
Do it with the carry in
Then talk about universal gates, and show to equivalent representation

References:
https://tikz.dev/library-circuits

https://yipenghuang.com/wp-content/uploads/2024/04/2024_04_18_combinational_logic.pdf
https://yipenghuang.com/wp-content/uploads/2024/04/2024_04_23_sequential_logic-1.pdf
-->