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
Text on FSM
Started by ●March 9, 2023
Reply by ●March 9, 20232023-03-09
On Thursday, March 9, 2023 at 5:17:18 PM UTC-5, jmariano wrote:> 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.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. -- Rick C. - Get 1,000 miles of free Supercharging - Tesla referral code - https://ts.la/richard11209
Reply by ●March 9, 20232023-03-09
On 3/9/2023 3:17 PM, jmariano wrote:> Hello Does anyone know of a nice text on finite state machines and their > software implementation on embedded systems?Implementations can vary widely. Do you want to present (current state, inputs) to a machine and have (next_state, outputs) emitted "immediately"? Or, is the processing time not critical (e.g., UI's tend to be this type) Do you want to limit the machine to the "classic" design? Or, add extensions (e.g., support the notion of "previous_state", "subroutines", etc.)?> 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 jmarianoIn the degenerate case, you build a matrix that is accessed by [state][inputs] and delivers (next_state, outputs). But, it's obvious that the size of this structure grows quickly with number of states and inputs. In practice, often a state may have only a few significant inputs that govern the choice of next state so the matrix contains lots of redundant entries. You can unfold the matrix into a series of switch/case statements -- but, I've found that makes it hard to sort out what's really happening (the beauty of a state machine is that it is concise). I prefer representations like: Case IDLE On <digit> GoTo ACCEPTING Executing GobbleDigit() On <clear> GoTo ISSUE_PROMPT Executing ClearValue() On <enter> GoTo TEST_VALUE Executing CheckLimits() .. Note that there are only 3 items encoded on each line: - the input being examined - the name of the intended next_state - the action to be performed *in* the transition As such, this can be encoded in as few as 3 bytes (depending on how many states, inputs, and actions you need to support) But, the big advantage is it's concise -- no extra syntactic sugar to clutter up the page (cuz you want to express the machine in as little space as possible as it gets harder to chase layers of case/switch statements with interspersed *actions*) [There are also UML techniques for their representation and tools that will parse such descriptions and build the code for you] In school, Hill & Peterson was our reference (_Intro to Switching Theory and Logical Design_) but you don't need much "text" to understand the concepts (assuming you already understand logic). OTOH, it's worth learning about minimization techniques -- esp if your approach to the machine's design is /ad hoc/ (ripe for hidden optimizations).
Reply by ●March 10, 20232023-03-10
On 10/03/2023 02:11, Don Y wrote:> On 3/9/2023 3:17 PM, jmariano wrote: >> Hello Does anyone know of a nice text on finite state machines and their >> software implementation on embedded systems? > > Implementations can vary widely. Do you want to present (current state, > inputs) to a machine and have (next_state, outputs) emitted "immediately"? > Or, is the processing time not critical (e.g., UI's tend to be this type) > > Do you want to limit the machine to the "classic" design? Or, add > extensions (e.g., support the notion of "previous_state", "subroutines", > etc.)? > >> 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 > > In the degenerate case, you build a matrix that is accessed by > [state][inputs] > and delivers (next_state, outputs). But, it's obvious that the size of > this structure grows quickly with number of states and inputs. In > practice, > often a state may have only a few significant inputs that govern the choice > of next state so the matrix contains lots of redundant entries. > > You can unfold the matrix into a series of switch/case statements -- but, > I've found that makes it hard to sort out what's really happening (the > beauty of a state machine is that it is concise). > > I prefer representations like: > > Case IDLE > On <digit> GoTo ACCEPTING Executing GobbleDigit() > On <clear> GoTo ISSUE_PROMPT Executing ClearValue() > On <enter> GoTo TEST_VALUE Executing CheckLimits() > .. > > Note that there are only 3 items encoded on each line: > - the input being examined > - the name of the intended next_state > - the action to be performed *in* the transition > As such, this can be encoded in as few as 3 bytes (depending on how > many states, inputs, and actions you need to support) > > But, the big advantage is it's concise -- no extra syntactic sugar > to clutter up the page (cuz you want to express the machine in > as little space as possible as it gets harder to chase layers of > case/switch statements with interspersed *actions*) > > [There are also UML techniques for their representation and tools that will > parse such descriptions and build the code for you] > > In school, Hill & Peterson was our reference (_Intro to Switching Theory > and > Logical Design_) but you don't need much "text" to understand the concepts > (assuming you already understand logic). > > OTOH, it's worth learning about minimization techniques -- esp if your > approach to the machine's design is /ad hoc/ (ripe for hidden > optimizations). >I went to a course of lectures on (and by) Harel state-charts. Here is one for text: https://github.com/cepsdev/machines4ceps There is also https://www.codeproject.com/Articles/11398/A-Lightweight-Implementation-of-UML-Statecharts-in
Reply by ●March 10, 20232023-03-10
Il 09/03/2023 23:17, jmariano ha scritto:> 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 > jmarianoSearch 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 by ●March 10, 20232023-03-10
On 3/10/2023 1:37 AM, Bill Davy wrote:> I went to a course of lectures on (and by) Harel state-charts. > > Here is one for text: https://github.com/cepsdev/machines4ceps > > There is also > https://www.codeproject.com/Articles/11398/A-Lightweight-Implementation-of-UML-Statecharts-inThe problem I see with using state machines to control processes is that those processes. however trivial they may APPEAR to be, often have lots of exceptions that are inherent in their *correct* implementation. Representing these in the state machine definition IN A WAY THAT DOESN'T CAUSE THEIR SIGNIFICANCE TO BE LOST (resulting in bugs!) becomes challenging. Few applications are simple models of DFA -- e.g., the grammar for a "numerical value". There are invariably other things going on *during* the processing of that DFA (which has no notion of time even though the application may be "human driven") that compete with and potentially override it! We bought a range, recently. It was less than an hour before I was able to stumble over a bug in their implementation -- because the implementer likely ASSUMED each segment of the grammar would operate essentially without disturbance. So, if the user wanted to change the temperature setting, this set of states (and state transitions) *looks* like it will achieve that goal... except it doesn't take into account that it takes some amount (UNCONSTRAINED!) of time for the user to perform those steps (generate the events that are prescribed by it). And, that while he is faithfully following the prescribed actions, other "stuff" can be happening. Like, the cook timer expiring and expecting acknowledgement. Oh, but how do you tell the timer that THIS "one big single control" activation is intended to acknowledge that event and *not* a step in the "change temperature" event sequence? And, what would happen if one leg of the AC mains "failed" (or appeared to) during these two overlapping sequences? Would the display be commandeered to indicate that failure? And, the acknowledgement of that alert be confused with these other two competing activities? Some other yet to be discovered "fault"? How do you express the priority of those events without makin ghte simple state machine look overly complex (have I handled the possibility of a partial AC mains failure at THIS point in the machine? SHOULD I??) And, what if the cook timer for the *second* oven expired while all this was happening? Or, the general purpose ("egg") timer? There are ways to resolve these problems (DFA hierarchies). But, it's too easy for the programmer to miss their potential conflicts, mistakenly thinking he's enumerated all of the input events, etc. as is required in a "state machine".
Reply by ●March 10, 20232023-03-10
On 3/10/2023 1:54 AM, pozz wrote:> 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.DFA have application besides handling "events". E.g., you can think of every character/octet in a message as an "event" (even though they all "appear" as a coherent unit) and use a DFA to parse the content for validity/meaning.> 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 by ●March 10, 20232023-03-10
On Fri, 10 Mar 2023 09:54:23 +0100, pozz <pozzugno@gmail.com> wrote:>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.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. -- RoRo
Reply by ●March 10, 20232023-03-10
On Friday, March 10, 2023 at 6:48:13 AM UTC-5, Robert Roland wrote:> On Fri, 10 Mar 2023 09:54:23 +0100, pozz <pozz...@gmail.com> wrote: > > >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. > 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.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. -- Rick C. + Get 1,000 miles of free Supercharging + Tesla referral code - https://ts.la/richard11209
Reply by ●March 10, 20232023-03-10
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: https://www.youtube.com/playlist?list=PLPW8O6W-1chxym7TgIPV9k5E8YJtSBToI 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
