# CS 211 - Lecture 25

## Computer Architecture

### Sequential Logic

Bernhard Firner

2026-04-27

---

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

* We can read off each line to solve for SUM
  * $Sum = (C_{in} \land \bar{B} \land \bar{A}) \lor  (B \land \overline{C_{in}} \land \bar{A}) ...$
  * Or $Sum = C_{in}\overline{AB} + B\overline{AC_{in}} + A\overline{BC_{in}} + ABC_{in}$
* 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>

---

## Adder with Carry

* The carry out has multiple solutions
  * $C_{out} = \bar{A}BC_{in}  + AC_{in}\bar{B} + AB\overline{C_{in}} + ABC_{in}$
* This simplifies multiple ways
  * $C_{out} = AB + C_{in}(A \oplus B)$
  * $C_{out} = BC_{in} + A(B \oplus C_{in})$
  * $C_{out} = AC_{in} + B(A \oplus C_{in})$

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

</div>
</div>

---

## Full Adder

* Circuits get messy rather quickly
* We usually hide the details in nicely labelled boxes
  * But it is important to notice the *critical path* of a circuit
  * That is the longest path of elements, which determines the circuit delay

---

## Full Adder

* The *critical path* of the full adder is in calculating the carry out
  * It is 3 gates long, so if each gate cost 1ps of time, this would take 3ps

---

## Ripple Carry Adder

* If we wanted to calculate the sum of 32 bit integers, we could chain 32 full adders
* But the carry out of each takes 3 gate delays to calculate
  * 32-bit addition would have a critical path of 96 gates

---

## Lookahead Adder

* We can "precalculate" if there will be a carry out
* Break it into two possible cases where carry out will occur
  * If A and B are both 1, then the adder will *generate* carry out
  * If either A or B are 1, then the adder will *propagate* a carry out if there is a carry in
* $P = AB$
* $G = (A \oplus B)$

</div>
<div class="col">
<img style="width: 65%" class="r-stretch" src="./figures/Four_bit_adder_with_carry_lookahead_trex4321Wikipedia.svg" />
<br/>
<small>From <a href="https://commons.wikimedia.org/wiki/File:Four_bit_adder_with_carry_lookahead.svg">wikimedia</a><small>
</div>
</div>

---

## Lookahead Adder

* P and G take 1 gate to calculate
* Forward those values to the next bit's results, speeding things up
* A final OR gate combines all P and G values
* This trades gate count for speed
  * 4 for any sum bit

---

## Universality

* No matter how complicated things become, 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
* This sum of products is the *disjunctive normal form*
* 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
* Numbers are usually compared by taking 2's complement negation of one and then adding
  * If the result isn't 0, they are not equal
  * Alternatively, custom cache logic could compare each bit and then OR them together

---

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

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

</div>
</div>

---

## What Does It Do?

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

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

</div>
</div>

---

## 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
* Conversely, 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

* Let's return to the NOR gate version
* Begin in an unknown state and set $S=1$

</div>
</div>

---

## SR Setting Example

* The signal exiting the lower 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 (one of) the delays in the multistage pipeline registers

---

## Race Conditions

* If we set $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 circuit, 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 to make 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 level
    * So the first changes, but the second won't look until the clock changes

---

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

---

## Rest of the Semester

* One more homework to simulate a ripple carry adder
* The last recitation will cover some DLD circuit example problems
* Next lecture will be a review of the course topics
* Next Monday's lecture we will go through the most challenging problems from the quizzes and midterm

---

## Seeking Help

* I will hold office hours during the reading days
* If everyone sends me emails from all of my classes then I won't be able to respond
* So post questions publicly on Piazza so that the class can see
  * I will answer questions more quickly on Piazza since they benefit the entire class
  * You'll benefit from using Piazza as well, since others will think of questions that you have not