0
\$\begingroup\$

I'm currently studying finite-state machines at my university and the topic of state assignment optimization came up today. Apparently there are several technique for finding the correct state assignment for a FSM, but the overall approach is based on heuristic methods invented by Humphrey ("rules for state code adjacency").
While reading some papers on the subject, it seems to me that doing this by hand could prove very difficult, but apparently that's how they expect us to do it at my university.
How should I proceed while assigning states in an FSM? Is there a standard technique/strategy people use today? Or is everything done by CAD tools?

\$\endgroup\$
1
  • 1
    \$\begingroup\$ You're correct in that, for the most part, the CAD tools (VHDL, Verilog, synthesis) takes care of that for you. It's more of a academic exercise nowadays. Back when I was in school, I had a whole course in Finite State Machine Theory. Never used any of that material even once in over 53 years. \$\endgroup\$
    – SteveSh
    Dec 7, 2021 at 11:46

1 Answer 1

2
\$\begingroup\$

The two extremes are binary coded, and 'one-hot'. The former uses log2(states) latches, the latter uses states latches.

If you want minimum state storage, then binary coded is the way to go. However, if the latches don't transition all at the same time, you may go through illegal states on the way from the start state to the final state. Gray-coding the transitions if possible with your particular sequence of inputs, or partially coding sub-sections, or ensuring that illegal transition states are 'don't cares' are the typical ways to overcome this.

One-hot sounds like more hardware, but it often makes decoding to the next state simpler. It's also easier to debug. Obviously two or more latches on at the same time is illegal, and you have to have similar measures to tolerate or avoid this possibility.

Needless to say, a CAD tool will not handle these considerations, it will only do as it's told. You need therefore to lay out a few FSMs by hand, using both extremes of design, and a few in the middle, seeing how each go wrong in their unique ways, before you have the insight to be able to instruct the CAD tools to 'build me a 'this type' of FSM'.

\$\endgroup\$
2
  • 2
    \$\begingroup\$ It might be worth noting that a lot of CAD tools (Synopsys, Vivado, Quartus etc), especially ones for FPGAs, ignore the user's state encoding entirely and just re-encode all FSMs in whatever way they see fit. It's actually very hard to stop them from doing that. \$\endgroup\$ Dec 7, 2021 at 12:52
  • \$\begingroup\$ There are also "safe state machine" techniques which may or may not be supported by the tools (or may be deliberately architected in the SM) to recover when a transient error (alpha particle?) lands the SM in an illegal state. One-hot provides a 2^N explosion in the number of illegal states (recovery requires detecting no-hot or n-hot (n>1)), while binary provides a more tightly bounded set of illegal states (which I usually daisy chain back to a safe state). Analysis of recovery techniques is not comment material; just be aware it's an issue. \$\endgroup\$
    – user16324
    Dec 7, 2021 at 14:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.