Finite State Machine Programming Basics – Part 2

The first part of this article introduced a simple Finite State Machine through the exercise of transforming the standard linearly programmed Blink example into a FSM style application.

In this part we’ll look at other common embedded applications and how they can be coded using FSM techniques.

Uses of FSM

One of the most important uses of a finite state machine is to convert an asynchronous system (such as might be built in a functional language) to a system that is synchronous. Synchronous systems are much easier to debug and to maintain than asynchronous systems.

For example, imagine you are implementing the logic for switch input into an application and you have a function that determines key down and key up events. Converting this sort of input into the slightly higher level of single press, double press, and long press events basically comes down to implementing a finite state machine based on timers and the key events (see the MD_UISwitch library).

Another very common application for FSM are communications protocols. A protocol is just a state machine. Protocols are everywhere, from Ethernet frames (there’s a state machine at the bitstream level to detect that a packet is being sent), TCP (a very complex state machine), HTTP, and even Ajax implementations that rely on a sequence of message exchanges.

Operating Systems are also filled with FSM when managing, for example, Processes or Thread states (DEAD, IDLE, SCHEDULED, RUNNING, BLOCKED, …), I/O devices (WRITING, IDLE, READING, DEAD, …), Files (OPEN, CLOSE, …) and Memory management (PAGED OUT, HOT, …)

Basically, you will find FSM everywhere, but especially in embedded programming where sequential logic needs to interface to unpredictable asynchronous real-world events.

A Note on Programming Structure

In the examples below, the FSM is coded as using switch/case statements. They could equally be coded using if/else statements. I find the case style more readable and maintainable, but this is a matter of personal preference.

Equivalently, the code found in each ‘case’ section could also be put into separate functions which are invoked based on the current state. This approach is useful when a formal representation of the FSM is translated into code, as the data from the transition table or state diagram can be independent of the FSM management code (ie, a data driven approach). Many libraries and frameworks use this approach.

Switch Debouncing (Real-World Event)

Switch debouncing is a classic application for a FSM and is at the core of the MD_UISwitch library.

If we are using a time-based switch debouncing algorithm, then the task of reading and debouncing a switch can be broken into the following subtasks:

  1. Wait for transition from inactive to active (switch press). This depends on whether the switch is wired as pullup or pulldown.
  2. Wait for the debounce time period to expire.
  3. If the current switch status is still active (the same as it was before the debounce), then this is a valid press.
  4. Wait for the transition from active to inactive (switch release).

This is implemented as a function isPressed(), in the code below.

One of the nice things about FSM is that they are relatively easy to debug as we can simply follow the flow through each state and, because there is usually only a small amount of code in each state, work out where things may be going wrong. As an example I have added debug statements to this code.

Although the code only returns a true value if the switch is pressed, it could easily be extended to return ‘action’ values like KEY_DOWN, KEY_PRESS, KEY_UP by defining an enumerated type and setting the return value in the appropriate spot in the FSM.

#define DEBUG 1
#if DEBUG
  define FSM_STATE(s) { Serial.print(F("n:")); Serial.print(F(s)); }
  define FSM_ERROR(s) { Serial.print(F("n:")); Serial.print(F(s)); }
#else
  define FSM_STATE(s)
  define FSM_ERROR(s)
#endif

// Switch parameters
define SW_PIN  2
define SW_ACTIVE LOW   // LOW -> INPUT_PULLUP, HIGH -> External pulldown

bool isPressed(bool reset = false)
{
  const uint32_t DEBOUNCE_TIME = 50;
  static enum { WAIT_START, DEBOUNCE, CHECK, WAIT_END } state = WAIT_START;
  static uint32_t timeLastTransition = 0;
  static bool swLastActive = false;
  bool swActive = (digitalRead(SW_PIN) == SW_ACTIVE);
  bool b = false;

  if (reset) 
  { 
    state = WAIT_START;
    swLastActive = false;
  }

  switch (state)
  {
    case WAIT_START:   // waiting for start transition
      if (!swLastActive && swActive)   // transition to active
      {
        FSM_STATE("START");
        state = DEBOUNCE;
        swLastActive = swActive;       // save the current state
        timeLastTransition = millis(); // time from now
      }
      break;

    case DEBOUNCE:  // wait for the debounce time
      if (millis() - timeLastTransition >= DEBOUNCE_TIME)
      {
        FSM_STATE("DEBOUNCE");
        state = CHECK;
      }
      break;

    case CHECK:    // check switch still active
      FSM_STATE("CHECK");
      b = swActive;   // return status
      state = WAIT_END;
      break;

     case WAIT_END:
       if (!swActive && swLastActive)   // transition to inactive
       {
          FSM_STATE("WAIT_END");
          swLastActive = swActive;
          state = WAIT_START;
       }
       break;

    default:
      state = WAIT_START;
      break;
  }
  return(b);
}

void setup(void) 
{
  Serial.begin(9600);
  pinMode(SW_PIN, (SW_ACTIVE == LOW) ? INPUT_PULLUP : INPUT);
}

void loop(void) 
{
  if (isPressed())
    Serial.print("\n--> PRESS");
  // do something else
}

Receiving a Message from an Serial Input Stream (Simple Protocol Handling)

Another common application for a FSM is receiving a stream of characters from the serial port.

For this example we’ll assume that a message is defined as readable ASCII characters between a start character (‘<‘) and and end character (‘>’).

Characters received through a serial port may not all be available at the same time, so the function of the FSM is to buffer all the valid characters until the full message is received. Additionally, if we are in the middle of a message and no character is received for 1 second, then the message times out and the FSM should resynchronise to the start of the next message.

We can break the FSM into the following tasks:

  1. Waiting for the start character.
  2. Buffering all the characters until the end character is detected.
  3. If no character is received in 1 second, go back to waiting for the start character.
  4. When the end character is received, process the message. IN this example, we’ll just print the text.

This is implemented as processInput() in the code below. The function returns true when the message has been received so the caller can take action if required.

A couple of notes about this code:

  • And empty (nul or ‘\0’) character indicates that no character has been received form the serial port. It is safe in this situation as we are expecting readable characters, but in general a zero byte could be valid in the input stream. This is used in various places, especially to throttle the amount of debug that is output from the sketch.
  • The serial character is received in common code before the switch statement. This makes it easy to consistently update the inter-character timer but it does mean an extra ‘special’ check not to read a character when the current state is PROCESS_MESG as that character would be lost. The special check can be avoided by not having the PROCESS_MESG state and process the message in BUFFERING as soon as it is received. Either works, it is just a matter of preference.
  • The BUFFERING state is relatively complex as it must deal with the timeout, buffer overflow, detection of end of message, as well as just buffering characters.
#define DEBUG 1
#if DEBUG
  #define FSM_STATE(s) { Serial.print(F("n:")); Serial.print(F(s)); Serial.print(F(": ")); Serial.print(c); }
  #define FSM_MESG(s) { Serial.print(F("n->")); Serial.print(F(s)); Serial.print(F(": ")); Serial.print(cBuf); }
#else
  #define FSM_STATE(s)
  #define FSM_MESG(s)
#endif
 
bool processInput(bool reset = false)
{
  const uint32_t TIMEOUT_DELAY = 1000;
  const uint16_t MAX_LEN = 20;
  const char CH_START = '<';   const char CH_END = '>';

  static char cBuf[MAX_LEN+1] = "";
  static uint16_t lenBuf = 0;
  static enum { WAIT_START, BUFFERING, PROCESS_MESG } state = WAIT_START;
  static uint32_t timeLastChar = 0;
  char c = '\0';
  bool b = false;

  if (reset) state = WAIT_START;
  // read the next char if there is one
  // don't read if we are about to process the message
  if (state != PROCESS_MESG)
  {
    if (Serial.available())
    {
      c = Serial.read();
      timeLastChar = millis();
    }
  }
 
  // process the char based on state
  switch (state)
  {
    case WAIT_START:   // waiting for start character
      if (c != '\0')
        FSM_STATE("START");
      if (c == CH_START)
      {
         state = BUFFERING;
         lenBuf = 0;
         memset(cBuf, sizeof(char)*(MAX_LEN+1), '\0');  // clear the buffer
      }
      break;

    case BUFFERING:   // buffer up all the characters
      if (c != '\0')
        FSM_STATE("BUFFER"); 

      // have we timed out?
      if (millis() - timeLastChar >= TIMEOUT_DELAY)
      { 
        FSM_MESG("Timeout");
        state = WAIT_START;
        break;
      }
  
      // process the character
      if (c == CH_END)
        state = PROCESS_MESG;
      else if (c != '\0')   // not empty
      {
        cBuf[lenBuf++] = c;
        if (lenBuf == MAX_LEN)   // buffer overflow
        {
          state = WAIT_START;
          FSM_MESG("Overflow");
        }
      }
      break;

    case PROCESS_MESG:     // do something with the message
      FSM_STATE("PROCESS_MESG");
      FSM_MESG("Received");
      state = WAIT_START;
      b = true;
      break;

    default:
      state = WAIT_START;
      break;
   }
 return(b);
 }

void setup(void) 
{
  Serial.begin(9600);
}

void loop(void) 
{
  if (processInput())
    Serial.print("\nYIPPEE");
  // do something else
}

Garage Door Opener (Controlling Automation)

The final example will be controlling a garage door. The garage door has the following characteristics

  • It is controlled by one momentary-on switch or remote control (ie, one digital signal).
  • It can be open or closed. In between states it is in transition.
  • Open and closed positions are confirmed by limit switches at the top and bottom of travel.
  • In the open to close transition phase, pressing the door controller will open the door (reverse the motion).

Given the above function description, the door control FSM can be broken into the following tasks:

  1. When door is open: if the activation signal is detected, start the motion to close the door.
  2. When door is closed: if the activation signal is detected, start the motion to open the door.
  3. When door is moving from open to closed:
    • If the activation signal is detected, reverse the motion.
    • If the closed limit switch is detected, stop the door motion.
  4. When door is moving from closed to open, if the open limit switch is detected, stop the door motion.

We can easily simulate this door opener with a 3 switches and 3 LEDs, as implemented in the code below.

The first thing to realise is that we will need to debounce 3 switches. The isPressed() function we created before did that, and the cSignal class is essentially the same code logic turned into a class, with previously static data declared as class member variables to allow class instances to manage separate signal pins.

class cSignal
{
  public:
    cSignal(uint8_t pin, uint8_t active): _pin(pin), _active(active) {}

    void begin(void) { pinMode(_pin, (_active == LOW) ? INPUT_PULLUP : INPUT); reset(); };
    void reset(void) { _state = WAIT_START; _sigLastActive = false; };

bool isActive(void)
{
  bool sigActive = (digitalRead(_pin) == _active);
  bool b = false;

  switch (_state)
  {
    case WAIT_START:   // waiting for start transition
      if (!_sigLastActive && sigActive)
      {
        _state = DEBOUNCE;
        _sigLastActive = sigActive;
        _timeLastTransition = millis();
      }
      break;

    case DEBOUNCE:   // wait for debounce time
      if (millis() - _timeLastTransition >= DEBOUNCE_TIME)
        _state = CHECK;
      break;

    case CHECK:     // check still active
      b = sigActive;  // return status
      _state = WAIT_END;
      break;

    case WAIT_END:
      if (!sigActive && _sigLastActive)  // transition inactive
      {
        _sigLastActive = sigActive;
        _state = WAIT_START;
      }
      break;

    default:
      reset();
      break;
  }

  return(b);
}

private:
  uint8_t _pin;     // pin for this signal
  uint8_t _active;  // HIGH or LOW

  const uint32_t DEBOUNCE_TIME = 50;

  enum { WAIT_START, DEBOUNCE, CHECK, WAIT_END } _state = WAIT_START;
  bool _sigLastActive = false;
  uint32_t _timeLastTransition = 0;
};

As the code simulates the garage door, the motor controller function runMotor() is used to set the indicator LEDs.

void runMotor(int direction)
// direction parameter
// -1 runs the motor in direction to open the door
// 0 stops the motor
// 1 runs the motor in direction to close the door
{
  switch (direction)
  {
    case -1:  // opening door
      digitalWrite(LED_OPEN, HIGH);
      digitalWrite(LED_CLOSE, LOW);
      digitalWrite(LED_TRANSITION, HIGH);
      break;

    case 0:  // stop motion in all modes (motor off)
      digitalWrite(LED_TRANSITION, LOW);
      break;

    case 1:  // closing door
      digitalWrite(LED_CLOSE, HIGH);
      digitalWrite(LED_OPEN, LOW);
      digitalWrite(LED_TRANSITION, HIGH);
      break;
  }
}

Finally, here is the rest of the code including the garageFSM() function to run the logic implementing the requirements stated above.

// Signal parameters
const uint8_t SW_CONTROLLER = 4;  // remote control signal
const uint8_t SW_LIMIT_OPEN = 2;  // limit switch for open door
const uint8_t SW_LIMIT_CLOSE = 3; // limit switch for closed door

const uint8_t SW_ACTIVE = LOW; // LOW -> INPUT_PULLUP, HIGH -> External pulldown

const uint8_t LED_TRANSITION = 7; // LED indicator we are in transition
const uint8_t LED_OPEN = 5; // LED indicator for open door
const uint8_t LED_CLOSE = 6; // LED indicator for closed door

cSignal sigControl(SW_CONTROLLER, LOW);
cSignal sigLimitOpen(SW_LIMIT_OPEN, LOW);
cSignal sigLimitClose(SW_LIMIT_CLOSE, LOW);

void garageFSM(void)
{
  static enum { OPEN, OPEN2CLOSE, CLOSE, CLOSE2OPEN } state = OPEN;

  switch (state)
  {
    case OPEN:
      runMotor(0);
      if (sigControl.isActive())
        state = OPEN2CLOSE;
      break;

    case OPEN2CLOSE:
      runMotor(1);
      if (sigControl.isActive())
        state = CLOSE2OPEN;  // reverse the motion
      else if (sigLimitClose.isActive())
        state = CLOSE;       // reached the end of motion
      break;

    case CLOSE:
      runMotor(0);
      if (sigControl.isActive())
        state = CLOSE2OPEN;
      break;

    case CLOSE2OPEN:
      runMotor(-1);
      if (sigLimitOpen.isActive())
        state = OPEN;   // reached the end of motion
      break;

    default:
      state = CLOSE2OPEN;
      break;
  }
}

void setup(void) 
{
  // signal debouncers
  sigControl.begin();
  sigLimitOpen.begin();
  sigLimitClose.begin();

  // simulation LEDs
  pinMode(LED_TRANSITION, OUTPUT);
  pinMode(LED_OPEN, OUTPUT);
  pinMode(LED_CLOSE, OUTPUT);
}

void loop(void) 
{
  garageFSM();
  // do something else
} 

In this last example, we have four FSMs running at the same time (three for signal debounce and one for garage control), so we have essentially created code that runs 4 concurrent independent non-blocking tasks. This can be scaled to more tasks using the same techniques.

Also note that we only process the inputs as we need them. For example, we are not interested in the state of the close limit switch while we are opening the door, so it is never processed while in that state. This is a common characteristic of FSM processing logic – use only what you need at any time.

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