Concurrent error detection in highly structured logic arrays

Two strategies for encoding the inputs and outputs of highly structured logic arrays (HSLAs) are introduced. The two schemes are particularly relevant for concurrent error detection of both permanent and nonpermanent errors in programmable logic arrays (PLAs) and read-only memories (ROMs). The first method of concurrent error detection (CED) is based on a comprehensive fault model and relies on detection of unidirection errors. The second approach relies on a detailed examined of decoder layouts resulting in fault avoidance through layout rules, which avoid failures causing unidirectional errors. Efficient parity techniques are shown to provide a low-overhead solution to concurrent error detection when coupled with appropriate fault-avoidance techniques.     

Area efficient computing structures for concurrent error detection in systolic arrays

A method of designing testable systolic architectures is proposed in this paper. Testing systolic arrays involves mapping of an algorithm into a specific VLSI systolic architecture, and then modifying the design to achieve concurrent testing. In our approach, redundant computations are introduced at the algorithmic level by deriving two versions of a given algorithm. The transformed dependency matrix (TDM) of the first version is a valid transformation matrix while the second version is obtained by rotating the first TDM by 180 degrees about any of the indices that represent the spatial component of the TDM. Concurrent error detection (CED) systolic array is constructed by merging the corresponding systolic array of the two versions of the algorithm. The merging method attempts to obtain the self testing systolic array at minimal cost in terms of area and speed. It is based on rescheduling input data, rearranging data flow, and increasing the utilization of the array cells. The resulting design can detect all single permanent and temporary faults and the majority of the multiple fault patterns with high probability. The design method is applied to an algorithm for matrix multiplication in order to demonstrate the generality and novelty of our approach to design testable VLSI systolic architectures.This work has been supported by a grant from the Natural Sciences and Engineering Research Council of Canada.     

A NOVEL CONCURRENT ERROR DETECTION/ CORRECTION SCHEME FOR FFT

By converting DFT of a data sequence into two partial transforms, a novel concurrent error detection/correction scheme for FFT networks is proposed based on coding theory. The scheme is realized in the computing procedure of FFT, which is different from the methods available, and has more error detection/correction capability than that of the known methods.     

A concurrent error detection IC in 2-μm static CMOS logic

When a comprehensive fault model is considered, static CMOS VLSI has long been prohibited from realizing concurrent error detecting (CED) circuits due to the unique analog faults (bridging and stuck-on faults). In this paper, we present the design, fabrication and testing of an experimental chip containing the integration of a totally self-checking (TSC) Berger code checker and a strongly code disjoint (SCD) built-in current sensor (BICS). This chip was fabricated by MOSIS using 2 μm p-well CMOS technology. In chip tests, all implanted faults, including analog faults, were detected as expected. We also show that the self-exercising mechanism of the SCD BICS is indeed functioning properly. This is the first demonstration of a working static CMOS CED chip     

Compaction-based concurrent error detection for digital circuits

We present a non-intrusive concurrent error detection (CED) method for combinational and sequential digital circuits. We analyze the optimal solution model and point out the limitations that prevent logic synthesis from yielding a minimal-cost monolithic CED implementation. We then propose a compaction-based alternative approach for restricted error models. The proposed method alleviates these limitations by decomposing the CED functionality into: compaction of the circuit outputs, prediction of the compacted responses, and comparison. We model the fault-free and erroneous responses as connected vertices in a graph and perform graph coloring in order to derive the compacted responses. The proposed method is first discussed within the context of combinational circuits, with zero detection latency, and subsequently extended to Finite State Machines (FSMs), with a constant detection latency of one clock cycle. Experimental results demonstrate that the proposed method achieves significant hardware reduction over duplication-based CED, while detecting all possible errors.     

Fault detection in programmable logic arrays

When designing fault-tolerant systems including programmable logic arrays (PLAs), the various aspects of these circuits concerning fault diagnosis have to be taken into account. The peculiarity of these aspects, ranging from fault models to test generation algorithms and to self-checking structures, is due to the regularity of PLAs. The fault model generally accepted for PLAs is the crosspoint defect; it is employed by dedicated test generation algorithms, based on the fact that PLAs implement a two-level combinational function. The problem of accessing inputs and outputs of the PLA can be alleviated by augmenting the PLA itself so as to simplify the test vectors to be applied, making them function independent in the limit. A further step consists in the addition of the circuitry required to generate test vectors and to evaluate the answer, thus obtaining a built-in self-test (BIST) architecture. Finally, high reliability can be achieved with PLAs featuring concurrent error detection.     

An IDDQ sensor for concurrent timing error detection

Error control is a major concern in many computer systems, particularly those deployed in critical applications. Experience shows that most malfunctions during system operation are caused by transient faults, which often manifest themselves as abnormal signal delays that may result in violations of circuit element timing constraints. We present a novel complementary metal-oxide-semiconductor-based concurrent error-detection circuit that allows a flip-flop (or other timing-sensitive circuit element) to sense and signal when its data has been potentially corrupted by a setup or hold timing violation. Our circuit employs on-chip quiescent supply current evaluation to determine when the input changes in relation to a clock edge. Current through the detection circuit should be negligible while the input is stable. If the input changes too close to the clock time, the resulting switching transient current in the detection circuit exceeds a reference threshold at the time of the clock transition, and an error is flagged. We have designed, fabricated, and evaluated a test chip that shows that such an approach can be used to detect setup and hold time violations effectively in clocked circuit elements     

VLSI-based array dividers with concurrent error detection

An alternative design of VLSI-based array dividers with concurrent error detection by recomputing using partitioned architecture (REPA) is proposed. The basic concept is that the divider array can be divided into two identical parts and its operation can be completed by using one part through two iterative calculations. With two such parts, a concurrent error detection scheme can be designed by using a space redundancy approach, and the detecting action is achieved at each iteration. The design is better than previous designs, such as RESO and AL, in terms of area requirement, time penalty, fault model and error latency. Advanced analysis of m partitions is also included. The experimental results are attractive, especially for designs with application-specified trade-offs between speed performance and area cost.     

Configurable array logic circuits for computing network error detection codes

Configurable Array Logic (CAL) has a basic architecture which is a cellular array with nearest neighbor connections. The cells in the array are dynamically programmable using transistor switches controlled by static RAM cells. Each cell can realize any two-input Boolean operation or act as a simple latch, as well as providing routing for pass-through connections to allow non-neighbor inter-cell connections. In this article, we demonstrate the versatility of the CAL technology by presenting efficient CAL circuits for computing all of the major error detection codes now in use for worldwide computer networking; these include CCITT, IEEE, Internet and ISO standard codes. The circuits, each having a version which comfortably fits on to a single 32×32 cell CAL chip, are appropriate for use as hardware accelerators to help computers deal with the ever increasing rates of data transmission over networks. The first class of error detection codes described are thecyclic redundancy codes (CRCs), which are in virtually universal use for bit serial transmission over physical links. The other class of error detection codes described are themodulo 2 ⁿ — 1checksums, which are in common use for byte transmission over networks and inter-networks.     

Design for testability of analog/digital networks

The testing of analog/digital integrated circuits is difficult since they allow direct access to relatively few signals. Since the probing of component pins is the fundamental chip production test technique (and possibly that of board test as well, i.e. in-circuit test), methods must be found to enhance the controllability and observability of internal signal networks. The authors provide a set of design for testability (DFT) principles that enhance their ability to test these networks when combined with the requisite analog test plans     

Design of concurrent error detectable current-mode A/D converters for real-time applications

Analog MOS circuits are becoming increasingly sophisticated in terms of checking and correcting themselves. Self-correcting, self-compensating, or self-calibrating techniques eliminate errors traditionally associated with analog circuits. For real-time applications, however, it is rather difficult to achieve validation of the data generated from analog-to-digital (A/D) converters in the presence of faulty switching element(s). Conventionally, the validation is accomplished by using a high resolution and high accuracy D/A converter and a window comparator; i.e., the validation must highly depend on the reliability of both the D/A converter and the window comparator. In this paper, a novel current-mode A/D converter design with concurrent error detection (CED) capability is presented. The A/D converter does not need well-matched components and high-gain amplifiers. Results show that the proposed design can detect all the transient faults and most of the permanent faults. The proposed design allows users to easily switch to the normal operation mode where CED capability is not used, without causing any performance degradation.     

Berger check prediction for concurrent error detection in the Braun array multiplier

The design and development of concurrent error detection arithmetic and logic units has initiated significant research concerning information coding schemes. Published research has used the unidirectional fault detection capabilities of Berger codes to achieve a fault tolerant Braun array multiplier.

In this paper we develop Berger check symbol prediction and show that the previously reported Berger coded prediction is in error, making the results inappropriate for the realization of practical concurrent error detection systems. Furthermore, we show that the Berger coded Braun array multiplier can not only achieve the objective for detecting unidirectional faults but analysis has indicated an inherent ability of the Berger check prediction technique for error detection beyond the scope for which it was originally intended. In fact the coding provides error detectability for single and multiple stuck-at faults. Further study suggests the performance of the Berger check prediction Braun array multiplier tends towards 100% error detectability for increasing input bit length and hence array dimensions.

The Berger check predictive Braun array multiplier has, therefore, introduced a high level of concurrent error detectability with only a minimal extension in the hardware implementation.     

Immediate soft error detection using pass gate logic for content addressable memory

Content addressable memory (CAM) is used in many applications. As the process technology scales into the deep sub-micron regime, soft error rate increases significantly. Densely integrated memory cells in CAM are prone to soft errors. Bit flipping in CAM leads to an incorrect search operation which could be fatal from a system point of view. The proposed scheme enables the detection of soft errors immediately and the correction of problems with small additional logic gates.     

Probability of correctness of processor-array outputs usingperiodic concurrent error detection

Processor arrays, featuring modularity, regular interconnection, and high parallelism, are well suited for VLSI/WSI implementation and specific applications with high computational requirements. Error detection and recovery are important for some applications of processor arrays. Concurrent error detection (CED) techniques, which check normal system operations, are designed to detect errors caused by transient and intermittent faults, However, CED techniques typically suffer from costly hardware penalties or performance costs. This paper describes the periodic application of concurrent error detection (PACED) technique which allows the performance costs incurred through the use of time-redundant CED in processor array architectures to be reduced. The application of CED is varied in both time and space to provide probabilistic detection of errors in processor arrays. The probability of correctness of outputs from processor arrays is studied. Formulae are derived that predict, upon error detection, the amount of possibly erroneous output, for single processors, linear arrays and 2-dimensional mesh processor arrays. The results indicate that the error coverage can be surprisingly high when PACED is applied in processor arrays, e.g., 95% for checking performed 50% of the time     

Monitoring machine based synthesis technique for concurrent error detection in finite state machines

This paper discusses a new design methodology for concurrent error detection in synchronous sequential circuits based on the use of monitoring machines. In this approach, an auxiliary sequential circuit, called the monitoring machine, operates in lock-step with the main machine, such that any fault in either of the two machines is immediately detected. This methodology is independent of the fault model. It can be applied to FSMs with pre-encoded states and can also be used for ones being synthesised. It also provides a systematic framework for the combined optimisation of the main and monitoring machines, and for exploring tradeoffs in their implementation. The design of monitored sequential circuits is a two-fold problem; namely one of designing an optimal monitoring machine given the main machine, and the other of encoding the main machine states so that the resulting monitoring machine is minimal. This paper formally discusses the design of both the main and monitoring machines and techniques for their combined optimisation. Tradeoffs in their implementation based on selective fault detection are also examined. Through experimental results, it is shown that the proposed synthesis technique is eminently suitable for the design of low-cost sequential circuits with concurrent error detection. The monitoring machine is less costly than the main machine. It is also not identical to it. As a result, a monitored sequential circuit has significantly lower hardware cost and improved fault coverage than previous implementations. Presently at Texas Instruments (India) Ltd., Bangalore, India.     

C-testable design techniques for iterative logic arrays

A design-for-testability (DFT) approach for VLSI iterative logic arrays (ILA's) is proposed, which results in a small constant number of test patterns. Our technique applies to arrays with an arbitrary dimension, and to arrays with various connection types, e.g., hexagonal or octagonal ones. Bilateral ILA's are also discussed. The DFT technique makes general ILA's C-testable by using a truth-table augmentation approach. We propose an output-assignment algorithm for minimizing the hardware overhead. We give a CMOS systolic array multiplier as an example, and show that an overhead of no more than 5.88% is sufficient to make it C-testable, i.e., 100% single cell-fault testable with only 18 test patterns regardless of the word length of the multiplier. Our technique guarantees that the test set is easy to generate. Its corresponding built-in-self-test structures are also very simple     

Designing for concurrent error detection in VLSI: application to a microprogram control unit

An integrated approach to the design of a microprogram control unit (MCU) that possesses the distinction of having comprehensive concurrent-error-detection (CED) capability for errors generated by VLSI physical failures is presented. The implementation of the functionally complex single-chip MCU is discussed and the fault model used is explained. Circuit design techniques that have recently been developed for self-checking VLSI systems are introduced. The first critical appraisal based on actual mask-level layouts of custom CED design versus error detection through duplication and comparison, are also presented.     

Design for testability of embedded integrated operationalamplifiers

The operational amplifier (op amp) is one of the most encountered analog building blocks. In this paper, the problem of testing an integrated op amp is treated. A new low-cost vectorless test solution, known as oscillation test, is investigated to test the op amp. During the test mode, the op amps are converted to a circuit that oscillates and the oscillation frequency is evaluated to monitor faults. The tolerance band of the oscillation frequency is determined using a Monte Carlo analysis taking into account the nominal tolerance of all important technology and design parameters. Faults in the op amps under test which cause the oscillation frequency to exit the tolerance band can therefore be detected. Some Design for Testability (DfT) rules to rearrange op amps to form oscillators are presented and the related practical problems and limitations are discussed. The oscillation frequency can be easily and precisely evaluated using pure digital circuitry. The simulation and practical implementation results confirm that the presented techniques ensure a high fault coverage with a low area overhead     

A function-independent self-test for large programmable logic arrays

It has been shown that small PLAs can be made self-testing. The proposed methods however fail to handle large functions fast or result in a large overhead. Here a method is shown that can be implemented efficiently at large PLAs. The test only needs a system clock and an initialization signal, producing a go/no-go signal after an AND plane size-dependent delay.     

Cell delay fault testing for iterative logic arrays

C-testable iterative logic arrays for cell-delay faults are proposed. A cell delay fault occurs if and only if an input transition can not be propagated to the cell's output through a path in the cell in a specified clock period. The set of single-path propagation, hazard-free robust tests that completely check all the paths in a cell is first derived, and then necessary conditions for sending this test set to each cell in the array and simultaneously propagating the fault effects to the primary outputs are given. Test set minimization can be solved in a similar way as for the fault cover problem. We use the pipelined array multiplier as an example, and show that it is C-testable with 214 two-pattern tests. With a small number of additional patterns, all the combinational faults can be detected pseudoexhaustive.