Coding approaches to fault tolerance in linear dynamic systems
AuthorHadjicostis, Christoforos N.
Verghese, G. C.
SourceIEEE Transactions on Information Theory
Google Scholar check
MetadataShow full item record
This paper discusses fault tolerance in discrete-time dynamic systems, such as finite-state controllers or computer simulations, with focus on the use of coding techniques to efficiently provide fault tolerance to linear finite-state machines (LFSMs). Unlike traditional fault tolerance schemes, which rely heavily - Particularly for dynamic systems operating over extended time horizons - On the assumption that the error-correcting mechanism is fault free, we are interested in the case when all components of the implementation are fault prone. The paper starts with a paradigmatic fault tolerance scheme that systematically adds redundancy into a discrete-time dynamic system in a way that achieves tolerance to transient faults in both the state transition and the error-correcting mechanisms. By combining this methodology with low-complexity error-correcting coding, we then obtain an efficient way of providing fault tolerance to k identical unreliable LFSMs that operate in parallel on distinct input sequences. The overall construction requires only a constant amount of redundant hardware per machine (but sufficiently large k) to achieve an arbitrarily small probability of overall failure for any prespecified (finite) time interval, leading in this way to a lower bound on the computational capacity of unreliable LFSMs. © 2005 IEEE.
Showing items related by title, author, creator and subject.
Sundaram, S.; Hadjicostis, Christoforos N. (2009)For any given fixed network of interconnected nodes, with some nodes designated as sources and some nodes designated as sinks, we investigate the problem of transmitting a stream of values from every source node to all of ...
Sundaram, S.; Hadjicostis, Christoforos N. (2008)We consider the problem of constructing partial state observers for discrete-time linear systems with unknown inputs. Specifically, for any given system, we develop a design procedure that characterizes the set of all ...
Structural controllability and observability of linear systems over finite fields with applications to multi-agent systems Sundaram, S.; Hadjicostis, Christoforos N. (2013)We develop a graph-theoretic characterization of controllability and observability of linear systems over finite fields. Specifically, we show that a linear system will be structurally controllable and observable over a ...