Hello Does anyone know of a nice text on finite state machines and their software implementation on embedded systems?
I'm looking for some theoretical background and design methodology. A few examples of "C" implementation would be a nice but not really needed. I'm not looking for a recipe or code but for a more formal explanation on the workings of FSM. Thanks jmariano
FSM are pretty simple. They usually use a directed graph (drawing with circles for states and arrows for transitions between states) to represent the design. It's always a good idea to start with that. Give the sames names, or values and put the inputs on the transitions. When a state is not changing, this should be represented with an arrow from the state back to itself. But it's not important to show these for the code. It does make it clear what's happening. Some states are transitory and do not remain in the same state. This helps you spot when you've missed an input condition.
The inputs to the FSM are the "inputs" (duh) but also the "current state". The FSM calculates "next states" and "outputs". That's a FSM in its simplest form.
The next state always depends on the current state and the inputs. The output can depend on the present state only, or can also change depending on inputs. In that case, I think of the outputs as being part of the "state" of the FSM, but the next state won't depend on outputs. This can be a bit complex, so it may be simpler to start with a FSM where the outputs only depend on the current state.
The code is typically written as a CASE statement on the present state. Within each present state of the CASE, code is written to examine the relevant inputs and decide the next state or possibly also outputs if you are doing that. Your outputs don't have to be calculated in the CASE statement. They can be calculated only on the present state.
That's it in a nutshell. I'm used to hardware, coding in VHDL, but it's the same thing in C or whatever. You just have to watch where you put what code since the order matters in C. In VHDL sections of code all run in parallel, since it's hardware.
Sorry I don't have a reference. I spent a lot of time reading about FSM coding. But most of it was a bit pedantic. For example, the theoretical analysis that was done nearly 100 years ago, resulted in the Mealy vs. Moore classification, depending on if the outputs depend on the inputs or just the present state. I never remember which is which because very few people use either. Instead they use a hybrid where the outputs are calculated in the same case statement, which means they are a cycle late if done with the classical approach.
Whatever. Just pay attention to the timing of your output changes, and if you want to have the next state depend on an output, move that output into part of the state, since that is what it is.
Search for Quantum Leaps. Miro Samek has written a very good book about state-machines for embedded systems with an implementation. However it isn't free of use, I think. But the book should be now free to download.
Hierarchical state-machines are a very interesting argument for a system that can be modeled as an event-driven system. An embedded systems can be usually described as an event-driver system.
There will be a time when the programmer would simply draw one or more state-machines and click a button to generate the full working code in whatever language.
The problem these have, like many graphic oriented approaches, is continuing support and version control of the source. I've never worked with a state machine that was so complex it required anything other than a diagram drawn up in your favorite word processor drawing package. Typically, FSM can be decomposed into multiple distinct FSM that are easier to understand, and typically relate to the problem better.
A FSM with 10 states is easy to code. A FSM with 100 states is probably several FSMs, mistakenly combined into one.
This question is precisely what I've been exploring, working on, and writing about for decades.
Unfortunately, like most terms in our discipline of embedded programming, the term FSM means different things to different people. That's why you will get many different answers because some people mean "input-driven" state machines, others mean "event-driven" state machines, and yet others mean everything in between. Of course, all of this means different implementations, from nested-switch, through state tables, OO State design patterns, various state machine "compilers", etc.
I tried to cut through this confusion in my video playlist "State Machines" on YouTube:
I've also collected a lot of resources about state machines, including my books and papers about the subject. To find out more, just google "Miro Samek".
Thank you all very much for your valuable inputs! I have A LOT of reading to do!
I'm not a professional developer, like most of you (I guess). I'm just a "gizmo" builder, serving mainly my own research and my colleagues. I don't have access to professional development tools. My background is in physics, although I took a few electronics courses in college. I took courses on embedded systems, usually called "microprocessor in physics" and the like, but the emphasis of these courses tended to be on the digital part and not so much on the computational aspects of the thing. That is why I usually get lost on the jargon of computer science and know very little of data structures and things like that.....
My first contact with FSM was many years ago when I was finishing my PhD. I had to implement a FSM on a FPGA and, of course, I was late, so I pick an example somewhere and just implemented, without really knowing what I was doing....
Now I would like to finally understand a little better how these things work.
Also, the sort of things that I build, usually have some type of "controller" in it, and usually talk to a PC via serial interface. This, it seems to me, could to be well modeled by a FSM. I understand that this representation might bring additional issues, as it was mentioned by Don Y, but my main goal here is to go one step further from the clumsy programming that I've been doing for the past few years into a bit more formal representation of the problems.
I also have some questions about synchronization of several FSM, but this is a subject for a feature post.
While you're last statement is true, I do not think it is a valid argument against adding another tool to the development process. In a work (not hobby) environment, I expect good management and teams to make considered choices about what tools to apply. If a tool is feature rich and well documented, then the knowledge should be available (either in you head or in the manual) to make the job easier.
Yes. When I have done a lot of regex work I kept a quick reference card handy.
Being tool agnostic is an ideal goal. In a practice, you must pick some specific tools to get the work done within schedule, budget, and quality constraints.
If you want portability of design then that should be an explicit fourth constraint. Most projects select tools with the additional LONG TERM constraint of support throughout the life of the product or product line.
Exactly why an abstracting tool that is more focused on the design is better than a specific tool.
State machine design tools are a good example. With a graphic design tool, it is much easier to spot missing states or incorrect transitions. It can be clear enough that even end users can understand and point out flaws or enhancements. I don't think the particular output language is the point here.
BTW, lots of your earlier comments match closely to what I would have posted. This one just struck me are being a little too idealistic.
This is a very simple topic, that can be made as complicated as you wish. It would be good to work through an example of yours, but until you provide one, here's a traffic light.
Assume there are separate timers and that inputs from sensors are all processed to be "clean". This is a pseudo language rather than any specific language. Because Google Groups does not preserve multiple spaces, I'm using underlines for indentation. The states are EW_GREEN, EW_YELLOW, NS_GREEN, NS_YELLOW. The inputs are EW_CAR, NS_CAR and the timer done indicators. Outputs are NS_RED_light, NS_YELLOW_light, NS_GREEN_light, EW_RED_light, EW_YELLOW_light, EW_GREEN_light, and the timer start signals. This intersection has more traffic in the NS direction, so that direction gets the green light until it times out (longer time than the EW time) or after a minimum delay, an EW car is detected.
cur_state CASE __ NS_GREEN OF ____ IF (NS_LONG_TIMER_done OR (NS_SHORT_TIMER_done AND EW_CAR_detected) ) THEN ______ cur_state <= NS_YELLOW; ______ NS_GREEN_light <= OFF; ______ NS_YELLOW_light <= ON; ______ NS_LONG_TIMER_enable <= OFF; ______ NS_SHORT_TIMER_enable <= OFF; ______ YELLOW_TIMER_enable <= ON; ____ ENDIF ; __ ENDOF ;
This all starts with a coherent description of the functions of the state machine, then a diagram. Once you have the diagram, it's a very simple process to turn it into the above coding style.
In an HDL, the above code would be in a process that runs when any of the specified inputs changes. Essentially, it's a data flow design. But I don't know how you would trigger that in something like C. I suppose you have interrupts from changes of the inputs, as well as timer interrupts. Each of these are events that can trigger the above code to run.
Hi jmariano, You are clearly on the right path. FSM are useful in many situations. With a physics background you will get it soon. You can consider time as an input for synchronization. Or a messaging system. If you would like help on your software design, feel free to email me.
My career went from physics to software, which I've done for about 40 years. Enjoy and good luck. Ed
To your 1st sentence: AMEN. We don't really disagree here. To the rest: I've seen it too. Developers that write C code thinking they are programming in C++ is an extreme example.
Personally, Yes, I admit to my own limitations.
True, but that is a different issue that the selection of the tool in the first place.
You're preaching to the choir here Don.
Yes a lot of projects don't follow due diligence. Hence my phrase earlier about "good management and teams" was used deliberately.
Yes. That's true. Computer engineering has been in constant flux for
70+years. Those that fail to learn history are condemned to repeat it.
I was focusing on documenting the design. I've tried to leave projects with enough clear design so that I can be replaced.
Well, whiteboard is easier to "edit and then save via camera (&/or printer)
Ideally it should do both, act as a design recording medium and output the implementation.
Haven't used Harel charts. That's part of UML and no place that I worked at has needed a tool set that complex. KISS Taking a quick look, [again!] I can see why it may not be a good choice.
If it is the design, then it better be clear enough to just read through and be understandable and complete. If it is the implementation, then I never assume I am familiar with the code (even it I wrote it).
On some projects more than others. But I've managed to work on a couple projects where putting in the time up front in design paid off big in the integration and release. I'm especially proud of those projects.
At one of the last places I worked we developed a saying that we violently agree. 8^)
You make great contributions here Don. Keep it up. Ed
I think the complexity of a FSM is not only related to the number if states, but also to the transitions/inputs.
It's much simpler to detect errors on a diagram instead on a cryptic list of switch/case instructions. The great advantage of a diagram is that it can be read by non-developers: customers, sales man, project managers and so on.
UML diagrams are there exactly for these reasons.
Now imagine a tool that takes as input the diagram and spits out a fsm.c without errors.
I know most of FSMs are simple, but most of the time you refuse to solve a problem with a FSM just because it could be too complex to convert in code. However, if you had this type of tool, you would consider FSMs for much more problems.
For example, a simple calculator can be modeled as a FSM: the transitions are keystrokes. However it isn't a simple FSM, because there are many subtle details that must be addressed. It is somewhat simple to make a diagram and solve some problems with arcs, arrows and rectangles, but it's much more complex to make the same things on a C code.
Indeed. Please check out the freeware QM modeling tool:
Automatic Code Generation video:
QM is an example of a modern, *lightweight* modeling tool. Older, "high-ceremony" tools have been available since the '90, but they couldn't pull their own weight and didn't catch on. However, things changed since the '90s...
Interesting that you mention the calculator problem. (I've used it in my "Practical Statecharts" book published back in 2022.) I've also used it in my recent video "State machines as "spaghetti" reducers:
It turns out that even the "simple" 4-operation calculator is complex enough to be almost impossible to get right with traditional "improvised" state management. A state machine, on the other hand, is quite manageable.
I learned state machines using the PLD compiler "CUPL" on a VAX11/750. That had a nice syntax for Mealy and Moore state machines and once I had understood that, I could also do it in PALASM or VHDL.
Another useful tool is yacc from Unix or bison on Linux. It reads a grammar and builds a state machine from it. The state machine is later a blob of C. It reads a series of symbols from its input much like your serial device and hopps through the state machine if the string of symbols is legal given the grammar. If a legal grammar rule is recognized, you can trigger the execution of some C code.
My syntax is wrong, but you get the principle. The stuff in curly braces is the executed C code when a rule is discovered, the $$ thingies are replaced by the relevant variables. Yacc tries to find the most general rules possible. That makes sure that y = a + b + c * sin(333); is recognized.
Usually you will insert a lexical scanner in the input, like lex, so that the state machine does not grow beyond a reasonable size. That would filter out things like "begin", "end", "integer", ":=" and so on. lex() would return integer constants like SY_BEGIN, VARIABLE_NAME, '(' and so on.
Yacc stands for "Yet Another Compiler Compiler", but it's original job was to create Weinberger arrays, a LSI structure not unlike a PAL.