One-hot Coding of State machines

[Clyde R. Shappee]

Hello, all,

I am having a dialog with a co-worker regarding state machine encoding.

We need to implement a synthesizer imdependant method of coding a state
machine so that if an illegal state has been entered, the machine will
always recover.

My associate insists that One-hot will always do it, and that the coding
style should be like that presented in the Ashenden text. This person
also claims that the "when others" clause in a case statement makes no
guarantees that fail safe logic will be generated.

Remember our requirement that it be synthesis tool independent.

I believe that one-hot is likely to be inherently faster, and less prone
to timing problems, but not a cure all.

I futher believe that with no fail safe logic, a one-hot machine will
fail if two bits are set.

I maintain that the only way to accomplish this goal is to specify every
single illegal state in the case statement, branching to the reset
state, or use a chain of if-then-elsif..... end if with the last block
specifying a branch to the reset state.

Your thoughts?

Clyde

 

[Jim Lewis]

Clyde,
I agree with your position.

Your goal of safe logic is in conflict with a synthesis
tools default goal of small, fast logic. To reach this
goal many of the synthesis tools ignore the fact that
you may have specified recovery logic in the default
statement.

I think you need two things to make sure your statemachine is
safe. First you need a state encoding with a hamming distance
of at least two (takes two bit flips to be in another legal
state), and you need the error recovery logic for handling
the error states and signaling the error. It is not intuitive
that the synthesis tool ignores your recovery statements,
so misunderstandings are only natural.

One hot statemachines have a hamming distance of 2, however,
the recovery logic can be expensive and you may need to
use synthesis tool specific attributes to force the tool
to maintain the recovery logic.

1076.6-2004 (VHDL RTL synthesis standard), specifies
attributes for specifying enumerated values and an attribute
for specifying that the synthesis tool is to create a
safe statemachine. For example (from the standard):

type StateType is (S0, S1, S2, S3, S4);
signal state, next: StateType;
attribute FSM_STATE of state : signal is
"0000 0011 0110 1100 1001" ;
attribute FSM_COMPLETE of state : signal is TRUE;
. . .
StateProc : process
begin
wait until Clk = '1' ;
if nReset = '0' then
state <= S0
else
case state is
when S0 => state <= S1;
when S1 => state <= S2;
when S2 => state <= S3;
when S3 => state <= S4;
when S4 => state <= S0;
when others => state <= S0;
end case;
end if ;
end process;

In the example above, the VHDL specification contains five
state values: S0, S1, S2, S3, and S4.
FSM_STATE specifies the encoding to be a four bit array
with S0 = 0000, S1 = 0011, S2 = 0110, S3 = 1100, and S4 = 1001.
The implementation contains 2**4 states = 16.
There are eleven states in the implementation that are not part of
the VHDL specification.
Since FSM_COMPLETE is true, the transition for the eleven unused
states is the the state specified in the others clause.


I don't know where synthesis tool vendors are on supporting this.
The draft was just approved recently. In general support of
a standard by EDA vendors is an investment. They only make
the investment if there is demand (request) for the feature.
So if these type of features interest you, ask your vendor to
support them. Most already support their own flavor of these
attributes so they already have the capability - it is just
a matter of getting them to support a standard set of features.

Best Regards,
Jim

Hello, all,

I am having a dialog with a co-worker regarding state machine encoding.

We need to implement a synthesizer imdependant method of coding a state
machine so that if an illegal state has been entered, the machine will
always recover.

My associate insists that One-hot will always do it, and that the coding
style should be like that presented in the Ashenden text. This person
also claims that the "when others" clause in a case statement makes no
guarantees that fail safe logic will be generated.

Remember our requirement that it be synthesis tool independent.

I believe that one-hot is likely to be inherently faster, and less prone
to timing problems, but not a cure all.

I futher believe that with no fail safe logic, a one-hot machine will
fail if two bits are set.

I maintain that the only way to accomplish this goal is to specify every
single illegal state in the case statement, branching to the reset
state, or use a chain of if-then-elsif..... end if with the last block
specifying a branch to the reset state.

Your thoughts?

Clyde

--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Jim Lewis
Director of Training mailto:Jim@SynthWorks.com
SynthWorks Design Inc. http://www.SynthWorks.com
1-503-590-4787

Expert VHDL Training for Hardware Design and Verification
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

 

[Jim Lewis]

Clyde,
On second thought, a purely VHDL way of handling
this is shown belwo. You loose the enumerated type.
For simulation debugging you can always write a process
that translates from the constants to an enumerated type
(since it has no outputs, no logic will be created).

Also since state is not an output, I have some concerns
that it may be possible for the synthesis tool to recognize
this as a statemachine and optimize away you carefully
planned hamming distance.


subtype StateType is std_logic_vector(3 downto 0) ;
constant S0 : StateType := "0000" ;
constant S1 : StateType := "0011" ;
constant S2 : StateType := "0110" ;
constant S3 : StateType := "1100" ;
constant S4 : StateType := "1001" ;
signal state : StateType ;

. . .
StateProc : process
begin
wait until Clk = '1' ;
if nReset = '0' then
state <= S0
else
case state is
when S0 => state <= S1;
when S1 => state <= S2;
when S2 => state <= S3;
when S3 => state <= S4;
when S4 => state <= S0;
when others => state <= S0;
end case;
end if ;
end process;

Perhaps someone else will chime in with something
different.

Cheers,
Jim
--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Jim Lewis
Director of Training mailto:Jim@SynthWorks.com
SynthWorks Design Inc. http://www.SynthWorks.com
1-503-590-4787

Expert VHDL Training for Hardware Design and Verification
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

 

[Peter Hermansson]

"Clyde R. Shappee" <cshappee_remove_@ieee.org> wrote in message news:<c9j8j8$qno$1@pcls4.std.com>...

Hi,

My only experience is with Synplify and according to the application
note "Designing Safe VHDL State Machines with Synplify", the "others"
clause is no guarantee that fail-safe logic is generated. The "safe"
attribute may be used to generate fail-safe logic, but not necessarily
to the state specified after the "others" clause....

If you must have an "exakt" behaviour of your machine (recovering to
the state after the "others" clause), I believe you must use constants
when you specify your states. I also believe that you must be careful
with your synthesis options, turning off the FSM compiler. A "clever"
synthesis program may think that your "unreachable" states may be
removed, optimizing for area.


/Peter

 

[Mike Treseler]

"Clyde R. Shappee" <cshappee_remove_@ieee.org> wrote in message news:<c9j8j8$qno$1@pcls4.std.com>...

I futher believe that with no fail safe logic, a one-hot machine will
fail if two bits are set.

This is the heart of the issue.
A "safe" one-hot machine will recover
because the "when others" logic covers
not just the n+1 legal one-hot states,
but all -1+2**n possible state bit
combinations.

Since state machines have so many side issues,
lets talk about a "safe" counter.
If I design a safe rollover counter covering 0000 to 1001,
it would be unacceptable for it to stick at
any other forced value.
If the a value 1010 to 1111 somehow
occurred, the count should return to zero on
the next clock.

Does your synthesis do the right thing for "when others"?
You have to try it and see to be sure. Some provide
a synthesis setting for safe or unsafe. Others
don't talk about it at all.

You can certainly improve your odds by specifying
binary or "minimal bits" encoding for enumerations.
A one-hot encoding requires extra logic to be safe.
A binary encoding requires extra logic to be unsafe.

I maintain that the only way to accomplish this goal is to specify every
single illegal state in the case statement, branching to the reset
state, or use a chain of if-then-elsif..... end if with the last block
specifying a branch to the reset state.

Yes, doing your own enumeration encoding will work
without knowing anything about the synthesis tool.
The downside is that you have to watch out for
duplicate assignments.

For me, it's worth a little synthesis research
and fiddling with synthesis settings
to be able to ignore the encoding details

--Mike Treseler

 

[Clyde R. Shappee]

Hi, Mike,

I agree with you that one should explore the synthesis tool... and on
any other job I have had I would do just that and let it be. Synplify
has a nice check box for "safe" state machines.

Unfortunately, I must be tool independant, perhaps allowing for a
recompile several years down the road.

I have thought about this some more. When I did gate level design, I
invariably used any coding scheme that I wanted, typically binary and it
always started out with a zero state.

I realize now that the next state logic in a one-hot state machine will
fail if given given a code outside of the legal set, and indeed, it
will fail by transitioning to state "00000" or however many zeros fit
the width. What is needed then, is a transition from "00000" to "00001"
assuming "00001" is the idle state. Ok, 2 transitions, but it makes
one-hot safe.

What I think I have just proven now, is that if one uses binary, and
"00000" is the idle state, then it is inherently safe.

I am mandated on this design to use one-hot, so I will try and simulate
my method above and see how it works.

Clyde

Mike Treseler wrote:

"Clyde R. Shappee" <cshappee_remove_@ieee.org> wrote in message news:<c9j8j8$qno$1@pcls4.std.com>...


I futher believe that with no fail safe logic, a one-hot machine will
fail if two bits are set.


This is the heart of the issue.
A "safe" one-hot machine will recover
because the "when others" logic covers
not just the n+1 legal one-hot states,
but all -1+2**n possible state bit
combinations.

Since state machines have so many side issues,
lets talk about a "safe" counter.
If I design a safe rollover counter covering 0000 to 1001,
it would be unacceptable for it to stick at
any other forced value.
If the a value 1010 to 1111 somehow
occurred, the count should return to zero on
the next clock.

Does your synthesis do the right thing for "when others"?
You have to try it and see to be sure. Some provide
a synthesis setting for safe or unsafe. Others
don't talk about it at all.

You can certainly improve your odds by specifying
binary or "minimal bits" encoding for enumerations.
A one-hot encoding requires extra logic to be safe.
A binary encoding requires extra logic to be unsafe.


I maintain that the only way to accomplish this goal is to specify every
single illegal state in the case statement, branching to the reset
state, or use a chain of if-then-elsif..... end if with the last block
specifying a branch to the reset state.


Yes, doing your own enumeration encoding will work
without knowing anything about the synthesis tool.
The downside is that you have to watch out for
duplicate assignments.

For me, it's worth a little synthesis research
and fiddling with synthesis settings
to be able to ignore the encoding details

--Mike Treseler

 

[Jim Lewis]

Clyde,
See the Synplicity application note on designing safe VHDL
statemachines. Based on this, I don't think any code alone
is enough.

http://www.synplicity.com/literature/pdf/designing_safe_vhdl.pdf

A final note, don't do one hot if you want small recovery logic.
Do a hamming distance of 2. For n-bits a hamming code will give
you 2**(n-1) states.

I have to rethink this now. When I did gate level design, I
invariably used any coding scheme that I wanted, typically
binary and it always started out with a zero state.

Thats because the statemachine tools back then were wimpy.
The default values in statemachine synthesis tools now is
intended to show that one synthesis tool is better than their
competition.

I realize now that the next
state logic in a one-hot state machine will fail if given given a code outside
of the legal set, and indeed, it will fail by transitioning to state "00000"
or however many zeros fit the width. What is needed then, is a transition
from "00000" to "00001" assuming "00001" is the idle state. Ok, 2
transitions, but it makes one-hot safe.

What I have just proven now, is that if one uses binary, and "00000" is the
idle state, then it is inherently safe.

Do you agree with this?

No. It can also illegally transition to state "00011".

/\/\/\/\/\

Ultimately my problem lies in the fact that I have to design for a
synthesis tool that does not exist today, but maybe 10 years down
the road..... No guarantees on what it will do.

The only real way to solve this problem long term
is to get synthesis tools to support a standard set of
attributes that convey the intent of what designers want.
This is part of the purpose of 1076.6. Make sure to
lobby your synthesis tool vendor to support it.

Cheers,
Jim
P.S.
Your synthesis guru should be helping us with the VHDL
standards. Have them go to:

See http://www.eda.org/vhdl-200x

Yes I am recruiting for the standards group,
volunteers are hard to come by.

P.P.S
Your email is bouncing
--
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Jim Lewis
Director of Training mailto:Jim@SynthWorks.com
SynthWorks Design Inc. http://www.SynthWorks.com
1-503-590-4787

Expert VHDL Training for Hardware Design and Verification
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

 

[Thomas Stanka]

Hi,

"Clyde R. Shappee" <cshappee_remove_@ieee.org> wrote:

I am having a dialog with a co-worker regarding state machine encoding.

We need to implement a synthesizer imdependant method of coding a state
machine so that if an illegal state has been entered, the machine will
always recover.

My associate insists that One-hot will always do it, and that the coding
style should be like that presented in the Ashenden text. This person
also claims that the "when others" clause in a case statement makes no
guarantees that fail safe logic will be generated.
Remember our requirement that it be synthesis tool independent.

I don't think there is a "safe" coding style for FSM that is tool
independent.
Synplify will mix up your design when not using constants for each
state and using a lot of attributes. The Synplify options for safe Fsm
are a pain, because they introduce extra registers without reason, so
you had trouble verifying your netlist with equivalence checking.
For Synopsys I would just check if you have 2^n encoded states and the
Others clause set.

I believe that one-hot is likely to be inherently faster, and less prone
to timing problems, but not a cure all.
I futher believe that with no fail safe logic, a one-hot machine will
fail if two bits are set.

Yes. And maybe even worse if all (or no) ff are set.

I maintain that the only way to accomplish this goal is to specify every
single illegal state in the case statement, branching to the reset
state, or use a chain of if-then-elsif..... end if with the last block
specifying a branch to the reset state.

This seems good and _should_ do for every synthesis tool, but will
unfortunately fail with Synplify (one reason why I hate this tool).

bye Thomas

 

[Peter Hermansson]

"Clyde R. Shappee" <cshappee_remove_@ieee.org> wrote in message news:<c9j8j8$qno$1@pcls4.std.com>...

One idea - which I have not tried - is to use binary encoding to
minimize the number of invalid states and to put all unused states in
a chain, with a branch to the reset state from the last state.
To prevent these states from being optimized away, a branch to the
first state in the chain must be specified from somewhere in the
machine. This particular branch condition shall never occur e.g. input
signal patterns that never exist.
Its just an idea....

/Peter

 

[Mike Treseler]

"Clyde R. Shappee" wrote in message news:<40BE723F.20900@ieee.org>...

I have thought about this some more. When I did gate level design, I
invariably used any coding scheme that I wanted, typically binary and it
always started out with a zero state.

Me too, and I expect that synthesis with binary encoding
works about the same.

I realize now that the next state logic in a one-hot state machine will
fail if given given a code outside of the legal set, and indeed, it
will fail by transitioning to state "00000" or however many zeros fit
the width. What is needed then, is a transition from "00000" to "00001"
assuming "00001" is the idle state. Ok, 2 transitions, but it makes
one-hot safe.

Half safe. Better cover more_than_one_hot also.

What I think I have just proven now, is that if one uses binary, and
"00000" is the idle state, then it is inherently safe.

For binary, I agree. A transition to states other than zero requires
a state decode anded with an input function for each hot bit in
the destination state. Transitions to zero are free with d-flops.

I am mandated on this design to use one-hot, so I will try and simulate
my method above and see how it works.

Good luck.

-- Mike Treseler

 

[Wallclimber]

First of all, how do you define the term 'recover'? If it enters an
invalid state, do you want to jump to the idle state or to the state
that has the closest encoding distance to the current state vector?
Let's assume that you want the first...

I maintain that the only way to accomplish this goal is to specify every
single illegal state in the case statement, branching to the reset
state, or use a chain of if-then-elsif..... end if with the last block
specifying a branch to the reset state.

I don't think it's necessary to specify every single illegal state. In
my opinion, the case statement with an 'others' will work, without any
need for attributes, if you don't use enumerated types and you
handcode the valid states. That is:

signal State : std_ulogic_vector(5 downto 0);

constant c_Idle : std_ulogic_vector(5 downto 0) := "00001";
constant c_State1 : std_ulogic_vector(5 downto 0) := "00010";
constant c_State2 : std_ulogic_vector(5 downto 0) := "00100";
constant c_State3 : std_ulogic_vector(5 downto 0) := "01000";
constant c_State4 : std_ulogic_vector(5 downto 0) := "10000";

case State is
when c_Idle => ...
when c_State1 => ...
when others => State <= c_Idle;
end case;

My only concern with this code is that a synthesizer tool might
recognize the fact that there is no legal way in which State gets ever
assigned a value that is not valid and that it would optimize the
'others' case away as a result. In that case, one could work around
this by adding this code

if LoadState='1' then
State <= ExternalInput;
end if;

Even if LoadState is never really used.

This is, admittedly, a VERY ugly contraption, but if you really want
to have it tool independent it may be the only way to go.

When you use enumerated types instead (and, again, don't want to use
attributes), then there is indeed no guarantee that the 'when others'
will be implemented for non-defined combinations. (I did try this long
ago with Synopsys and the others statement was simply ignored.)

Note that, in the example above, I have used one-hot encoding, but it
doesn't really matter in this case.

Tom Verbeure