Multiple-output parity bit signature for exhaustive testing

In this article we propose a multiple-output parity bit signature generation method for exhaustive testing of VLSI circuits. Given a multiple-output combinational circuit, a parity bit signature is generated by first EXORing all the outputs to produce a new output function and then feeding this resulting function to a single-output parity bit signature generator. The method preserves all the desirable properties of the conventional single-output circuits response analyzers and can be readily implemented using the current VLSI technology.     

Evaluating the safety of self-checking circuits

In this paper, we consider the evaluation of the safety of a self-checking circuit with combinational logic. Since the circuit is tested under normal operation, it may stay in different states such as a perfect state in which any erroneous output can be detected, unstable states in which an erroneous output may be detected or may not, a safe-state when the erroneous output has been caught, and a fail-state because the erroneous output is undetected, as time goes on. Consequently, we propose a fail-safe evaluation, using a Markov model to describe the state transitions and predicate the probability of the circuit not being in the fail-state.We include a comparison with existing evaluation methods, the proposed approach being more practical because it estimates the safety of the circuit, which is reducing as time goes on, instead of giving a constant probability measure.This work was supported in part by Research Grant No. 5711 from the Natural Sciences and Engineering Research Council of Canada and by an equipment loan from the Canadian Microelectronics Corporation.     

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.     

Parity bit calculation and test signal compaction for BIST applications

Parity bit checking and pseudo-exhaustive testing are two design techniques which have been widely discussed in the BIST literature but have seldom been employed in practice because of the exponential nature of the processes involved. In this paper we describe several procedures designed to avoid these exponential explosions. Specifically we show how the parity of a large combinational function can (often) be quickly calculated. This is accomplished by an examination of the circuit realization itself particularly with regard to the connectivity between the various inputs and outputs. We then show how this same approach can be used to partition circuits so that they can be tested efficiently with a relatively small number of test patterns. Using these methods we were able to calculate the parity bits for more than 80% of ISCAS benchmark circuits' outputs. Interestingly enough, only 15% of these outputs were found to be parity-odd, but for these cases high fault coverage was invariably found to result. Several examples are included.This work was partially supported by the National Science Foundation under grant MIP-8902014.     

DMR +: An efficient alternative to TMR to protect registers in Xilinx FPGAs

Registers are one of the circuit elements that can be affected by soft errors. To ensure that soft errors do not affect the system functionality, Triple Modular Redundancy (TMR) is commonly used to protect registers. TMR can effectively protect against errors affecting a single flip-flop and has a low overhead in terms of circuit delay. The main drawback of TMR is that it requires more than three times the original circuit area as the flip-flops are triplicated and additional voting logic is inserted. Another alternative is to protect registers using Error Correction Codes (ECCs), but those typically require a large circuit delay overhead and are not suitable for high speed implementations. In this paper, DMR + an alternative to TMR to protect registers in FPGAs, is presented. The proposed scheme exploits the FPGA structure to achieve a reduction in the FPGA resources (LUTs and Flip-Flops) at the cost of a certain overhead in delay. DMR + can correct all single bit errors like TMR but is more vulnerable to multiple bit errors. To evaluate the benefits, the DMR + technique has been implemented and compared with TMR considering standalone registers and also some simple designs.     

Soft-error filtering: A solution to the reliability problem of future VLSI digital circuits

As the semiconductor industry continues to scale down the feature sizes in VLSI digital circuits, soft errors will eventually limit the reliability of these circuits. An important source of these errors will be the products of radioactive decay. It is proposed to combat these transient errors by a new technique called soft-error filtering (SEF). This is based on filtering the input to every latch in the VLSI circuit, thereby preventing these transients, generated by alpha particle hits in the combinational section, from being latched in the corresponding registers. Several approaches to the problem of designing filtering latches are compared. This comparison demonstrates the superiority of a double-filter realization. The design for a CMOS implementation of the double-filter latch is presented. Not only is the design simple and efficient, but it can be expected to be tolerant to process variations. A comparison of SEF with conventional techniques for dealing with soft errors shows the former to be generally much more attractive, from the point of view of both area and time overhead.     

Mitigating Soft Errors in SRAM Address Decoders Using Built-in Current Sensors

In this paper, we propose a diagnose strategy based on built-in current sensors able to detect the effects of single event transients (SETs) in SRAM memory decoders. By analyzing the effects, it is possible to mitigate the error by warning the system about the erroneous write and read operation or by circuit error correction avoiding catastrophic multiple bit upset errors. While EDAC can only protect faults in the memory cell array, the proposed method can cope with faults in the combinational memory circuitry. This BICS-based technique can be used in combination with EDAC to achieve high reliability in memories fabricated in nanometer technologies. Our methodology has been validated by Spice simulation and results show that our approach presents a low area, performance and power dissipation penalty.     

Applications of Boolean Satisfiability to Verification and Testing of Switch-Level Circuits

This work extends to the switch level the verification and testing techniques based upon boolean satisfiability (SAT), so that SAT-based methodologies can be applied to circuits that cannot be well described at the gate level. The main achieved goal was to define a boolean model describing switch-level circuit operations as a SAT problem instance, to be applied to combinational equivalence checking and bridging-fault test generation. Results are provided for a set of combinational CMOS circuits, showing the feasibility of SAT-based verification and testing of switch-level circuits.     

Self-checking self-repairing computer nodes using the MirrorProcessor

Circuitry added to fault-tolerant systems for concurrent error detection usually reduces performance. Using a technique called micro rollback, it is possible to eliminate most of the performance penalty of concurrent error detection. Error detection is performed in parallel with intermodule communication, and erroneous state changes are later undone. The author reports on the design and implementation of a VLSI RISC microprocessor, called the Mirror Processor (MP), which is capable of micro rollback. In order to achieve concurrent error detection, two MP chips operate in lockstep, comparing external signals and a signature of internal signals every clock cycle. If a mismatch is detected, both processors roll back to the beginning of the cycle when the error occurred. In some cases the erroneous state is corrected by copying a value from the fault-free processor to the faulty processor. The architecture, microarchitecture, and VLSI implementation of the MP, emphasizing its error-detection, error-recovery, and self-diagnosis capabilities are described     

RSYN: a system for automated synthesis of reliable multilevelcircuits

Conventional logic synthesis systems are targeted towards reducing the area required by a logic block, as measured by the literal count or gate count; or, improving the performance in terms of gate delays; or, improving the testability of the synthesized circuit, as measured by the irredundancy of the resultant circuit. In this paper, we address the problem of developing reliability driven logic synthesis algorithms for multilevel logic circuits, which are integrated within the MIS synthesis system. Our procedures are based on concurrent error detection techniques that have been proposed in the past for two level circuits, and adapting those techniques to multilevel logic synthesis algorithms. Three schemes for concurrent error detection in a multilevel circuit are proposed in this paper, using which all the single stuck at faults in the circuit can be detected concurrently. The first scheme uses duplication of a given multilevel circuit with the addition of a totally self-checking comparator. The second scheme proposes a procedure to generate the multilevel circuit from a two level representation under some constraint such that, the Berger code of the output vector can be used to detect any single fault inside the circuit, except at the inputs. A constrained technology mapping procedure is also presented in this paper. The third scheme is based on parity codes on the outputs. The outputs are partitioned using a novel partitioning algorithm, and each partition is implemented using a multilevel circuit. Some additional parity coded outputs are generated. In all three schemes, all the necessary checkers are generated automatically and the whole circuit is placed and routed using the Timberwolf layout package. The area overheads for several benchmark examples are reported in this paper. The entire procedure is integrated into a new system called RSYN     

Self-timed is self-checking

Self-checking circuits detect (at least some of) their own faults. We describe self-timed circuits, including combinational logic and sequential machines, which either halt or generate illegal output if they include any single stuck-at faults. The self-timed circuits employ dual rail data encoding to implement ternary logic of 0, 1, andundefined states; the fourth state is used to signal illegal output and is shown to result only from certain circuit faults. The self-timed circuits also employ four-phase signaling according to a well-defined protocol of communications between the circuit and its environment; failures due to certain faults prevent the circuit from communicating properly, thus causing the circuit to halt. We show that any single stuck-at fault falls in either the first or the second category, thus providing complete fault coverage through self checking. No hardware needs to be added to our circuits to achieve the complete self-checking property; further, the circuit is guaranteed to never generate a legal but erroneous output if it contains a fault. Minimal hardware is needed to detect that a circuit has either halted or has generated an illegal output.     

On the effectiveness of residue code checking for parallel two'scomplement multipliers

The effectiveness of residue code checking for online error detection in parallel two's complement multipliers has only up until now been evaluated experimentally for few architectures. In this paper a formal analysis is given for most of the current multiplication schemes. Based on this analysis it is shown which check bases are appropriate, and how the original scheme has to be extended for complete error detection at the input registers and Booth recoding circuitry. In addition, we argue that the hardware overhead for checking can be reduced by approximately one half if a small latency in error detection is acceptable. Schemes for structuring the checking logic in order to guarantee it to be self-testing, and thus achieve the totally self-checking goal for the overall circuit, are also derived     

Fault tolerant encoders for Single Error Correction and Double Adjacent Error Correction codes

Error correction codes (ECCs) are commonly used to deal with soft errors in memory applications. Typically, Single Error Correction-Double Error Detection (SEC-DED) codes are widely used due to their simplicity. However, the phenomenon of more than one error in the memory cells has become more serious in advanced technologies. Single Error Correction-Double Adjacent Error Correction (SEC-DAEC) codes are a good choice to protect memories against double adjacent errors that are a major multiple error pattern. An important consideration is that the ECC encoder and decoder circuits can also be affected by soft errors, which will corrupt the memory data. In this paper, a method to design fault tolerant encoders for SEC-DAEC codes is proposed. It is based on the fact that soft errors in the encoder have a similar effect to soft errors in a memory word and achieved by using logic sharing blocks for every two adjacent parity bits. In the proposed scheme, one soft error in the encoder can cause at most two errors on adjacent parity bits, thus the correctness of memory data can be ensured because those errors are correctable by the SEC-DAEC code. The proposed scheme has been implemented and the results show that it requires less circuit area and power than the encoders protected by the existing methods.     

Fault-Tolerant Bit-Parallel Multiplier for Polynomial Basis of GF(2m)

Novel fault-tolerant architectures for bit-parallel polynomial basis multiplier over GF(2m), which can correct the erroneous outputs using linear code, are presented. A parity prediction circuit based on the code generator polynomial that leads lower space overhead has been designed. For bit-parallel architectures, the space overhead is about 11%. Moreover, there is only marginal time overhead due to incorporation of error-correction capability that amounts to 3.5% in case of the bit-parallel multiplier. Unlike the existing concurrent error correction (CEC) multipliers or triple modular redundancy (TMR) techniques for single error correction, the proposed architectures have multiple error-correcting capabilities.     

Fault-Tolerant Bit-Parallel Multiplier for Polynomial Basis of GF（2^m）

Novel fault-tolerant architectures for bit-parallel polynomial basis multiplier over GF（2^m）, which can correct the erroneous outputs using linear code, are presented. A parity prediction circuit based on the code generator polynomial that leads lower space overhead has been designed. For bit-parallel architectures, the Moreover, there is incorporation of space overhead only marginal time error-correction is about 11%. overhead due to capability that amounts to 3.5% in case of the bit-parallel multiplier. Unlike the existing concurrent error correction （CEC） multipliers or triple modular redundancy （TMR） techniques for single error correction, the proposed architectures have multiple error-correcting capabilities.     

Synthesis of Circuits with Low-Cost Concurrent Error Detection Based on Bose-Lin Codes

This paper presents a procedure for synthesizing sequential machines with concurrent error detection based on Bose-Lin codes. Bose-Lin codes are an efficient solution for providing concurrent error detection as they are separable codes and have a fixed number of check bits, independent of the number of information bits. Furthermore, Bose-Lin code checkers have a simple structure as they are based on modulo operations. Procedures are described for synthesizing circuits in a way that their structure ensures that all single-point faults can only cause errors that are detected by a Bose-Lin code. This paper presents an efficient scheme for concurrent error detection in sequential circuits with no constraint on the state encoding. Concurrent error detection for both the state bits and the output bits is based on a Bose-Lin code and their checking is combined such that one checker suffices. Results indicate low area overhead. The cost of concurrent error detection is reduced significantly compared to other methods based on other codes.     

Design, analysis, and evaluation of concurrent checking sortingnetworks

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%~30% hardware) but still achieves virtually 1001 fault coverage     

ATPG for combinational circuits on configurable hardware

In this paper, a new approach for generating test vectors that detects faults in combinational circuits is introduced. The approach is based on automatically designing a circuit which implements the D-algorithm, an automatic test pattern generation (ATPG) algorithm, specialized for the combinational circuit. Our approach exploits fine-grain parallelism by performing the following in three clock cycles: direct backward/forward implications, conflict checking, selecting next gate to propagate fault or to justify a line, decisions on gate inputs, and loading the state of the circuit after backup. In this paper, we show the feasibility of this approach in terms of hardware cost and speed and how it compares with software-based techniques     

Modelling digital circuits with delays by Stochastic Petri Nets

The analysis of the behaviour of digital circuits, with special reference to signal propagation delays, is performed by means of the Petri Nets (PN) formal model. In particular, concurrent signal changes in the circuit which may give rise to possible functional errors such as races or hazards, are represented by this model. Moreover, the delays, assumed to be random variables with assigned probability distributions and Stochastic Petri Nets (SPN), which are an extension of classical PN's, are employed. By the resulting model, a great flexibility of representation is achieved, matching also the requisites of the particular technology employed.It is also possible to account for time varying inputs both in combinational and sequential circuits, reconvergent fanouts and conflicting events.The algorithm derived from this model allows to obtain a static logic verification of the circuit and exhibits shorter simulation times as compared to those of classical simulators.     

A concurrent built-in self-test architecture based on a self-testing RAM

Manufacturing test is carried-out once to ensure the correct operation of the circuit under test right after fabrication, while testing is carried-out periodically to ensure that the circuit under test continues to operate correctly on the field. The use of offline built-in self-test (BIST) techniques for periodic testing imposes the interruption of the normal operation of the circuit under test. On the other hand, the use of input vector monitoring concurrent BIST techniques for periodic testing provides the capability to perform the test, while the circuit under test continues to operate normally. In this paper, a novel input-vector monitoring concurrent BIST technique for combinational circuits based on a self-testing RAM, termed R-CBIST, is presented. The presented technique compares favorably to the other input vector monitoring concurrent BIST techniques proposed so far with respect to the hardware overhead, and the time required for the concurrent test to be completed (concurrent test latency). R-CBIST can be utilized to test ROM because it results in small hardware overhead, whereas there is no need to stop the ROM normal operation.