one-hot encoding and fale-safe condition.

M

Mohammed A khader

Guest
Hi all,

I am designing a fsm which has more then 8 states.I would like to have
a one-hot machine but at the same time it should have the fail-safe
condition that is if accidentally fsm goes into illegal state(i:e Two
or more FFs are high) then it should be forced back to initial state.
That is having WHEN others => next_state <=Inital_state clause as
the last statement.

But if I implement that then the function for next state becomes as
many states as my fsm is having.

Do we have any technique to detect an illegal state while making the
fsm as one-hot.

Thanks in Advance.
 
Mohammed A khader wrote:

I am designing a fsm which has more then 8 states.I would like to have
a one-hot machine but at the same time it should have the fail-safe
condition that is if accidentally fsm goes into illegal state(i:e Two
or more FFs are high) then it should be forced back to initial state.
Click to expand...
The basis for one-hot encoding is that it might save some gates.
However when you add the fail-safe requirement to a one-hot
machine, this savings (if there really is any) goes out the window.

Another twist that synthesis may optimize out the "WHEN others" logic
in any case.

Consider binary encoding.

-- Mike Treseler
 
Never do anything like adding fail-save conditions for a state machine.
You just waste your time.

Intel, AMD never do it. Professtionals never do it. Why? If your logic
is correct, you don't have to worry about any unsafe conditions.

Weng
 
Mohammed A khader wrote:
But if I implement that then the function for next state becomes as
many states as my fsm is having.
Click to expand...
Actually, with one hot I would expect the others branch to contain way more
states than your fsm. Not that this matters of course, since your compiler
should handle that for you. What exactly are your reasons for wanting a
one-hot fsm?

Do we have any technique to detect an illegal state while making the
fsm as one-hot.
Click to expand...
I'd leave that to the compiler; in general they're a lot better at reducing
logic than you or I.

Regards,

Pieter Hulshoff
 
Mohammed A khader wrote:

Thank you very much Mike. I have considered your suggestion but now I
have much similar problem to ask in in Binary Encoding..
Click to expand...
Binary encoding gives you an inherent transition to
to state zero from any undefined state for little
or no cost. This is not fail-safe, but it is
simple and I expect that doing any more is not
worth the effort.

Real trouble in large designs is more likely
from missing or inadequate synchronization,
than it is from cosmic rays.

-- Mike Treseler
 
Pieter Hulshoff wrote:
Mohammed A khader wrote:

But if I implement that then the function for next state becomes as
many states as my fsm is having.


Actually, with one hot I would expect the others branch to contain way more
states than your fsm. Not that this matters of course, since your compiler
should handle that for you. What exactly are your reasons for wanting a
one-hot fsm?


Do we have any technique to detect an illegal state while making the
fsm as one-hot.


I'd leave that to the compiler; in general they're a lot better at reducing
logic than you or I.

Regards,

Pieter Hulshoff

As mentioned earlier many compilers optimise out the when others choice.
Click to expand...

If one really wants one hot, it is really easy to guard against a
failure. If the machine fails the next state logic will transisition
to all state bits as a zero. So, I always code the others case and one
I call "hung" to transition from an all zero case to whatever state I
want the machine to recover to.

(Rove the under score to get a real address.)

Clyde
 
Clyde R. Shappee wrote:
Tim Hubberstey wrote:

Clyde R. Shappee wrote:

If one really wants one hot, it is really easy to guard against a
failure. If the machine fails the next state logic will
transisition to all state bits as a zero. So, I always code the
others case and one I call "hung" to transition from an all zero case
to whatever state I want the machine to recover to.

This is not sufficient. Noise and/or timing issues are just as likely
to result in a 2-or-more-hot state as in the 0-hot state you are
covering. See
http://groups.google.ca/groups?hl=en&lr=&selm=3FC2E205.A635F699%40no.spam
where this has been covered previously.

A two or more hot state will then transisiton to the all zeros case, and
as I propose, the machine would recover. It just takes two illegal
states before the machine recovers. Maybe not what you desire, but it
recovers.
Click to expand...
No, that's not guaranteed. The reason for using one-hot is that state
"decoding" consists of sampling the output of a single state FF. This
means the state machine does not consider the output of any other state
FFs except for the current state FF when making a transition. The result
is that if 2 state FFs are set, the machine will transition to 2
(probably different) next states simultaneously.

As a very simple example, consider this example code:

type state_vector is (state1,state2,state3,state4);
....
case state_vector is
when state1 => state_vector <= state2;
when state2 => state_vector <= state3;
when state3 => state_vector <= state4;
when state4 => state_vector <= state1;
end case;

Without any safety logic, this translates to the following logic (use
fixed-space font to view):

+- state1 +- state2 +- state3 +- state4
| | | |
+---[d FF1 q]-+-[d FF2 q]-+-[d FF3 q]-+-[d FF4 q]-+-+
| |
+---------------------------------------------------+

It is obvious from looking at this that if a two-hot situation arises,
the machine will always have 2 FFs set from then on. In the more general
case, a machine will probably converge to having only 1 FF hot but this
is by no means guaranteed, will take an indeterminate number of clocks,
and the resulting parallel states will wreak who knows what kind of
havoc on the rest of the circuit before converging.
--
Tim Hubberstey, P.Eng. . . . . . Hardware/Software Consulting Engineer
Marmot Engineering . . . . . . . VHDL, ASICs, FPGAs, embedded systems
Vancouver, BC, Canada . . . . . . . . . . . http://www.marmot-eng.com
 
Tim Hubberstey wrote :
No, that's not guaranteed. The reason for using one-hot is t­hat
state
"decoding" consists of sampling the output of a single state­ FF.
This means the state machine does not consider the output of any
­other state
FFs except for the current state FF when making a transition­. The
result
is that if 2 state FFs are set, the machine will transition ­to 2
(probably different) next states simultaneously.
Click to expand...
Yes, I completely agree with this. The rate of comversion to legal
state will be more unpredictable if it has more states.For example
consider a state machine with 40 states . Due to noise if state 3
and state 12 are set as high , then in next clock cycle state 4 and
state 13 will be high and then state 5 and state 14 and so on ...

But can we have some extra logic to detect if more then 1 bit is
high. Is it possible to read the State FFs and check whether more then
1 bit is high with some combinational logic and give this output as
the input to the one-hot fsm. That is state machine would have one
more extra input signal to resolve the next state. Has anybody tried as
the combinational logic which I am refering here.Is it practically
feasibly to do like this.

Mohammed A khader.
 
Tim Hubberstey wrote:

As a very simple example, consider this example code:

type state_vector is (state1,state2,state3,state4);
...
case state_vector is
when state1 => state_vector <= state2;
when state2 => state_vector <= state3;
when state3 => state_vector <= state4;
when state4 => state_vector <= state1;
end case;

Without any safety logic, this translates to the following logic (use
fixed-space font to view):

+- state1 +- state2 +- state3 +- state4
| | | |
+---[d FF1 q]-+-[d FF2 q]-+-[d FF3 q]-+-[d FF4 q]-+-+
| |
+---------------------------------------------------+
Click to expand...
Well said.
If this example were redone with binary encoding, illegal
states would return to zero.

-- Mike Treseler
 
If your inputs and your clock are correct, you never have to worry....

Now try real life, with clocks that may get turned on and off. Add
excessive jitter. Any stray 'event' that causes the state machine to enter
the 'twilight zone.'

Don't bet that the big guys don't do it when the circumstances demand
automatic recovery from an errant condition.

Jason

"Weng Tianxiang" <wtx@umem.com> wrote in message
news:1106587916.440784.84130@c13g2000cwb.googlegroups.com...
Never do anything like adding fail-save conditions for a state machine.
You just waste your time.

Intel, AMD never do it. Professtionals never do it. Why? If your logic
is correct, you don't have to worry about any unsafe conditions.

Weng
Click to expand...
 
Mike Treseler worte:
The basis for one-hot encoding is that it might save some gates.
However when you add the fail-safe requirement to a one-hot
machine, this savings (if there really is any) goes out the window.

Another twist that synthesis may optimize out the "WHEN others" logic
in any case.
Consider binary encoding.
Click to expand...
Thank you very much Mike. I have considered your suggestion but now I
have much similar problem to ask in in Binary Encoding..
Following is the excerpt from the synopsys
documentation...................

" Designers using VHDL often create an enumerated type for their FSM,
as shown in
the following example:

type state_type is (IDLE, S1, S2, S3,S4);
signal state, next_state : state_type;
begin
process (state, NEXT)
begin
next_state <= state;
case state is
when IDLE =>
if (NEXT) then
next_state <= S1;
end if;
when S1 =>
if (NEXT) then
next_state <= S2;
end if;
when S2 =>
if (NEXT) then
next_state <= S3;
end if;
when S3 =>
if (NEXT) then
next_state <= S4;
end if;
when S4 =>
if (NEXT) then
next_state <= IDLE;
end if;
end case;
end process;

In this example, the behavior for each of the enumerated states is
described.
However, when this code is synthesized to hardware, there will be three
remaining states in which the FSM can potentially get stuck. Using
"when
others" is not sufficient by itself to prevent problems in this
situation,
because no other enumerated states exist for this type. Consequently
dummy
states must be created to make the FSM fail-safe.

Dummy States Example

type state_type is (IDLE, S1, S2, S3, S4, S5_dummy, S6_dummy,
S7_dummy);
signal state, next_state : state_type;
begin
process (state, NEXT)
begin
next_state <= state;
case state is
when IDLE =>
if (NEXT) then
next_state <= S1;
end if;
when S1 =>
if (NEXT) then
next_state <= S2;
end if;
when S2 =>
if (NEXT) then
next_state <= S3;
end if;
when S3 =>
if (NEXT) then
next_state <= S4;
end if;
when S4 =>
if (NEXT) then
next_state <= IDLE;
end if;
when others =>
next_state <= "IDLE";
end case;
end process;

Design Compiler will report that these dummy states are unreachable
because
there are no transitions into them, but the transition logic from the
dummy
states back to the useful states will still be synthesized.
Fortunately, Design
Compiler doesn't automatically remove the unreachable dummy states.
However,
when an FSM optimization command such as fsm_enable_state_minimization
is used,
these unreachable states are optimized away. Therefore, to build a
fail-safe
FSM, do not use the FSM optimization capability."

Now I would like to ask that if a design has 17 legal states then do
I have to follow the same guidelines and create additional 15 dummy
states to accomplish fail-safe requirments. Or do we have any other
better technique for this.

Thanks..
-- Mohammed A khader.
 
Clyde R. Shappee wrote:

Pieter Hulshoff wrote:

Mohammed A khader wrote:

But if I implement that then the function for next state becomes as
many states as my fsm is having.



Actually, with one hot I would expect the others branch to contain way
more
states than your fsm. Not that this matters of course, since your
compiler
should handle that for you. What exactly are your reasons for wanting a
one-hot fsm?


Do we have any technique to detect an illegal state while making the
fsm as one-hot.



I'd leave that to the compiler; in general they're a lot better at
reducing
logic than you or I.

Regards,

Pieter Hulshoff

As mentioned earlier many compilers optimise out the when others choice.

If one really wants one hot, it is really easy to guard against a
failure. If the machine fails the next state logic will transisition
to all state bits as a zero. So, I always code the others case and one
I call "hung" to transition from an all zero case to whatever state I
want the machine to recover to.
Click to expand...
This is not sufficient. Noise and/or timing issues are just as likely to
result in a 2-or-more-hot state as in the 0-hot state you are covering.
See
<http://groups.google.ca/groups?hl=en&lr=&selm=3FC2E205.A635F699%40no.spam>
where this has been covered previously.
--
Tim Hubberstey, P.Eng. . . . . . Hardware/Software Consulting Engineer
Marmot Engineering . . . . . . . VHDL, ASICs, FPGAs, embedded systems
Vancouver, BC, Canada . . . . . . . . . . . http://www.marmot-eng.com
 
Tim Hubberstey wrote:
Clyde R. Shappee wrote:

Pieter Hulshoff wrote:

Mohammed A khader wrote:

But if I implement that then the function for next state becomes as
many states as my fsm is having.




Actually, with one hot I would expect the others branch to contain
way more
states than your fsm. Not that this matters of course, since your
compiler
should handle that for you. What exactly are your reasons for wanting a
one-hot fsm?


Do we have any technique to detect an illegal state while making the
fsm as one-hot.




I'd leave that to the compiler; in general they're a lot better at
reducing
logic than you or I.

Regards,

Pieter Hulshoff

As mentioned earlier many compilers optimise out the when others choice.

If one really wants one hot, it is really easy to guard against a
failure. If the machine fails the next state logic will transisition
to all state bits as a zero. So, I always code the others case and
one I call "hung" to transition from an all zero case to whatever
state I want the machine to recover to.


This is not sufficient. Noise and/or timing issues are just as likely to
result in a 2-or-more-hot state as in the 0-hot state you are covering.
See
http://groups.google.ca/groups?hl=en&lr=&selm=3FC2E205.A635F699%40no.spam
where this has been covered previously.
A two or more hot state will then transisiton to the all zeros case, and
Click to expand...
as I propose, the machine would recover. It just takes two illegal
states before the machine recovers. Maybe not what you desire, but it
recovers.

Clyde
 
You must log in or register to reply here.

Welcome to EDABoard.com

Sponsor

Back
Top