"Safe" State Machines:
If the number of states (N) is a power of 2 and you use a binary or gray-code encoding algorithm, then the state machine is "safe." This ensures that you have M number of registers where N = 2M. Because all of the possible state values (or register statuses) are reachable, the design is "safe."
"Unsafe" State Machines:
If the number of states is not a power of 2, or if you do not use binary or gray-code encoding algorithm with fully defined states (e.g., one-hot), then the state machine is "unsafe" as it can stray into an undefined state.
FSM types and significance in detail:
Binary Encoding:
1. States are numbered starting from binary '0' and above.
2. '1' flip flop for very bit of the encoded binary number.
3. States are assigned in binary sequence.
Adv:
1. Lesser number of flip flops - log(n) for n states.
2. Less area, so good for area constrained circuits.
Dis-Adv:
1. More that '1' bit can flip anytime.
2. Getting into a stale state is possible.
3. Complex decoding logic is necessary to find the state that you are currently in.
4. More number of ff toggling at the same time causes more power to be consumed.
Gray Encoding:
1. States are numbered starting from binary '0' and above in gray style.
2. One flip flop for very bit of the encoded gray code.
3. Assign adjacent gray codes to adjacent states.
Adv:
1. Same number of ff's as binary.
2. Only '1' bit is different for adjacent states, so less chance of getting in to a stale state.
3. Only '1' ff changes at any given time so less power consumed.
4. Less area so good for area constarined circuits.
Dis-Adv:
1. Decoding logic is complex.
One Hot Encoding
1. Only '1' flip flop for every state rather than '1' flip flop for every bit..
2. Only '1' flip flop can be '1' at any time, all others must be '0'.
Adv:
1. Very simple decoding logic, so checking for a particular state is as easy as reading the correspoding ff.
2. '2' ff's change their state every time - less power.
Dis-Adv:
1. More ff's
Suited for FPGAs
1. Uses the ffs in the CLBs for state decoding.
2. Lesser number of routing hops required for decoding.
Post a Comment
7Comments
Your comments will be moderated before it can appear here. Win prizes for being an engaged reader.
Post a Comment
waiting ....
ReplyDeleteasynchronous logic It was an elementary intro to state machine encoding. It's not always possible and not necessary to design a state m/c with N = 2^M. With some extra combinatorial logic you can get back to the safe(legal) states in one or two hops.
ReplyDeleteBTW, "one-hot encoding" is not an example of grey-code. In grey-code the sequence of number differ by only one bit position. There can be multiple representation for the same integer. The size of state register is M in this case. Whereas in one-hot encoding only one bit of the state register is set. So the size of the state register has to be 2^M. Since the number of flops used is large, it's only suitable for FPGA systems. The only advantage of this code being that subsequent states maintain a hamming distance of 2. In the event of any radiaton upset, the machine is more likely to be forced to an illegal state and recovery is possible.
The statements made above have a lot of insight. Anybody who designs a state machine should know the difference between a "safe" and "unsafe" methods of designing a state machine. I agree that getting out from an unsafe state is easy but when the # of states is a power of 2 why would anybody go for any other style except binary encoded :-). But when it is not the case you are forced to take up other strategies like "one hot".
ReplyDeleteI never stated that "one-hot" is a "gray code". The sentence means that "one hot" is a style which is neither "gray" nor "binary".
I agree with all your other statements.
Hope that Helps.
Interesting discussion...
ReplyDeleteYesterday i was talking to a co-worker and had similar thoughts on styles of FSM's
Thought i will contribute:
There are numerous advantages to using the one-hot design methodology:
1• One-hot state machines are typically faster. Speed is independent of the number of states, and instead depends only on the number of transitions into a particular state. A highly-encoded machine may slow dramatically as more states are added.
2• Don’t have to worry about finding an "optimal" state encoding. This is particularly beneficial as the machine design is modified, for what is "optimal" for one design may no longer be best if you add a few states and change some others. One-hot is equally "optimal" for all machines.
3• One-hot machines are easy to design. Schematics can be captured and HDL code can be written directly from the state diagram without coding a state table.
4• Modifications are straightforward. Adding and deleting states, or changing excitation equations,
can be implemented easily without affecting the rest of the machine.
5• Easily synthesized from VHDL or Verilog.
6• There is typically no area penalty over highlyencoded machines.
7• Critical paths are easy to find using static timing analysis.
8• Easy to debug. Bogus state transitions are obvious, and current state display is trivial.
Hamming 3 is the best type of encoding :-)
ReplyDeletecheck this out.
ReplyDeletehttp://asics.chuckbenz.com/detailed_one_hot.htm
Gray is good for low-power applications where consecutive data values typically differ by 1 (e.g.
ReplyDeleteno random jumps).
One-hot usually has less combinational logic and runs faster than binary for machines with up
to a dozen or so states. With more than a dozen states, the extra flip-flops required by one-hot
encoding become too expensive.
Custom is great if you have lots of time and are incredibly intelligent, or have deep insight into
the guts of your design.