Chapter 5: Finite State Machines

This chapter follows Lecture 5. Chapter 4 introduced registers and circuits that retain values: the timer, counters, accumulators and shift registers. A finite state machine is what you get when you decide on purpose what a controller must remember: a small number of situations the circuit can be in, a rule for moving between them on each clock tick, and an output that depends on where it is and what it sees.

The chapter follows the way a designer works. You start from a description in words and draw a state diagram. You turn the diagram into a truth table and then into gates and flip-flops, the kind of translation a synthesis tool makes. You write the same machine in SystemVerilog, and you test it by taking every arrow of the diagram at least once. The testbenches for the machines themselves have a clock, so the chapter begins with the statements that let a testbench wait for one.

What you will be able to do

After this chapter you can:

• make a testbench wait for a delay, a clock edge or a condition, and say what value a signal has when the next line runs;
• read a state diagram, trace an input sequence through it one clock cycle at a time, and draw a diagram for a behavior described in words;
• choose a code for each state, write the encoded truth table of a machine, and minimize each next-state bit and output with a K-map;
• say what a circuit does if it lands in a state code that the diagram does not use;
• go through the four steps of a design, from a problem statement to the logic, on a small machine such as a vending machine;
• write a machine in SystemVerilog in four parts and recognize a Mealy output from the code;
• plan a test that takes every arrow of a diagram from reset, and read the waveform to check it.

Sections

• 5.1 Timing controls in testbenches
• 5.2 State diagrams
• 5.3 From state diagram to circuit
• 5.4 The FSM design process: a vending machine
• 5.5 FSMs in SystemVerilog
• 5.6 Testing FSMs

Section 5.1 is a short detour into testbench syntax, and it comes first because the testbenches for state machines in this chapter all use a clock. Section 5.2 is the heart of the chapter: it introduces the state diagram with one example, the long-press detector, and the sections that follow keep coming back to it. Section 5.3 takes that detector from the diagram down to gates, using the K-map skills of Chapter 3. Sections 5.4 to 5.6 put the pieces together on a design from scratch, in SystemVerilog, and in a test.