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.
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.
/* 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—
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 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.
Sponsor this Article
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.
