Hardware 101 (1/N)

In hardware, everything is a voltage. Digital electronics, which is what we're exploring here, consists of a high (or $V_{DD}$) voltage and a low (or GND) voltage. The choice of the high voltage is left to the designer/fabrication facility; however, if a voltage is in an intermediate zone (between $V_{DD}$ and GND), this is usually a metastable region, where the behavior of the circuit cannot be guaranteed. For our purposes, a signal that is not high (which we will call '1') or low (which we will call '0') is invalid.

Basic Logic

If you've used a programming language before (or taken a computer science class), you're probably familiar with some logical operations, e.g., AND, OR, NAND, NOR, XOR, XNOR, NOT. Those same operations exist in hardware and are often denoted with truth tables and symbols. Before we explore the symbols and truth tables of all those logic gates, let's first go through an example for AND using two one-bit signals: a and b.

So, how should we interpret the logic gate and truth table for the AND gate? The AND gate depiction shows an AND2 (2-input AND gate), which produces the logical AND of the two inputs. Side note, if we have two signals a and b, ab denotes AND-ing the signals, while a + b denotes OR-ing the signals. Due to the limitations of Markdown (and my own abilities), either $\overline{a}$ or !a may indicate the negation of a (see the NOT table below if this explanation is not clear). The truth table makes the behavior extra clear, and for more complicated combinational logic consisting of many more gates, elucidates the behavior of the circuit for every possible input combination. In this case, we see that the gate always results in a '0' unless both a and b are '1', in which case the output is '1'. Here's a quick overview of the rest of the gates.

OR:

NAND:

NOR:

XOR:

XNOR:

NOT:

In general, there are two types of digital logic: combinational and sequential. The output of combinational logic depends only on the inputs, while the output of sequential logic depends on the history (previous inputs) and current inputs.

Let's start with combinational logic. Combinational logic consists of a few different gates, such as AND, OR, NAND, NOR, XOR, XNOR, and NOT. With our newfound knowledge, let's build a half adder circuit!

Combinational Logic

Half Adder:

Imagine the most basic calculator you can think of. It's so simple, it can only add two single digits together. This is exactly what a half adder is for a computer. At its core, a computer's brain only understands two things: ON and OFF, which we represent with the numbers 1 and 0. The half adder is a fundamental circuit that knows how to add just two of these numbers together.

Since it only works with 0 and 1, there are only four possible addition problems a half adder can solve:

1. 0 + 0 = 0
   • The Sum is 0.
   • There's nothing to carry, so the Carry is 0.
2. 1 + 0 = 1
   • The Sum is 1.
   • The Carry is 0.
3. 0 + 1 = 1
   • The Sum is 1.
   • The Carry is 0.
4. 1 + 1 = 2
   • This is the interesting one! A computer can't write "2". It has to use 0s and 1s. The number 2 in binary is written as "10".
   • This result is split into two parts:
     • The Sum is 0. (The digit you write down).
     • The Carry is 1. (The digit you carry over).

Seeing as we can have two possible inputs (a and b) and two possible outputs (sum and carry), we can now assemble two truth tables (for each output) that describe our circuit's behavior for every possible input combination.

Sum Truth Table

Carry Truth Table

Great, with our truth tables, we can now assemble our circuit. Using the logical gates we covered above, how might we assemble this circuit? It should look like the circuit below:

Just like that, we can add two one-bit numbers together! How about a slightly more complicated example?

Multiplexer (MUX)

Imagine you have four different TV channels you want to watch—say, a news channel, a sports channel, a movie channel, and a cartoon channel. The problem is, you only have one TV screen. How do you choose which channel appears on your single screen? You use a remote control. You press a button, and the remote tells a selector box which of the four signals to send to the screen. In the world of electronics, a multiplexer (or MUX) is that selector box. It's a fundamental circuit that chooses one signal from many available input signals and sends it to a single output.

1. The Inputs (The Channels): These are the multiple lanes of information (the 0s and 1s) that are available to be chosen. You can have a MUX with 2, 4, 8, 16, or even more inputs.
2. The Output (The Selected Channel): This is the single lane where the one chosen piece of information comes out. No matter how many inputs there are, there is always only one output.
3. The Select Lines (The Button): This is the "brain" of the MUX. These are special control wires that tell the MUX which input to select. The pattern of ONs and OFFs (1s and 0s) on these select lines acts like a code, or an "address," for the input you want.
   • If you have 2 inputs, you only need 1 select line to choose between them (0 for the first, 1 for the second)
   • If you have 4 inputs, you need 2 select lines. You can pick input #0 with 00, input #1 with 01, input #2 with 10, and input #3 with 11
   • If you have 8 inputs, you need 3 select lines
   • In general you need $\\lceil \\log_2 n \\rceil$ bits for the select signal, when $n$ is the number of inputs. You should also consider why this is true

Let's build a simple MUX with two inputs (a and b) and a one-bit select signal (sel). Once again, let's construct a truth table:

If you would like to be more verbose (use only 1 or 0 in the truth table), we can write a few more truth tables:

This truth table is slightly trickier, in my opinion, but we should be able to reduce it to the following circuit (though there is an even more efficient way in terms of transistors used):

Nice! We should note that we are not going to cover Boolean minimization (such as through Karnaugh maps or Boolean algebra), but we highly recommend looking into how to do Boolean minimization by hand, even though most tools can automatically reduce Boolean logic to use the fewest literals.

Before we move on to sequential circuits, let's analyze our MUX design. Suppose we start with a high, b low, and sel high. What do you think out is? It should be high. Now, suppose we set sel to be low. In theory, should out change immediately, after some gate delay, or be dependent on the history of the circuit's state (hint: we're only looking at theory here)?

In our idealized model, out changes immediately. However, we know that the logic gates (AND, OR, NOT) that make up the MUX are physical transistors. They don't switch instantly. It takes a tiny, but measurable, amount of time for a change at a gate's input to propagate to its output. This is called gate delay or propagation delay. When you flip sel from high to low, that electrical signal has to travel through the NOT gate and the AND gates inside the MUX. The output of those gates then has to travel to the final OR gate, which then produces the final out signal. So, in this model, out will change after some gate delay. The change is not immediate, but it is very, very fast (nanoseconds).

Finally, will a combinational circuit ever be dependent on the history or state of a circuit? NO.

The definition of a combinational circuit is a circuit whose outputs are determined only by its current inputs. It has no memory. A MUX, an adder, a decoder—these are all combinational. Think of a simple light switch: the light is on or off based only on the switch's current position, not the history of how many times you've flipped it.

Sequential Circuit

A sequential circuit is a circuit that has this ability to remember. Its output depends on two things:

1. Its current inputs.
2. Its past history, which is stored as its "state."

So, how do we keep track of history in our lives? With a clock! Let's introduce the digital clock before we go any further into sequential circuits:

A waveform is a visual representation of how a signal, like voltage, changes over time. Time moves from left to right, and the signal's value is shown by its height. This specific blocky shape is a digital waveform, which acts as the steady "heartbeat" or clock for a sequential circuit, keeping everything synchronized.

The flat, horizontal parts of the waveform represent the signal's stable states. When the line is at the top (like the blue section), the signal is in a high state, representing a logical '1'. When the line is at the bottom (like the gold section), it is in a low state, representing a logical '0'. The circuit spends most of its time holding in one of these two states.

The most critical moments for a sequential circuit are the instantaneous transitions between these states, known as edges. The moment the signal jumps from low to high, highlighted by the vertical green line, is called the positive edge (or posedge). The moment it drops from high to low, shown by the vertical pink line, is the negative edge (or negedge). These edges act as the primary trigger, telling the memory elements in the circuit precisely when to "wake up" and update their state.

With this knowledge, how would we go about storing a single bit of information? Introducing the humble SR latch.

SR Latch

The SR Latch, standing for Set-Reset, is the most fundamental electronic circuit capable of storing a single bit of memory. It operates like a sticky light switch with two separate buttons: a 'Set' (set) input to turn the output (q) ON (a state of '1'), and a 'Reset' (reset) input to turn it OFF (a state of '0'). The latch's primary feature is its memory state: when both s and r inputs are inactive ('0'), it holds or 'latches' onto its last value, whether it was a '1' or a '0'. Here's the truth table:

The behavior of the latch is defined by its inputs. Activating the Set input forces the output to 1, while activating the Reset input forces it to 0. A critical condition exists when both Set and Reset are activated simultaneously; this gives the circuit a contradictory command to be both ON and OFF at the same time. This is known as the 'forbidden' or 'invalid' state because its outcome is unpredictable, and it is therefore avoided in circuit design. The design follows from the truth table:

The key limitation of the SR latch is that it's asynchronous—it reacts the instant its inputs change. This immediate responsiveness would be chaotic in a complex device like a computer, which requires all its components to act in perfect harmony. This need for synchronization is what leads to the development of the flip-flop, which is essentially an SR latch that is tamed by a clock signal, telling it precisely when to pay attention to its inputs.

Flip-Flop (FF)

The best way to understand a flip-flop is to think of it as a digital camera that is always pointed at something, but only takes a picture when you press the button.

Let's break down this analogy:

1. The Scene (d): The "thing" the camera is pointed at is the data you want to store. This is called the Data input, or d. This input can be changing all the time—sometimes it's a '1', sometimes it's a '0'.
2. The Shutter Button (clk): The camera doesn't save anything until you press the shutter button. This button is the Clock input, or clk. As we discussed, this input receives the steady, rhythmic pulse of the clock waveform.
3. The Photograph on the Wall (q): This is the last picture you took. It represents the single bit that is currently stored inside the flip-flop. This is called the Output, or q. This photo on the wall does not change, even if the scene in front of the camera changes, until you press the button again.

Let's look at a waveform example with clk, d, and q.

Notice how the output of the flip-flop, q, only changes on the positive edge of the clock.

First, imagine adding a gate to the SR latch's inputs that only "opens" when the clock signal is high. This creates a gated latch, but it's still not perfect, as it allows changes for the entire duration the clock is high. The true innovation of the flip-flop is to make it edge-triggered, meaning it only pays attention at the precise, instantaneous moment the clock transitions from low to high. The provided waveform demonstrates this perfectly. Look at the green dotted line: at that exact moment, the clk has a positive edge. The flip-flop "wakes up," sees that the data input d is high, and captures that value, causing its output q to go high.

Next, observe the period between the green and red lines. The d input goes low, but q remains high. This is the crucial "memory" function. Because there is no rising clock edge, the flip-flop ignores the change in d and holds its previously stored value. It isn't until the next rising clock edge, marked by the red dashed line, that the flip-flop wakes up again. At this instant, it sees that d is now low, and it captures this new value, causing q to go low. The output q is therefore a delayed version of the input d, only updating at the specific moments dictated by the clock's positive edge.

Finally, to create the D-type flip-flop from an SR latch, we simplify the inputs to eliminate the SR latch's "forbidden state." We use a single Data (d) input. This d signal is fed directly to the internal set input, while an inverted version of d is fed to the reset input. This clever trick ensures that set and reset can never be high at the same time. If d is '1', the flip-flop gets a set command. If d is '0', it gets a reset command. This creates the simple, predictable behavior seen in the waveform: on the rising clock edge, the output q becomes whatever the input d is.

Finite State Machine (FSM)

We're going to design the FSM "brain" for a single traffic light, like one you'd see at a pedestrian crossing. It will cycle through its three colors in a safe, predictable sequence: Green, then Yellow, then Red, and back to Green.

Following the suggested structure:

Step 1: Define the Inputs and Outputs

First, we define what our FSM needs to know and what it needs to control.

• Inputs: To keep it simple, the FSM only needs one piece of information: when it's time to change color. This will come from a timer.
  • timer_done: A single signal that becomes 1 when the light should change to the next color.
• Outputs: The FSM directly controls the three colored bulbs in the traffic light fixture.
  • red_light
  • green_light
  • yellow_light

(For any given state, only one of these outputs will be ON ('1') at a time).

Step 2: Determine the States

A "state" is just a stable condition of our system. For a single traffic light, we have three very obvious states, one for each color.

1. State GO: The green light is on.
   • Outputs: green_light = ON, red_light = OFF, yellow_light = OFF.
2. State CAUTION: The yellow light is on.
   • Outputs: yellow_light = ON, green_light = OFF, red_light = OFF.
3. State STOP: The red light is on.
   • Outputs: red_light = ON, green_light = OFF, yellow_light = OFF.

Step 3: Define the State Transitions

Now, we define the rules that make the FSM move from one state to the next. The timer_done signal is our only trigger.

• From GO to CAUTION:
  • IF the current state is GO AND timer_done is 1, THEN the next state is CAUTION.
• From CAUTION to STOP:
  • IF the current state is CAUTION AND timer_done is 1, THEN the next state is STOP.
• From STOP to GO:
  • IF the current state is STOP AND timer_done is 1, THEN the next state is GO.

This creates the endless, safe loop: GO -> CAUTION -> STOP -> GO...

Step 4: Visualize It - The State Diagram

Reading a ton of text is not a lot of fun (well, other than this blog post). This simple FSM is very easy to draw, giving us a clear blueprint of the logic and introducing you to the much more complicated FSMs to come for our fixed-point calculator project! A few notes: if an output is not mentioned in the state, assume it is LOW unless otherwise specified. If an input is not specified on the edges/transitions, assume it does not matter for that edge/transition.