This is a guest post written by 43oh member, Fmilburn. You may ask questions related to the post in the comments below or in the 43oh forum.

Finite State Machines (FSM) are widely used in embedded applications and are well suited to controlling things that are event driven. The potential benefits include:

  1. A formal method to capture and test all states and inputs,
  2. easily defined logic, and
  3. simpler code to extend and maintain. In this introduction a simplified alarm system will be created with a Texas Instruments LaunchPad and Energia.

A Finite State Machine is an abstraction built around the concept of a finite number of states, with only one state active at any point in time. In the Moore FSM, which is used here, the output depends solely on the current state and the inputs / events determine the transition to a new state. The Moore FSM machine executes the following steps over and over again:

  1. Perform the output of the current state
  2. Get input and evaluate events
  3. Determine the next state based on the current state and the input / events
  4. Go to the next state and make it current (i.e. Step 1.)

To further illustrate the concept, consider a building divided into security zones. There is an alarm control panel with a green, yellow, and red LED for every zone as illustrated in Figure 1.

Figure 1 – Alarm Control Panel

The LEDs represent states, and the transition between states is determined by the inputs – e.g. a sensor in the building indicating fire, an intruder, or the operator clearing an alarm by pushing the reset button. The FSM could have multiple outputs for each state – such as an evacuation message and simultaneous activation of a fire suppression system.

For this simple example when there are no alarms the system will be in the GREEN state. When an ALARM is sensed the system will transition to the YELLOW state. The FSM will then pause for a predetermined time to allow the operator to reset the system with an input named RESET. This would be useful if for example it is a false alarm. If not reset it will move to the RED state.

This can be visualized graphically with a state machine diagram as shown in Figure 2.

Figure 2 – State Machine Diagram

 

The possible states are in boxes along with the actions they perform. Transitions between states are shown as arrows. The names of the events that cause a transition are written above the arrow. The three states are GREEN, YELLOW, and RED. Note that there is a specified pause in the YELLOW state and a transition to RED cannot occur until the timeout is completed. The meaning of each state and the events that cause transitions will be discussed further shortly.

The state transition diagram gives a quick impression of what the states do and how they transition. Another way to capture the same information is through a state transition table like the one in Figure 3.

Figure 3 – State Transition Table

Figure 3 contains a table for every state with the state name in the upper left hand corner. The actions performed in the state are in the upper right hand corner. The states that can be reached next (next state) and the events that can cause the transition are at the bottom.

Taking GREEN as an example, the green LED in the panel is turned on upon entry and all other LEDs turned off. Note that the RESET input has been left out of the table. RESET will not cause a transition when in the GREEN state. The firmware will contain a comprehensive table that covers every possible input for every state as well as any timeout between transitions.

When the YELLOW state is entered all LEDs are turned off except the yellow one. There are two transitions that can occur:

  1. A transition to RED with a TIMEOUT, or
  2. if RESET input is received it will return to GREEN. RESET will cause a return to GREEN even if the ALARM is ongoing.

The starting time is captured and the elapsed time watched while in the YELLOW state. The yellow LED is left on. A transition will occur if the elapsed time exceeds the specified timeout or the operator pushes the RESET button.

The RED state turns off all LEDs except the red one. A transition will occur if RESET occurs even if the alarm is active. However, unless the operator continually holds RESET the FSM will immediately move to YELLOW if the ALARM is active. In a real system it might be desirable to have another timeout before transitioning to YELLOW.

A Texas Instruments LaunchPad MSP-EXP430F5529LP and a breadboard will be used to demonstrate but it should be possible to use most LaunchPads where Energia is available. The red button switches in Figure 4 set ALARM and the green buttons are used for RESET. Three zones have been set up.

Figure 4 – Security System Demonstration with MSP430-EXPF5529LP

LEDs are connected from their respective pins to a suitable resistor, to the LED anode, and then from the LED cathode to ground. Switches are connected from their respective pins (pulled high by the microcontroller) to the button and then ground.

The full code can be found here on github.

The simplicity of the implementation is seen in Figure 5, the Energia sketch. Adding an additional zone can be done with two lines of code – a call to the constructor with the Energia pin numbers and desired timeout, plus the addition of the method Update() in loop() for the new zone.

#include "Security.h"
// Yellow
// |---- Energia Pin Numbers ----| timeout
// alarm reset green yellow red (mSec)
Security zone_1 (2, 3, 4, 5, 6, 4000); 
Security zone_2 (7, 8, 9, 10, 11, 2000);
Security zone_3 (12, 13, 14, 15, 19, 3000);

void setup() {
// Nothing needed here.
}

void loop() {
zone_1.Update();
zone_2.Update();
zone_3.Update();

The Finite State Machine is implemented as a C++ class in Security.cpp and has the header file Security.h.

Pay particular attention to the definition of the Finite State Machine table in Security.cpp. The resultant state for input that causes transitions is defined for every state and matches the diagrams and tables generated earlier. The table also holds the timeout for every state but is initialized to 0. In this example only the yellow timeout is greater than zero, and the new value is placed in the table when the constructor is called.

When the Update() method is called, a case / switch control structure is used to select the proper state. Update() should be called frequently to avoid undesired lag. Note that the state is called only if there has been a change in state.

The private methods doGreen(), doYellow(), and doRed() carry out the appropriate actions for their state. In this simple example that is mostly limited to getting the proper LED lit. But also notice that the timeout is read for each state and a start time for the timeout recorded. This allows for a more general FSM where all states have a timeout.

Input and the elapsed time are then evaluated in getEvents(). The inputs are determined first and then timeout is evaluated. When a timeout is greater than zero, a check is made to see if the elapsed time is greater than the desired timout. The event is initialized as NONE – i.e. the buttons are not pushed and there is not a TIMEOUT in progress. IF RESET is pushed it takes priority over all other inputs. The ALARM event cannot be set if there is a timeout in progress. Finally, the event will be TIMEOUT if it was determined to be true earlier in the method.

In getNextState() two possibilities are possible. If the event was NONE, then no change in state has occurred. Otherwise, the next state can be determined directly from the table.

For the MSP430F5529 and Energia V18 the reported memory usage is 1914 bytes code and 30 bytes data written to FLASH. The expected RAM usage is 274 bytes so the implementation is reasonably compact.

My thanks to @chicken for providing links, reviewing the code, and offering valuable perspective on the use and structure of FSMs (any errors belong to me). I have chosen to use a Moore FSM and a table to implement this example but there are other approaches. Additional information on Finite State Machines can be found in the following links:

  1. https://github.com/fmilburn3/Security_FSM/tree/master – the latest version of the source code in this tutorial.
  2. http://users.ece.utexas.edu/%7Evalvano/Volume1/E-Book/C10_FiniteStateMachines.htm – page down for a look at the traditional Traffic Light Controller FSM implemented in C using pointers on a Texas Instruments Tiva C LaunchPad.  There is also a vending machine example.
  3. http://forum.43oh.com/topic/728-state-machine-example-code/ – a series of posts started by @zeke on 43oh
  4. https://learn.adafruit.com/multi-tasking-the-arduino-part-1/a-classy-solution?view=all – a gentle introduction without formal theory.  Uses C++ classes to manage multiple tasks involving LEDs and servos.
  5. http://barrgroup.com/Embedded-Systems/How-To/Coding-State-Machines – FSM examples using C/C++ and considerations for selecting states
  6. http://barrgroup.com/Embedded-Systems/How-To/State-Machines-Event-Driven-Systems – compares FSMs to other approaches and outlines the advantages
  7. http://www.faisoncomputing.com/publications/articles/OOStateMachines.pdf
  8. https://en.wikipedia.org/wiki/Finite-state_machine  – had to include Wikipedia of course… an overall discussion plus illustrations of different transition table and diagram methods.
  9. http://www.plantuml.com/plantuml/uml/SyfFKj2rKt3CoKnELR1Io4ZDoSa70000 – Online diagram generation tool
  10. http://plantuml.com/state-diagram – Instructions for using online diagram generation tool
  11. http://energia.nu/guide/tutorial_library/ – An introduction to libraries in Energia and C++ classes.