1. Home
2. Academy
3. State Machines from Zero
4. Volume 00

0.1 How to use this course

This course teaches one skill - designing circuits that remember what they are doing - in small steps. Each step uses only what came before it.

Welcome. This course is about state machines. A state machine is a circuit that always knows which situation it is in. When something happens, it moves to a new situation. You meet state machines every day. A traffic light is one. So are a lift, a washing machine and a ticket machine.

You do not need to know electronics or programming to start. This first volume teaches the few ideas the rest of the course needs. It takes less than an hour.

How every lesson is built

Every sub-module follows the same pattern, so you always know where you are:

1. The big idea - the whole sub-module in one sentence, at the top.
2. In plain words - the idea explained simply, without jargon.
3. Think of it like this - an everyday picture of the same idea.
4. A figure - a diagram or a timing picture to study.
5. The exact version - the precise words an engineer would use.
6. An example or some code - the idea put to work.
7. Common mistake - the trap most beginners fall into, so you can step around it.
8. Quick check - one or two questions, to make sure the idea has landed.

The explanations sit in coloured boxes. Here is what each kind looks like:

New words

Every technical word is explained the first time it appears. It has a dotted underline, like this: bit. Point at it with your mouse, or tap it, to see a short meaning. Click it to open the full glossary, which lists every word from every course. At the end of each volume, a "Key words" list collects that volume's new words.

Optional parts

Check yourself, then mark it done

Each sub-module ends with a quick check. Choose an answer, and the page tells you at once whether it is right, and why. If you get one wrong, read the explanation and try again. Mistakes made here are cheap, and they teach you the most.

When you finish a volume, press Mark as complete at the bottom of the page. Your progress then shows in the sidebar. It is saved only in this browser, so there is no account and nothing to sign up for.

The road ahead

0.2 Bits, 0 and 1, and logic gates

Digital circuits work with just two values, 0 and 1, and combine them using a few simple building blocks called logic gates.

One bit: 0 or 1

Inside a digital circuit, every wire is in one of two conditions. It is either at a low voltage or at a high voltage. We call low 0 and high 1. One wire carrying a 0 or a 1 holds one bit of information.

Why only two values? Because two values are easy to tell apart, even when the circuit is noisy. A little noise can make a "high" wire slightly lower. It is still clearly high, so the circuit still reads a 1. With ten levels to tell apart, small errors would change the value.

Many bits together

One bit gives two choices. Put bits side by side, and the number of patterns grows fast. Two bits make four patterns: 00, 01, 10 and 11. Each extra bit doubles the count.

This rule matters a lot for state machines. A state machine stores its situation as a pattern of bits. If a machine has 5 different situations, it needs at least 3 bits, because 2 bits give only 4 patterns. You will use this rule again in Volume 03.

We can also use bit patterns to count. This is called binary. Each place is worth twice the place to its right: 4, then 2, then 1. So the pattern 101 means 4 + 0 + 1, which is 5.

Logic gates

A logic gate is a tiny circuit. It takes one or more bits in and gives one bit out, following one fixed rule. The four gates you need are NOT, AND, OR and XOR. Figure 0.1 shows the symbol for each one.

We describe a gate with a truth table. A truth table lists every possible input, and the output for each one. Here are all four gates in one table:

In plain words:

• An AND gate gives 1 only when all of its inputs are 1.
• An OR gate gives 1 when at least one input is 1.
• A NOT gate flips its input: 0 becomes 1, and 1 becomes 0.
• An XOR gate gives 1 when its two inputs are different.

Gates have no memory

A gate reacts to its inputs right now. Change an input, and the output changes a moment later. The gate does not know what its inputs were a second ago. Logic like this, with no memory, is called combinational logic.

That is a problem for us. A traffic light cannot be built from gates alone, because it must remember which colour it is showing. For that we need memory, which is the next sub-module.

In Verilog, the language this course uses, gates are written with symbols:

// Each line describes one gate. "assign" means: keep this wire
// always equal to the expression on the right.
assign y_not = ~a;       // NOT
assign y_and = a & b;    // AND
assign y_or  = a | b;    // OR
assign y_xor = a ^ b;    // XOR

0.3 What a flip-flop remembers

A flip-flop is a one-bit memory: at each tick of the clock it copies its input, and it holds that value until the next tick.

The clock

Most digital circuits have a special signal called the clock. It goes 0, 1, 0, 1, over and over, at a steady rate. The clock carries no information of its own. Its only job is to say "now!" to the rest of the circuit.

The moment the clock changes from 0 to 1 is called a rising edge. Most circuits act only on rising edges. The time from one rising edge to the next is one clock cycle. A clock with 100 million cycles in each second has a frequency of 100 MHz.

The flip-flop

A flip-flop is the smallest memory in a digital circuit. It stores one bit. The most common kind is the D flip-flop. It has an input called D (for data), a clock input, and an output called Q.

Its rule is short:

Figure 0.2 shows the rule at work. Read it from left to right. D changes at odd moments, but Q changes only just after a rising edge.

Follow the figure edge by edge:

1. Edge 1. Just before the edge, D is 0. So Q becomes 0.
2. Edge 2. D rose to 1 during the last cycle. At this edge Q copies it and becomes 1.
3. Edge 4. D fell back to 0 during the last cycle. Q copies it and drops to 0.
4. Between edges 4 and 5. D jumps up and falls back down. No edge happens during the pulse, so Q never sees it.
5. Edge 7. D is 1 again, so Q becomes 1.

Why flip-flops matter for state machines

The flip-flop is the memory we were missing. A group of flip-flops that share one clock is called a register. A register of 3 flip-flops holds a 3-bit pattern, so it can hold 8 different values. A state machine keeps its current situation in exactly this kind of register.

Logic that contains memory is called sequential logic. What it does depends on the sequence of things that happened before, not only on its inputs right now.

Reset: a known starting point

When power first comes on, a flip-flop may hold a 0 or a 1. Nobody knows which. That is fine for some circuits, but not for a state machine. A machine that wakes up in a random situation could do something dangerous - such as showing green to every road at a crossing.

So circuits have a reset signal. While reset is active, it forces the flip-flops to a known value. Every state machine in this course starts from a reset.

In Verilog

You do not need to understand every word of this yet. Volume 04 explains Verilog properly. For now, read the comments on the right.

// A D flip-flop with a reset.
module dff (
  input  wire clk,    // the clock
  input  wire rst,    // reset: 1 means "go back to 0"
  input  wire d,      // the value to store
  output reg  q       // the stored value
);
  always @(posedge clk) begin   // at every rising edge of clk:
    if (rst) q <= 1'b0;         //   reset wins - store 0
    else     q <= d;            //   otherwise, store d
  end
endmodule

Two pieces of this code are worth knowing already. posedge clk means "at the rising edge of clk". And 1'b0 means "a value one bit wide, equal to 0".

0.4 Reading a timing diagram

A timing diagram is a graph of signals over time. Read it from left to right, one clock edge at a time.

You have already seen one timing diagram: Figure 0.2. Every later volume uses them, so it is worth learning to read them properly.

The parts of a timing diagram

1. Time runs from left to right. Each dotted vertical line marks a rising clock edge. The small numbers along the top count the edges.
2. Each row is one signal. Its name is on the left. The line it draws is its waveform.
3. High means 1, low means 0. A line near the top of its row is a 1. A line near the bottom is a 0.
4. A band with a word inside is a bus. A bus is a group of wires that carry a value wider than one bit. The value is written inside the band. Where the band pinches, the value changes.
5. Hatching means unknown. A hatched band is a value that nobody knows yet.

Figure 0.3 has all of these parts. It shows a tiny machine that waits for a start signal, works for three cycles, and then says it is done.

Follow it edge by edge:

1. Edge 1. Reset is 1, so the state is forced to IDLE. Before this, the state was unknown.
2. Edge 2. Start is still 0, so the machine stays in IDLE.
3. Edge 3. Start is 1 just before this edge. The machine sees it and moves to RUN. Busy goes to 1, because the machine is now working.
4. Edges 4 and 5. The machine stays in RUN. Start has gone back to 0, but that does not matter. The machine remembers that it was started.
5. Edge 6. Three cycles of work are done. The state moves to DONE, and busy drops to 0.
6. Edge 7. The machine returns to IDLE, ready for the next start.

Look again at edges 4 and 5. This is the whole point of a state machine. The start input was 1 for only one cycle, yet the machine kept working, because its state remembered.

Just before the edge, then just after it

Here is the most important reading rule. At a rising edge, a flip-flop takes the value its input had just before the edge. Its new output appears just after the edge. That is why, in these diagrams, outputs change a little to the right of the dotted line.

Unknown values

At the start of Figure 0.3, the state and busy rows are hatched. This is an unknown value. The flip-flops have power, but nothing has told them what to hold yet. Reset fixes that at edge 1. A simulator prints an unknown value as x. If you see x after reset, some signal was not reset or not driven - a bug worth chasing.

0.5 Running Verilog free in your browser

You can describe a circuit in Verilog and watch it work in a simulator, for free, without installing anything.

Three new words

• Verilog is a hardware description language. You write text that describes a circuit. It looks a little like a programming language, but it describes wires and flip-flops, not a list of steps.
• A simulator is a program that reads your Verilog and behaves like the circuit would. You can watch every signal.
• A testbench is extra Verilog that exercises your circuit during simulation. It drives the inputs, and it prints or checks the outputs.

Where to run it

This course uses EDA Playground in its examples, because it needs nothing but a browser. Every example also works with Icarus Verilog on your own computer.

Your first simulation

You will simulate the D flip-flop from sub-module 0.3. You need two pieces of code: the design, which is dff.v above, and a testbench. Here is the testbench:

module dff_tb;
  reg  clk = 0, rst = 1, d = 0;   // signals we drive
  wire q;                         // the signal we watch

  dff dut (.clk(clk), .rst(rst), .d(d), .q(q));  // the design under test

  always #5 clk = ~clk;           // flip the clock every 5 time units

  initial begin
    $dumpfile("dump.vcd");        // record every signal change...
    $dumpvars(0, dff_tb);         // ...so the waveforms can be drawn
    #12 rst = 0;                  // release reset at time 12
    #10 d = 1;                    // at time 22, set d to 1
    #20 d = 0;                    // at time 42, set d back to 0
    #20 $finish;                  // at time 62, stop
  end

  initial $monitor("t=%0t rst=%b d=%b q=%b", $time, rst, d, q);
endmodule

The clock starts at 0 and flips every 5 time units, so it rises at t = 5, 15, 25, 35 and so on. The last line prints a report whenever a signal changes. When you run it, you should see:

t=0 rst=1 d=0 q=x
t=5 rst=1 d=0 q=0
t=12 rst=0 d=0 q=0
t=22 rst=0 d=1 q=0
t=25 rst=0 d=1 q=1
t=42 rst=0 d=0 q=1
t=45 rst=0 d=0 q=0

Read it line by line. At t=0, q is x, because nothing has happened yet. At t=5, the first rising edge comes while reset is 1, so q becomes 0. At t=22, d becomes 1, but q stays 0. At t=25, the next rising edge arrives, and only then does q copy d. The same thing happens in reverse at t=42 and t=45.

Step by step in EDA Playground

1. Open EDA Playground and log in. The account is free.
2. In the menu on the left, under Tools & Simulators, choose Icarus Verilog.
3. Paste the testbench into the code box named testbench.sv, and the design into the box named design.sv.
4. Tick Open EPWave after run, so the waveforms open by themselves.
5. Press Run. The printed lines appear at the bottom, and the waveform window opens.

Working offline instead

If you prefer your own computer, install Icarus Verilog and GTKWave. Both are free. Then run three commands in a terminal:

iverilog -o sim dff.v dff_tb.v    # build the simulation from both files
vvp sim                           # run it
gtkwave dump.vcd                  # open the waveforms

The file dump.vcd is a VCD file. It records every change of every signal. A waveform viewer, such as GTKWave or EPWave, reads it and draws the timing diagram for you.

What you learned

• A bit is a 0 or a 1. With n bits you can make 2ⁿ different patterns.
• Logic gates (NOT, AND, OR and XOR) combine bits, but they have no memory.
• A D flip-flop stores one bit. It copies D to Q only at a rising clock edge.
• A register is a group of flip-flops. Reset puts it into a known starting value.
• In a timing diagram, look just before an edge to see what was captured, and just after it to see the result.
• You can simulate Verilog for free in EDA Playground, or offline with Icarus Verilog and GTKWave.

Key words from this volume

Every word below has a plain-English entry in the glossary.

• State machine (FSM)
• Bit
• Voltage
• Binary
• Logic gate
• Truth table
• AND gate
• OR gate
• NOT gate (inverter)
• XOR gate
• Combinational logic
• Verilog
• Clock
• Rising edge
• Clock cycle
• Frequency
• Flip-flop
• D flip-flop
• Register
• Sequential logic
• Reset
• Setup time
• Hold time
• Timing diagram
• Waveform
• Bus
• Unknown value (X)
• Hardware description language (HDL)
• Simulator
• Testbench
• Simulation
• VCD file
• Waveform viewer

Practice

Next, Volume 01 puts these pieces together and builds your first state machine - on paper, one arrow at a time.