State Machines – an Introduction

By | May 5, 2014

State machines are very useful tools in any computer system. They make it easy to visualise and solve all kinds of problems. Any small robot is likely to have a use for several state machines. This introduction looks at some basic types of state machine and an easy way to implement them. 

A state machine is a device that keeps track of the status of something. That status can change as a result of changes to input values or it may change over time in some pre-determined sequence. A common example might be a traffic signal at a junction or road works. The status describes which of the light may be lit at the same time. For simple timed lights, the status will change regularly after fixed time intervals. The same lights could be made more flexible if some input can also cause the state to change. That might be from a radar detector or magnetic coil in the road. Sets of lights could incorporate a pedestrian crossing and then the pedestrian request button would be another input.

State Machine States

Clearly a state machine must have some initial state to make sure that everything starts up in the right sequence. It is less clear whether there should be a final state. Traffic lights have no need for a final state. Once started, they cycle through their states forever. Some kinds of state machines have one or more terminating conditions. For example, a key-code lock responds to input in the form of buttons pressed on a keypad and, only when the correct sequence is, the state machine enters an accepting state and the lock is opened. The same lock could be made more secure if only a certain number of tries is allowed. After a number of unsuccessful attempts, a rejecting state could prevent any further activity until the system is reset.

A State Machine Example

Inputs and Outputs

A state machine that did nothing would be no good so it will have some kind of output actions or values. The traffic lights have the red, amber and green lamps as outputs. The key-code lock would have a lock actuator and possibly a warning or error lamp as outputs.

Both inputs and outputs can be treated as values or, in real time systems, as events. An input value might be a sensor reading or the value on a processor IO pin. The state machine would regularly check these inputs at intervals. The input levels themselves have no effect until they are tested by the state machine and then acted upon. In that sense, a change in input value could be seen as an event. The consequent output is also an event. Events mark a change to inputs or outputs. It is common in embedded systems to have inputs tested at regular intervals.

Some events may not have to be checked regularly. That may be because they are relatively rare and there is no point wasting processor time checking for something that is very infrequent. For example, compared to the speed of a modern computer, the user is very slow and the central processor does not keep looking to see if the human user has done something like press a key. Instead, when a significant input change happens, an event is generated and sent to the operating system for it to act upon. Other events may be particularly important – like power failure – or time-sensitive – like the arrival of a character from a serial port. If these events are not acted upon immediately there could be significant data loss.

State Machine Features

So, for a state machine there will be

– input events
– output events or actions
– an initial state
– a number of additional states resulting from events

There is a lot of formal computing wrapped around state machines but I want to concentrate on simple, common uses in a way that shows how they can be used. In particular, the ways that diagrams are drawn and the names used for different parts of a state machine diagram vary according to actual use and the user doing the work. There are standards but always check the rules for the diagram you are looking at to make sure there is no misunderstanding.

Detecting change

Suppose I want to monitor a digital IO pin and find out if it has changed. This is trivially easy in code without any reference to state machines but it will illustrate how to describe, create and use a simple state machine. The single input is going to have two values: 0 and 1. The single output is also going to have two values: 0 if there is no change and 1 if there has been a change. The state machine will need three states. An initial state to get things going and then two states that keep track of whether the input just went high or just went low.

Edge Detecting State Machine

On the diagram, states are shown as circles with their name written inside. The initial state has a double outline to help make it stand out from the others. There is no terminating or accepting state because this state machine will run forever. Between the states are arrow. Change always happens in the direction of the arrows. Sometimes, the movement between states is called a transition. In this diagram, the transitions are labelled with two values like this: 0/1. The first number is the input and the second one is the output. Since the input can have one of two values, each state should have exactly two arrows coming out from it. There will be at least one arrow going in to a state but there could be many more than two.

State Machine Implementation

To implement this state machine, a variable would be used to store the value of the current state. It could have one of the value START, HIGH or LOW. No other values are permitted. The input will be read at intervals. That could be regular intervals with a timer interrupt or just whenever the code needs to know if the value has changed. For each state, there ios a value of the input that maintains the current state, outputting a zero, and a value of the input that causes the state to change and that outputs a 1.

A common and easily understood way to implement a simple state machine in code is to use some kind of switch statement. Here I will use C but similar constructs are used in many languages. The resulting code takes quite a lot of lines but is very simple and will compile to a compact and fast solution. There are many other ways to implement a state machine but this article just looks at the simple and easy ways.


int testInput(int input) {
  static int state = START;
  int output;
  switch (state) {
    case START:
      if (input == 0) {
        state = LOW;
        output = 0;
      } else {
        state = HIGH;
        output = 0;
      }
      break;
    case LOW:
      if (input == 0) {
        state = LOW;
        output = 0;
      } else {
        state = HIGH;
        output = 1;
      }
      break;
    case HIGH:
      if (input == 0) {
        state = LOW;
        output = 1;
      } else {
        state = HIGH;
        output = 0;
      }
      break;
  }
  return output;
}

This code would be executed periodically from a timer tick or as required by the caller. Clearly, if the input changes twice between calls, the output will appear not to have changed.

Other State Machines

There are many uses for state machines in computer systems. There is a good chance any menu is implemented as a state machine. The process of connecting a web server can be performed with a state machine – or making the initial TCP connection in a network. Handshaking a serial connection is another example. A line follower robot could use a simple state machine to govern all its activity including navigating corners, responding to user input, detecting start/stop markers and pausing in the start area. If there is a push button in a project, there is a need to detect presses and debounce the button.This state machine debounces button presses.

A state machine for debouncing a button

To work in a real system, the state machine should be updated about every 10ms. It will take two state changes to update the debounced value of the buttonA button that bounces for longer will need a slower update rate.

Another application of state machines is finding information from a data stream. That could be detecting specific sequences like the key-code lock or transforming a stream of data from one form to another. It could be translating data from one format to another. At the simplest level, run-length encoding data could use a state machine. Converting ASCII numbers into their internal binary representation can be done with a state machine. At the top of this post is a sequence detecting state machine that looks for the binary bit pattern 1011. Now that you know a little more, go back and follow it through to see how it does that.

For the micromouse builder there are some good examples of state machines in the task of finding a smooth path from start to goal. More details on this will be in the next post on smooth path finding.

References

 

 




2 thoughts on “State Machines – an Introduction

  1. Joffmann

    I think there’s an error in the code.
    It should be:
    case START:
    if (input == 0) {
    state = LOW;
    // …

  2. Peter Harrison Post author

    You are quite right. I will fix that.

    Thank you for letting me know.

Leave a Reply