Fault-Tolerant Coding for State Machines

NASA’s Jet Propulsion Laboratory, Pasadena, California

Friday, February 01 2008

State machines can be rendered immune to single-event upsets.

Two 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 onehot 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.

Like one-hot encoding, one of the two proposed schemes satisfies criteria 1 through 4. However, the Hamming distance of 2 encoding is more efficient in that it requires fewer than N bits to represent N states. The scheme is denoted H2 because it requires a Hamming distance of 2 between any two adjacent legal state representations: that is, the strings of bits representing any two adjacent states must differ in two places. Starting from any legal state representation in H2 encoding, an SEU changes the contents of the register to a defined illegal state representation. Because the illegal representation is defined, it can be recognized automatically and used to prevent the state machine from entering an illegal state and from generating incorrect outputs. An H2 code can be generated by adding one additional bit to a binary encoding scheme, as shown in the table.