Re: [Statemachine-development] References for FSM's

[<vvi...@in...>]

Hello John,

Welcome to the prject. Here's an introduction to FSM.

An FSM software architecture is particularly ideal for event-driven
applications. These applications simply sit and wait for input to change or
for a signal or interrupt to arrive. When such an event arrives, it
performs some action, produces some output, then goes into a waiting
pattern again.


     A major advantage of using an FSM is the ability to decompose large
     applications using a very small number of items in a diagram.


     For example, the following seemingly trivial FSM:


(Embedded image moved to file: pic03510.gif)
This FSM has two states, two inputs, and four different actions and outputs
defined, for a total of 16 different items that need to be considered by
the software. To be able to clearly show 16 different items on a single
diagram with this much simplicity makes FSMs valuable for relaying an
architectural design.


     A circle in an FSM represents a "state". Think of a state as "waiting
     for something to happen". The "something" comes in the form as a
     change in input, or arrival of a signal, or perhaps the interrupt
     generated by a timer. The input then triggers an action, possibly
     produces output, and possibly changing the next state.


     In digital logic designs, the inputs are generally always binary. In
     these cases, implementing the FSM in hardware (e.g. using an FPGA)
     might be preferable to doing it in software. The power of using
     software becomes apparent when inputs are not necessarily binary. For
     example, the input can be specified as "an alphanumeric character,"
     which means the letter is in the range {`A'..'Z' || `a'..'z' ||
     `0'..'9'}. In software, this range is easily specified as isalpha(ch).
     The software FSM can also have inputs that are inequalities, such as
     "if (inputA < 100) do action 1".


     The actions can also be as simple or as complex as necessary. An
     action could simply toggle a value (like selecting or de-selecting an
     item), or it can be extremely complex, like starting an entirely new
     process.


     The output can have many forms. The most obvious is information
     displayed on the terminal for the user. But output can also be data to
     a file or to global memory, a return value for a function, a message
     to another system, or any other form of output.


     Once the event has been processed, the final item to be done before
     going to check for a new input is to determine the next state. The
     diagram clearly shows the next state for any input; this can be
     translated to code using either state tables, or a global "state"
     variable that is used as an index in deciding what to do when the next
     input arrives.


     For example, the simple state machine above can be implemented in code
     as a switch statement as follows:


switch (state) {

           case A:
                     switch (input) {
                               case 0:
 do action a1

produce output 1

break;

                               case 1:
 do action2

produce output 2

break;
                     }
           case B:
                     switch (input) {
                               case 0:
 do action3

produce output 3

break;

                               case 1:
 do action4

produce output 4

break;
                     }
}


     A switch statement, however, is not necessarily the best way to
     implement an FSM. In particular, the inputs must be constant, and a
     lot of code might be required to do similar things.


     There exist many alternatives. For example, if the input values are
     constants, jump and lookup tables or hash tables become especially
     efficient. For example, the simple two-state two-input FSM can be
     shown in a table as follows:


|------+                ---------------|
|      |               |     input     |
|------+---------------+---------------|
| state|       0       |       1       |
|------+---------------+---------------|
| A    | action1/output| action2/output|
|      | 1             | 2             |
|------+---------------+---------------|
| B    | action3/output| action4/output|
|      | 3             | 4             |
|------+---------------+---------------|





     A major advantage of the tabular form is that you can quickly identify
     any undefined combinations of inputs and states, as well as ensure
     there are no conflicting actions. Such completeness aids in producing
     robust code.


     We can then write the code as follows:


call  function action[state,input]();
generate output lookup[state,input];


     Of course, the output might be dependent on the action as well. But
     the above shows how jump tables (i.e. arrays of functions) and lookup
     tables can be used to efficiently implement code that is structured as
     a finite state machine.


     As the software designer, you have total control on how states are
     numbered. Generally you number them beginning at 0, so that lookup
     tables are concise. However, if any other state numbering works, then
     use it.


     In cases where software is defined with dozens of states and hundreds
     of possible inputs (e.g. what if every key on your keyboard can do
     something different, like if you were writing code for an editor?),
     such abbreviated code becomes very easy to work with. Each action is
     then defined as a standalone subroutine, and the task of integrating
     everything is very simple.


     On the other hand, with a large number of states or inputs, there
     might only be only a few different states and actions, and rather more
     complex conditions are used to determine the action. For example,
     "input 0" might refer to "all alphanumeric characters" while "input 2"
     is all special characters. Maybe there is a third input, "all
     non-printable characters".


     In such cases, either large if-then-else statements can replace the
     use of a switch statement, or the conditions for each input can be
     encoded as functions. The use of large if-then-else statements does
     make it much more difficult to modify and debug. However, sometimes it
     is the best way. But at the very least, always consider the alternate
     lookup table methods.


     Suppose we define each box in the state table by a structure:


typedef struct {
           fsmCond_f                                          condition;
                                               // returns a boolean value
           fsmAction_f                                        action;
                                          // return value is the output
           int                                      nextstate;
} fsm_t;


The state table is then defined as follows:


fsm_t statetable[MAXSTATES][MAXINPUTS] = {
           { abcCondition, abcAction, 1 },
           { defCondition, defAction, 3 },
           etc.
}


     The MAXINPUTS refers to the number of input columns in the table, not
     the number of inputs. Thus, if one of the columns is "all alphanumeric
     characters", that counts as a single input.


     Note the structure of the functions in the table. This is the same as
     you did in question 2 of the exam, so you already know how to build
     these kinds of tables. Later we will see a trick using C macros to
     make the definition of these types of tables even easier.


     The state machine can then be implemented as a single loop within the
     infinite outer loop:


fsm_t *fstate;
while (1) {                                                   // infinite
loop waits for events
           state = nextstate;
           wait for event;
           fstate = &statetable[state][i];

           for (i=0;i<MAXINPUTS;++i) {[i];ite
                     if (fstate->condition(args-if-any)) {
                               output = fstate->action(args-if-any);
                               send output to wherever
                               nextstate = fstate->nextstate;
                     }
           }
}



     Variations to the above loop can be made as necessary. But the closer
     the design of the system can correspond to the above basic structure,
     the easier it will be to implement. New states can then easily be
     added just by building a module with the xyzCondition() and
     xyzAction() functions defined, then adding them to the state table.



     That was just an intro so that we are all thinking on similar lines.


     You also find some good stuff on the following sites

http://www.bagpuss.dircon.co.uk/courses/chs-217/Semester2/Week8/Lecture2/

http://helios.hud.ac.uk/staff/scomhro/Courses/Spr01/CHS217/lecture/lecture8/#SECTION00050000000000000000

     I have also downloaded some lectures from various Univs, I'll post a
summary some time later as I still have to go thru them.

     Till then, bye


     Vishakha