Redundant Implementations of Linear Finite-State Machines

This chapter applies techniques similar to those of Chapter 5 to provide fault tolerance to linear finite-state machines (LFSM’s) [Hadjicostis, 1999]. The discussion focuses on linear encoding techniques and, as in Chapter 5, results in a complete characterization of the class of appropriate redundant implementations. It is shown that, for a given LFSM and a given linear encoding, there exists a variety of possible implementations and that different criteria can be used to choose the most desirable one [Hadjicostis, 2000; Hadjicostis and Verghese, 2002]. The implications of this approach are demonstrated by studying hardware implementations that use interconnections of 2-input XOR gates and single-bit memory elements (flip-flops). The redundancy in the state representation (which essentially appears as a linearly encoded binary vector) is used by an external, fault-free mechanism to perform concurrent error detection and correction at the end of each time step. The assumption of a fault-free error corrector is relaxed in Chapter 7.