Topics Topics Edit Profile Profile Help/Instructions Help Member List Member List  
Search Last 1|3|7 Days Search Search Tree View Tree View  

How do you implement a state machine ...

:: EPE Chat Zone ­:: ­Radio Bygones Message Board :: » EPE Chat Zone » Archive through 29 March, 2016 » How do you implement a state machine in a micro? « Previous Next »

  Thread Last Poster Posts Pages Last Post
  ClosedClosed: New threads not accepted on this page        

Author Message
Top of pagePrevious messageNext messageBottom of page Link to this message

atferrari
Frequent Contributor
Username: atferrari

Post Number: 1759
Registered: 05-2005


Rating: N/A
Votes: 0 (Vote!)

Posted on Sunday, 21 February, 2016 - 03:10 pm:   Edit Post Delete Post Print Post    Move Post (Moderator/Admin Only)

I am not C conversant; I do all in Assembly for 18F micros.

I've been thinking of implementing a basic elevator controlled by a micro.

After reading several articles and references, I see that a state machine is frequently (if not always) mentioned what I understand is the way to consider the problem.

I then browsed two pieces of software implementing the basics (I regret losing track of them) and depending if written in (maybe) C or Assembly, what they did was implementing long blocks of "switch case" chains or something similar to this in Assembly:


SKIP_IF_DIFFERENT,B'01111000'
BRA COMB_CASE_C7_R3

SKIP_IF_DIFFERENT,B'01110010'
BRA COMB_CASE_C7_R1

SKIP_IF_DIFFERENT,B'10111000'
BRA COMB_CASE_C6_R3

SKIP_IF_DIFFERENT,B'10110010'
BRA COMB_CASE_C6_R1

and so on ------------------------------------------------


Found this quite a crude way to implement it but I cannot see other way of doing it.

My question: is this the actual way you implement a state machine with a micro?
Agustín Tomás - Buenos Aires - Argentina
Top of pagePrevious messageNext messageBottom of page Link to this message

zeitghost
Frequent Contributor
Username: zeitghost

Post Number: 2000
Registered: 01-2006

Rating: N/A
Votes: 0 (Vote!)

Posted on Monday, 22 February, 2016 - 09:27 am:   Edit Post Delete Post Print Post    Move Post (Moderator/Admin Only)

It works.
Top of pagePrevious messageNext messageBottom of page Link to this message

jgurley
Regular Contributor
Username: jgurley

Post Number: 24
Registered: 12-2011

Rating: N/A
Votes: 0 (Vote!)

Posted on Monday, 22 February, 2016 - 01:54 pm:   Edit Post Delete Post Print Post    Move Post (Moderator/Admin Only)

It's pretty much the same thing, but I simply have a label for each state, and the code at that label just tests the various reasons you want to leave the state and branch to the new state (the arrows on your state diagram). In assembler, you can always economize code by inverting branch sense, etc.

S0: TSTSZ reason_to proceed to state 1
BRA S1
TSTSNZ reason to go to state 2
BRA S0
s2: TSTsz reason to proceed to state 3
BRA S3
TSTSNZ reason to processd to state 0
BRA S2
BRA S0
S1: ...
Top of pagePrevious messageNext messageBottom of page Link to this message

hackinblack
Frequent Contributor
Username: hackinblack

Post Number: 678
Registered: 09-2006

Rating: N/A
Votes: 0 (Vote!)

Posted on Monday, 22 February, 2016 - 11:42 pm:   Edit Post Delete Post Print Post    Move Post (Moderator/Admin Only)

this is the simplest C example i can find

basic (sequential) state machine
runs from state 1,then increments through the rest in sequence:-

for(;;)
{
state = 1;
switch (state)
{
CASE 1:
implement TASK 1
state++;
break;
CASE 2:
implement TASK 2
state++;
break;
CASE 3:
implement TASK 3
state = 1;
break;
}
Delay_ms(n);
}

state machine directly-oprated, or condition-based
implements tasks without going through all of them in sequence;but can't prioritise:-

for(;;)
{
state = 1;
switch (state)
{
CASE 1:
implement TASK 1
state = 2;
break;
CASE 2:
implement TASK 2
state = 3;
break;
CASE 3:
implement TASK 3
state = 1;
break;
}
Delay_ms(n);
}

presumably the second one will run faster on the actual hardware as it 'skips' states;making it seem a little 'smarter'
Top of pagePrevious messageNext messageBottom of page Link to this message

dreamrm
Member
Username: dreamrm

Post Number: 7
Registered: 03-2014

Rating: N/A
Votes: 0 (Vote!)

Posted on Tuesday, 23 February, 2016 - 08:56 pm:   Edit Post Delete Post Print Post    Move Post (Moderator/Admin Only)

Both of these examples have a bug in them - they will always be in state 1.
You just need to move the state = 1; statement outside the for loop.
Top of pagePrevious messageNext messageBottom of page Link to this message

bowden_p
Frequent Contributor
Username: bowden_p

Post Number: 485
Registered: 01-2006

Rating: N/A
Votes: 0 (Vote!)

Posted on Wednesday, 24 February, 2016 - 05:24 pm:   Edit Post Delete Post Print Post    Move Post (Moderator/Admin Only)

Hi Agustin,
I don't know much about state machine theory, but if you can group tasks with related sub-tasks, the testing for a particular state becomes simpler.

i.e If a single byte is used to define all states, use the upper nibble of the state byte to define the main tasks, so allowing 16 possible main tasks. The lower nibble is then defined for each task, allowed 16 sub-tasks for each main task.

To determine the main task, mask out the sub-task nibble and go through the task comparison list for the upper nibble. Each task will need its own sub-task comparison list to determine the required sub-task.
Thus a fully populated state byte would need a max of 16 + 16 comparisons to get to the state code required.

Another method might be using a computed goto. If you can set up the task/sub-task list correctly, a computed goto will get to your state destination code directly in a single jump.

With regards, Paul.
Top of pagePrevious messageNext messageBottom of page Link to this message

dreamrm
Member
Username: dreamrm

Post Number: 8
Registered: 03-2014

Rating: N/A
Votes: 0 (Vote!)

Posted on Wednesday, 24 February, 2016 - 09:44 pm:   Edit Post Delete Post Print Post    Move Post (Moderator/Admin Only)

It wasn't clear from your original question whether you intend to code this in C or assembler.

However, on the assumption you want some ideas in C then a possible alternative to the switch construct mentioned above is to use an array of function pointers as in the example code below:

// Function prototypes
int fn01( void );
...etc

// typdef a function pointer
typedef int(*fnPtr)(void);

// N.B. the function pointer and the functions must match, i.e. same arguments
// and same return type.

// This array, together with the for loop below, constitutes the state machine.
// Declare and initialise an array of function pointers.
fnPtr arrFnPtr[5] = { fn01, fn02, fn03, fn04, fn05 };

int main(int argc, const char * argv[])
{
// Loop through the array calling the appropriate function each time
for( int nState = 0; nState < 5; ++nState )
{
(*arrFnPtr[ nState ])();
}

return 0;
}


// The functions called for each state transition
int fn01( void )
{
printf( "fn01 called\n" );
return 1;
}

...etc

This may not be as easy to read as the switch construct but would probably be easier if you need a large number of states.

You could extend this idea further by defining a struct as follows:

struct statemachine
{
int nCurrentState;
int nCondition1; // A value to be matched to an an external value
int nCondition2; // Ditto
fnPtr fnTask; // See definition of fnPtr above
};

and then an array of structs:

struct statemachine arrSM[5] =
{
{ 1, 12, 23, fn01 },
{ 2, 2, 23, fn02 },
{ 3, 0, 1, fn03 },
{ 4, 12, 23, fn04 },
{ 5, 0, 3, fn05 }
};

Now when you loop through ths array you would call the appropriate fnTask when the relevant conditions are met, i.e. nCurrentState matches current state and the condition values match. Invoke the task as follows:

arrSM[ i ].fnTask();

Hope this makes sense.
Top of pagePrevious messageNext messageBottom of page Link to this message

atferrari
Frequent Contributor
Username: atferrari

Post Number: 1761
Registered: 05-2005


Rating: N/A
Votes: 0 (Vote!)

Posted on Thursday, 25 February, 2016 - 11:21 am:   Edit Post Delete Post Print Post    Move Post (Moderator/Admin Only)

Hola dream:

At the very first line I said: I am not C conversant; I do all in Assembly for 18F micros.

Thanks for replying anyway.

Hola Paul,

I started to understand that I should break the whole FSM in smaller linked ones.

While this is now a mental exercise to relax from my current project, sooner or later it will become a project of sorts.

Gracias.
Agustín Tomás - Buenos Aires - Argentina
Top of pagePrevious messageNext messageBottom of page Link to this message

james
Frequent Contributor
Username: james

Post Number: 622
Registered: 02-2007

Rating: N/A
Votes: 0 (Vote!)

Posted on Saturday, 27 February, 2016 - 03:24 pm:   Edit Post Delete Post Print Post    Move Post (Moderator/Admin Only)

Hi Agustin,

My attempt at a simple state machine to turn 4 LEDs on in sequence and then back to a waiting state with all LEDs off.
It's a bit overkill for this simple application but the principle may be OK for a more complicated application.

Simple State Machine


text/plainState Machine Code
STATE.txt (2.7 k)


Cheers

James
Top of pagePrevious messageNext messageBottom of page Link to this message

atferrari
Frequent Contributor
Username: atferrari

Post Number: 1763
Registered: 05-2005


Rating: N/A
Votes: 0 (Vote!)

Posted on Thursday, 03 March, 2016 - 11:03 am:   Edit Post Delete Post Print Post    Move Post (Moderator/Admin Only)

Hola James

Sorry for not replying earlier. Preparing to move to a new house. Definitely not the best thing to do.

After getting suggestions I started to make my mind about the possibilities of something like you suggest.

I recall implementing something somewhat similar, (also with LEDs to see it working).

I understand that creating the different FSMs is the most important (and first) step. I need to think more on that part.

Gracias.
Agustín Tomás - Buenos Aires - Argentina

Administration Administration Log Out Log Out   Previous Page Previous Page Next Page Next Page