one-hot encoding and fale-safe condition.

M

Mohammed A khader

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.
 
M

Mike Treseler

Mohammed said:
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.

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
 
W

Weng Tianxiang

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
 
J

jtw

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
 
P

Pieter Hulshoff

Mohammed said:
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
 
M

Mohammed A khader

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.

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.
 
M

Mike Treseler

Mohammed said:
Thank you very much Mike. I have considered your suggestion but now I
have much similar problem to ask in in Binary Encoding..

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
 
T

Tim Hubberstey

Clyde said:
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=&[email protected]>
where this has been covered previously.
 
C

Clyde R. Shappee

Pieter said:
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?




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.

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

Clyde
 
C

Clyde R. Shappee

Tim said:
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=&[email protected]>
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.

Clyde
 
T

Tim Hubberstey

Clyde said:
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.

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.
 
M

Mohammed A khader

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.

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.
 
M

Mike Treseler

Tim said:
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]-+-+
| |
+---------------------------------------------------+

Well said.
If this example were redone with binary encoding, illegal
states would return to zero.

-- Mike Treseler
 

Ask a Question

Want to reply to this thread or ask your own question?

You'll need to choose a username for the site, which only take a couple of moments. After that, you can post your question and our members will help you out.

Ask a Question

Members online

No members online now.

Forum statistics

Threads
473,769
Messages
2,569,582
Members
45,062
Latest member
OrderKetozenseACV

Latest Threads

Top