Q: state encoding in FSM for simple cases ?

Hi, I'm discovering the wonderful world of FPGA, so please excuse the
probably stupid question and use of improper terminology.

It seems to be a trivial case of the difficult "state assignment
problem" but i must admit i'm to lazy to read the 199 pages of
http://alexandria.tue.nl/extra2/200413270.pdf now :-/)

There are 2 very simple situations in FSM
1. n-step cycle   S1 -> S2 ->  Sn -> S1 -> S2 -> ....
2. n-step, last is a sink : S1 -> S2 -> Sn -> Sn -> Sn -> Sn ...
that can be easily implemented with counters, binary, gray code,
whatever.

The question is: what's your favorite representation when you
have strong restrictions on the number of gates/FF ?

I guess everybody uses a standard binary counter for large values,
say N>1000) with initial state = 0 and last = N-1, or the other way,
but are there "good practices" for small ones ? 

Michel Billaud

-- 
Michel BILLAUD                  billaud@labri.fr
LABRI-Universit� Bordeaux I     tel 05 4000 6922 / 05 5684 5792
351, cours de la Lib�ration     http://www.labri.fr/~billaud
33405 Talence  (FRANCE)     

"Michel Billaud" <billaud@labri.u-bordeaux.fr> schrieb im Newsbeitrag
news:7zekeupgbe.fsf@serveur5.labri.fr...

> There are 2 very simple situations in FSM
> 1. n-step cycle   S1 -> S2 ->  Sn -> S1 -> S2 -> ....
> 2. n-step, last is a sink : S1 -> S2 -> Sn -> Sn -> Sn -> Sn ...
> that can be easily implemented with counters, binary, gray code,
> whatever.
>
> The question is: what's your favorite representation when you
> have strong restrictions on the number of gates/FF ?

Binary or Gray offer the highest density when it comes to FF count. Using
Toggle-FFs instead of "ordinary" D-FFs can sometimes simplify the next state
encoding logic.

Regards
Falk

Michel Billaud wrote:

> It seems to be a trivial case of the difficult "state assignment
> problem" but i must admit i'm to lazy to read the 199 pages of
> http://alexandria.tue.nl/extra2/200413270.pdf now :-/)

The state assignment "problem" is an academic one.
The average fpga controller, say (idle, start, cook, stop)
has not many states to begin with and playing
with assignments makes very little difference for utilization.

> There are 2 very simple situations in FSM
> 1. n-step cycle   S1 -> S2 ->  Sn -> S1 -> S2 -> ....
> 2. n-step, last is a sink : S1 -> S2 -> Sn -> Sn -> Sn -> Sn ...
> that can be easily implemented with counters, binary, gray code,
> whatever.

Yes, those are counters and are better described
with an n:= n + 1; than a circle and arrow for each count value.
I expect that any counter you come up with
will fit your device.

                -- Mike Treseler

While I agree that theoretically state assignment is a tough problem, yet in 
practice an FPGA designer rarely would need to get involved and can safely 
leave it to the synthesize tool. For small designs it does not really matter 
and for large/critical designs, better synthesize tools like Synplify give 
you the freedom to choose between several possible state assignment 
algorithms and the designer can SEE the quality of the output (in terms of 
the used resources/speed) and decide upon it (Synpfily Pro even tries to do 
this automatically).
I think "generally" it is a bad idea for a designer to try to do the 
state-assignment by hand and would recommend using symbolic names for the 
states and let the synthesize tool do the "dirty" job. Why? First, this is a 
difficult job and for large state-machines can easily get tedious and 
potentially produce bugs. Also, what if you want to port your VHDL code from 
say, Altera to Xilinx or even ASIC? Optimal state assignment can be 
different on different architectures. However, the problem itself is very 
interesting and very IMPORTANT for the synthesize tool designers...

Regards
Arash

"Michel Billaud" <billaud@labri.u-bordeaux.fr> wrote in message 
news:7zekeupgbe.fsf@serveur5.labri.fr...
>
> Hi, I'm discovering the wonderful world of FPGA, so please excuse the
> probably stupid question and use of improper terminology.
>
> It seems to be a trivial case of the difficult "state assignment
> problem" but i must admit i'm to lazy to read the 199 pages of
> http://alexandria.tue.nl/extra2/200413270.pdf now :-/)
>
> There are 2 very simple situations in FSM
> 1. n-step cycle   S1 -> S2 ->  Sn -> S1 -> S2 -> ....
> 2. n-step, last is a sink : S1 -> S2 -> Sn -> Sn -> Sn -> Sn ...
> that can be easily implemented with counters, binary, gray code,
> whatever.
>
> The question is: what's your favorite representation when you
> have strong restrictions on the number of gates/FF ?
>
> I guess everybody uses a standard binary counter for large values,
> say N>1000) with initial state = 0 and last = N-1, or the other way,
> but are there "good practices" for small ones ?
>
> Michel Billaud
>
> -- 
> Michel BILLAUD                  billaud@labri.fr
> LABRI-Universit&#4294967295; Bordeaux I     tel 05 4000 6922 / 05 5684 5792
> 351, cours de la Lib&#4294967295;ration     http://www.labri.fr/~billaud
> 33405 Talence  (FRANCE) 

The basic structure of most FPGAs ( with an abundance of flip-flops)
favors one-hot encoding.
The alleged problem of many illegal states can easily be alleviated
since it is so easy to detect all illegal states, whereas there are no
illegal states in binary encoding. So, in one-hot you know at least
that something went wrong...
Gray is not a real option, since Gray coding only makes sense when the
code sequence is linear, like in a counter. Once you can jump from one
state to either one of several, Gray coding has lost its meaning.
Just my $0.02
Peter Alfke

Peter Alfke wrote:

> The basic structure of most FPGAs ( with an abundance of flip-flops)
> favors one-hot encoding.
> The alleged problem of many illegal states can easily be alleviated
> since it is so easy to detect all illegal states, whereas there are no
> illegal states in binary encoding. So, in one-hot you know at least
> that something went wrong...
> Gray is not a real option, since Gray coding only makes sense when the
> code sequence is linear, like in a counter. Once you can jump from one
> state to either one of several, Gray coding has lost its meaning.

This is broadly correct, but I have coded Gray State engines, where
it is not linear, but there are a very small number of branch choices.

That is because there are a number of Gray solutions, and you have
the freedom to map state-gray.
Too many branches, and it quickly becomes impossible to keep one-bit.

Also, if you are register constrained (CPLDs), you can code in a mix of
Binary and One-Hot/Gray. Use Binary for the 'major' branches, and
Gray for the 'minor' branches.

-jg

Arash Salarian wrote:
> I think "generally" it is a bad idea for a designer to try to do the 
> state-assignment by hand and would recommend using symbolic names for the 
> states and let the synthesize tool do the "dirty" job. Why? First, this is a 
> difficult job and for large state-machines can easily get tedious and 
> potentially produce bugs. Also, what if you want to port your VHDL code from 
> say, Altera to Xilinx or even ASIC? Optimal state assignment can be 
> different on different architectures. However, the problem itself is very 
> interesting and very IMPORTANT for the synthesize tool designers...

I agree that designing the state-transition should be a seperate task 
from the state encoding, and that a good engineer shall focus on the the 
former. However, a good design enigneer shall take in considerations of 
the impacts of different encoding scheme (area, speed, resource use, 
safety, etc) to his/her fsm design.

More synthesizers have automatic fsm exploration built-in, and defaults 
to one or another encoding. It is the design engineer's responsibility 
to know such settings (for example synplicity defaults to 1-hot), 
otherwise you will have no idea what exactly you are designing.

I final suggestion is to design for portability and maintainability, 
while being aware of the subtle differences among the synthesizers.

Peter Alfke wrote:
> The basic structure of most FPGAs ( with an abundance of flip-flops)
> favors one-hot encoding.
> The alleged problem of many illegal states can easily be alleviated
> since it is so easy to detect all illegal states, whereas there are no
> illegal states in binary encoding. So, in one-hot you know at least
> that something went wrong...
That's the entirely true. Binary encoding also have illegal states if 
the number of states is not power of 2. Furthermore, you don't always 
know that something is wrong with 1-hot encoding, e.g. two bits get 
flipped with one being the "hot" bit.

Having said that, I still agree with you that one-hot is very safe and fast.

Peter Alfke wrote:
> The basic structure of most FPGAs ( with an abundance of flip-flops)
> favors one-hot encoding.

You have to try it both ways on each design to be sure.
I have found that one-hot encoding usually improves
speed by about 3% but not always. It can be slower in some cases.
One-hot always costs something in device utilization.
However, I have never seen the choice of encoding
make or break the design fit or timing.

       -- Mike Treseler

Here's a recent benchmark:
-------------------------------------------------------------------------------
begin              -- ___Relative Synthesis Performance virtex2
    template_standard; -- 180 MHz 50 FF   91 LUTS encoding=auto   OK
                       -- 194 MHz 47 FF   84 LUTS encoding=bin MIN LUTS
-------------------------------------------------------------------------------
-- template_s_reset;  -- 222 MHz 50 FF  102 LUTS encoding=auto FAST
                       -- 181 MHz 47 FF   91 LUTS encoding=bin  SMALL
------------------------------------------------------------------------------- 

-- template_trick;    -- 239 MHz 49 FF   92 LUTS encoding=auto  FASTEST
                       -- 184 MHz 46 FF   86 LUTS encoding=bin MIN FLOPS

Mike Treseler wrote:
> Peter Alfke wrote:
> 
>> The basic structure of most FPGAs ( with an abundance of flip-flops)
>> favors one-hot encoding.
> 
> 
> You have to try it both ways on each design to be sure.
> I have found that one-hot encoding usually improves
> speed by about 3% but not always. It can be slower in some cases.

3%? I wonder how you implemented your 1-hot state machine. My benchmark 
with multiple synthetic state designs indicate at least 50% speedup over 
binary.

jz