MAPLD2004: Session D -- Logic Design and Processors

Topic: PLD Failures, Analyses, and the Impact on Systems

Title: Automated FSM Error Correction for Single Event Upsets

Authors: Nand Kumar & Darren Zacher, Mentor Graphics

Keywords: FSM, FPGA, error correction, fault tolerant, Hamming code, TMR,
encoding, synthesis, PLD, programmable logic

Abstract:

FPGAs are increasingly being used for mission-critical applications in hazardous
operating environments (space, military, medical etc.). In these applications the
circuit must be fault-tolerant, especially finite state machines (FSMs), where
failures are very hard to detect [1]. Most single-fault-tolerant FSMs are
implemented using triple module redundancy (TMR) or by using a single-errorcorrecting
(SEC) code during state encoding [6, 7]. Typical instances of SEC
employ a minimal encoding (binary, Gray etc.) scheme to force a Hamming [2]
distance of three. Commercially available FPGA synthesis tools [8, 9] only
implement error recovery to a specified recovery state. They do not implement
error correction. In this paper, we investigate a general technique of adding
Hamming error checking bits to any encoding style of FSMs to automatically
recover from single event upsets (SEUs) within the same clock cycle. We shall
report on the efficacy of this method to correct single-bit errors and detect two-bit
errors. Area and delay results of using this technique on selected designs are
also explored.



References:

[1] S. Leveugle, L. Martinez, “Design methodology of FSMs with intrinsic fault
    tolerance and recovery capabilities,” IEEE Proc. EuroASIC’92, 1992, pp. 
    201 – 206.

[2] R.W. Hamming, “Error Detecting and Error Correcting Codes,” The Bell
    System Technical Journal, Vol. 29, April 1950, pp. 147 – 160.

[3] D.B. Armstrong, “A general method of applying error correction to
    synchronous digital systems,” The Bell System Technical Journal, Vol. 40, No. 2,
    March 1961, pp. 577 – 593.

[4] J.F. Meyer, “Fault-tolerant sequential machines,” IEEE Trans. On Computers,
    Vol. C-20, No. 10, October 1971, pp. 1167 – 1177.

[5] R Leveugle, “Optimized state assignment of single fault tolerant FSMs based
    on SEC codes,” Proc. 30th DAC, 1993, pp. 14 – 18.

[6] C. Bolchini, R. Montandon, F. Salice, and D. Sciuto, “A State Encoding For
    Self-Checking Finite State Machines,” Proceedings of the ASP-DAC '95/CHDL
    '95/VLSI '95., IFIP International Conference on Hardware Description
    Languages; IFIP International Conference on Very Large Scale Integration.,
    Asian and South Pacific, 1995, pp. 711 – 716.

[7] R. Rochet, R. Leveugle, and G. Saucier, “Analysis and Comparison of Fault
    Tolerant FSM Architecture Based on SEC Codes,” Proc. IEEE International
    Workshop on Defect and Fault Tolerance in VLSI Systems, 1993, pp. 9 – 16.

[8] Precision™ Synthesis Reference Manual, Mentor Graphics Corp. 2004.

[9] Synplify Pro™ Reference Manual, Synplicity Inc. 2003.

[10] Z. Kohavi, Switching and Finite Automata Theory, McGraw-Hill Book
    Company.