TDEB Top Bar

Trending
Semiconductor Industry News — The Digital Electronics Blog
Follow Us

TDEB Masthead

The Semiconductor Hub

Semiconductors.  Chips and Systems.  Innovation.

Indexed by leading Search Engines, AI and referenced by Engineers worldwide 500+ Articles 10M+ Pageviews 30+ Reports 50+ Citations

Safe and Unsafe State Machines: FSM Encoding and Illegal States

The Editor's Desk
by
7
Share Facebook X LinkedIn WhatsApp Email

A "safe" state machine is one that cannot get stuck in an undefined state: either every possible value of its state register is a legal state, or the design includes logic that forces any illegal value back to a known state. An "unsafe" state machine has unused encodings with no guaranteed way out, so a glitch, a timing violation, a bad reset or a radiation upset can leave it locked up. Whether an FSM is safe depends on the number of states, the encoding, and how the RTL and synthesis settings handle the unused codes.

Key takeaways

  • With M state flip-flops there are 2M possible codes. If an FSM uses fewer than 2M of them, the rest are illegal states.
  • Binary or Gray encoding with exactly 2M states has no illegal codes, so the machine is "safe" in the sense that it can never be in an undefined state.
  • One-hot always leaves illegal codes (2M minus M of them), so it is unsafe unless recovery logic is added.
  • A default branch in the RTL is not enough on its own: synthesis tools may optimize it away unless a safe-FSM option or attribute is set.
  • Choice of encoding is a trade between flip-flop count, decode logic, power and the ability to recover from upsets.

"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 registers where N = 2M. Because all of the possible state values (or register values) are legal, reachable states, there is no undefined state for the machine to stray into.

That is the structural meaning of safe. Two cautions apply. First, "safe" here means the machine cannot be in an undefined state; an upset can still flip it into a wrong but legal state, so safety-critical designs may add error detection on top. Second, FPGA and ASIC synthesis tools also use "safe" for a tool option that adds recovery logic, covered in the deep dive.

"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 with fully defined states (e.g. one-hot), then the state machine is "unsafe" as it can stray into an undefined state.

Example: a five-state FSM in binary needs 3 flops, giving 8 codes, so 3 codes are illegal. The same FSM in one-hot needs 5 flops, giving 32 codes, so 27 are illegal. In the one-hot case, codes with zero bits set or with two or more bits set are all illegal, and some of them can make the next-state logic hold the machine there forever.

How an FSM reaches an illegal state

  • An asynchronous input sampled without synchronization, so different state bits see different values.
  • A setup or hold violation on the state register, for example from a path that fails timing at a corner.
  • Reset released asynchronously so that some state flops leave reset one cycle before others.
  • A single-event upset from radiation, a concern in space, avionics, automotive and high-reliability systems.
  • Power supply noise or a glitch on the clock.

The three common encodings in plain words

  • Binary: number the states 0, 1, 2 and so on and store the number. Fewest flip-flops, but several bits can change at once and decoding takes more logic.
  • Gray: number the states in Gray-code order so that neighboring states differ in one bit. Same flip-flop count as binary and less switching on sequential steps.
  • One-hot: one flip-flop per state, with exactly one of them set. More flip-flops, but checking which state you are in is just reading one bit.

Why one-hot suits FPGAs

  1. FPGAs have plenty of flip-flops in their logic blocks (CLBs), and one-hot uses them to keep the state decoding simple.
  2. Fewer routing hops are required for decoding, because each next-state equation depends on only a few inputs and fits in one or two lookup tables. This usually means higher clock speed.

This is why FPGA synthesis tools often choose one-hot by default when they extract and re-encode an FSM.

Common mistakes

  • Assuming a default branch survives synthesis without checking the report.
  • Using one-hot in a safety-critical block without any recovery logic.
  • Recovering to IDLE silently when the system needs to know an upset happened; sometimes an error flag or interrupt is the right response.
  • Feeding unsynchronized inputs directly into next-state logic, which is the most common real cause of illegal states.

Interview angle

Interviewers often ask how many illegal states a given encoding has, what happens if a one-hot FSM ends up with two bits set, and whether a default case is enough to make an FSM safe. The strong answer explains the 2M count, gives the recovery approach, and mentions that the synthesis tool needs to be told to preserve it.

FAQ

Is a binary FSM with 8 states always safe?

It has no illegal codes, so it can never be in an undefined state. An upset can still move it to a wrong legal state, which only error detection can catch.

Does a default case make an FSM safe?

In RTL, yes. In the netlist, only if the synthesis tool keeps the logic, which usually needs a safe-FSM attribute or option.

Which encoding uses the least power?

It depends on the transition pattern. Gray is lowest for sequential stepping, one-hot keeps switching at two bits per transition but uses more flops, and binary can be fine for small FSMs. Measure with realistic activity.

Deep dive: the numbers and details

This part holds the encoding details, the comparison table and the Verilog for a recoverable FSM. Skip it if the overview is all you need.

Binary encoding

  1. States are numbered starting from binary 0 and up.
  2. One flip-flop for every bit of the encoded binary number.
  3. States are assigned in binary sequence.

Advantages

  1. Fewest flip-flops: ceil(log2 N) for N states.
  2. Less area, so good for area-constrained circuits.

Disadvantages

  1. More than one bit can flip on a transition (for example 3 to 4 changes three bits).
  2. Getting into an illegal (stale) state is possible when N is not a power of 2.
  3. More complex decoding logic is needed to find the state you are currently in.
  4. More flip-flops toggling at the same time causes more power to be consumed.

Gray encoding

  1. States are numbered from 0 upward in Gray-code order.
  2. One flip-flop for every bit of the encoded Gray code.
  3. Adjacent Gray codes are assigned to adjacent states.

Advantages

  1. Same number of flip-flops as binary.
  2. Only one bit differs between adjacent states, so there is less chance of landing in a wrong state if the transition is sampled mid-change.
  3. Only one flip-flop changes on each transition between adjacent states, so less power is consumed.
  4. Less area, so good for area-constrained circuits.

Disadvantages

  1. Decoding logic is complex.
  2. The single-bit property holds only for transitions between adjacent codes. An FSM that branches or jumps between non-adjacent states will still change several bits on those transitions.

One-hot encoding

  1. One flip-flop for every state rather than one flip-flop for every bit.
  2. Only one flip-flop can be 1 at any time; all others must be 0.

Advantages

  1. Very simple decoding logic: checking for a particular state is as easy as reading the corresponding flip-flop.
  2. Exactly two flip-flops change on every transition (one clears, one sets), so switching in the state register stays low even for large FSMs.

Disadvantages

  1. More flip-flops: N instead of ceil(log2 N).
  2. Many illegal codes, so it needs recovery logic to be safe.

Comparison table

EncodingFlops for N = 5Illegal codesBits changed per transitionDecode
Binary331 to 3Complex
Gray331 between adjacent codesComplex
One-hot527Always 2Simple

The illegal-code count is 2M - N. For one-hot with N = 5, M = 5, so 32 - 5 = 27. For a 16-state machine the gap widens fast: binary needs 4 flops and has 0 illegal codes, while one-hot needs 16 flops and has 65,536 - 16 = 65,520.

Making an unsafe FSM safe

The usual RTL step is a default branch that sends any unused code back to a known state, such as IDLE. The example below is a five-state binary FSM with codes 5, 6 and 7 unused.

// Five-state controller, binary encoded, with explicit recovery
module ctrl_fsm (
  input  wire clk,
  input  wire rst_n,
  input  wire go,
  input  wire ack,
  output reg  busy
);
  localparam [2:0] IDLE = 3'd0, LOAD = 3'd1, RUN = 3'd2,
                   WAIT = 3'd3, DONE = 3'd4;   // codes 5, 6, 7 are unused

  reg [2:0] state, next;

  always @(posedge clk or negedge rst_n)
    if (!rst_n) state <= IDLE;
    else        state <= next;

  always @(*) begin
    next = state;
    case (state)
      IDLE:    if (go)  next = LOAD;
      LOAD:             next = RUN;
      RUN:              next = WAIT;
      WAIT:    if (ack) next = DONE;
      DONE:             next = IDLE;
      default:          next = IDLE;   // recover from 5, 6 or 7
    endcase
  end

  always @(*) busy = (state != IDLE);
endmodule

In simulation, forcing the state register to 6 shows the machine back in IDLE one clock later. In synthesis, though, the tool knows that codes 5 to 7 are unreachable from reset and may remove the recovery logic as redundant, especially if it re-encodes the FSM as one-hot. To keep it, use the tool's safe-FSM control, for example the syn_encoding = "safe" attribute in Synopsys Synplify, the fsm_safe_state attribute in AMD Vivado, or the safe state machine option in Intel Quartus. Alternatively, turn off FSM extraction for that machine so the RTL is built as written. Check the tool documentation for the exact syntax of the version you use, and confirm the result in the synthesis report.

Going further for high reliability

For high-reliability work, designers go further: Hamming-distance-3 encodings so a single bit flip can be detected and corrected, triple modular redundancy (TMR) on the state register, or a parity bit that flags an upset to a supervisor. The cost is easy to count. A five-state FSM with TMR on a 3-bit binary register needs 9 flops plus three majority voters, still fewer flops than some wide one-hot machines, while a single parity bit adds one flop and an XOR tree that detects any single-bit upset but cannot correct it.

The Editor's Desk
About the Author
The Editor's Desk
Share Facebook X LinkedIn WhatsApp Email

Post a Comment

7 Comments

Your comments will be moderated before it appears here.

  1. asynchronous 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.
    BTW, "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.

    ReplyDelete
  2. 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".

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

    ReplyDelete
  3. Interesting discussion...
    Yesterday 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.

    ReplyDelete
  4. Hamming 3 is the best type of encoding :-)

    ReplyDelete
  5. check this out.

    http://asics.chuckbenz.com/detailed_one_hot.htm

    ReplyDelete
  6. Gray is good for low-power applications where consecutive data values typically differ by 1 (e.g.
    no 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.

    ReplyDelete
Post a Comment

#buttons=(Ok, Go it!) #days=(20)

Our website uses cookies to enhance your experience. Learn more
Ok, Go it!