safe state machines

It seems we are still learning from this interesting post.

I am surprised to conclude two points:

- managing illegal states needs a lot of logic(a bucket of logic) and so most tools abandoned it

- safety critical applications demand it and so some tools have this safety option

The following excerpt from the link below explains it well:

http://klabs.org/mapld04/papers/d/d219_berg_p.doc

2. State

Most designers believe that they are implementing a bucket-approach to fault tolerance when using the default clause (VHDL- when others) within a CASE statement. However, the synthesis tools ignore these statements when synthesizing state machines. Most designers are not aware that these statements (that suggest “bucketing” unused states and supplying a transition out of a fault condition) have no bearing on the actual gates being created. The reasoning behind this is that if the synthesis tool were to implement all unused states, the required area would be excessive.

Synthesis tools have a directive that the designer can use called “safe”. When applying this directive to a state machine, the tool can produce a bucket of illegal states. However, the designer must be forewarned that using the “safe” directive has many flaws:

1. It generally creates more gates than desired, i.e. buckets of illegal states can become very large.

2. Synplify will implement a “safe” one-hot but Leonardo and Precision will only implement a sequential state machine (binary or Gray encoding) while using the “safe” directive.

2. how Safe

Recently, there has been a surge of designers using the “safe” options offered by several different synthesis tools. They have defined a safe state machine as one that will always transition to a known state - i.e., if an SEU occurs and an illegal or unmapped state is reached, one will recover to a known state.

Synthesis tools offer a “safe” option (demand from the Aerospace industry):TYPE states IS ( IDLE, GET_DATA, PROCESS_DATA, SEND_DATA, BAD_DATA );

[/INDENT]SIGNAL current_state, next_state : states;

[/INDENT]attribute SAFE_FSM: Boolean;

[/INDENT]attribute SAFE_FSM of states: type is true;

[/INDENT]Although this scheme may appear to be “fool-proof”, it is not. The “safe” option will not always transition to a reliable (or known) state. Some have defined the word “known” as mapped. However, the idea is to be deterministic. The idea is to always flip into some “ERROR” or “IDLE” state upon getting an SEU. Flipping into a mapped state, in which the rest of the system may not know the state machine is there, is not deterministic. It is not good enough to transition to a mapped state:

• The machine can get stuck waiting for an input that will never occur (rest of the system doesn’t know that you have flipped into this mapped state).

• Unexpected signals can turn on (or off).

• And many more reasons…

Good post. It doesn't usually add a ton of logic, but it's more than the decode of the other states(especially one-hot encoded machines, which have 2^n-n unencoded states). For one-hot, probably the best thing to do is not look for an unencoded state, but OR together something that looks for all the available states, and if it's a 0 then we're in no-man's land.

For safety critical, this is definitely an improvement, but my personal feeling is that it is far from safe. A safe state-machine with binary encoding will most likely jump to a known state, which often suffers from that previous problem of waiting for a signal that will never come because the rest of the system thinks it's in another state. And even if state-machines could be truly safe, everything in the design that has a feedback path will need checks. If a counter jumps to a different count value it may never recover from that(yes it could flip, but if the incrementer is dependent on some value decode, i.e. it counts different values based on it's current state) then it might be in an out of bounds value. It's just really, really difficult to be sure, and the people who really need it usually resort to redundant systems and polling, or stuff like that.

I'm not saying safe encoding is not important, just that most users don't really know how much it helps their system reliability, as it is not the only consideration. And I've seen users argue they need it for stuff that probably really doesn't, like a video game.

To refer to the initial discussion theme, Rysc summarized the Quartus 5.1 Handbook statements regarding safe FSM correctly. It clarifies, that OTHERS doesn't implement safe behaviour respectively, that Quartus didn't have a means to implement safe FSM behaviour. By using a binary state coding without unused states, a similar behaviour could be achieved anyway, if necessary for some reason.

The most common reasons for geting stuck in illegal states are violations of timing requirements, either with asynchronous inputs to a FSM or the clock itself, e. g. if the clock is supplied from an unsafe source, that can show glitches in some situations.

While the first problem can be easily avoided, the latter to my opinion contains a residual risk and may be a reason to use safe FSM. Although I basically agree with kaz, that safe behaviour must be achieved for the design as a whole, not only for an individual FSM, I think, that safe FSM in fact can help to make machines recover automatically from accidental states.

Excellent discussion chaps - very useful informative and demonstrative of what the forum is here for.

Good form.

I apologize that this comes late, but I've finally found the printed Altera booklet where this information appears. It's named "qil51006-5.0.0" and dated May 2005. In chapter 5 ("Design Recommendations for Altera Devices"), in the "State Machines" sections, the second bullet says:

--- Quote Start ---

Assign a default clause or statement to direct the state machine if it accidentally reaches an unused state.

--- Quote End ---

It doesn't say anything about minimizing such clauses automatically in this section, and nothing about the safe state machine option.

Safe state machine option wasn't yet available with Quartus V5, so it can't play a role in the said document.

I don't have the May 2005 version of the Quartus Handbook, but I found the same statement in the previous December 2004 edition. In October 2005, (with Quartus V5.1) the chapter was completely edited. Particularly the limited effect of a default statement had been clarified:

--- Quote Start ---

Synthesis tools remove any logic generated by a default state if it is not reachable by normal state machine operation.

--- Quote End ---

According to a more recent revision history, your May 2005 version is reflecting Quartus V5.0 functionality. I doubt however, that Quartus V5.0 is behaving different regarding default state.

It's a shame that we were misleaded by this particular version of the handbook.

As far as I understand, it's hard to check what Quartus really implements there? Can I see if it has actually minimized the states without digging in the netlist file?

Quartus is not minimizing the states rather than the connecting logic, with the result, that some illegal state codings may be non-escapable. You can check this with the Quartus FSM template design. In default one-state-hot coding, it uses four state variables. The FFs (with the input signal as clock enable) are simply connected to a chain with two inverters.

You can immediately identify two illegal state codings "1000" and "0111" that are non-escapable, cause they have an identical successor.

P.S.: I apologize for the picture quality. Unfortunately good quality gif files are resampled to bad quality jpg by the forum software.