Register forum user name Search FAQ

Gammon Forum

Notice: Any messages purporting to come from this site telling you that your password has expired, or that you need to verify your details, confirm your email, resolve issues, making threats, or asking for money, are spam. We do not email users with any such messages. If you have lost your password you can obtain a new one by using the password reset link.
 Entire forum ➜ Electronics ➜ Microprocessors ➜ State machines

State machines

Postings by administrators only.

Refresh page


Posted by Nick Gammon   Australia  (23,094 posts)  Bio   Forum Administrator
Date Wed 04 Dec 2013 06:15 AM (UTC)

Amended on Thu 05 Dec 2013 08:48 PM (UTC) by Nick Gammon

Message
What is a state machine?


The words sound scary, but "state machines" are all around us. To put it simply, it is something that does something differently depending on what state it is in.

This page can be quickly reached from the link: http://www.gammon.com.au/statemachine


Example 1 - a TV remote




We've all seen these, and we take for granted that if we punch the "power" button (circled) the TV turns on if it is off, and off if it is on.

But wait! That one button does two things, right? It can either:


  • Turn the TV off; or
  • Turn the TV on


So what makes the TV decide what to do? It depends on the state of the TV. If you hit the remote "power" button:


  • Turn the TV off if it is currently on
  • Turn the TV on if it is currently off


Expressing this in code, like you might write in C:


if (powerButtonPressed)
  {
  if (tvState == stateOn)
    turnTvOff ();
  else if (tvState == stateOff)
    turnTvOn ();
  }


Example 2 - a Caps Lock button




We are all also familiar with these. If pressed, the keyboard is put into "caps lock" state, otherwise it is in "lower-case" state.

We might write some C code to handle that situation:


int getKeyPress ()
  {

  // see if any input
  if (Serial.available () == 0)
    return -1;

  // get the input
  char c = Serial.read ();

  // convert to upper case or lower case
  if (capsLockDown)
    return toupper (c);
  else
    return tolower (c);
  }  // end of getKeyPress


Again, the important point is we do something different depending on the "state" of the Caps Lock key.

Example 3 - setting a clock




This alarm clock has buttons that either set the date or the time depending on what state the switch on the side (circled) is. If it is in "time set" mode then pressing the top button changes the hour, otherwise it changes the month.

Example 4 - blinking an LED


Let's look at some code to blink an LED (as suggested by westfw from the Arduino forum).


const byte LED = 13;

enum { LEDON, LEDOFF } ledstate = LEDOFF;

void setup ()
  {
  pinMode (led, OUTPUT);
  }
  
void loop() 
  {
  delay(1000);
  switch (ledstate) 
    {
    case LEDON:
      digitalWrite(LED, LOW);  // if the LED was on, turn it off.
      ledstate = LEDOFF;  // new state
      break;
      
    case LEDOFF:
      digitalWrite(LED, HIGH);  //if it was off, turn it on.
      ledstate = LEDON;  // new state
      break;
    }  // end of switch
} // end of loop


That shows a concrete example of maintaining a "state" variable, namely the current state of the LED.

State diagram for the above code



The general technique


When using a state machine you basically do this:


  • When an event happens (eg. serial input, switch press) then
  • Check what the current state is.

    • If the current state is A, then do X, and maybe change to state B.
    • If the current state is B, then do Y, and maybe change to state C.
    • And so on ...




More elaborate example


The code below demonstrates how you might use a state machine to process input from the serial port. In this case we are expecting input in the form of a letter "R" (for rotation) or "S" (for speed) followed by a number which might be negative. For example:


R12345
S63
R-22 S47
S-800 R-22


We have a few states in this code to handle the various stages we are at in processing a line:


  • No state (eg. just started, or finished a previous number)
  • Got the letter "R"
  • Got the letter "S"
  • After we get "R" or "S" we might get a positive or negative sign (+ or -).
  • After the optional positive or negative sign we expect to get some digits.


The number is expected to be ended (terminated) by either a space, carriage-return, linefeed, or another "command letter" (another R or S).

We can formalize these states in our code like this:


// the possible states of the state-machine
typedef enum { STATE_NONE, 
               STATE_R, 
               STATE_S, 
               STATE_POSITIVE, 
               STATE_NEGATIVE } states;


Our state machine expects to go from STATE_NONE to either STATE_R or STATE_S, and then after that to either STATE_POSITIVE or STATE_NEGATIVE.

Jumping states is not permitted so you can't go from STATE_NONE to STATE_POSITIVE, for example, because we wouldn't know what the command letter is (R or S).

State diagram



This diagram indicates what happens for every possible input and every possible state. Many inputs change from one state to another, and also take some sort of action.

Complete code


// Example of state machine
// Author: Nick Gammon
// Date: 5 December 2013

// the possible states of the state-machine
typedef enum { STATE_NONE, 
               STATE_R, 
               STATE_S, 
               STATE_POSITIVE, 
               STATE_NEGATIVE } states;

// current state-machine state
states state = STATE_NONE;

void setup ()
  { 
  Serial.begin (115200);
  Serial.println (F("Starting ..."));
  } // end of setup
  
void doRotate (const long angle)
  {
  // rotate to desired angle 
  Serial.print (F("Rotating to "));
  Serial.println (angle); 
  }  // end of doRotate
  
void doSpeed (const long speed)
  {
  // set to desired speed  
  Serial.print (F("Setting speed to "));
  Serial.println (speed); 
  }  // end of doSpeed
  
void processNumber (char command, long n)
  {
  switch (command)
    {
    case 'R' : doRotate (n); 
                   break;
      
    case 'S' : doSpeed (n); 
                   break;
    }  // end of switch
  }  // end of processNumber
  
void unexpectedInput (char c)
  {
  Serial.print (F("Unexpected input: '"));
  Serial.print (char (c));
  Serial.println (F("'"));
  }  // end of unexpectedInput

// current number    
long receivedNumber = 0;
// what command we received
char commandType;
 
void gotSpace ()
  {
  switch (state)
    {
    case STATE_NONE: 
    case STATE_R:
    case STATE_S:
         break;  // ignore space 
          
    case STATE_POSITIVE:
         processNumber (commandType, receivedNumber);
         state = STATE_NONE;
         break; 

    case STATE_NEGATIVE:
         processNumber (commandType, -receivedNumber);
         state = STATE_NONE;
         break; 
    }  // end of switch on state
  
  }  // end of gotSpace
  
void gotNewline ()
  {
  switch (state)
    {
    case STATE_NONE: 
         break;  // ignore newline/carriage-return

    case STATE_R:
    case STATE_S:
        Serial.print (F("Unexpected line ending."));
        state = STATE_NONE;
        break;
          
    case STATE_POSITIVE:
         processNumber (commandType, receivedNumber);
         state = STATE_NONE;
         break; 

    case STATE_NEGATIVE:
         processNumber (commandType, -receivedNumber);
         state = STATE_NONE;
         break; 
    }  // end of switch on state

  }  // end of gotNewline
  
void gotR (const char c)
  {
  commandType = 'R';
  receivedNumber = 0;
    
  switch (state)
    {
    case STATE_NONE: 
         state = STATE_R;
         break;

    case STATE_R:
    case STATE_S:
         unexpectedInput (c);
         state = STATE_R;
         break; 
          
    case STATE_POSITIVE:
         processNumber (commandType, receivedNumber);
         state = STATE_R;
         break; 

    case STATE_NEGATIVE:
         processNumber (commandType, -receivedNumber);
         state = STATE_R;
         break; 
    }  // end of switch on state
    
  }  // end of gotR
  
void gotS (const char c)
  {
  commandType = 'S';
  receivedNumber = 0;

  switch (state)
    {
    case STATE_NONE: 
         state = STATE_S;
         break;

    case STATE_R:
    case STATE_S:
         unexpectedInput (c);
         state = STATE_S;
         break; 
          
    case STATE_POSITIVE:
         processNumber (commandType, receivedNumber);
         state = STATE_S;
         break; 

    case STATE_NEGATIVE:
         processNumber (commandType, -receivedNumber);
         state = STATE_S;
         break; 
    }  // end of switch on state
    
  }  // end of gotS
  
void gotDigit (const char digit)
  {
  switch (state)
    {
    case STATE_NONE: 
         unexpectedInput (digit);
         break;

    case STATE_R:
    case STATE_S:
         state = STATE_POSITIVE;
         break; 
          
    case STATE_POSITIVE:
    case STATE_NEGATIVE:
         break; 
    }  // end of switch on state
    
  receivedNumber *= 10;
  receivedNumber += digit - '0';
    
  }  // end of gotDigit
  
void gotMinus (const char c)
  {
  switch (state)
    {
    case STATE_NONE: 
    case STATE_POSITIVE:
    case STATE_NEGATIVE:
         unexpectedInput (c);
         state = STATE_NONE;
         break; 

    case STATE_R:
    case STATE_S:
         state = STATE_NEGATIVE;
         break; 
          
    }  // end of switch on state
    
  }  // end of gotMinus
  
void gotPlus (const char c)
  {
  switch (state)
    {
    case STATE_NONE: 
    case STATE_POSITIVE:
    case STATE_NEGATIVE:
         unexpectedInput (c);
         state = STATE_NONE;
         break; 

    case STATE_R:
    case STATE_S:
         state = STATE_POSITIVE;
         break; 
          
    }  // end of switch on state
    
  }  // end of gotPlus
  
void gotOther (const char c)
  {
  switch (state)
    {
    case STATE_NONE: 
    case STATE_R:
    case STATE_S:
    case STATE_POSITIVE:
    case STATE_NEGATIVE:
         unexpectedInput (c);
         state = STATE_NONE;
         break; 
    }  // end of switch on state
    
  }  // end of gotOther
  
void processInput ()
  {
  
  byte c = Serial.read ();

  // process according to what the input was  
  switch (toupper (c))
    {
    case ' ':
      gotSpace ();
      break;
      
    case '\n':
    case '\r':
      gotNewline ();
      break;
      
    case 'R':
      gotR (c);
      break;

    case 'S':
      gotS (c);
      break;
      
    case '0' ... '9': 
      gotDigit (c);
      break;
      
    case '-':
      gotMinus (c);
      break;

    case '+':
      gotPlus (c);
      break;
      
    default:
      unexpectedInput (c);
      break;
    } // end of switch on event (input) type
  }  // end of processInput
  
void loop ()
  {
  
  if (Serial.available ())
    processInput ();
    
  // do other stuff here
  
  } // end of loop


The advantage of this code over trying to store lines in memory (and process them when you get, say, a newline) is that you only ever have to "remember" the last incoming character, which is very memory-efficient.

As each character arrives the processInput function is called, and the switch statement then checks for various allowed characters.

Each input calls a function (a single one for the digits 0 to 9) and that function then decides what to do based on the current state, as in the state diagram above.

Depending on the current state, it might change to a new state, accumulate the number (in receivedNumber) by multiplying the current value by 10 and then adding in the new digit, or raising an error message.

If we happen to raise an error message we put the state back to STATE_NONE, as at this point we aren't too sure what is happening.

You can see that the code closely follows the state diagram, so if the diagram is correct, then the code should be correct.

Example operation:


Input:  r42 s-65

Rotating to 42
Setting speed to -65

Input: hello

Unexpected input: 'h'
Unexpected input: 'e'
Unexpected input: 'l'
Unexpected input: 'l'
Unexpected input: 'o'

Input: r--42

Unexpected input: '-'
Unexpected input: '4'
Unexpected input: '2'

Input: s 12345678

Setting speed to 12345678


Other techniques


If the example above is too complex, remember you can write your own to do what you want. Your basic requirement is to have some sort of "state" variable, to remember your current state, and go from one state to another state as required.

Other examples might be:


  • If access card is validated, unlock door if it is a week-day. (The state is the day of the week)
  • If too many incorrect passwords entered, lock out the user. (The state is the number of incorrect passwords entered).
  • If the user pushes a button once, turn on a motor. If s/he presses it again, turn off the motor. (The state is whether or not the motor is on).


More reading


More state machine examples on my page about serial input:

http://www.gammon.com.au/serial

Also on Wikipedia: Finite-state machine

- Nick Gammon

www.gammon.com.au, www.mushclient.com
Top

The dates and times for posts above are shown in Universal Co-ordinated Time (UTC).

To show them in your local time you can join the forum, and then set the 'time correction' field in your profile to the number of hours difference between your location and UTC time.


37,029 views.

Postings by administrators only.

Refresh page

Go to topic:           Search the forum


[Go to top] top

Information and images on this site are licensed under the Creative Commons Attribution 3.0 Australia License unless stated otherwise.