State Machines in C

If a system functionality is where outputs depend on the order in which input events occur, or input events that occur at different times (states) will cause to different output, then these models are called "Time-Ordered Behavior". For example:

  • An electronic lock may require a user to press and release button 5, then 3, then 2 to unlock a door
  • A fan has only one button. When a user first presses the button to turn on fan at 25% speed. If the user presses the button continuously, the fan speed will be changed to 50%, 75%, then 100%. When the fan speed reaches to 100% and user presses the button again, the system will turn off the fan.

State machines are perhaps the most effective method for capturing Time-Ordered Behavior for embedded system. A state machine has several components:

  • Set of inputs and outputs
  • Set of states with actions
  • Set of transitions with conditions
  • and an initial state

The following tools are used to describe the time-ordered behaviors:

  • State Diagram:
    A drawing of a state machine, also called State Transition Graph, (STG). It is a popular way for representing state machines.
    A state diagram includes the following components:
    • State: stores information about the past and reflect changes from the start of system to the present state.
    • Current State: determined by past states of the system.
    • Transition: indicates a change from one state to another. Transitions are invoked by Events.
    • Event: the inputs to a state machine.
    • Action: also called an output. It is a description of an activity that is to be performed as a result of an input and change of state. An event can be depicted either on the transition or within the state.

    MooreSM 01MealySM 01
    Figure 1
    : State Diagrams
  • State Transition Table:
    A state transition table (or state table) describes a state machine in a tabular format.

    Table 1: State Transition Table
    SM DataTable

    This simple model exemplifies a LED controller that embodies two states: LED off (S_IDLE) and LED on (S_1) and two inputs: SW1 and SW2. If the LED is in the S_IDLE state, and an input SW1 is presented, the state machine progresses to the S_1 state. If an input of SW1 is presented to the machine in the S_1 state the machine stays in the S_1 state.

 

There are two models for incorporating actions into state machines:

  • Moore
    A Moore machine performs actions when entering a state. Each state may have it's own entry action.
  • Mealy
    A Mealy machine performs actions on transitions. Each transition in a state machine may invoke a unique action.

Moore and Mealy state machines have their own advantages and disadvantages. But one of great advantage of both is that they are not mutually exclusive, and these two models can be used together in the system.

 

 

What are the difference between Moore and Mealy state machines? The following table shows the point the differences from a Moore machine to  a Mealy machine:

Moore State Machine Mealy Sate Machine
Outputs depend on current state only
outputs = F(currentState);
nextState = F(inputs, currentState);
Outputs depend on current state and the inputs
outputs = F(inputs, currentState);
nextState = F(inputs, currentState);
Generally, it has more states then Mealy Generally, it has fewer states than Moore
Output does not react immediately to input change (one clock cycle later) Outputs have immediate reaction to inputs
Output is placed on states Output is placed on transitions
Easy to design It it difficult to design

 


Implement State Machine in C

State machine for a stoplight controller is shown as Figure 5.

StoplightController SM
Figure 5: Stoplight Controller

A state diagram can be implement in three main ways: Nested Switch, the State Pattern, and State Tables.

State machines are a very useful programming model, especially when the system needs to act according to its history (state) and the environment (event). Implementing code using a state machine is very difficult to maintain, because the system reacts differently depending on the state and event. Therefore, a good documentation is very important.

 

State Machines v.s. Flowcharts

Maybe you will confuse state machines with flowcharts. The most important difference between state machines and flowcharts is that the state machines perform to next actions (state) only in response to explicit events, they are event driven. In contrast, flowcharts do not need to be triggered by events; they are used to describe the progression of the task from beginning to end, step by step.

StateMachineVsFlowchart
Figure 6
: State Machine vs Flowchart

The distinction between state machines and flowcharts is especially important when analyzing system behavior. Because these two concepts represent two diametrically opposed programming paradigms: state machines are event-driven programming; and flowcharts are transformational programming.

When you design a state machine, you have to constantly thinking about available events (inputs). In contrast, events are not the first concern for flowcharts, but procedures.