Algorithm-based fault tolerance (ABFT) is used to provide low-cost error protection for VLSI processor arrays used in real-time digital signal processing. The main objective of incorporating an ABFT technique in a processor array is to improve its reliability. All previous approaches on ABFT are evaluated in terms of their error detecting/correcting capabilities, the reliability improvement has never been addressed. In this paper, we develop a stochastic model for an array processor incorporating ABFT that takes the behavior of transient/intermittent failures and hardware overhead into account. This model is then used to evaluate reliability and reliability improvements of several existing ABFT techniques that tolerate single faults. Therefore, a user can evaluate a number of ABFT techniques and make a trade-off between reliability and cost prior to the implementation. Moreover, we have conducted extensive simulation experiments and the simulation results validate the proposed model.

In this brief, we propose two new concurrent error-detection (CED) schemes for a class of sorting networks, e.g., odd-even transposition, bitonic, and perfect shuffle sorting networks. A probabilistic method is developed to analyze the fault coverage, and the hardware overhead is evaluated. We first propose a CED scheme by which all errors caused by single faults in a concurrent checking sorting network can be detected. This scheme is the first one available to use significantly less hardware overhead than duplication without compromising throughput. From this scheme, we develop another fault detection scheme which sharply reduces the hardware overhead (using an additional 10%/spl sim/30% hardware) but still achieves virtually 1001 fault coverage.

Algorithm-based fault tolerance (ABFT) can provide a low-cost error protection for array processors and multiprocessor systems. Several ABFT techniques (weighted check-sum) have been proposed to design fault-tolerant matrix operations. In these schemes, encoding/decoding uses either multiplications or divisions so that overhead is high. In this paper, new encoding/decoding methods are proposed for designing fault-tolerant matrix operations. The unique feature of these new methods is that only additions and subtractions are used in encoding/decoding. In this paper, new algorithms are proposed to construct error detecting/correcting codes with the minimum Hamming distance 3 and 4. We will show that the overhead introduced due to the incorporation of fault tolerance is drastically reduced by using these new coding schemes.

The algorithm-based fault tolerance techniques have been proposed to obtain reliable results at very low hardware overhead. Even though 100% fault coverage can be theoretically obtained by using these techniques, the system performance, i.e., fault coverage and throughput, can be drastically reduced due to many practical problems, e.g., round-off errors. A novel algorithm-based fault tolerance scheme is proposed for fast Fourier transform (FFT) networks. It is shown that the proposed scheme achieves 100% fault coverage theoretically. An accurate measure of the fault coverage for FFT networks is provided by taking the round-off error into account. The proposed scheme is shown to provide concurrent error detection capability to FFT networks with low hardware overhead, high throughput, and high fault coverage.>

An efficient technique for designing a totally self-checking checker for 1/n code (n>3) with minimum possible gate delay is proposed. The checker consists of a 1/n to k/2k translator and a k/2k code checker. The translator is implemented using a NOR array and checker using a NOR-NOR PLA. The design technique is applicable for all but a few values of n. It has been shown that the checkers constructed using the proposed technique occupy minimum or near-minimum chip area depending on the value of n. This new technique also has the advantage over existing ones in terms of speed or hardware.>

Recently D.J. Lin and B. Bose, (1988) proposed a class of t error correcting and d unidirectional error detecting codes (t-EC/d-UED codes) where d>t. The authors refine the codes in such a way that the error detecting capability of the resulting codes is considerably better than the existing codes in many cases. The decoding algorithm is described. The proposed codes are compared to the Lin-Bose codes.>

A method for constructing a class of t-error correcting and all unidirectional error-detecting systematic codes is proposed. These codes have been shown to be more efficient than codes constructed using other methods proposed in the literature. In a special case, the code constructed is the Berger code.>