Finite State Machine Matrix-Style C Implementation

Finite State Machine Matrix-Style C Implementation

Date: September 8, 2008
Author: Bennet Gedan
Category:
Tags: , , , , ,

There are several implementations of finite state machines avaible, the only drawback most of them are suffering is that they are moore machines (under certain circumstances this means a large number of states) and changing the machines behaviour will change the whole code structure (this means low flexibility and the reprogramming may be a huge cause of defects).

I’d like to present an Implementation of a FSM, i’ve found during my student research project that is a mealy machine and does not require a reprogramming of the underlying structure.

I realized this implementation in an event-driven structure in LabVIEW (g) (file a comment if you’re interested in that implementation). However i recently needed a state machine implementation in C, and tested some implementations and remebered my old implementation of that matrix-style implementation.

State Transition Table

The basic idea of this implementation is that every state machine can be directly represented as a state transition table. I’ll be using a two-dimensional transition table (matrix), depending of current active state and possible events (see Table 1).

Table 1: State Transition Table
Event 1 Event 2 Event 3
State 1 State 2, Action 2 State 3, Action 1 State 1, Action 4
State 2 State 1, Action 3 State 2, Action 1 State 2, Action 3
State 3 State 3, Action 1 State 1, Action 4 State 2, Action 2

e.g. the current state would be ‘State 2′ and the second event has been triggered, the machine will initiate ‘Action 1′ and stay in ‘State 2′.

This compact representation can easily be derived from any state diagramm. Suchlike tabular structures can be transferred into programming languages without difficulty. This is the main benefit of this representation.

C Code

States, events and actions are represented by enumerator typedefinitions. All the rest will be build upon them.

/*******************************
 * typedefs
 *******************************/

typedef enum {
       STATE_0,
       STATE_1,
       STATE_2
} state;

typedef enum {
      NILACTION,
      ACTION_1,
      ACTION_2,
      ACTION_3,
      ACTION_4
} action;

typedef enum {
      NILEVENT,
      EVENT_1,
      EVENT_2
} event;

typedef struct {
      state nextState;
      action actionToDo;
}  stateElement;

Based on these type definitions the state transition table can be developed as a 2D-Array of stateElement structs.

stateElement stateMatrix[3][3] = {
       { {STATE_0,NILACTION}, {STATE_1,ACTION_1}, {STATE_1,ACTION_4} },
       { {STATE_1,NILACTION}, {STATE_2,ACTION_3}, {STATE_2,ACTION_2} },
       { {STATE_2,NILACTION}, {STATE_0,ACTION_2}, {STATE_1,ACTION_3} }
}

these definitions and constants can be stored in the header file. Getting the machine running is realized via a basic function.

/***************************************
 * prototypes
 ***************************************/
action stateEval(event e);

This function determines what action will be occasioned depending on the triggered event and sets the new state of the machine. The mechanism behind this function is lightweight.

action stateEval(event e)
{
	//determine the State-Matrix-Element in dependany of current state and triggered event
       stateElement stateEvaluation = stateMatrix[currentState][e];

	//do the transition to the next state (set requestet next state to current state)...
	currentState = stateEvaluation.nextState;
	//... and fire the proper action
	return stateEvaluation.actionToDo;
}

All that is done is indexing the stateMatrix-Array depending on current state (row) and occured event (column). All things additional needed will be a global constant currentState to store the machines state. This could be done in the main()-loop. Control of the state machine can be achieved via simple mechanism over the stateEval()-function.

        // this single line is the whole FSM-Call, easy as that!
        actionToDo = stateEval(eventOccured);

This could be put in an event-triggered interrupt-routine, a while-loop, a for-loop over each triggered event, or whatever is reasonable. The eventOccured has to be computed by a special algorithm, for example an combination of more or less complex expressions. In the easiest imaginable way this would be an if-structure:

if ( T > T_MAX ) {
   eventOccured = overTemperatureEvent;
}

All these little parts combined lead to a quite simple approach for a state machine implementation in programming languages.

The most convincing part is the state transition table, wich is the only thing –beneath the states und events type definition– that has to be changed, to change the whole state machine behaviour. It has a direct connection to state machine theory and the common state diagram representation. Thus making this approach tremendously customizable and understandable.

Related Posts