FSM in illegal state

Do you have a question? Post it now! No Registration Necessary

Translate This Thread From English to

Threaded View
Hi all! I'd like to once again bring up the subject of state machines
running into illegal states (illegal in the sense that the state vector does
not correspond to any of the states defined in the VHDL code), because
despite having spent half a day googling and reading related threads, I'm
still left with a couple of questions:

1. Most discussions cover how to recover from illegal states, but few cover
how it actually happens. What are the (I presume) electrical reasons to that
a state machine runs into an illegal state in the first place? Is there
anything one can do to reduce the risk? Assume all FSM inputs connected to
I/O pins are synchronized with one FF each, and the whole design is
synchronous. Does anyone know of a good tutorial on this issue? I could add
that in my case, the transition into an illegal state almost always happen
immediately upon startup of the system, if it happens.

2. How can I force Xilinx XST (6.2 SP3) to produce a safe FSM that recovers
from an illegal state? A "when others => state <= IDLE;" clause doesn't seem
to help (which I think is stupid, isn't this problem so well known that they
should make XST recognize it instead of optimizing it away?). I realize that
changing coding style to "Binary" will reduce the number of illegal state
and thus the risk for it to happen, but it's not completely safe, unless the
number of states is a power of two. What's more, binary coding style seems
to increase slice utilization for the whole design by up to 10%.

Thanks in advance!

/Jerker



Re: FSM in illegal state

Quoted text here. Click to load it

How is the reset signal handled?  If the FFs are asynchronously reset,
then the end of reset can happen at different times to different FFs,
leading to an illegal state.


--
Phil Hays
Phil-hays at posting domain should work for email


Re: FSM in illegal state

Quoted text here. Click to load it

Internal noise coupling in the chip (crosstalk), power drops, alpha
particles, not properly double-sync'ing an async signal before using
it in two different places (BTDT, seen it in a real chip), ... the
list goes on!


--Kai

Re: FSM in illegal state
 > Internal noise coupling in the chip (crosstalk), power drops, alpha
 > particles, not properly double-sync'ing an async signal before using
 > it in two different places (BTDT, seen it in a real chip), ... the
 > list goes on!

OK, probably I would need the complete list with full descriptions! Do
you know of any books or tutorials on this subject? I'm not really an
electrical engineer but I have to deal with this, so any pointers would
be appreciated.

/Jerker

Re: FSM in illegal state
 > How is the reset signal handled?  If the FFs are asynchronously reset,
 > then the end of reset can happen at different times to different FFs,
 > leading to an illegal state.

Hi Phil! I use no reset signal at all; instead I specify initial values
for all signals by the declarations, which is supposed to work fine with
XST. But your point is still interesting in case I would need to
introduce an asynchronous reset some day. Does that mean one should
avoid them if illegal states are a concern?

/Jerker

Re: FSM in illegal state
Hi Jerker,
Well, you _do_ have a reset. It's just a little hidden. At some point the
storage elements stop being held at the initial values. This is the
equivalent of your reset being released. If the elements are being clocked
asynchronously to the release signal at this time, you could be in trouble.
Cheers, Syms.
Quoted text here. Click to load it



Re: FSM in illegal state

Quoted text here. Click to load it

You do have an asynchronous reset, you just didn't know that you did.
When a Xilinx FPGA finishes the program download, it has all initial
values held until an internal signal is released.  This release is
asynchronous to your clock.  To avoid problems with this add a counter
that is reset to all zeros.  Until that counter counts to 15, keep the
state machine in the initial state.

(Note: Startup is a messy subject.  This is a simplified version.)

There is another common issue with DCMs or DLLs that you might also be
having a problem with.  Are you using a DCM or a DLL?


Quoted text here. Click to load it

Yes.  Suppose the initial state is "100" and the desired next state is
"010".  This would be a three state one-hot machine.
If the first bit is held until just after the first edge of the clock
and the second bit is held until just before the first edge of the
clock, then the next state will be illegal, "110".
If the first bit is held until just before the first edge of clock and
the second bit is held until just after the first edge of the clock,
then the next state will be illegal, "000".  

Does that make it clear?


--
Phil Hays
Phil-hays at posting domain should work for email

Re: FSM in illegal state
Phil

Your allusion to "common"  DCM / DLL issues has aroused my curiosity.

Could you elucidate please.

Martin


Quoted text here. Click to load it



DCM / DLL issues was: FSM in illegal state

Quoted text here. Click to load it


Sure.  I'm not sure "common" was the correct word, but I suspected
that the original poster might have run into the following issue.
I've seen it in someone else's design.  These problems are curable by
reading the fine manual (RTFM).

RTFM # 1 "Do not use the DCM output clock signals until after
activation of the LOCKED signal. Prior to the activation of the LOCKED
signal, the DCM output clocks are not valid and can exhibit glitches,
spikes, or other spurious movement."

You can keep the part in configuration until the DCMs are locked by a
bitgen option, or you can use the synchronized locked signal to force
reset to all state machines and all other critical logic.  Better do
one of the two.  The bitgen option is probably best, unless you may be
resetting the DCMs after configuration, in which case you need to do
the second.


I didn't think he had this issue, but I've seen it as well.  In my own
design.

RTFM # 2 "To ensure consistent locking, if a DCM is configured with
external feedback, applying a reset after configuration is strongly
recommended."

"Strongly recommended" isn't quite correct.  "Required" would be
better wording.


--
Phil Hays
Phil-hays at posting domain should work for email



Re: DCM / DLL issues was: FSM in illegal state
Phil

Thank you for the dits

If only one could RTFM (Read The Full Manual) - it never seems to get
published  these days

An F* problem in its own right; but fore warned is fore armed

Martin


Quoted text here. Click to load it



Re: FSM in illegal state
Quoted text here. Click to load it

I have never had a design with a state machine which got into illegal
states.  The only two reasons that I can think of for this happening is

1) electrical noise which would also cause upset of *other* FFs in the
system causing other symptoms and

2) timing issues with the FSM.  This can be either from async inputs
(metastability) or from failing to meet setup time on a reg input.  If
you have done your static timing analysis correctly, then it must be a
metastability issue.  The fact that it occurs happens on startup says to
me it is a timing issue.  If you can chase the problem away by slowing
your clock, then it is a static timing issue.  If it persists, then you
most likely have a metastable issue.  

Figure out what is wrong and deal with the cause of the problem.  


Quoted text here. Click to load it

I am not a fan of dealing with this type of problem by illegal state
recognition.  If it gets into an illegal state it has already caused a
malfunction of the rest of the circuit most likely.  Getting back to a
known state is only useful in that it can resume normal operation.  But
it is not a "fix".  

I am unclear as to why the others clause would not result in recovery
from an illegal state.  That could very easily add a lot of extra logic
and even slow the max speed of the FSM.  But it should not be optimized
away since it is a specified part of the machine.  I assume the illegal
state detection works in simulation, no?  If so, it should work in
operation.  

--

Rick "rickman" Collins

snipped-for-privacy@XYarius.com
We've slightly trimmed the long signature. Click to see the full one.
Re: FSM in illegal state
Quoted text here. Click to load it

The synthesis tools are "smart" enough to recognize that there is no
logical way to reach the "others" state. Therefore it is optimized out.
Many synthesis tools do this.

--
My real email is akamail.com@dclark (or something like that).

Re: FSM in illegal state
Quoted text here. Click to load it

Wow, isn't software clever... and it probably does not tell you it did
this either... but never mind, the other state have no logical pathways,
so everything will be OK.

Back to the real engineering world:
  Do LOOK at the resultant output of your tools, and HOW it actually
built the FSM. It can use .D or .T registers, with .D the most common.

Implicit in most .D coding is that state 00000 is the goto state from
any illegal ones : Thus for many reasons (hopefully very rare) you MIGHT
goto an illegal state, but the one after that will be 00000.

This should be a cornerstone state of your legal state list, either
the POR state, or the safe-idle state.

Choosing gray code related states can reduce the pathways to illegal
states, but in complex FSM's, this is not always possible.

  You should not rely on this recovery pathway in regular system
operation, it should be a safety-net.
  During tests, you could INC a counter when passing through 00000,

.T register state engines can be smaller, but they also can literally
stick at an illegal state.

-jg


Re: FSM in illegal state
Hi Jim!

 >   Do LOOK at the resultant output of your tools, and HOW it actually
 > built the FSM. It can use .D or .T registers, with .D the most common.

Well, the output netlist isn't exactly human-readable, although I guess
I could write a simple FSM, synthesize it and study it. But actually I
already know how XST has encoded my machine. My options are essentially
One-Hot, Compact (binary), Sequential, Gray, and Johnson, all presumably
on D flip-flops. I get One-Hot encoded machines unless i ask for
something else.

However, correct me if I'm wrong, the state encoding itself doesn't
change anything in the machine's ability to recover from illegal states
- it takes some logic that detects these illegal states and forces the
state vector back to normal, and that logic obviously isn't there. Many
synthesis tools provide an extra option "safe FSMs" which will add such
logic, but XST doesn't. So my question is XST-specific - how do I add
illegal state recovery logic with XST?

/Jerker

Re: FSM in illegal state

Quoted text here. Click to load it

No, not quite.
If you consider .D registered FSMs, then if you have enumerated 00000
as a legal state, that naturally maps what you call recovery logic.
If the tools choose one-hot, and take 00000 as illegal/not possible,
(since it is not a one-hot state) then you loose the natural recovery path.
ie the state encoding itself CAN affect the recovery, as if you
avoid the .D recovery path of all low, your FSM will not perform
the same as one that includes all lows as a specified state.

Try Gray or Johnson, and make sure the 00000 is an enumerated/specified
state, and see what happens ?

-jg


Re: FSM in illegal state
 > If you consider .D registered FSMs, then if you have enumerated 00000
 > as a legal state, that naturally maps what you call recovery logic.
 > If the tools choose one-hot, and take 00000 as illegal/not possible,
 > (since it is not a one-hot state) then you loose the natural recovery
 > path. ie the state encoding itself CAN affect the recovery, as if you
 > avoid the .D recovery path of all low, your FSM will not perform
 > the same as one that includes all lows as a specified state.

But that only solves the problem for one specific illegal state... or do
I misunderstand something? Say I have a three-state machine, where XST
by default would encode the states "100", "010", and "001". So there are
now five illegal states. If I follow your suggestion, I could encode the
states like "00", "10", and "01". But there is still one illegal state,
namely "11". I agree this is a lot better and it significantly reduces
the risk of falling into the illegal state, but the risk is still there.
And if the machine somehow falls into this illegal state, I want there
to be some recovery logic to take the machine out of it.

Simply put - no matter what encoding I use, there will always be illegal
states (except when the number of states is an exact power of two, so
that I can assign each state vector configuration to a legal state). And
if there are illegal states, the machine can fall into them. And if the
machine can fall into an illegal state, I want it to get out of there
automatically.

 > Try Gray or Johnson, and make sure the 00000 is an
 > enumerated/specified state, and see what happens ?

I have tried binary encoding, and indeed wouldn't hang anymore. But
considering what I wrote above, I don't feel confident that it really
solved the problem - I believe I just reduced the probability for it to
happen. But I would happily be proved wrong!

/Jerker

Re: FSM in illegal state
Quoted text here. Click to load it

With .D registers, and you can consider FSMs as low level coded as:
Q0.D = SeriesOfTerms0;
Q1.D = SeriesOfTerms1;

Each valid state will have a number of hold-until-next-move-true terms,
but states not covered will have NO .D terms, and so their NEXT state is
Q0.D = 0;
Q1.D = 0;
or to the 00 state.

If you code
  IF State11% THEN immediate_next = 00, then no more logic is generated,
as that is implicit.

So it will get out of there automatically. With one-hot, the actual
problem is that where it GOES NEXT is also not on the state map, whereas
with other schemes, esp if you implicitly include 0000, then there is a
recovery path.

Quoted text here. Click to load it

See above.


Re: FSM in illegal state
Quoted text here. Click to load it

All right, NOW I see your point! But it seems to me you're assuming that the
synthesis tool always generates the transition logic such that illegal
states always transition to the state vector of all zeroes, and I'm not yet
convinced that this is the case. I would have believed that the transition
function would map all illegal states to "Don't care", allowing the tool to
minimize the transition logic. As a consequence, the illegal states could
transition to anyting, including the same illegal state, which means it's
stuck. But I will try to investigate how XST generates the transition logic.
If you're right, you definitely answered my question no 2.

/Jerker



Re: FSM in illegal state

Quoted text here. Click to load it
<paste>
Quoted text here. Click to load it
logic for them, even states that are legal and have their own "when" clause.
I've even seen in another thread on comp.lang.vhdl the suggestion to connect an
input pin to ground, then add code to the state machine like
Quoted text here. Click to load it
was hoping there were better solutions...
Quoted text here. Click to load it

To solve any reliance on 'what xxxx tools might choose to do', the best
solution is to code
   ELSE
     state <= Enumerated_0000_State;

  Normally, that should have zero additional hardware logic cost [except
for one-hot], ( because it is implicit in the .D construction), but now
you are more certain you and the tools 'are on the same page'.
  I would try to avoid trying to add logic outside the state
expressions, as there you are again on thin-ice, with tool dependance.

-jg


Re: FSM in illegal state
Quoted text here. Click to load it

One other thing you can do is to add the logic manually.  If you are
using an enumerated data type, you can get the encoded value.  Write
your own logic on this state value and detect the illegal combinations.  

--

Rick "rickman" Collins

snipped-for-privacy@XYarius.com
We've slightly trimmed the long signature. Click to see the full one.

Site Timeline