NASA Logo

NTRS

NTRS - NASA Technical Reports Server

Collections About News Help Login
Back to Results
Fault-Tolerant Coding for State MachinesTwo reliable fault-tolerant coding schemes have been proposed for state machines that are used in field-programmable gate arrays and application-specific integrated circuits to implement sequential logic functions. The schemes apply to strings of bits in state registers, which are typically implemented in practice as assemblies of flip-flop circuits. If a single-event upset (SEU, a radiation-induced change in the bit in one flip-flop) occurs in a state register, the state machine that contains the register could go into an erroneous state or could hang, by which is meant that the machine could remain in undefined states indefinitely. The proposed fault-tolerant coding schemes are intended to prevent the state machine from going into an erroneous or hang state when an SEU occurs. To ensure reliability of the state machine, the coding scheme for bits in the state register must satisfy the following criteria: 1. All possible states are defined. 2. An SEU brings the state machine to a known state. 3. There is no possibility of a hang state. 4. No false state is entered. 5. An SEU exerts no effect on the state machine. Fault-tolerant coding schemes that have been commonly used include binary encoding and "one-hot" encoding. Binary encoding is the simplest state machine encoding and satisfies criteria 1 through 3 if all possible states are defined. Binary encoding is a binary count of the state machine number in sequence; the table represents an eight-state example. In one-hot encoding, N bits are used to represent N states: All except one of the bits in a string are 0, and the position of the 1 in the string represents the state. With proper circuit design, one-hot encoding can satisfy criteria 1 through 4. Unfortunately, the requirement to use N bits to represent N states makes one-hot coding inefficient.
Document ID
20090020514
Acquisition Source
Jet Propulsion Laboratory
Document Type
Other - NASA Tech Brief
External Source(s)
http://www.techbriefs.com/component/content/article/2620
Authors
Naegle, Stephanie Taft (California Inst. of Tech. Pasadena, CA, United States)
Burke, Gary (California Inst. of Tech. Pasadena, CA, United States)
Newell, Michael (California Inst. of Tech. Pasadena, CA, United States)
Date Acquired
August 24, 2013
Publication Date
February 1, 2008
Publication Information
Publication: NASA Tech Briefs, February 2008
Subject Category
Technology Utilization And Surface Transportation
Report/Patent Number
NPO-41050
Distribution Limits
Public
Copyright
Public Use Permitted.

Related Records

IDRelationTitle20090020506Collected WorksNASA Tech Briefs, February 2008
No Preview Available