One-hot Coding of State machines

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

Clyde R. Shappee

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 private.php?do=newpm&u=
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 private.php?do=newpm&u=
SynthWorks Design Inc. http://www.SynthWorks.com
1-503-590-4787

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

Jim Lewis

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

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

Peter Hermansson

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

> 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

Mike Treseler

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

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..._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 private.php?do=newpm&u=
SynthWorks Design Inc. http://www.SynthWorks.com
1-503-590-4787

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

Jim Lewis

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

Thomas Stanka

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

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

Peter Hermansson

"Clyde R. Shappee" wrote in message news:<>...

> 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

Mike Treseler