State machines

Most embedded systems are event driven, that is they need to respond in some way to an externally or internally generated event. Often the required response to that event will depend on the current state of the system. For example consider the shift key on a computer when pressed the characters entered should appear in capital case, when un-pressed they should appear as lower case.

Figure 1 UML State Transition Diagram for the shift key

This action can be readily captured in the UML state machine shown in Figure 1. The States are represented in the boxes, which also includes the Activity associated with the state. The Activity is the function that is carried out by the system whilst it is in that state. The transitions are shown as the arrows between the states where the Event that causes the transition is labelled first followed by the Action that is associated with the transition. The Action is the function that is carried out in response to the Event before the system enters the new state.

The state machine formalism provides a structured way to design such systems and also allows for efficient implementation in an embedded system. There a three ways to approach the coding of a state machine

  1. Using a series of nested switch statements
  2. Define a state table containing an (typically sparse) array of transitions for each state and then a small function to respond to events and update the current state
  3. Object-oriented designs that represent a state machine as a dynamic tree-like structure of state and transition objects traversed at run time by a specialized “state machine interpreter.”

For simple or small state machines the nested switch statement works well but was the number of states and complexity increases then this approach becomes harder to code and maintain. The state table approach greatly simplifies the implementation and maintenance, however, it can be inefficient in terms of space as the state transition and action tables can often be quite sparse. The most efficient approach is to make use of the object orientated approach.

FSM Implementations

Nested Switch Statement

State Transition Table

Advertisements

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s