NASA Office of Logic Design

NASA Office of Logic Design

A scientific study of the problems of digital engineering for space flight systems,
with a view to their practical solution.


Please e-mail comments and suggestions for these guidelines and criteria.

Design Guidelines and Criteria

for

Space Flight Digital Electronics

Finite State Machines

Finite state machine design can become a religious issue.  What is the best style for a finite state machine?  Should the human or the machine perform state assignment?  How do we design safe finite state machines?  There is no best answer for all situations and there is no magical style to be checked.  It does, however, have to follow the basic principles of good logic design.  It is noted that many engineers now use HDLs to design the state machine and never see the logic.  This must be done with extreme care for critical applications.

Some design guidelines for high-reliability circuits mandate that one-hot state machines not be used since the larger number of flip-flops increase the probability of an SEU.  While true, a careful analysis of the state machines shows that the one-hot topology has a Hamming distance of 2, making all single bit errors detectable.  By comparison, an equivalent binary coded state machine has a Hamming distance of 1 and, while not having any lockup states if all 2n states are used, you can not detect illegal transitions without an extra checking mechanism, which itself will be subject to SEUs and together will have lockup states.

A.1 Strategy and Analysis of Lockup States - Schematic-based machines: For critical state machines, the analysis must cover all possible logic states and demonstrate that the machine behaves in a deterministic and desired fashion.  The analysis must consider off-nominal events.  One such example is an SEU, a credible failure mode.  Finite state machines in many consumer-grade IC's do have lockup states, such as SDRAMs.  For critical controllers this is not acceptable.  Analysis should include all possible 2n states.  It is a credible failure mode to be in any of these states as a result of a disturbance on the power bus, an ESD event, etc.  Any high reliability machine must be robust under all credible failure modes.  Additionally, one must ensure that the FSM starts out in a legal state and than transitions through the desired sequences.  One method is to use a power-on reset (POR) indicator.  This must be checked to ensure that it is synchronous with the clock.  It is not necessary to have the POR go into the asynchronous or reset input of every flip-flop.  Indeed, this is often undesirable as it increases the load on the reset signal distribution and makes it tougher to meet removal times for all flip-flops in high-speed circuits.  Indeed, one may not need any reset for a finite state machine if it can be shown to always go into a desired state.  This can be done in the trivial case of a divide by n master counter, for example, where a reset is not needed and a fault on the reset line can halt the machine.  Another technique is to gate the inputs with the POR signal and design an FSM such that it is guaranteed to go into a hold state.  One consideration with the reset function is design-for-test and design-for-simulation, which sometimes results in additional reset connections.

A.2 Strategy and Analysis of Lockup States - HDL Synthesized Machines: Obviously, all of the criteria for schematic-based machines apply.  However, there are special considerations for designing with HDL, as the CAE writer might generate circuits that are not desirable for high-reliable circuits.  Hence, for critical circuits, one must examine the output reports from the synthesizer very carefully.  Common things to check for include: lockup states; outputs of Gray encoded machines that can glitch: unintended flip-flop replication; not implementing the desired and specified style (sometimes the synthesizers just think they know better than the human and will substitute one type of state machine for another).  Additionally, some logic synthesizers will generate "safe" state machines.  Examine the generated design carefully.  For instance, it has been seen that sometimes the logic will explode with excessive gates.  Other times there are resets generated on the opposite edge of the clock resulting in tight timing for the removal of clears which are not visible to the designer.  Note that languages such as VHDL can not cover all physical states, just logical ones.  Hence, the "others" clause will only refer to states in the enumerated type and not the physical realization.  The HDL doesn't know if it is a one-hot or binary or gray coded implementation and what flip-flops have been replicated.  This is not detectable at the black box simulation level nor by Boolean equations for logical equivalence.

 

B. Flip-Flop Replication:

Logic designers often replicate logic for reliability or performance reasons. For example, if the load on an output is too high, then the load will often be split between multiple drivers (in some cases outputs may be joined together but this is not preferred and is usually avoidable). In other cases, cutting the load and duplicating the driver can help make timing by distributing the capacitive load. The replication of combinational logic is quite straightforward.

However, if this concept is extended to sequential logic and finite state machine design then the situation is trickier since state information is involved. Indeed, the logic may present different information to different parts of the circuit and, for example, may be inconsistent in the presence of a trasient fault such as a single event upset, ESD event, etc. That is, the logical flip-flop can present different values to different parts of the circuit depending on which physical flip-flop they connected to. This is a call for caution in high-reliability applications. Software CAE tools are more than happy to generate circuits of this class and do not generate logic to ensure self-consistency.  Examples are given in an application note.

 

C. Error Detection and Correction Requirements and Implementation: It is often tempting to design robust state machines by simply appending a Hamming code and correction circuits.  If you realize that SEUs or ESD events are not synchronized to the system clock and that the logic network is not guaranteed to be glitch free, then you will have second thoughts about the ability of this type of structure to provide robust operation.  In the general case, you must analyze the combinational circuits which implement the next-state logic and their inputs to the flip-flops making up the state register.  In particular, for any of these schemes, you must look at whether or not the circuit implementations are static hazard free and, if not, can an erroneous transition to a state (or set of states) be made.

References, Notes, and Related Documents

  1. For visibility into the operation of the system, debug, and test, bring FSM state flip-flops to spare I/Os and test points.
  2. "Sequential Circuit Design for Spaceborne and Critical Electronics," R. Barto, presented at the 2000 MAPLD International Conference. 
  3. "Logic Design: Clocking, Timing Analysis, Finite State Machines, and Verification," Presented at the 2002 MAPLD International Conference, Laurel, MD, September 9, 2002. 
  4. Flip-Flop Replication.  This application note gives an introduction to the topic and examples.  Cases examined are VHDL synthesis, netlist translation, and backend place and routing.
  5. "XC4000XL/Spartan PAR - Router duplicates registers for use as output-to-output route-thrus,"XL Xilinx answers database #3813.
  6. "Asynchronous & Synchronous Reset Design Techniques - Part Deux"
  7. "Startup Transient," from Advanced Design: Designing for Reliability, 2001 MAPLD International Conference, Laurel, MD, September 10, 2001.
  8. Analysis of POR Circuit Topologies
  9. Discussion of MetastableStates
  10. Timing Analysis of Asynchronous Signals

TOP LEVEL: "Design Guidelines and Criteria for Space Flight Digital Electronics"


Home - NASA Office of Logic Design
Last Revised: February 03, 2010
Digital Engineering Institute
Web Grunt: Richard Katz
NACA Seal