Coding approaches to fault tolerance in linear dynamic systems

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.     

Probabilistic detection of FSM single state-transition faults based on state occupancy measurements

This note discusses a probabilistic methodology for detecting single permanent or transient functional changes in the state-transition mechanism of a deterministic finite-state machine (FSM). The associated probabilistic detector observes the empirical frequencies with which different states are occupied and detects faults by analyzing the discrepancy between the observed state occupancy measurements and the expected frequencies. In addition to state occupancy measurements, the detector requires a statistical characterization of the input, but does not need to know the order with which states appear or the exact input sequence that is applied to the FSM. These features can be useful in settings where the input/state order may not be known due to synchronization, communication or other constraints.     

Decoding algorithm and architecture for BCH codes under the Lee Metric

The Lee metric measures the circular distance between two elements in a cyclic group and is particularly appropriate as a measure of distance for data transmission under phase-shift-keying modulation over a white noise channel. In this paper, using newly derived properties on Newton?s identities, we initially investigate the Lee distance properties of a class of BCH codes and show that (for an appropriate range of parameters) their minimum Lee distance is at least twice their designed Hamming distance. We then make use of properties of these codes to devise an efficient algebraic decoding algorithm that successfully decodes within the above lower bound of the Lee error-correction capability. Finally, we propose an attractive design for the corresponding VLSI architecture that is only mildly more complex than popular decoder architectures under the Hamming metric; since the proposed architecture can also be used for decoding under the Hamming metric without extra hardware, one can use the proposed architecture to decode under both distance metrics (Lee and Hamming).     

Determination of the Number of Errors in DFT Codes Subject to Low-Level Quantization Noise

This paper analyzes the effects of quantization or other low-level noise on the error correcting capability of a popular class of real-number Bose-Chaudhuri-Hocquenghem (BCH) codes known as discrete Fourier transform (DFT) codes. In the absence of low-level noise, a modified version of the Peterson-Gorenstein-Zierler (PGZ) algorithm allows the correction of up to corrupted entries in the real-valued code vector of an DFT code. In this paper, we analyze the performance of this modified PGZ algorithm in the presence of low-level (quantization or other) noise that might affect each entry of the code vector (and not simply of them). We focus on the part of the algorithm that determines the number of errors that have corrupted the real-number codeword. Our approach for determining the number of errors is more effective than existing systematic approaches in the literature and results in an explicit lower bound on the precision needed to guarantee the correct determination of the number of errors; our simulations suggest that this bound can be tight. Finally, we prove that the optimal bit allocation for DFT codes (in terms of correctly determining the number of errors) is the uniform one.     

Probabilistic system opacity in discrete event systems

In many emerging security applications, a system designer frequently needs to ensure that a certain property of a given system (that may reveal important details about the system’s operation) be kept secret (opaque) to outside observers (eavesdroppers). Motivated by such applications, several researchers have formalized, analyzed, and described methods to verify notions of opacity in discrete event systems of interest. This paper introduces and analyzes a notion of opacity in systems that can be modeled as probabilistic finite automata or hidden Markov models. We consider a setting where a user needs to choose a specific hidden Markov model (HMM) out of m possible (different) HMMs, but would like to “hide” the true system from eavesdroppers, by not allowing them to have an arbitrary level of confidence as to which system has been chosen. We describe necessary and sufficient conditions (that can be checked with polynomial complexity), under which the intruder cannot distinguish the true HMM, namely, the intruder cannot achieve a level of certainty about its decision, which is above a certain threshold that we can a priori compute.     

A Robust Control Approach to Perfect Reconstruction of Digital Signals

In this paper we present a deterministic worst-case approach for reconstructing discrete-valued signals that have been filtered via dispersive and noisy systems (ldquochannelsrdquo). This approach, which is explored based on robust control ideas and makes no assumption on the noise (distribution or structure) other than a requirement that its magnitude be bounded, can serve as a complement to existing approaches that attempt to reconstruct discrete-valued signals by optimizing probabilistic criteria. The particular problems touched upon are: (i) necessary and sufficient conditions for causal (possibly delayed) perfect reconstruction under deterministic magnitude bounded noise for single-input single-output (SISO) and multi-input multi-output (MIMO) channels; (ii) perfect reconstruction based on decision feedback (DF) structures; and (iii) necessary and sufficient conditions for perfect reconstruction with DF structures in the presence of uncertainties in the channel. The l¹ control theory emerges as the natural key player for analysis and synthesis of perfect reconstructing strategies in this framework.     

Delayed Observers for Linear Systems With Unknown Inputs

We present a method for constructing reduced-order state observers for linear systems with unknown inputs. Our approach provides a characterization of observers with delay, which eases the established necessary conditions for existence of unknown input observers with zero-delay. We develop a parameterization of the observer gain that decouples the unknown inputs from the estimation error, and we use the remaining freedom to ensure stability of the error dynamics. Our procedure is quite general in that it encompasses the design of full-order observers via appropriate choices of design matrices     

Max-product algorithms for the generalized multiple-fault diagnosis problem.

In this paper, we study the application of the max-product algorithm (MPA) to the generalized multiple-fault diagnosis (GMFD) problem, which consists of components (to be diagnosed) and alarms/connections that can be unreliable. The MPA and the improved sequential MPA (SMPA) that we develop in this paper are local-message-passing algorithms that operate on the bipartite diagnosis graph (BDG) associated with the GMFD problem and converge to the maximum a posteriori probability (MAP) solution if this graph is acyclic (in addition, the MPA requires the MAP solution to be unique). Our simulations suggest that both the MPA and the SMPA perform well in more general systems that may exhibit cycles in the associated BDGs (the SMPA also appears to outperform the MPA in these more general systems). In this paper, we provide analytical results for acyclic BDGs and also assess the performance of both algorithms under particular patterns of alarm observations in general graphs; this allows us to obtain analytical bounds on the probability of making erroneous diagnosis with respect to the MAP solution. We also evaluate the performance of the MPA and the SMPA algorithms via simulations, and provide comparisons with previously developed heuristics for this type of diagnosis problems. We conclude that the MPA and the SMPA perform well under reasonable computational complexity when the underlying diagnosis graph is sparse.