Homework — Finite State Machines

Introduction to Finite State Machines (FSMs)

A Finite State Machine (FSM) provides a systematic way to design sequential logic for control sequences.

Structure

The figure shows the generic structure of a synchronous sequential system. The outputs of the system depend on some internal state (state in the figure).

Depending on this state and the inputs of the system, we can compute combinatorially its next state value (n_state in the figure) that will replace the state value at the next clock edge.

The outputs of the system will only depend on its state value (combinatorially).

This kind of synchronous system is called a Moore Finite State Machine (FSM).

The name (FSM) comes from the fact that with this structure, the number of states that a system can have is limited (and thus finite) by the size of the state register.

Methodology

Starting from a functional specification.

Draw a state transition diagram

Each node is one of the possible states of the system. The arcs represent the transitions from one state to the other. The label on each arc represents the condition for which the transition is taken (functions of the inputs).

Remember that this diagram represents the state transitions of a synchronous system. The evolution of the state can only happen at the clock edge.

In this example:

• S0 represents the initial state (i.e. after an active reset)
  • there is an explicit transition from S0 to S1 when c is high,
  • there is an implicit transition, if c is not high, the state remains S0
• From S1 to S2 there is an unlabeled arc, this indicates that we will systematically go from S1 to S2 at the next clock cycle.

State encoding

Represent each state by a numerical value.

For example:

This encoding is arbitrary and not unique.

State transitions

The state transition function can be constructed using a truth table. For the previous example:

This table describes the combinatorial function to compute the next state. Note that 'x' in the table stands for don't care, i.e. the given transition will be the same for any value (0 or 1) of the respective input. Note also that there is one unreachable state, which corresponds to the value 11.

From the above table, we can derive Boolean equations for the state transition function. Ther is only one transition to S2, and it is always taken from state S1 so the function for the most significant bit can simply be expressed as

\[ \text{n_state}_1 = \overline{\text{state}_1} \cdot \text{state}_0 \]

There are two transitions to state S1, setting the least significant bit of the state encoding to 1. The function can thus be expressed by

\[ \text{n_state}_0 = \overline{\text{state}_1} \cdot \overline{\text{state}_0} \cdot \text{c} + \text{state}_1 \cdot \overline{\text{state}_0} \cdot \overline{\text{e}} \]

Exercise

We want to design a finite state machine corresponding to the following specification:

• We want to control two LEDs via the output signals \(LED_0\) and \(LED_1\)
• The only input signal besides the clock \(clk\) and an asynchronous \(reset\) is a \(button\)
• In the initial state, both LEDs are off
• When the button is pressed once, \(LED_0\) is turned on
• When the button is pressed once more, \(LED_0\) is turned off again
• When the button is pressed once more, \(LED_1\) is turned on
• When the button is pressed once more, the system return to the initial state (both LEDs switched off)

Note: The clock signal is very fast compared to any input action performed using a big human finger on the button. Pressing the button will result in the corresponding input signal going high for many cycles. So you need to somehow ensure that only a single change of the lights is triggered by a button press.

Question 1: Draw the state transition graph of an FSM realising the above specification. Indicate the conditions of the state transitions as well as the output values corresponding to the states. How many states does your solution need?

There are several possible solutions, one of which is a pure state machine solution, while another one combines a state machine with an edge detector. In the following we will consider this latter solution and assume that the button is connected to a rising edge detector, which generates the signal \(top\) on each rising edge of the button.

Question 2: Draw again the state transition graph, this time using \(top\) as input instead of the button.

In the following, you will construct a circuit realising the finite state machine. Let's revise the general structure of an FSM's hardware implementation:

Here, the cloud on the left hand side represents the next state function, while the one on the right hand side represnets the output function. The current state is stored in the central register. Both next state and output function are combinatorial.

Question 3: Choose a state encoding for your state machine. First determine the number of bits (and therefore flip-flops) needed to represent all of your states. Then establish a mapping of your states to concrete values of the flip-flops.

We will call the output signals of the state register \(S_i\) in the following.

Question 4: Establish the output function. In a first step, fill in a truth table, mapping your state encoding to the outputs \(LED_0\) and \(LED_1\). For example, if your states are encoded in two bits, this corresponds to the following table:

Question 5: From the truth table, derive the Boolean equations for both output signals.

Question 6: Establish the next state function. Start again with a truth table. This time, we need to consider the combinations of the input \(top\) and the current state. Here is again a table for a two-bit state encoding, \(S_0'\) and \(S_1'\) being the next state signals.

Question 7: From the truth table, derive the Boolean equations for the next state signals.

Question 8: Implement the state machine in logisim. A template circuit can be found in the archive:

cd fsm
logisim fsm-impl.circ &

Note that there is a second circuit sim in the same file, which you can use to test your solution. In the same directory, the file fsm-solution.circ contains a correct implementation for comparison.