Synchronous Digital Systems
Table of Contents
1. Transistors
The hardware underlying almost every processor is a Synchronous Digital System (SDS). It is synchronous in that all operations are coordinated by a central clock, and digital in that it represents all values by discrete levels, i.e. binary digits.
Wires are used to encode binary data using electrical signals. A wire with high voltage represents a 1, and a wire with low voltage represents a 0. We can use multiple wires to represent multiple bits.
We use transistors to turn voltage into logic. An NMOS transistor connects source to drain when the gate input is high, and disconnects when gate input is low. A PMOS transistor connects source to drain when gate input is low, and vice versa:
\begin{document}
Using a combination of PMOS and NMOS transistors, we can make logic gates.
1.1. NOT
We can use an NMOS and PMOS transistor in the following configuration to make an inverter:
This is represented by the NOT gate:
1.2. NAND
The following configuration gives us a NAND gate:
NAND is the same as NOT AND, with the following truth table:
| InA | InB | Out |
|---|---|---|
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 1 | 0 |
| 0 | 0 | 1 |
We can represent the NAND gate like so:
1.3. AND
We can use a NAND and a NOT gate to create an AND gate like so:
The AND gate is represented like so:
1.4. OR
We can use a NAND and two NOT gates to create an OR gate like so:
\begin{document}
The OR gate is represented like so:
1.5. Sum of Products
Using just OR, AND, and NOT, we can create a circuit for any given truth table. For each row of the truth table that outputs 1, you come up with a system of equations where each equation combines each input with AND and NOTs each input to get the corresponding output. Then, ORing each equation in the system together creates a expression that is equivalent to the truth table.
2. Boolean Algebra
We can use boolean algebra to simplify many of our boolean expressions. Since AND has many properties similar to multiplication, we use the multiplication operator \(\cdot\) to represent AND, and since OR has many properties similar to addition, we use \(+\) to represent OR:
| AND Form | OR Form | Property |
|---|---|---|
| \(x\cdot y=y\cdot x\) | \(x+y=y+x\) | Commutativity |
| \((xy)z=x(yz)\) | \((x+y)+z=x+(y+z)\) | Associativity |
| \(x\cdot 1=x\) | \(x+0=x\) | Identity |
| \(x\cdot 0 = 0\) | \(x+1=1\) | Laws of 0’s and 1’s |
| \(xy+x=x\) | \((x+y)x=x\) | Uniting Theorem |
| \(x(y+z)=xy+xz\) | \(x+yz=(x+y)(x+z)\) | Distributivity |
| \(x\cdot x = x\) | \(x+x=x\) | Idempotence |
| \(x\cdot\bar{x}=0\) | \(x+\bar{x}=1\) | Inverse |
| \(\overline{xy}=\bar{x}+\bar{y}\) | \(\overline{x+y}=\bar{x}\cdot\bar{y}\) | DeMorgan’s Laws |
3. Finite State Machines
A finite state machine (FSM) consists of a set of states. Computation is done in clock cycles. Every clock cycle, the FSM receives an input; based on that input, it will move to a new state (potentially its own) and output a value. For example, the following FSM performs a logical shift on the input:
A RISC-V processor can be modeled as an FSM where each insruction is an input. More importantly, we can construct an FSM with a circuit: at the start of a clock cycle, we need to send input, compute output and new state, save new state, and repeat.
4. Flip Flops and Registers
4.1. NAND Latch
The following is an example of a NAND latch:
This circuit has the following states:
| A | B | Out0 | Out1 |
|---|---|---|---|
| 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 |
| 1 | 0 | 0 | 1 |
| 1 | 1 | -- | -- |
The state at \((1,1)\) depends on the previous state. If we moved from \((0,1)\) or \((1,0)\), the circuit “remembers” the previous state and stays stable. However, if we moved from \((0,0)\) the outputs oscillate wildly.
The NAND latch is an example of a state element: circuit components that store information. They require two phases:
- Set: sets the value of output to a certain value (either input \((0,1)\) or \((1,0)\)).
- Stable: while in this phase, output doesn’t change from the previous value (input \((1,1)\)).
4.2. Flip Flops
A latch by itself reacts to its input whenever one of its inputs is 0. A more complex structure is the flip flop, which receives both a clock input and a data input, and whose output reacts to the data input only when the clock changes from 0 to 1:
Formally, a flip flop behaves like so:
- when CLK changes from 0 to 1, set Q to D
- otherwise, ignore D and maintain Q
4.3. Registers
32 flip-flops together make a register. It has the same behavior as a flip-flop, but 32 bits at a time. Therefore, we can use registers to save information.
4.3.1. Register Timing
The register is a circuit, which means it has a delay. In other words, there is a minimum interval of time between clock triggers for the previous data to be stable. If we trigger it too fast, we risk not capturing data properly and for the register to be put in an undefined state.
To prevent this, we need the input to be stable for some time before the clock trigger, and for some time after the clock trigger: this is because the feedback loops in the latches need some time to stabilize. Thus, we define the following values:
- Clk-to-Q delay: the delay between the clock trigger and when Q gets updated
- Setup time: the time that D needs to be stable before a clock trigger
- Hold time: the time that D needs to be stable after a clock trigger
Note that these times only apply to writing to a register.
5. Clock
We use a clock to provide precise timings to our circuits. They are often made with a vibrating crystal to generate a rising edge for every set period of time. The clock must be chosen with regard to the minimum clock period for a circuit, which is the total amount of delay that we need to take into account before the output is stable.