A Simple State Machine

[croberts]

State machines are a great way to quickly organize your thoughts for almost any programming task from simple to complex. They can be inserted anywhere in the structure of a program such as the main loop or the interrupt handler. Multiple state machines can be in the same program and they can even be nested. Here we will use the simple state machine structure I use in almost all my assembly language programming to do a very simple task. We will change the state of two LEDs every second. Yes, there are many simpler ways to accomplish this task other than using a state machine but we will use it to introduce you to the concept. You should be able to quickly adapt the same mechanism to your own programming task by adding more states and redefining the function of each state. Notice in particular when waiting for an event such as a timer timing out that you just pass through the state and onto other code with almost no delay and you just keep looping through the same state until the event occurs and you change the state.

The state machine I use is made up of a steering code block and a code block for each state. The state machine uses two microcontroller ram memory resources. The first is a byte for the state variable and the second is a bit for the initialization flag.

The steering code block ‘steers’ program execution to the current state by reading the value in the state variable and jumping to the correct state code block. The steering code usually has provision to set the state variable to some initial state if the value is out of bounds.

To look at state code blocks let’s do a simple state machine that toggles the state of two LEDs every second. We will use a software timer that is decremented in an interrupt routine every 100mS until it reaches zero. We will initialize the state variable (State) to 1, LED1 = On, LED2 = Off, and the initialization flag (SM_Init) to 1 on microcontroller start.

Attached are the following;
State machine flowchart (pdf)
Steering code block flowchart (pdf)
State 1 code block flowchart (pdf)
State 2 code block flowchart (pdf)
State 3 code block flowchart (pdf)
State 4 code block flowchart (pdf)
Assembly language source code (asm)*
Test circuit schematic (pdf)**

* Composed in MPLAB. Columns may not appear as intended if viewed with other text editors.
** Uses PIC16F690. Code and circuit can be easily adapted for other PICs.

Give it a try and then try to modify the state machine by adding more states (remember to change the steering code block to include the new states) and changing the functions of the states. After you play with them for a while you should begin to see how state machines can help you quickly organize and execute almost any programming task.

[Mechatrommer]

and it can also be applied to C/C++ assembly is harder to read.

[mark-r]

State machines are brilliant for initialising hardware that needs a complicated startup process (you know the sort of thing - set pin 1 high for 10ms then set pin 2 high for 1ms then wait for pin 3 to go high then set pin 1 low then wait 1ms then pin 2 low...) If your steering loop runs on a fixed tick then wait states simply increment a counter and flip to the next state when the correct count is reached. Non fatal missing hardware is easily skipped by conditionally entering different states, and of course you can have a "failed" state that can be entered from anywhere if anything goes wrong in the process.

[westfw]

Ah; I wrote a brilliant state-machine feature once, as a sysadmin-level feature for an async device server.
You know how such servers buffer data, and sometimes it is desirable to determine when to actually SEND the buffer?  Well, our customers didn't like the simplicity of a timeout and "dispatch-character", and we didn't want to keep special-casing one situation after another.
So we implemented a user-definable state machine.  Stimuli included each possible input character, plus a timeout, actions were buffer or transmit, with optional time setting, and go to new state.
It could handle things like "the end of a packet is 03, followed by two CRC bytes."
It could handle ansi function keys (esc [ mumble UPPERCASEALPHABETIC.)
It was wonderful.

I don't think I ever saw a case where a customer was able to configure this feature on their own :-(  Sigh.  It takes practice to THINK of things like this, at least in a way that is formal enough to implement.

[Kremmen]

If you create a lot of state machines, and especially if they are at all complex then one way to visualize the functionality is to create a SDL diagram out of it.
I recently made a simple gadget which needed some adjustable configuration parameters. These were edited using a few simple buttons. The state machine to handle the editing looks in SDL like the attached picture (in SDL behavioral presentation).
At first sight it looks just like a normal flowchart, and it almost is one. There are a couple of differences in the emphasis that make an SDL diagram very useful presentation for state madhines:
- The rounded rectangles are _states_ where the machine sits, until triggered by one of the _signals_ relevant to that particular state. The stipulation is that all other signals are ignored.
- All triggers initiate a sequence of actions that terminate in a state - either the same one or some other state. The machine stays in this new state until triggered by an event.
- SDL has specific notation for a number of things, such as external and internal events, and one especially useful one, the concept of "any state" or *. You can see it in the attached diagram, in this case handling the input timeout. The meaning of the presentation is that in any state the internal timeout signal triggers a transition to the idle state. How the timeout is implemented in the code is not the concern of this presentation. In an embedded system a simple counter attached to a hardware timer interrupt is the normal way to do these.

So you can follow what is happening, the state machine in this case works like this:
- Program start clears the state machine variables and puts the machine in idle state
- Menu key advances the system to item selection state. Any other key just returns the system to IDLE, i.e. they are ígnored. This is usually not shown explicitly, but i did it here once for clarity.
- Up and Down keys in item selection state increment/decrement the selected config item. Details like range limits are not usually shown explicitly, the sidebars in the action box mean that it is a formal procedure that can take care of itself. The state returns to item selection. Once "OK" is hit the state advances to editing or, if "Menu" is hit, the operation is canceled and state returns to idle.
- While editing the numeric value of the item can be incremented or decremented. To facilitate handling of large config values, the decade to edit can be selected to speed up things. "OK" stores the currently displayed value, and "Menu" again cancels everything.

In the top right corner are 2 special items.
-From any state the key timeout returns the state to idle. If the user just walks away, the editing is canceled after a time with this method.
-Any input will reset the key timeout timer to the starting value, again giving the user the set time to hit next button. This sequence does not have any impact to the state of the machine.

So, SDL is a bit different from just a regular flowchart. For a more formal presentation, see e.g. http://www.sdl-forum.org/sdl2000present/sld001.htm

[jeroen74]

Hierarchical state machines (or UML state machines) are interesting too and can prevent state explosion and loads of mostly identical states. Common functionality in states are handled by a superstate. Basically you code by difference.

While state machines are powerful, it's also easy to create an incredible mess undoing the advantages they have over complicated multilevels flag checking constructs.

[croberts]

Thanks everyone for the great comments about state machines. There are so many interesting and useful ways of using and implementing this great construct. I use state machines in almost every assembly language program I do. I am currently using a PIC16F690 to control the solar powered LED lighting I designed for my home. I have posted on that system previously. Of course state machines work very well for all programming languages but I have been programming PICs for some time and still prefer the low overhead and hands on feel of assembly language.

I have another post on this topic in the works that will add one additional feature to the simple state machine.

For the next couple of weeks I will be a little slow responding to replies. A storm took down a tower providing our internet service Monday night (1/28) and I have to drive to a wifi snack bar once a day to use the internet.

[croberts]

I would like to ask you to tolerate my very simple LED state machine example one more time so I can introduce one more mechanism to the simple state machine, next_State. Time delays are not always given a separate state as they are here but it does offer a good way to show how next_State works.

In the first version of the Simple State Machine we had four states. The two states that did the one second delay were identical. It would be nice to just type in the one second delay state once and then use it as required. We can do just that by using one more microcontroller ram resource, the byte variable next_State. Now in the one second delay state we just set State equal to next_State when the timer reaches zero. Now state 1 that sets the two LEDs to the desired on/off pattern sets State equal to 3 to go to the time delay state and next_State to 2 so when the time delay is done execution will be steered to state 2. Next state 2 that sets the two LEDs to the toggled on/off pattern sets State equal to 3 to go to the time delay state and next_State to 1 so when the time delay is done execution will be steered to state 1....and so on.

Attached are the following;
State machine flowchart 2 (pdf)
Steering code block flowchart 2 (pdf)
State 1 code block flowchart 2 (pdf)
State 2 code block flowchart 2 (pdf)
State 3 code block flowchart 2 (pdf)
Assembly language source code 2 (asm)
Test circuit schematic (same as first post) (pdf)

[Harvs]

I use state machines all the time to do co-operative multi-tasking on small microcontrollers.  It's simple to code and a very efficient use of system resources as long as the tasks can be effectively broken down into states (as most hardware interface tasks can.)


I read a book about it a few years ago, don't remember the name anymore.  But it was one of those "ah ha" moments for me.  Ever since simple multi-tasking has been a breeze.  I rarely write a uC program now without at least one state machine running off a periodic interrupt to handle background IO.

[croberts]

Hello Harvs

I agree you can't beat the simple coding and the way a programming task can be quickly organized and executed using this fairly simple construct. State machines are not for every task in a program but I rarely ever complete a job without one or more state machines being used.

[croberts]

Ok. One last example with the simple state machine. We will combine the time delay and LED pattern change into a single state and flash the LEDs with two states. I hope those of you who haven't tried state machines will give the simple state machine a try. You will be surprised how easily you can organize and code some fairly complex tasks.

Attached are the following;
State machine flowchart 3 (pdf)
Steering code block flowchart 3 (pdf)
State 1 code block flowchart 3 (pdf)
State 2 code block flowchart 3 (pdf)
Assembly language source code 2 (asm)
Test circuit schematic (same as first post) (pdf)

[andyturk]

I read a book about it a few years ago, don't remember the name anymore.  But it was one of those "ah ha" moments for me.  Ever since simple multi-tasking has been a breeze.  I rarely write a uC program now without at least one state machine running off a periodic interrupt to handle background IO.

This one?

Practical UML Statecharts in C/C++: Event-Driven Programming for Embedded Systems?

[Harvs]

No it wasn't that book I was referring to, but I do remember reading most of that one at the time.


What frustrated me a bit, was the book quickly turned into a guide on how to use the author's event driven framework, and less about the what the title would suggest it's about.

[jeroen74]

I guess you refer to the framework designed by Miro Samek? His site is here. He's the author of the aforementioned book.

[Harvs]

Yeah that's the one.  I'm not saying it's not a good book or the framework's not good (I haven't had an application to use it), just that the book is for that framework. 


Where as for small applications you can very effectively roll your own system.

[jeroen74]

I studied that framework too about a year ago. For simpler systems you can indeed roll your own, especially if you don't need all hierarchical possibilities,; I looked at the transition code which is quite big (mainly the part that searches for a common super state IIRC).

[brainwash]

I have a hard time visualizing complex state machines. Especially if in assembler which is foreign language to me.
I don't understand, how are these things back-annotated once implemented? How is the implementation verified to coincide with the intent? How is flow verified against illegal states?

I'm not putting the technique down, I understand how it principles and advantages, I just want to gain a deeper understanding.
The implementations I saw in higher-level languages just defined a class for each state but there was no central controller to centralize all the transitions. Each state effectively had to specify its preconditions and postconditions, so in order to gain a view you had to go through all the code, every line. That's either a bad idea or a bad implementation.
I would love to see some examples in a readable language that I could either understand just by glancing at the code or by someone opening my eyes.

[croberts]

Hello Brainwash

In the context of the state machine I describe in the original post I feel they offer an excellent way to organize code. In a particular state, you can monitor a timer, switch or sensor status,etc without having to stay in that block of code. You leave the state and go on to deal with other tasks in the main program loop including other state machines knowing you will quickly return to the same state through each main loop until a particular terminal condition occurs and then change states. I have provision for initializing each state only when first entered. I usually describe the function of the state machine and individual states as I go but revisiting code within a state is something I have to do from time to time when I've been away from the program for a while. Most of the code I write these days is to add new features to the LED lighting system in my home so I suppose the other concerns you mentioned may not apply in my case. I appreciate the comments in any case and thanks for the reply.

[Smokey]

One of the best classes I had in college was a processor architecture class where we had to write a complete general purpose processor in VHDL then write a program for that processor and make it execute code on an FPGA.  Man, did I learn a lot about how computers actually worked from writing that VHDL.  If you didn't know how to make a good state machine and data-path, you were hosed. 

It was later one of those AH-HA! moments when I got a job and had to write an FPGA routine that needed a complex state machine in VHDL, and I could say to my boss "Hey I know how to do that.  I'm cool!"  I just said the "I'm cool" part to myself though.