State Machine in MCU

[BuffaloEngineer]

What's the best way to implement a finite state machine in a microcontroller? I have been using a switch statement to transfer between modes. That is, the switch statement is the bulk of main(), but it only executes code for the current state, and each case corresponds to a state.

Is it better (or more accepted) to put each state in a function? Or use another method altogether? Thanks!

 

[MikeMl]

I just use linear code. Each block of code has the same labelled entry-point as the corresponding State bubble in the State Transistion Diagram. The State Transitions are all coded as "IF(Condition) THEN GOTO another-state" or its equivalent. If none of the exits from the current State are taken, the last statement is an unconditional GOTO to the entry point in the present state. If there is code that is executed only once upon entering a given state, then you might need two labels, as in STATEnew and STATEloop.

 

[cr0sh]

Any one of these methods mentioned would work (though I shudder at Mike's solution); for readability and future ease-of-maintenance, having the state machine set up as a switch-case works best, but put the functionality for each state into separate functions (unless the code for each is small - say less than 10 lines). Finally - use plenty of comments, as always...

 

[MikeMl]

...(though I shudder at Mike's solution); for readability and future ease-of-maintenance, having the state machine set up as a switch-case works best,

Spoken like a programmer, instead of a hardware designer. Why, and how is a SWITCH-CASE any different or any more readable than an IF-THEN construct?

..but put the functionality for each state into separate functions (unless the code for each is small - say less than 10 lines). Finally - use plenty of comments, as always...

Since all the State Variables, Inputs and Outputs are global to ALL states, why bother with Functions?
My code is written so that it mimics the State Transition Diagram, which I always draw first before starting to code. I use '***********' to enclose the States, so it is easy to go from code to diagram and vice versa...

 

[3v0]

MikeMl

It is easier to ensure the integrity of the state machine with the case-switch. With it you can not shift things about and incorrectly move one case inside another or some conditional logic up to the state level. It constrains the logic in a reasonable way.

When a compiler encounters a function that is only called once it should inline that function, there is no downside to moving the details of each state to a function. It makes the code easier to read and maintain.

 

[cr0sh]

Spoken like a programmer, instead of a hardware designer. Why, and how is a SWITCH-CASE any different or any more readable than an IF-THEN construct?

With the switch-case construct, you can allow for fall-thru logic, which as far as I know (but always willing to learn something new) is not possible in an if-then-else construct without the use of the goto statement. If goto was bad enough for K&R dissuade programmers from using it, I'll heed their advice. Using goto for this purpose should be avoided in favor of switch-case (that isn't to say there isn't call to use goto in C, you just need to be aware when).

Logically (aside from fall-thru), they are identical. If you know for a fact that you'll never need (now or in the future) fall-thru logic, then usage of if-then-else is perfectly reasonable. I like to keep my options always open, though, so I tend to go for the construct that is more easily expanded upon, switch-case.

Since all the State Variables, Inputs and Outputs are global to ALL states, why bother with Functions?

Mainly to keep things readable; furthermore, none of the variables need to be global - in fact, you want to localize what you can, and globalize only what is needed. This is so you could do things like nested state machines (perhaps as part of one state, you transfer operation to another state machine). Keeping all of this in functions (or as method calls within object instances, if you are going with OOP) allows easier maintenance, as well as keeping readability high of the process being performed (self-documenting code - to an extent, but properly formed comments are still important).

Its all about making code reuse as simple and natural as possible, so you don't need to re-invent the wheel for each project, as well as be able to come back to a project five years down the line and understand it easily as if it were yesterday when you last touched it.

My code is written so that it mimics the State Transition Diagram, which I always draw first before starting to code. I use '***********' to enclose the States, so it is easy to go from code to diagram and vice versa...

Well, like I said, if you don't need the fall-thru logic, and your commenting things in sections, it probably sounds ok; maybe I was a bit harsh - can you show an example of the style (nothing real, just an example)? As I said, I'm always willing to learn something new.

And you are right about me being a software developer; going on 20 years professionally starting next February - almost 30 if you count all the time prior to that as a kid in school...

I do hardware stuff in my free time; currently building a UGV (unmanned ground vehicle) in my shop. I don't have the knowledge in this domain as some others do, but I keep from burning myself with a soldering iron, mostly. I just try to impart my knowledge of software to those involved in hardware, and I hope to learn something similar from those whose passion (to the point of a career) is hardware. A cross pollination of ideas and best-practices, so to speak. I think it could ultimately make both our jobs easier, in the long run.

 

[BrownOut]

I've written many state machines, and I agree the switch statement is the only way to go. Nobody writes if-then-else structure anymore for parallel decision branches, if it can be avoided. That's why the switch statement was invented.

If-then-else statements priority encode your logic, which can be good for some solutions, but not useful for state machines.

 

[MikeMl]

I have designed hundreds of state machines, some very complex, which were first hand-drawn as a State Transition Dagram on paper, simulated in a computer program, then were converted to gates/flip-flops for implementation in VLSI logic, were then simulated again using a Hardware Logic Simulator, layed out on Silicon, simulated again using Spice and extracted parasitics. I got most of them to work the first time.

I started doing this before programming languages had a CASE statement. Since the collective wisdom of the Software experts on this forum is that a CASE statement is superior to using a IF (condition) THEN GOTO xxxx method, then it is time for you to educate me. Please post an example coded in C which implements this State Transition Diagram that I posted in this thread.

 

[Nigel Goodwin]

IF/THEN/ELSE and SWITCH/CASE are high level constructs for essentially the same thing, and may well produce pretty well identical code and results.

SWITCH/CASE was introduced to give a 'prettier' look in the HLL, so if it's available it makes sense to use it.

BOTH will produce loads of GOTO lines in order to function - particularly on a PIC

 

[BrownOut]

It not only a case of which is prettier. Whenever a programming construct makes the language easier to use, there are lots of good benefits, program maintainability for one. But the two are not equivilent from a programming language standpoint. For example, the following code:

if( A <= B) then
do something;
else if (A>=B) then
do something else;
else if (A=B) then
do something else still
end if;

.. is prefectly fine for this construct, but this logic cannot be coded with the switch/case statement. An attempt to do so, either on purpose or by accident, will probably result in a compiler error. Using the compiler as a means to debug code is one reason we use high level programming.

If you get to any type of hardware programming language, the situation gets even more complicated. The resulting hardware from the if/then/else structure is different than what would come from a case structure, and if implemented by mistake or by lack of knowledge, can wreck havoc on the logic that gets synthesized.

 

[cr0sh]

BOTH will produce loads of GOTO lines in order to function - particularly on a PIC

Well, ultimately, down at the assembly/machine-code level, of course there will be GOTOs galore; the statement itself, if the HLL used supports it, should be avoided if at all possible (which is the majority of the time).

 

[cr0sh]

Please post an example coded in C which implements this State Transition Diagram that I posted in this thread.

I think this code would work (in somewhat C-like syntax) - I haven't fully debugged it:

void main() {
  int state = 0; // wait for button
  int floor = 1; // start on first floor
  int button = 0; // no button pressed

  loop {
    switch (state) {
      case 1: // get direction
        direction = getDirection(button, floor);      
        state = 2;
        break;
      case 2: // move in direction
        motorOn(direction);
        state = 3;
        break;
      case 3: // check limit
        if (atLimit(button)) {
          state = 0;
          floor = button;
        }
        break;
      default:
        button = getButton(); // returns 0, 1, 2, or 3 for whichever button is pressed
        state = (button > 0) ? 1 : 0;
    }
  }
}

int getDirection(int floor_wanted, int floor_on) {
  int direction = 0;

  if (floor_on > floor_wanted) {
    direction = 1; // down
  }
  else if (floor_on < floor_wanted) {
    direction = 2; // up
  }

  return (direction);
}

void motorOn(int direction) {
  switch (direction) {
    case 1:
      // motor on "down"
      break;
    case 2:
      // motor on "up"
      break;
    default:
      // motor off/stop
  }
}

int atLimit(int limit) {
  int currLimit = getLimit(); // returns 0, 1, 2, or 3 for whichever limit switch is tripped
  return ((currLimit == limit) ? 1 : 0);
}

Also - you could possibly replace the setting of "floor" to 1 before the loop with a call to "getLimit()" - so that no matter where the system was at power up (ie, elevator on a different floor at power up), it would move properly (at least, I think this would work???)...

Heh - just noticed my code is broken in that it doesn't test for extreme end-limits; ah, the joys of coding "blind" - oh well, leave it for version 2.0 I guess!

 

[cr0sh]

Version 2.0?

I think this might work to correct some of the bugs:

void main() {
  int state = 0; // wait for button
  int floor = getLimit(); // returns 0, 1, 2, or 3 for whichever limit switch is currently tripped (0 if between floors)
  int button = 0; // no button pressed
  int direction = 0; // motor off

  loop {
    switch (state) {
      case 1: // get direction
        direction = getDirection(button, floor);      
        state = 2;
        break;
      case 2: // move in direction
        motorOn(direction);
        state = 3;
        break;
      case 3: // check limit
        if (atLimit(button)) {
          state = 0;
          floor = button;
        }
        break;
      default:
        motorOn(direction);
        button = getButton(); // returns 0, 1, 2, or 3 for whichever button is pressed
        state = (button > 0) ? 1 : 0;
    }
  }
}

int getDirection(int floor_wanted, int floor_on) {
  int direction = 0;

  if (floor_on > 0) {
    if (floor_on > floor_wanted) {
      direction = 1; // down
    }
    else if (floor_on < floor_wanted) {
      direction = 2; // up
    }
  }
  else {
    direction = 1; // down
  }

  return (direction);
}

void motorOn(int direction) {
  switch (direction) {
    case 1:
      // motor on "down"
      break;
    case 2:
      // motor on "up"
      break;
    default:
      // motor off/stop
  }
}

int atLimit(int limit) {
  int currLimit = getLimit(); // returns 0, 1, 2, or 3 for whichever limit switch is tripped
  return ((currLimit == limit) ? 1 : 0);
}

 

[MikeMl]

cr0sh,

How did you get from seven states to three? You didn't implement the state transition diagram I posted.

If you think your code implements an equivalent state machine to the one I posted, then working backwards from your posted code, it should be possible to draw out a State Transition Table from the code that could be converted to a Present State - Next State Table for implementation into hardware using flip-flops and gates...

 

[Nigel Goodwin]

Well, ultimately, down at the assembly/machine-code level, of course there will be GOTOs galore; the statement itself, if the HLL used supports it, should be avoided if at all possible (which is the majority of the time).

As a Pascal (and later Delphi) programmer I'm obviously VERY anti-Goto - it's seriously frowned upon in Pascal, which is why Pascal used to be the programming language taught in Universities (because it forced good practice).

However, when converting a large VB program to Delphi I came up on a very few Goto's I couldn't get rid of (without even more serious re-writing), so I had to look up GOTO in the help file, as I'd NEVER used it before

 

[cr0sh]

cr0sh,

How did you get from seven states to three? You didn't implement the state transition diagram I posted.

You know - you're right; I didn't implement that same state machine - my bad; the code I originally posted implemented a completely different machine whereby the states were effectively:

1) Waiting for button
2) Get direction (quick transitory state, and could be combined with next one)
3) Move in direction
4) Check limits

Looking at your diagram, I realize now that the states are completely different (your's are states of travel directions and stops); I swear I was looking at it before, but I guess my nature got in my way. I decided to try again; I think the following code implements your diagram properly...?

void main() {
  int state = 7; // send car to first floor on start

  while (1) {
    switch (state) {
      case 1: // FIRST
        state = getFloor(1);
        break;
      case 2: // UP2
        goUp(2);
        state = 3;
        break;
      case 3: // SECOND
        state = getFloor(2);
        break;
      case 4: // UP3
        goUp(3);
        state = 5;
        break;
      case 5: // THIRD
        state = getFloor(3);
        break;
      case 6: // DN2
        goDown(2);
        state = 3;
        break;
      case 7: // DN1
        goDown(1);
        state = 1;
        break;
      default: // UNKNOWN
        state = 7; // send car to first floor - invalid state
    }
  }
}

int getFloor(current_floor) {
  while (1) {
    int button = getButton(); // returns 0, 1, 2 or 3 for button selected

    switch (button) {
      case 1:
        if (current_floor == 2 || current_floor == 3) {
          return (7);
        }
        break;
      case 2:
        if (current_floor == 1) {
          return (2);
        }
        else if (current_floor == 3) {
          return (4);
        }
        break;
      case 3:
        if (current_floor == 1 || current_floor == 2) return (4);
        break;
      default:      
    }
  }
}

void goUp(floor) {
  while (getLimit() != floor) {
    motorUp();
  }

  motorOff();
}

void goDown(floor) {
  while (getLimit() != floor) {
    motorDown();
  }

  motorOff();
}

int getLimit() {
  return (#); // returns 0, 1, 2 or 3 for current set limit switch for each floor
}

Also - this new code seems simpler, or easier to read, than my first post - not sure...

If you think your code implements an equivalent state machine to the one I posted, then working backwards from your posted code, it should be possible to draw out a State Transition Table from the code that could be converted to a Present State - Next State Table for implementation into hardware using flip-flops and gates...

As already has been noted, my states were completely different; I think I like my new rewrite more than my old code. I do think my original code could be written into a similar diagram as you posted, but it might not look as pretty!

 

[cr0sh]

For example, the following code... is prefectly fine for this construct, but this logic cannot be coded with the switch/case statement.

So something like this wouldn't work?:

switch ((a - b) / abs(a - b)) {
  case -1: // a < b
    break;
  case 0:  // a = b
    break;
  case 1:  // a > b
    break;
  default:  // error?
}

Actually - your code wouldn't really work either, as the A=B clause could never be hit (it would hit the A<=B clause). My code above is making the assumption that the checks are for "A < B", "A > B", and "A == B"...

Note, BTW, that I am not saying the above is what should be used; it actually makes things more obscure (and probably slower) because of the calculation in the switch() clause...

 

[BrownOut]

Actually - your code wouldn't really work either, as the A=B clause could never be hit (it would hit the A<=B clause).

Right you are, though one might only get a warning about code not reached rather than an error. OK, let's try something more logical:

If(A<=B) then
  do something;
else if (A>=B) then
  do something else;
else if(A==0) then
  do something else still;
end if;

The obvious problem with using case would be there are more than one possible branch that can be taken. That is handled by the priority encoding that comes along with if/then/else structure.

 

[MikeMl]

Here is what my way looks like: What could be simpler or more readable?

 

[BrownOut]

I would do one thing to Crsh0's code and that would be to make the "states" an enumerated type. That way the state machine could be coded with descriptive state names. Thus, readibility could be maintained while using structured methods.