System-level self-diagnosis in sparsely interconnected systems

A probabilistic diagnosis algorithm for identifying faulty units in sparsely interconnected systems is presented. The algorithm is partially based on a comparison approach where identical test vectors are applied to all units and their outputs are intracompared. The comparison diagnosis schemes based on majority-voting or voting-with-threshold-of-1 are inappropriate for diagnosing those systems implemented on a single chip or wafer. Unlike other schemes, the authors' scheme adjusts algorithm parameters depending on unit yield, degree of connectivity, and the probability of common-cause failures. Fault coverage is further improved by disseminating test results to neighbors. The fault coverage of the diagnosis algorithm is remarkably high, and diagnosis decisions are made in a distributed manner. The algorithm is quite general in that it can be applied to arbitrarily connected systems     

Bayes analysis for fault location in distributed systems

The authors propose a simple and practical probabilistic model, using multiple incomplete test concepts, for fault location in distributed systems using a Bayes analysis procedure. Since it is easier to compare test results among processing units, their model is comparison-based. This approach is realistic and complete in the sense that it does not assume conditions such as permanently faulty units, complete tests, and perfect or nonmalicious environments. It can handle, without any overhead, fault-free systems so that the test procedure can be used to monitor a functioning system. Given a system S with a specific test graph, the corresponding conditional distribution between the comparison test results (syndrome) and the fault patterns of S can be generated. To avoid the complex global Bayes estimation process, the authors develop a simple bitwise Bayes algorithm for fault location of S, which locates system failures with linear complexity, making it suitable for hard real-time systems. Hence, their approach is appealing both from the practical and theoretical points of view     

Self-repairing processor modules

A processor is any self-contained computer of at least personal-computer capability. The paper explores how much the processor mean time-to-failure can be improved by replacing it with an N-processor module, where each processor in the module consists of a copy of the original processor augmented with a communication protocol unit. The copy of the original processor is faulty with probability, p_c, and the protocol unit is faulty with probability, p. The asynchronous N-processor module uses a Byzantine agreement (F-ID-P) algorithm to identify which of its processors disagreed with a module consensus. The identified processors are presumed faulty, and the module replaces them with duplicates from a set of standbys. The F-ID-P algorithm is a modification of Bracha's, which guarantees that in a module of 3t+1 processors, up to t faults can be identified by at least t+1 non-faulty processors. The module fails if faults in more than t of its processors prevent it from: 1) obtaining a correct consensus, or 2) executing the algorithm. The F-ID-P algorithm departs from Bracha's by using a random instead of an adversary scheduler of message delays. Simulation showed that almost always F-ID-P algorithm correctly identified all of a module's faulty processors if more than half of them were nonfaulty. Thus F-ID-P algorithm was about 3/2 more fault tolerant than guaranteed. Also, compared to a single processor's mean number of decisions to failure, the F-ID-P module was 841 times better when N=37, down to 5.1 times better when N=10     

Board-level built-in self-repair method of RAM

This paper describes the method of built-in self-repairing of RAM on board, designs hardware circuit, and logic for the RAM’s faults self-repairing system based on FPGA. The key technology is that it utilizes FPGA to test RAM according to some algorithm to find out failure memory units and replace the faulty units with FPGA. Then it can build a memory that has no fault concern to external controller, and realizes the logic binding between external controller and RAM. Micro Controller Unit (MCU) can operate external RAM correctly even if RAM has some fault address units. Conventional MCS-51 is used to simulate the operation of MCU operating external memory. Simulation shows FPGA can complete the faulty address units’ mapping and MCU can normally read and write external RAM. This design realizes the RAM’s built-in self-repairing on board.     

Automated repair of complex systems by fault compensation

A formal method used to repair discrete-event systems consisting of communicating processes is described. Two mechanisms of repairing faulty systems are proposed: the first inserts a new “compensator module” into the communication channel between the faulty process and one or more of its neighbors; the second modifies a neighbor of the faulty process in a compensating manner. The two mechanisms fall under a class of methods in which faults are not fixed by replacement of a faulty unit with a fault-free one, but where changes to the non-faulty parts of the system repair the system. A finite-state model is used to describe processes, and the problem is solved for two models of communication: the symmetric (or the handshake) model and, an asymmetric model. The algorithm is described, and examples are presented, including an indication of how the approach may be applied as part of a sophisticated fault management system for communication networks     

On the optimal reconfiguration of multipipeline arrays in thepresence of faulty processing and switching elements

The reconfiguration of multipipeline arrays in the presence of both faulty processing elements (PEs) and switching elements (SEs) is addressed. Different fault models are used for the PEs and SEs: a PE can be either fault free or faulty; a SE is modeled using a novel functional approach which relates its switching capabilities to its status. This permits a PE to retain a partial functionality in the presence of a fault. An appropriate transformation of the multipipeline array reconfiguration problem to a maximum flow problem is then presented. The conditions under which this transformation is possible, are fully analyzed. A reconfiguration algorithm based on the maximum flow algorithm is presented; the proposed algorithm is optimal as the number of reconfigured pipelines is maximized     

Resynthesis of combinational logic circuits for improved path delayfault testability using comparison units

We propose a resynthesis method that modifies a given circuit to reduce the number of paths in the circuit and thus improve its path delay fault testability. The resynthesis procedure is based on replacing subcircuits of the given circuit by structures called comparison units. A subcircuit can be replaced by a comparison unit if it implements a function belonging to the class of comparison functions defined here. Comparison units are fully testable for stuck-at faults and for path delay faults. In addition, they have small numbers of paths and gates. These properties make them effective building blocks for resynthesis to improve the path delay fault testability of a circuit. Experimental results demonstrate considerable reductions in the number of paths and increased path delay fault testability. These are achieved without increasing the number of gates, or the number of gates along the longest path in the circuit. The random pattern testability for stuck-at faults remains unchanged     

A Classical Parameter Identification Method and?a?Modern Test Generation Algorithm

Many methods have been presented for the testing and diagnosis of analog circuits. Each of these methods has its advantages and disadvantages. In this paper we propose a novel sensitivity analysis algorithm for the classical parameter identification method and a continuous fault model for the modern test generation algorithm, and we compare the characteristics of these methods. At present, parameter identification based on the component connection model (CCM) cannot ensure that the diagnostic equation is optimal. The sensitivity analysis algorithm proposed in this paper can choose the optimal set of trees to construct an optimal CCM diagnostic equation, and enhance the diagnostic precision. But nowadays increasing attention is being paid to test generation algorithms. Most test generation algorithms use a single value in the fault model. But the single values cannot substitute for the actual faults that may occur, because the possible faulty values vary over a continuous range. To solve this problem, this paper presents a continuous fault model for the test generation algorithm which has a continuous range of parameters. The test generation algorithm with this model can improve the treatment of the tolerance problem, including the tolerances of both normal and faulty parameters, and enhance the fault coverage rate. The two methods can be applied in different situations.     

NASA ground terminal communication equipment: Automated fault isolation expert systems

This paper describes the prototype expert systems that diagnose the Distribution and Switching System I and II (DSS1 and DSS2), Statistical Multiplexers (SM), and Multiplexer and Demultiplexer systems (MDM) at the NASA Ground Terminal (NGT) located at White Sands, New Mexico. A system-level fault isolation expert system monitors the activities of a selected data stream, verifies that the fault exists in the NGT and identifies the faulty equipment. Equipment-level fault isolation expert systems will be invoked to isolate the fault to a Line Replaceable Unit (LRU) level. Input and sometimes output data stream activities for the equipment are available. The system-level fault isolation expert system will compare the equipment input and output status for a data stream and perform loopback tests (if necessary) to isolate the faulty equipment. The equipment-level fault isolation system utilizes the process of elimination and/or the maintenance personnel's fault isolation experience stored in its knowledge base. The DSS1, DSS2, and SM fault isolation systems, using the knowledge of the current equipment configuration and the equipment circuitry, will issue a set of test connections according to the predefined rules. The faulty component or board can be identified by the expert system by analyzing the test results. The MDM fault isolation system correlates the failure symptoms with the faulty component based on maintenance personnel experience. The faulty component can be determined by knowing the failure symptoms.

The NGT fault isolation prototype is implemented in Prolog, C, and VP-Expert, on an IBM AT compatible workstation. The DSS1, DSS2, SM, and MDM equipment simulators are implemented in PASCAL. The equipment simulator receives connection commands and responds with status for the expert system according to the assigned faulty component in the equipment. The DSS1 fault isolation expert system was converted to C language from VP-Expert and integrated into the NGT automation software for offline switch diagnoses.

Potentially, the NGT fault isolation algorithms can be used for the DSS1, SM, and MDM located at Goddard Space Flight Center (GSFC). The prototype could be a training tool for the NGT and NASA Communications (Nascom) Network maintenance personnel.     

A precise sensor fault detection technique using statistical techniques for wireless body area networks

One of the major challenges in wireless body area networks (WBANs) is sensor fault detection. This paper reports a method for the precise identification of faulty sensors, which should help users identify true medical conditions and reduce the rate of false alarms, thereby improving the quality of services offered by WBANs. The proposed sensor fault detection (SFD) algorithm is based on Pearson correlation coefficients and simple statistical methods. The proposed method identifies strongly correlated parameters using Pearson correlation coefficients, and the proposed SFD algorithm detects faulty sensors. We validated the proposed SFD algorithm using two datasets from the Multiparameter Intelligent Monitoring in Intensive Care database and compared the results to those of existing methods. The time complexity of the proposed algorithm was also compared to that of existing methods. The proposed algorithm achieved high detection rates and low false alarm rates with accuracies of 97.23% and 93.99% for Dataset 1 and Dataset 2, respectively.     

基于探测圈覆盖的光突发交换网络故障定位

针对光突发交换(Optical Burst Switching,OBS)网络在干扰告警信息情况下定位率低的问题,在最短长度m2圈算法的基础上,提出了相应的故障定位机制。首先,故障探测阶段收集由故障触发的告警信息,并组成相应的二进制告警相关矩阵,然后,故障定位阶段利用告警矩阵进行快速定位,找到可能的故障设备集合。     

Fault diagnosis in wireless sensor network using clonal selection principle and probabilistic neural network approach

The fault diagnosis in wireless sensor networks is one of the most important topics in the recent years of research work. The problem of fault diagnosis in wireless sensor network can be resembled with artificial immune system in many different ways. In this paper, a detection algorithm has been proposed to identify faulty sensor nodes using clonal selection principle of artificial immune system, and then the faults are classified into permanent, intermittent, and transient fault using the probabilistic neural network approach. After the actual fault status is detected, the faulty nodes are isolated in the isolation phase. The performance metrics such as detection accuracy, false alarm rate, false‐positive rate, fault classification accuracy, false classification rate, diagnosis latency, and energy consumption are used to evaluate the performance of the proposed algorithm. The simulation results show that the proposed algorithm gives superior results as compared with existing algorithms in terms of the performance metrics. The fault classification performance is measured by fault classification accuracy and false classification rate. It has also seen that the proposed algorithm provides less diagnosis latency and consumes less energy than that of the existing algorithms proposed by Mohapatra et al, Panda et al, and Elhadef et al for wireless sensor network.     

一个基于并行集团的系统级故障概率诊断算法

概率诊断算法是系统级故障诊断研究的一个重要方面,本文提出了一种基于并行集团的概率诊断算法-PGSFPD算法,并设计了一个系统级故障诊断软件仿真系统,对诊断算法进行仿真,分析比较各算法的性能,仿真结果表明PGSFPD算法性能优于经典的概率诊断算法-Somani & Agrawal算法,可在只需较少测试数的情况下,在保持很高诊断正确率的同时,大大降低系统的规模.     

Fault dictionary based switched current circuit fault diagnosis using entropy as a preprocessor

A novel method based on a fault dictionary that uses entropy as a preprocessor to diagnose faulty behavior in switched current (SI) circuit is presented in the paper. The proposed method uses a data acquisition board to extract the original signal form the output terminals of the circuit-under-tests. These original data are fed to the preprocessors for feature extraction and finds out the entropies of the signals which are a quantitative measure of the information contained in the signals. The proposed method has the capability to detect and identify faulty transistors in SI circuit by analyzing its output signals with high accuracy. Using entropy of signals to preprocess the circuit response drastically reduces the size of fault dictionary, minimizing fault detect time and simplifying fault dictionary architecture. The result from our examples showed that entropies of the signals fall on different range when the faulty transistors^` Transconductance G_m value varying within their tolerances of 5 or 10%, thus we can identify the faulty transistors correctly when the response do not overlap. The average accuracy of fault recognition achieved is more than 95% although there are some overlapping data when tolerance is considered. The method can classify not only parametric faults but also catastrophic faults. It is applicable to analog circuits as well as SI ones. A low-pass and a band-pass SI filter and a Clock feedthrough cancellation circuit have been used as test beached to verify the effectiveness of the proposed method. A comparison of our work with Yuan et al. (IEEE Trans Instrum Meas 59(3):586–595, 2010), which used entropy and kurtosis as preprocessors, reveals that our method requiring one feature parameter reduces the computation and fault diagnosis time.     

Multi-valued logic mapping of resistive short and open delay-fault testing in deep sub-micron technologies

In advanced technologies an increasing proportion of defects manifest themselves as small delay faults. Most of today’s advanced delay-fault algorithms are able to propagate those delay faults which create logic or glitch faults. An algorithm is proposed for circuit fault diagnosis in deep sub-micron technology to propagate the actual timing faults as well as those delay faults that eventually create logic faults to the primary outputs. Unlike the backtrack algorithm that predicts the fault site by tracing the syndrome at a faulty output back into the circuit, this approach propagates the fault from the fault site by mapping a nine-valued voltage model on top of a five-valued voltage model. In such a forward approach, accuracy is greatly increased since all composite syndromes at all faulty outputs are considered simultaneously. As a result, the proposed approach is applicable even when the delay size is relatively small. Experimental results show that the number of fault candidates produced by this approach is considerable.     

Real-Time Management of Faulty Electrodes in Electrical Impedance Tomography

Completely or partially disconnected electrodes are a fairly common occurrence in many electrical impedance tomography (EIT) clinical applications. Several factors can contribute to electrode disconnection: patient movement, perspiration, manipulations by clinical staff, and defective electrode leads or electronics. By corrupting several measurements, faulty electrodes introduce significant image artifacts. In order to properly manage faulty electrodes, it is necessary to: (1) account for invalid data in image reconstruction algorithms and (2) automatically detect faulty electrodes. This paper presents a two-part approach for real-time management of faulty electrodes based on the principle of voltage-current reciprocity. The first part allows accounting for faulty electrodes in EIT image reconstruction without a priori knowledge of which electrodes are at fault. The method properly weights each measurement according to its compliance with the principle of voltage-current reciprocity. Results show that the algorithm is able to automatically determine the valid portion of the data and use it to calculate high-quality images. The second part of the approach allows automatic real-time detection of at least one faulty electrode with 100% sensitivity and two faulty electrodes with 80% sensitivity enabling the clinical staff to fix the problem as soon as possible to minimize data loss.     

Fault diagnosis and its prediction in wireless sensor networks using regressional learning to achieve fault tolerance

Due to the wide range of critical applications and resource constraints, sensor node gives unexpected responses, which leads to various kind of faults in sensor node and failure in wireless sensor networks. Many research studies focus only on fault diagnosis, and comparatively limited studies have been conducted on fault diagnosis along with fault tolerance in sensor networks. This paper reports a complete study on both 2 aspects and presents a fault tolerance approach using regressional learning with fault diagnosis in wireless sensor networks. The proposed method diagnose the different types of faulty nodes such as hard permanent, soft permanent, intermittent, and transient faults with better detection accuracy. The proposed method follows a fault tolerance phase where faulty sensor node values would be predicted by using the data sensed by the fault free neighbors. The experimental evaluation of the fault tolerance module shows promising results with R² of more than 0.99. For the periodic fault such as intermittent fault, the proposed method also predict the possible occurrence time and its duration of the faulty node, so that fault tolerance can be achieved at that particular time period for better performance of the network.     

基于UIO测试序列的错误诊断算法

唯一输入输出(Unique Input Output)测试序列是协议测试中常用的一种测试序列,在一个已有的错误诊断算法基础上,结合UIO测试序列的一些特点,该文提出了一种应用于UIO测试序列的错误诊断算法。该算法充分利用了UIO测试序列给出的判定消息,及测试结果中可能的错误转换后的输入/输出消息,从而能高效完全地诊断单个错误。最后用实验数据给出了该文算法和原始算法之间的比较结果。     

A scalable built-in self-recovery (BISR) VLSI architecture and design methodology for 2D-mesh based on-chip networks

On-Chip Networks (OCNs) have been proposed to solve the complex on-chip communication problems. In Very Deep-Submicron era, OCN will also be affected by faults in chip due to technologies shrinking. Many researches focused on fault detection and diagnosis in OCN systems. However, these approaches didn’t consider faulty OCN system recovery. This paper proposes a scalable built-in self-recovery (BISR) design methodology and corresponding Surrounding Test Ring (STR) architecture for 2D-mesh based OCNs to extend the work of diagnosis. The BISR design methodology consists of STR architecture generation, faulty system recovery, and system correctness maintenance. For an n×n mesh, STR architecture contains one controller and 4n test modules which are formed as a ring-like connection surrounding the OCN. Moreover, these test modules generate test patterns for fault diagnosis during warm-up time. According to these diagnosis results, the faulty system is recovered. Finally, this paper proposes a fault-tolerant routing algorithm, Through-Path Fault-Tolerant (TP-FT) routing, to maintain the correctness of this faulty system. In our experiments, the proposed approach can reduce 68.33∼79.31% unreachable packets and 4.86∼23.6% latency in comparison with traditional approach with 8.48∼13.3% area overhead.     

改进的基于故障特征平面的双星故障识别算法

针对基于识别门限的奇偶矢量法等双星故障识别算法存在较大误警率、漏检率以及故障偏差抵消致使双星故障正确识别率较低的问题,提出了一种改进的用于双星故障识别的接收机自主完好性监测算法.在奇偶矢量法的基础上,构造故障特征平面和改进奇偶矢量,分析二者之间的几何特征与卫星故障的关系,并设计相应算法识别故障卫星.该算法不受识别门限的影响,避免了由识别门限引起的识别率较低的不足.半物理仿真结果显示：改进后的算法故障识别率达到90%以上,与直接利用奇偶矢量法相比,可以显著提高双星故障识别率.