Text on FSM

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

Reply to
jmariano
Loading thread data ...

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.

I hope this helped.

Reply to
Rick C

I went to a course of lectures on (and by) Harel state-charts.

Here is one for text:

formatting link
There is also
formatting link

Reply to
Bill Davy

Il 09/03/2023 23:17, jmariano ha scritto:

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.

Reply to
pozz

When I went to school, 30 or so years ago, we did have such a program. I am not able to remember its name, though.

Reply to
Robert Roland

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.

Reply to
Rick C

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:

formatting link
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".

--MMS

Reply to
StateMachineCOM

Hello again!

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.

Cheers, jmariano

Reply to
jmariano

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.

Ed

Reply to
Ed Prochak

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 ;

__ NS_YELLOW OF ____ IF (YELLOW_TIMER_done) THEN ______ cur_state <= EW_GREEN; ______ NS_YELLOW_light <= OFF; ______ NS_RED_light <= ON; ______ EW_RED_light <= OFF; ______ EW_GREEN_light <= ON; ______ YELLOW_TIMER_enable <= OFF; ______ EW_TIMER_enable <= ON; ____ ENDIF ; __ ENDOF ;

__ EW_GREEN OF ____ IF (EW_TIMER_done) THEN ______ cur_state <= EW_YELLOW; ______ EW_GREEN_light <= OFF; ______ EW_YELLOW_light <= ON; ______ EW_TIMER_enable <= OFF; ______ YELLOW_TIMER_enable <= ON; ____ ENDIF ; __ ENDOF ;

__ EW_YELLOW OF ____ IF (YELLOW_TIMER_done) THEN ______ cur_state <= NS_GREEN; ______ EW_YELLOW_light <= OFF; ______ EW_RED_light <= ON; ______ NS_RED_light <= OFF; ______ NS_GREEN_light <= ON; ______ YELLOW_TIMER_enable <= OFF; ______ NS_LONG_TIMER_enable <= ON; ______ NS_SHORT_TIMER_enable <= ON; ____ ENDIF ; __ ENDOF ; ENDCASE ;

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.

Reply to
Rick C

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

Reply to
Ed Prochak

If you *really* want the theory, you can take a look at Hopcroft and Ullman's "Intro To Automata Theory, Languages And Computation".

It's available free as an ebook from

formatting link

Be aware that there is little/no code in this book - it's theory only and you will need to figure out how to implement.

Good luck! George

Reply to
George Neuner

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

Reply to
Ed Prochak

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.

Reply to
pozz

Indeed. Please check out the freeware QM modeling tool:

-

formatting link
Automatic Code Generation video:

-

formatting link
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:

-

formatting link
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.

Reply to
StateMachineCOM

Am 10.03.23 um 18:51 schrieb jmariano:

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.

Grammar:

expression = number: { $$ = $1; ) | expression = sym_variable: { $$ = $1; ) | expression = Number '+' number : { $$ = $1 + $3; } | expression = epression '*' expression: { $$ = $1 * $3; } | expression = epression '/' expression: { $$ = $1 / $3; } | expression = '(' expression and so on

assignment = sym_variable ":=" expression: { $$ = $3; )

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.

Cheers, Gerhard

Reply to
Gerhard Hoffmann

yacc and bison will remove unreachable PDA states. Unreachable states in the parser typically are not deliberate but rather result from ambiguities in the grammar. lex, being LALR(1), does not tolerate much ambiguity - however bison can generate more powerful LR(1) and GLR(1) parsers, and these are far more likely to have unreachable states accidentally generated.

Similarly, lex will remove unreachable DFA states. Again, these typically are not deliberate, but rather result from lex combining the various input regex into a single DFA having multiple entry points and multiple accepting states.

Then there is flex.

flex has some DFA optimizations available. First, flex can compress the data tables which encode its DFA states. Second, flex can discover "equivalence" classes: groups of characters which result in the same action. And finally, flex can [sometimes] discover "meta-equivalence" classes: commonly expected sequences of characters and/or other equivalence classes.

All of these can result in a smaller and/or more efficient recognizer than is possible with lex.

yacc and lex are ancient and haven't been maintained for decades. They have limitations that will never be addressed, and bugs that will never be fixed. If you really need backward compatibility with them, it is available using bison and flex ... and if you don't need bacward compatibility, bison and flex are much more powerful and modern tools for use with new projects. [There are other modern alternatives to yacc and lex also, but discussion of them is beyond the scope of this missive.]

George

Reply to
George Neuner

Il 13/03/2023 16:55, StateMachineCOM ha scritto:

Yes, I know this tool and I like its philosopy. However I understood I can't use the generated code in closed source projects without a commercial license.

I read your book ;-)

*Hierarchical* state-machine is fundamental here to reduce complexity.
Reply to
pozz

A good diagram is always much more expressive than a good code, for developers and for non-developers.

Hierarchical state-machines (UML state-machines) are fully qualified monsters.

This is the reason why a fsm generation tool could help. You don't need to build with /ad hoc/ approach.

I didn't get your point of these all. There are simple applications and complex applications, I don't think you need to convince me.

Anyway even a simple application such as a standard calculator can be complex enough to be implemented as a flat state-machine without any tool.

However the complexity can be managed and reduced on a diagram of a UML/hierarchical state-machine. After that, click on a build button and you error-free code is done.

Reply to
pozz

In my experience, diagrams that describe all the details of the code, as would be required for generating the code from the diagram, are usually much too complex to comprehend easily ("visually"). They tend to be mazes where one can perhaps trace out some significant paths with a careful finger, unless too many lines cross at one point.

To get a good, visually graspable diagram, IME one must almost always simplify and elide details. And then such diagrams are very good entry points into the code, if one has to read the code to get a complete understanding.

I remember one case where the SW for the central computer of a satellite was generated from state-and-message diagrams by an automatic "model-based design" tool. In graphical form, the diagrams covered numerous A4 pages and each page had several cryptically labelled inter-page links for messages coming from other pages and going to other pages. It was very difficult to get any kind of overall understanding of the SW.

I admit that there are some domains -- for example, servo-control systems -- where it is possible to generate significant amounts of code from readable diagrams, eg. SIMULINK diagrams. But I don't think it works well for most code in embedded systems.

Reply to
Niklas Holsti

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.