# CS 211 - Lecture 25

## Computer Architecture

### Sequential Logic

Bernhard Firner

2025-12-02

---

## Review

* We separate logic into two categories
  * combinational: stateless
  * sequential: has state
* Any sequential logic can be represented by truth tables
  * And any truth table can be implemented with AND, OR, and NOT gates

---

## All Gate Symbols

---

## Adder with Carry

* The truth table for even one bit addition with carry is quite large
* Two representations:
* $Sum = (C_{in} \land \bar{B} \land \bar{A}) \lor  (B \land \overline{C_{in}} \land \bar{A}) ...$
* Simpler with XOR
* $Sum = (C_{in} \oplus A \oplus B)$

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

---

## Universality

* We can **always** write the truth table of a circuit as a sum of products
  * AND together the elements of each row with output 1
  * OR those together to get a possible circuit
* But we may not always want to use AND, OR, and NOT gates

---

## More Universality

* Both NAND and NOR are universal on their own

---

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

---

## Stacked Decoders

* We can stack multiple decoders together
* Notice that only one output is active at a time
  * We could use this to select a single cache line given an input address

</div>
</div>

---

## Cache Logic

* Consider directly mapped cache cache with 8 sets and blocks of size 32 bytes
* The byte at address 0x100 (100000000b) is requested; what happens?
  * Lower 5 bits go to a decoder, to select a particular byte in a block
  * Which block?
    * Next 3 bits of address go through a decoder and select the set

---

## Cache Logic

* The line at the correct set is fetched
  * the valid bit is compared to 1
  * the tag is compared to the upper address bit
    * A NAND of those two indicates a cache miss

---

## Sequential Logic

* What we've talked about doesn't capture the changing states of a computer
  * For computation, we need *state*
* That's where sequential logic comes in
  * Think of the latches in the SRAM that hold register values

---

## Simplest State Element

* Latch
  * So-named because it "sticks" in a state
* This version is the "SR Latch"

</div>
</div>

---

## What Does It Do?

* Examine sequentially?
  * $Q_{out} = \overline{R + \overline{Q_{in}}}$
  * $\overline{Q_{out}} = \overline{S + Q_{in}}$
* If $Reset=1$, $Q$ must be 0
* If $Set=1$, $\overline{Q}$ must be 0
  * That is fed into the NOR gate for Q, so S=1, R=0, means Q=1
* If $Set=0, Reset=0$, outputs depend upon $Q, \overline{Q}$

---

## More on the Latch

* Consider $Set=Reset=0$
* If $Q=0$, $\overline{Q}=1$, which is fed back to the top NOR gate
  * So $Q$ remains 0
* Likewise, if $Q=1$ then it remains 1

</div>

</div>
</div>

---

## Latch Truth Table

| R      |     S | $Q$   | $\overline{Q}$   |
| :----: | :---: | :---: | :---:            |
| 0      | 0     | $Q$   | $\overline{Q}$   |
| 0      | 1     | 1     | 0                |
| 1      | 0     | 0     | 1                |
| 1      | 1     | 0     | 0 (don't do this)|

---

## Also a NAND Version

* Simply treat Set and Reset as inverted
* This version is the "$\overline{SR}$ Latch"

</div>
</div>

---

## SR Setting Example

* Begin in an unknown state and set $S=1$

</div>
</div>

---

## SR Setting Example

* The signal coming from the gate must be 0

</div>
</div>

---

## SR Setting Example

* Once the signal has propagated through the second gate, the Set line can go back to 0
* Now the latch will hold on to its new state

</div>
</div>

---

## Propagation Delays

* There is some delay between setting Set or Reset to 1 and seeing a change in Q
* This is called the settling time
* This obviously constrains the maximum speed of the latch
* This is a source of the delay in the multistage pipeline registers

---

## R=S=1 Case

* Hold $R=S=1$ and both $Q$ and $\overline{Q}$ must be zero
  * What happens upon the return to $R=S=0$
* The currenet state should remain stored, but it is not stable
  * When S goes low, a $Q=1$ signal begins to propagate
  * When R goes low, a $\overline{Q}=1$ signal begins to propagate
* Those signals race around to the inputs and set each other to 0, and the state oscillates

---

## Clocks

* So we need to synchronize our signalling, or we can get into strange states
* Bad clock: charge a capacitor that is connected to a resistor
  * At some point ($RC seconds$ to be exact), it "overflows"
  * This emits a brief high voltage signal

---

## RC Oscillators

* RC clocks drift with temperature, and time, and everything else
  * But they are very low power and very simple
* Use one in your car key fob
  * Don't use one in your watch

---

## Crystal Oscillators

* So how do we keep time when we care?
  * With a crystal, such as quartz
* Needs to be piezoelectric so that voltage will cause it to deform
  * As it unflexes, it emits a small voltage
  * Use a circuit to resonate with the crystal and you a precise (ppm) clock

---

## Thin Film Resonators

* At higher frequencies, we can also use a thin film of piezoelectric material
  * The operation is similar to crystals, but they can oscillate at tens of GHz
* Used in radio and acoustic applications
  * and any other times very high frequencies are desired

---

## Using Our Clock

* The clock signal cleverly gates activity on Set or Reset
  * Called a "Gated SR Latch"

---

## Removing Bad States

* That latch still allows for Set and Reset to be high
  * Doesn't matter when the clock is low, but still leads to trouble if the clock is high
* So let's change this to make bad inputs impossible

---

## D-Latch

---

## D-Latch Simplified

---

## Issue with Latches

* The D-latch is still level sensitive
  * So while the clock pulse is high, its state still can still change
* We really only want **one** change per clock tick
  * One step of ALU per clock, one register update per clock, etc, etc

---

## Flip-Flops

* So in synchronous circuits we use flip-flops instead of latches
* They are *edge-triggered*, meaning they change only when the clock value changes
* Just chain two latches in a row
  * The first can change with the inputs at the correct clock level
  * the second uses the opposite clock, so it only change at the changing edge

---

## Example

* Negative edge triggered D flip-flop
  * There are other options, but just one example is enough for the idea

---

## Synchronous Circuits

* Everything in a synchronous circuit happens according to the clock tick
* The clock tick propagates through combinational circuits and changes the state of sequential logic
* All actions are aligned by the clock

---

## Asynchronous Circuits

* The alternative is asynchronous
  * Use latches instead of flip flops, don't align anything
  * Far harder to design around

---

## Architectures We Know

* You are used to working on synchronous systems
  * Even with threads, we can easily use variables to align state
* It's hard to predict what systems you may see in the future
  * So be prepared for anything!

---

## Next Class

* A last look at hardware
* Next week's class be a review
  * And then the final!
* Post questions publicly on Piazza so that the class can see
  * You'll benefit as well, since others will think of questions that you have not