Q: state encoding in FSM for simple cases ?

"Michel Billaud" schrieb im Newsbeitrag news: snipped-for-privacy@serveur5.labri.fr...

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

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.

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

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

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

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.

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.

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

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

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" 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

By changing a synthesis option setting. The state type is just an enumeration. See:

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