Fault-tolerant linear finite state machines
Date
1999ISBN
0-7803-5682-9Publisher
Institute of Electrical and Electronics Engineers Inc.Source
Proceedings of the IEEE International Conference on Electronics, Circuits, and SystemsProceedings of the IEEE International Conference on Electronics, Circuits, and Systems
Volume
2Pages
1085-1088Google Scholar check
Keyword(s):
Metadata
Show full item recordAbstract
In this paper we develop a framework for constructing fault-tolerant dynamic systems, focusing primarily on linear finite state machines (LFSMs). Modular redundancy, the traditional approach to fault tolerance, is expensive because of the overhead in replicating the hardware and its reliance on the assumption that the error-correcting (voting) mechanism is fault-free. Our approach is more general, makes efficient use of redundancy, and relaxes the strict requirements regarding the reliability of the error corrector. By combining linear coding techniques and dynamic system theory, we characterize the class of all appropriate redundant implementations. Furthermore, we construct reliable LFSM's assembled exclusively from unreliable components, including unreliable voters and parity checkers in the error correcting mechanism. Using constant redundancy per system, we obtain implementations of identical LFSM's that operate in parallel on distinct input sequences and achieve arbitrarily low probability of failure during any specified finite time interval. © 1999 IEEE.