CC Blog Quick Bits Resources

Simple State Machines

Written by Andrew Levido

State machines are a critical building block for anyone writing firmware. They provide a simple method for describing and coding relatively complex behavior. A state machine – more properly called a finite state machine—is an abstract machine that can be in just one of a finite number of states at any one time. It transitions from one state to another based on some combination of inputs known as a trigger. This state transition can also be associated with some action that is executed whenever it occurs. State transitions can have guard conditions must be satisfied before the transition occurs, even if the trigger is present. Each state can also have an optional entry action or exit action which are executed on entering or exiting the state respectively. We are going to ignore guard conditions and entry or exit actions for this exercise.

A state machine can be fully defined by its list of states, the transitions between those states and an initial state. One way to visualise this is through a state diagram. There are many conventions for drawing state diagrams, and I have shown the one I use to illustrate a simple example in Figure 1. In this example we have a pushbutton that our firmware polls periodically to determine if the button is open or closed. We are interested in capturing the event that the button is pressed or released for some hypothetical user interface.

FIGURE 1. A simple state diagram. The states are represented by the boxes. Optional entry and exit actions are shown inside the box – there are none in this case. The arrows represent state transitions. The label names the trigger that causes the transition, followed optionally by the transition action. The initial transition (the arrow with the black dot) indicates which state the machine will be on at start-up.

In this case we set up two states, PRESSED and RELEASED, illustrated by the rectangles. The state name is at the top, and entry and exit actions listed below (there are none in our example). The state transitions are indicated by the arrows, and the transition trigger, followed by the transition action (if any) are written next to the transitions. The transition with the black dot is the initial transition which defines the state in which the machine will start.

Initially the button will be in the RELEASED state. In this case, when we poll the button, and find it open, we do nothing and remain in the current state. If we find the button is closed, we switch to the PRESSED state and execute the transition action to signal the button has been pressed. Similarly, when we are in the PRESSED state, if we find the button closed, we do nothing, but if we find it open, we transition to the RELEASED state and signal that the button has been released. We can also describe a state machine via a state table (Figure 2) which sets out the same information in a tabular form. I find making a state transition table a useful step in getting from state diagram to code. The code snippet in Listing 1 shows how this simple state machine might be implemented in C.

FIGURE 2. This state table contains the same information as the state diagram of Figure 1 but in tabular form. I find this a very useful format when coding the state machine because it is almost pseudocode as it stands. Note the “do-nothing” transitions are not necessary but are shown here for completeness.
/* Code Snippet 1
 * A simple state machine to extract button press and release 
 * events fromm button position (open = 0 or closed = 1) when polled.
 * Includes "do-nothing" transitions for completeness. Lines 
 * commented /// can be deleted if desired.
 */

/* Set up the states */
enum buttonState { RELEASED, PRESSED };

/* Create a variable to hold state and initialize */
enum buttonState state = RELEASED;

/* Executed every time the button is polled - first read
 * the button value and then execute the state machine 
 */
unsigned button = getButton();

switch(state) {
    case RELEASED:                  // RELEASED state
        if(button == 1) {           // trigger: closed 
            state = PRESSED;        // next state
            signalPress();          // transition action
        }
        else {                      /// trigger: open
                                    /// do nothing
        }                           ///
        break;
    case PRESSED:                   // PRESSED state
        if(button == 0) {           // trigger: open
            state = RELEASED;       // next state
            signalRelease();        // transition action
        }
        else {                      /// trigger: closed
                                    /// do nothing
        }                           ///
        break;
    default:
        break;
}

Up to this point we have explicitly shown the “do nothing” transitions where the particular combination of state and trigger does not require a state transition or transition action. In more complex cases with many inputs there can be a lot of these. They don’t add anything to our understanding of the state machine and so they are usually left out of the diagram table and code.

Let’s look at a slightly more complex example. Imagine we want our button to behave differently. We want a press on the button to turn a LED on and another press to turn it off. At first you might create a state diagram like the one in Figure 3.  We’ve ignored the do-nothing transitions in this case. If we are in the OFF state, and we see the button is closed we move to the ON state. If we are in the ON state and we see the button is closed, we transition to the OFF state.

— ADVERTISMENT—

Advertise Here

FIGURE 3. This is a naïve attempt at capturing a state machine to toggle a LED each time a button is pressed. Because we execute the state machine every time the button is polled, the LED will toggle every polling period while the button remains closed. We really need to introduce some more states to ensure the button is pressed and released to toggle the LED.

You can probably already see a problem. If the user holds the button down, or even if the press on the button is longer then the polling period, we will oscillate back and forth between states. What we really need is to ensure there is a distinct press-and-release action to change from off to on and vice versus.

FIGURE 4. To correctly implement our LED-toggling state machine we need more states. The diagram at the top which illustrates the behavior we want clearly shows us we have four states to contend with. The state machine below shows the triggers, transitions and transition actions that will achieve the result we are looking for.

Figure 4 shows a revised state machine that addresses the problem. The diagram at the top helps us understand that we really have four possible states: ON_OPEN, ON_CLOSED, OFF_OPEN and OFF_CLOSED. We start in the OFF_OPEN state with the LED off. If the button is closed, then we transition to the ON_CLOSED state and turn the LED on. We remain in this state until the button is opened, when we transition to the ON_OPEN state. When the button is next closed, we transition to the OFF_CLOSED state and turn the LED off. Finally, when the button is opened again, we transition to the OFF_OPEN state. The code snippet in Listing 2 shows how this might be implemented in C.

LISTING 2

/* Code Snippet 2

 * A simple state machine to turn a led on and off on
 *  successive button presses 
 */

/* Set up the states */
enum buttonState { OFF_OPEN, ON_CLOSED, ON_OPEN, OFF_CLOSED };

/* Create a variable to hold state and initialise */
enum buttonState state = OFF_OPEN;

/* Executed every time the button is polled - first read
 * the button value and then execute the state machine 
 */
unsigned button = getButton();

switch(state) {
    case OFF_OPEN:                  // LED Off Button open state
        if(button == 1) {           // trigger: closed 
            state = ON_CLOSED;      // next state
            LEDOn();                // transition action
        }
        break;
    case ON_CLOSED:                 // LED On Button closed state
        if(button == 0) {           // trigger: open
            state = ON_OPEN;        // next state
        break;
    case ON_OPEN:                   // LED On Button open state
        if(button == 1) {           // trigger: closed 
            state = OFF_CLOSED;     // next state
            LEDOff();               // transition action
        }
        break;
    case OFF_CLOSED:                // LED Off Button closed state
        if(button == 0) {           // trigger: open
            state = OFF_OPEN;        / next state
        break;

    default:
        break;
}

State machines can get a lot more complex than this. In more complex systems state machines will normally be arranged in a hierarchy in which each state of a high-level state machine contains one or more lower-level state machines. There is way too much to go into here, but it’s an abstraction technique that is extremely useful in breaking down complex behaviours into simple-to-implement chunks.

References:

“Finite-State Machine.” In Wikipedia, June 3, 2021. https://en.wikipedia.org/w/index.php?title=Finite-state_machine&oldid=1026568157.

“State Machine Diagram – UML 2 Tutorial | Sparx Systems.” Accessed July 1, 2021. https://sparxsystems.com/resources/tutorials/uml2/state-diagram.html.

Keep up-to-date with our FREE Weekly Newsletter!

Don't miss out on upcoming issues of Circuit Cellar.


Note: We’ve made the May 2020 issue of Circuit Cellar available as a free sample issue. In it, you’ll find a rich variety of the kinds of articles and information that exemplify a typical issue of the current magazine.

— ADVERTISMENT—

Advertise Here

Would you like to write for Circuit Cellar? We are always accepting articles/posts from the technical community. Get in touch with us and let's discuss your ideas.

+ posts

Andrew Levido (andrew.levido@gmail.com) earned a bachelor’s degree in Electrical Engineering in Sydney, Australia, in 1986. He worked for several years in R&D for power electronics and telecommunication companies before moving into management roles. Andrew has maintained a hands-on interest in electronics, particularly embedded systems, power electronics, and control theory in his free time. Over the years he has written a number of articles for various electronics publications and occasionally provides consulting services as time allows.

Sponsor this Article

Supporting Companies

Upcoming Events


Copyright © KCK Media Corp.
All Rights Reserved

Copyright © 2021 KCK Media Corp.

Simple State Machines

by Andrew Levido time to read: 6 min