Finite State Machine Programming Basics – Part 1

Many beginner programmers, once they go beyond the ‘blinking LED’ code, get blocked by not being able to do more than one thing at once. In many cases they are directed to the ‘Blink WithOut Delay’ code (BWOD) as a hint about what to do, but this soon also runs out of steam. BWOD implies, but does not make explicit, a Finite State Machines (FSM) approach.

In this article we’ll evolve the simple linear Blinking LED sketch into a FSM to illustrate the difference in approach.

Finite State Machines

The Finite State Machine is an important technique for creating non-blocking code and making many things happen at once in embedded programming.

FSM programming is a model of computation based on a hypothetical machine made of one or more states. Only a single state can be active at any time, so the machine must transition from one state to another in order to perform different actions.

FSM can be formally represented in a number of ways, including tables and state transition diagrams. To keep it basic, we’ll use simple lists of tasks. More formal methods will make sense, and are useful, once you know how to use a FSM and are ready for more complex applications.

We’ll focus on the practical aspects of programming a task using a FSM, using the blinking LED as an initial example. To be clear, this is not a task that really needs a FSM approach, but it is useful to illustrate how to transition from linear code into a FSM structure with a simple and familiar example.

There is a lot of information already available about FSM so I won’t repeat it here – a simple internet search will yield many millions of hits. A good video introduction to FSM programming can be found here.

The Blinking LED

The ‘Hello World’ of embedded programming is a blinking LED. Most beginners start with code like this standard blink.ino Arduino example to toggle a LED on and off.

void setup() 
{
  pinMode(LED_BUILTIN, OUTPUT);
}

void loop() 
{
  digitalWrite(LED_BUILTIN, HIGH);
  delay(1000);
  digitalWrite(LED_BUILTIN, LOW);
  delay(1000);
}

While there is nothing wrong with the code as it stands, a problem instantly arises if we want to do something else in loop(), as the blinking takes 2 second to complete, nearly all of which is actually doing nothing in delay(). We could try to reduce delays. For example:

void setup(void) 
{
  pinMode(LED_BUILTIN, OUTPUT);
}

void blink(void)
{
  const uint32_t LED_DELAY = 1000;

  digitalWrite(LED_BUILTIN, !digitalRead(LED_BUILTIN));
  delay(LED_DELAY);
}
 
void loop(void) 
{
  blink();
  // do something else
}

This somewhat improves the situation as blink() now only takes one second to complete. Realistically though, this is still unacceptable for any application processes real-time events.

Note, however, that implicit in this code structure is a break down of the blinking task into two distinct subtasks which we will return to later:

  1. Toggle the LED
  2. Wait for the delay period

A Better Blinking LED

The first thing is to replace delay() by a non-blocking timer check, as illustrated in the Arduino BlinkWithoutDelay (BWOD) example. We can modify blink() as follows:

void blink(void)
{
  const uint32_t LED_DELAY = 1000;
  static uint32_t timeLastTransition = 0;

  if (millis() - timeLastTransition >= LED_DELAY)
  {
    digitalWrite(LED_BUILTIN, !digitalRead(LED_BUILTIN));
    timeLastTransition = millis();
  }
}

This timing technique avoids blocking while waiting for time to pass. blink() now compares the current time (in milliseconds) to the time when the last LED transition occurred. The timeLastTransition variable is declared with local static scope to retain its value between calls to blink(). The logic is now:

  • If enough time has passed, it toggles the LED as before and sets the current time as the new transition time.
  • If not enough time has passed, it simply does nothing and exits the function.

Blinking LED as a FSM

We now have all the right parts to change blink() into a FSM. Recall that earlier we divided the blinking task into two subtasks. These subtasks are used to convert the linear code to a FSM.

void blink(void)
{
  const uint32_t LED_DELAY = 1000;
  static uint8_t state = 0;
  static uint32_t timeLastTransition = 0;

  switch (state)
  {
    case 0:   // toggle the LED
      digitalWrite(LED_BUILTIN, !digitalRead(LED_BUILTIN));
      timeLastTransition = millis();
      state = 1;
      break;

    case 1:   // wait for the delay period
      if (millis() - timeLastTransition >= LED_DELAY)
        state = 0;
      break;
  }
}

So what has happened? We organised each of the subtasks into a sequence of code in the switch statement. The ‘subtask’ code is essentially the same as in the previous version of this sketch but split into sections within the switch statement.

The flow of execution through blink() needs some explanation. When it is invoked, the code ‘resumes’ at the case bookmarked by the state variable (which is initially 0) and stops executing at break. This state bookmark only changes if is assigned a new value. Case 1 (non-blocking wait) is executed repeatedly until the time check expires and the state bookmark is changed to 0. The next time through, case 0 toggle the LED and changes the state to 1, and the cycle continues.

Importantly, blink() never holds up the the execution of the rest of the code running inside or from loop().

A More Robust FSM

We can evolve this FSM code to make it more robust, readable and maintainable.

void blink(bool reset = false)
{
  const uint32_t LED_DELAY = 1000;
  static enum { LED_TOGGLE, WAIT_DELAY } state = LED_TOGGLE;
  static uint32_t timeLastTransition = 0;

  if (reset)
  { 
    state = LED_TOGGLE;
    digitalWrite(LED_BUILTIN, LOW);
  }

  switch (state)
  {
    case LED_TOGGLE:   // toggle the LED
      digitalWrite(LED_BUILTIN, !digitalRead(LED_BUILTIN));
      timeLastTransition = millis();
      state = WAIT_DELAY;
      break;

    case WAIT_DELAY:   // wait for the delay period
      if (millis() - timeLastTransition >= LED_DELAY)
        state = LED_TOGGLE;
      break;

    default:
      state = LED_TOGGLE;
      break
  }
}

A few things have changed:

  • blink() takes an optional boolean parameter that allows the code to reset the FSM to a known state. This could be done in setup() or anytime that the blinking needs to stop and turn off the LED.
  • state is defined as an enumerated type. This makes it much easier to read and follow the code, especially when there are more than just a handful of states. It also avoids the practical problem renumbering all the states when additional intermediate states are added or deleted (from experience, this will happen!).
  • the default state in the switch statement is a defensive measure to ensure that any undefined or corrupted state does not stop the FSM – an unhandled state would otherwise simply skip over the whole switch block! Examples of when this can arise is if a state is added and you omit code in the switch statement, or if the state variable’s memory becomes corrupted.

Conclusion

The control of program flow using FSM style coding is a powerful model that is applicable in many situations where a task is made up of ‘doing’ and ‘waiting’ subtasks or a number of tasks that can be logically separated.

In the next part we’ll examine other common examples where FSM programming is usefully applied.

Advertisements

One thought on “Finite State Machine Programming Basics – Part 1

  1. Kartik Arora

    This is really nice for getting people started and also helping them with the basics of computational thinking!

    Kudos! Sharing.

    Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s