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.
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
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:
A Moore machine performs actions when entering a state. Each state may have it's own entry action.
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.
Moore State Machine
The interior of the Moore state machine consists of three blocks:
- Next state block: a function of current state and inputs to decide the next state.
- State Register: to store current state from next state.
- Output: depends on current state.
Figure 2: Moore State Machine Architecture
Moore state machine has following characteristics:
- Output value or action depends on current state: output = F(CurrentState);
- Significance is the state
- Input: when to change state
- Output: what to do while in that state
State Diagram for Moore State Machine
The state diagram of a Moore state machine is shown below:
State Transition Table for Moore State Machine
The state transition table of the above Moore state machine is shown below:
Table 2: State Transition Table for Moore State Machine
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.
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.
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.