A state machine is a computational model based on automata theory. The state machine model is widely used to describe discrete systems, where the current behavior is a function of previously occurring events. At a given point in time the system is in one of several possible states. The system can change its state depending on input from the environment. As a state change occurs, actions can be performed on the environment.
A state machine is generally defined by a set of:
- States - A state embodies information about the current situation in the system.
- Events - An event is an input message to the state machine.
- Transitions - A transition is a change from one state to another, usually triggered by an event.
- Actions - An action is an activity to be performed by the state machine at a given point in time.
- A set of primitives to express guard conditions on transitions.
There are a number of different notations and semantics for state machines; the ones most widely used in the design of embedded systems have probably been Moore machines and Mealy machines. The main difference between these notations is when an action can occur. In a Moore machine, actions can take place upon the entry of a state. A Mealy machine can only have actions associated with transitions between states.
In 1987 David Harel introduced the concept of hierarchical state machines that can capture concurrent behavior inside one state machine.
Click to see larger image.
The state machine semantics defined by UML is largely based on the Harel notation and incorporates both Mealy and Moore semantics.
A formal treatment of state machines and automata theory can be found at the National Institue of Standards and Technology. More information is also available at Wikipedia.
State machines in visualSTATE
In visualSTATE, state machines or systems of parallel machines are designed using the UML notation. The design philosophy of visualSTATE can be expressed as follows:
- Map events in the environment, like device driver input or interrupts, to state machine events.
- Capture the discrete system logic in states, events, transitions and actions using UML diagrams.
- Map actions to functions or device drivers interacting with the environment.
By separating the core system logic from the environment, a number of benefits arise:
- It is possible to generate extremely tight C code for the state machine logic. visualSTATE was designed from the start with code generation efficiency in mind.
- Existing hardware board support can be reused as is, with minor modifications, if it is reasonably structured.
- The design model is very clean, dealing only with the discrete behavior of the system.
- Formal verification can be performed on the model, thereby discovering possibly erroneous behavior at an early stage.
IAR visualSTATE has modest requirements on the run-time environment:
- An ANSI C or C++ compiler to compile the generated code. This code can run on any 8-, 16- or 32-bit target, regardless of OS. This includes your PC or workstation, running any proprietary or non-proprietary OS.
- No requirements on any OS services. If running close to the hardware, visualSTATE can remove the need for a task switcher, since a design model can express concurrency among state machines.
- If an OS is present, it is very easy to integrate a visualSTATE model into the run-time environment.
- 1-2 kByte of ROM for the fixed overhead for the state machine representation, plus a few bytes for each transition. This shall be compared to coding the logic by hand. (The fixed overhead can be lower or larger, depending on the actual target and compiler used, but the figures are representative.)