FPGA Central

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 [email protected]
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" <[email protected]> schrieb im Newsbeitrag
news:[email protected]..

> 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" <[email protected]> wrote in message
news:[email protected]..
>
> 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 [email protected]
> 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)

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

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,

How? Suppose I have a one-hot SM with 32 states. The only good way
I've found so far to detect illegal states takes 29 LUTs. Basically I
have a first level of six blocks that each take four inputs and produce
a two-bit output that encodes whether there were 0, 1, or more than 1
input high. Those take two LUTs each. Then there are three more levels
that take two pairs of encoded bits like that, and produce yet another
encoded pair. The final level only takes one LUT because it only
has to distinguish the "<= 1" and ">1" cases.

There's probably some more clever solution that I've overlooked.

Eric

Eric Smith wrote:
> 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,
>
>
> How? Suppose I have a one-hot SM with 32 states. The only good way
> I've found so far to detect illegal states takes 29 LUTs. Basically I
> have a first level of six blocks that each take four inputs and produce
> a two-bit output that encodes whether there were 0, 1, or more than 1
> input high. Those take two LUTs each. Then there are three more levels
> that take two pairs of encoded bits like that, and produce yet another
> encoded pair. The final level only takes one LUT because it only
> has to distinguish the "<= 1" and ">1" cases.
>
> There's probably some more clever solution that I've overlooked.
>
> Eric
Actually there's a solution with 3 levels of logic and 13 4-LUTs.

jz

Jason Zheng wrote:
> Eric Smith wrote:
>
>> 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,
>>
>>
>>
>> How? Suppose I have a one-hot SM with 32 states. The only good way
>> I've found so far to detect illegal states takes 29 LUTs. Basically I
>> have a first level of six blocks that each take four inputs and produce
>> a two-bit output that encodes whether there were 0, 1, or more than 1
>> input high. Those take two LUTs each. Then there are three more levels
>> that take two pairs of encoded bits like that, and produce yet another
>> encoded pair. The final level only takes one LUT because it only
>> has to distinguish the "<= 1" and ">1" cases.
>>
>> There's probably some more clever solution that I've overlooked.
>>
>> Eric
>
> Actually there's a solution with 3 levels of logic and 13 4-LUTs.
>
> jz
Nevermind, I thought you meant 16 states.

-jz

Jason Zheng wrote:

> 3%? I wonder how you implemented your 1-hot state machine.

By changing a synthesis option setting.
The state type is just an enumeration. See:
http://home.comcast.net/~mike_treseler/uart.vhd
-- Mike Treseler

Mike Treseler wrote:
> Jason Zheng wrote:
>
>> 3%? I wonder how you implemented your 1-hot state machine.
>
>
> By changing a synthesis option setting.
> The state type is just an enumeration. See:
> http://home.comcast.net/~mike_treseler/uart.vhd
> -- Mike Treseler
I'm not a VHDL coder but I read your code and have a feeling that your
VHDL code did not synthesize to an optimal one-hot state machine. In
verilog, there's a synthesis directive called "full-case" which tells
the synthesizer that all the cases are covered and it doesn't need to
generate the default case, which can kill 1-hot performance.