Testable Design and BIST Techniques for Systolic Motion Estimators in Transform Domain

Testable design techniques for systolic motion estimators based on M-testability conditions are proposed in this paper. The whole motion estimator can be viewed as a two-dimensional iterative logic array （ILA） of processing elements （PEs） and multiplying elements （MULs）. The functions of each PE and MUL are modified to be bijective to meet the M-testable conditions. The number of test patterns is 2^w, where w denotes the word length of a PE. The proposed testable design techniques are also suitable for built-in self-test implementation. According to experimental results, our approaches can achieve 99.27 % fault coverage. The area overhead is about 9 %. To verify our approaches, an experimental chip is also implemented.     

On methods to match a test pattern generator to acircuit-under-test

Autonomous circuits such as linear feedback shift registers (LFSRs) and cellular automats are used as low-cost test pattern generators for circuits testable by pseudo-random patterns. We demonstrate that different LFSRs of the same degree, started from different initial states, may yield significantly different fault coverages and test lengths when used as test pattern generators for a given circuit, especially when the circuit has faults which are hard to detect by a practical number of pseudo-random patterns. Methods to tailor an LFSR to a circuit-under-test are proposed, that attempt to select the most effective LFSR and initial state for the circuit. The first method is based on a learning process that can be applied directly to certain types of circuits. The learning process is also used to establish a collection of (primitive and nonprimitive) LFSRs and initial states, effective for arbitrary circuits. This collection can then be used as a starting point for a genetic optimization procedure aimed at improving the selected LFSR and initial state. The use of an LFSR that can apply complemented as well as uncomplemented test patterns is shown to significantly improve the fault coverage, at the cost of a small area overhead. Experimental results demonstrate the applicability of the proposed approaches to stuck-at faults and to transition faults     

TESTCHIP: a chip for weighted random pattern generation,evaluation, and test control

In self-testable circuits, additional hardware is incorporated for generating test patterns and evaluating test responses. A built-off test strategy is presented which moves the additional hardware to a programmable extra chip. This is a low-cost test strategy in three ways: (1) the use of random patterns eliminates the expensive test-pattern computation; (2) a microcomputer and an ASIC (application-specific IC) replace the expensive automatic test equipment; and (3) the design for testability overhead is minimized. The presented ASIC generates random patterns, applies them to a circuit under test, and evaluates the test responses by signature analysis. It contains a hardware structure that can produce weighted random patterns corresponding to multiple programmable distributions. These patterns give a high fault coverage and allow short test lengths. A wide range of circuits can be tested as the only requirement is a scan path and no other test structures have to be built in     

Techniques for estimating test length under random test

When a circuit is tested using random or pseudorandom patterns, it is essential to determine the amount of time (test length) required to test it adequately. We present a methodology for predicting different statistics of random pattern test length. While earlier methods allowed estimation only of upper bounds of test length and only for exhaustive fault coverage, the technique presented here is capable of providing estimates of all statistics of interest (including expected value and variance) for all coverage specifications.Our methodology is based on sampling models developed for fault coverage estimation [1]. Test length is viewed as awaiting time on fault coverage. Based on this relation we derive the distribution of test length as a function of fault coverage. Methods of approximating expected value and variance of test length are presented. Accuracy of these approximations can be controlled by the user. A practical technique for predicting expected test length is developed. This technique is based on clustering faults into equal detectability subsets. A simple and effective algorithm for fault clustering is also presented. The sampling model is applied to each cluster independently and the results are then aggregated to yield test lengths for the whole circuit. Results of experiments with several circuits (both ISCAS '85 benchmarks and other practical circuits) are also provided.This work was done while the author was with the Department of Electrical Engineering, Southern Illinois University, Carbondale, IL 62901.     

Physical design of testable VLSI: techniques and experiments

It is shown that the layout of VLSI circuits can affect testability and in some cases reduce the number of faults likely in a design, easing test generation. A method for analyzing circuits at the symbolic layout level and enhancing testability using local transformations is presented. To demonstrate the application of the technique a set of CMOS standard cells was redesigned. The standard cells are used in the MIS synthesis system, allowing the designer to modify interactively designs to perform tradeoff analysis on testable designs. To show the usefulness of the technique, an experiment was performed: example circuits were synthesized, and test vectors were generated and then used in a transistor-level fault simulator. It was found that the modified designs have significantly higher fault coverage than unmodified designs. A strategy for the synthesis of easily testable combinational random logic circuits is presented     

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.     

Combined probabilistic testability calculation and compact test generation for PLAs

PLAs (programmable logic arrays) may be tested internally by self-test, or externally by applying test patterns. Fault coverage by nonexhaustive self-test is assured by computing a lower bound for estimated fault coverage vs. test pattern number. First, a lower bound for probabilistic detectability per fault is computed by a method based on Shannon's expansion theorem. In the process of finding a lower bound detectability for a particular fault, a test pattern for the fault is generated automatically, at no extra cost. These patterns often contain several don't cares. Traditional test pattern compaction is then applied to the test pattern set. In addition, a novel test pattern compaction method is introduced, suitable for embedded circuitry. The method may be used in conjunction with a serial scan architecture, whereby each test pattern is shifted one position before being applied to the circuit under test. The compaction scheme was applied to a benchmark set of 53 PLAs. An average reduction of 70% in the number of test bits and clock cycles was achieved.¹ This work was done while B. Reppen was with the Norwegian Institute of Technology.     

Online Testable Approaches in Reversible Logic

We present an overview and analysis of existing work in the design of online testable reversible logic circuits, as well as propose new approaches for the design of such circuits. We explain how previously proposed approaches are unnecessarily high in overhead and in many cases do not provide adequate fault coverage. Proofs of the correctness of our approaches are provided, and discussions of the advantages and disadvantages of each design approach are given. Experimental results comparing our approaches to existing work are presented as well. Both approaches that we propose have better fault coverage and significantly lower overheads than previous approaches.     

Design for Test of Asynchronous NULL Convention Logic (NCL) Circuits

Due to the absence of a global clock and the presence of more state holding elements that synchronize the control and data paths, conventional Automatic Test Pattern Generation (ATPG) algorithms fail when applied to asynchronous circuits, leading to poor fault coverage. This paper presents a design for test (DFT) technique for a popular asynchronous design paradigm called NULL Convention Logic (NCL) aimed at making NCL designs testable using existing DFT tools with reasonable gate overhead. The proposed technique performs test points (TPs) insertion using Sandia Controllability and Observability Program (SCOAP) analysis to enhance the controllability of feedback nets and observability for fault sites that are flagged unobservable. An Automatic DFT Insertion Flow (ADIF) algorithm and a custom ATPG NCL primitive gates library are developed. The developed DFT technique has been verified on several NCL benchmark circuits

Multiple Stuck-at Fault Testability Analysis of ROBDD Based Combinational Circuit Design

Automatic test pattern generation (ATPG) is the next step after synthesis in the process of chip manufacturing. The ATPG may not be successful in generating tests for all multiple stuck-at faults since the number of fault combinations is large. Hence a need arises for highly testable designs which have 100% fault efficiency under the multiple stuck-at fault(MSAF) model. In this paper we investigate the testability of ROBDD based 2×1 mux implemented combinational circuit design. We show that the ROBDD based 2×1 mux implemented circuit is fully testable under multiple stuck-at fault model. Principles of pseudoexhaustive testing and multiple stuck-at fault testing of two level AND-OR gates are applied to one sub-circuit(2×1 mux). We show that the composite test vector set derived for all 2×1 muxes is capable of detecting multiple stuck-at faults of the circuit as a whole. Algorithms to derive test set for multiple stuck-at faults are demonstrated. The multiple stuck-at fault test set is larger than the single stuck-at fault test set. We show that the multiple stuck-at fault test set can be derived from the Disjoint Sum of Product expression which allows test pattern generation at design time, eliminating the need of an ATPG after the synthesis stage.     

The OR-k method for on-line checking of programmable logic arrays

A programmable logic array (PLA) is nonconcurrent if every input pattern selects exactly one product term. We relax this requirement to limited concurrency where all product terms selected by the same input pattern must have identical output parts. A new testing method, OR-k testability, is developed for the on-line (concurrent) checking of limited concurrency PLAs. OR-k testing detects errors due to the selection of one or more extra product terms, and a conventional two-rail parity check on the outputs detects the other errors from single stuck-at, bridging, cross-point and broken line faults. The output patterns of an OR-k testable PLA must be unordered. For such PLAs, certain subsets of the outputs take on an all 1's pattern only in the presence of an extra product term error condition. A limited concurrency PLA tested by OR-k testability is strongly fault secure.This work was supported in part by the Natural Sciences and Engineering Research Council of Canada.     

DFT Techniques and Automation for Asynchronous NULL Conventional Logic Circuits

Conventional automatic test pattern generation (ATPG) algorithms fail when applied to asynchronous NULL convention logic (NCL) circuits due to the absence of a global clock and presence of more state-holding elements, leading to poor fault coverage. This paper presents a design-for-test (DFT) approach aimed at making asynchronous NCL designs testable using conventional ATPG programs. We propose an automatic DFT insertion flow (ADIF) methodology that performs scan and test point insertion on NCL designs to improve test coverage, using a custom ATPG library. Experimental results show significant increase in fault coverage for NCL cyclic and acyclic pipelined designs.     

A class of two-dimensional cellular automata and their applications in random pattern testing

A basic framework to characterize the behavior of two-dimensional (2-D) cellular automata (CA) has been proposed. The performance of the regular structure of the 2-D CA has been evaluated for pseudo-random pattern generation. The potential increase in the local neighborhood structure for 2-D CA has led to better randomness of the generated patterns as compared to LFSR and 1-D CA. The quality of the random patterns generated with 2-D CA based built-in-self-test (BIST) structure has been evaluated by comparing the fault coverage on several benchmark circuits. Also a method of synthesizing 2-D CAs to generate patterns of specified length has been reported. The patterns generated can serve as a very good source of random two-dimensional sequences and also variable length parallel pattern generation having virtually nil correlation among the bit patterns.     

阵列乘法器通路时延故障的内建自测试

阵列乘法器因高度集成和高速运行,容易受到时延故障的困扰.该文对阵列乘法器的通路时延故障提出了一种用累加器实现的以单跳变序列作为测试序列的内建自测试方案.已有的理论和实践表明采用单跳变测试序列比多跳变序列具有更高的测试鲁棒性.同时,该文的测试方案在测试通路覆盖率和测试向量数之间做到了兼顾.仿真结果表明这种单跳变测试序列具有高测试通路覆盖率.此外,测试生成通过系统已有累加器的复用可节省硬件成本开销.     

A Ring Architecture Strategy for BIST Test Pattern Generation

This paper presents a new effective Built-In Self Test (BIST) scheme that achieves 100% fault coverage with low area overhead, and without any modification of the circuit under test (CUT), i.e., no test point insertion. The set of patterns generated by a pseudo-random pattern generator, e.g. a Linear Feedback Shift Register (LFSR), is transformed into a new set of patterns that provides the desired fault coverage. To transform these patterns, a ring architecture composed by a set of masks is used. During on-chip test pattern generation, each mask is successively selected to map the original pattern sequence into a new test sequence. We describe an efficient algorithm that constructs a ring of masks from the test cubes provided by an automatic test pattern generator (ATPG) tool. Moreover, we show that rings of masks are implemented very easily at low silicon area cost, without requiring any logic synthesis tool; a combinational mapping logic corresponding to the masks is placed between the LFSR and the CUT, together with a looped shift register that acts as a mask selecting circuit. Experimental results are given at the end of the paper, demonstrating the effectiveness of the proposed approach in terms of area overhead, fault coverage and test sequence length. Note that this paper is an extended version of [1].     

Efficient design of parity preserving logic in quantum-dot cellular automata targeting enhanced scalability in testing

Design of parity preserving logic based on emerging nanotechnology is very limited due to present technological limitation in tackling its high error rate. In this work, Quantum-dot cellular automata (QCA), a potential alternative to CMOS, is investigated for designing easily testable logic circuit. A novel self-testable logic structure referred to as the testable-QCA (t-QCA), using parity preserving logic, is proposed. Design flexibility of t-QCA then evaluated through synthesis of standard functions. The programmability feature of t-QCA is utilized to implement an ALU, realizing six important functions. Although the parity preservation property of t-QCA enables concurrent detection of permanent as well as the transient faults, an augmented test logic circuit (TC) using QCA primitives has been introduced to cover the cell defects in nanotechnology. Experimental results establish the efficiency of the proposed design that outperforms the existing technologies in terms of design cost and test overhead. The achievement of 100% stuck-at fault coverage and the 100% fault coverage for single missing/additional cell defects in QCA layout of the t-QCA gate, address the reliability issues of QCA nano-circuit design.     

用可测性设计的方法设计PLA

全面、有效地测试PLA ,是保证PLA类产品可靠性的重要手段。在设计的同时就考虑其测试问题 ,是解决PLA测试问题行之有效的方法。介绍了怎样用可测性设计的方法解决PLA的测试问题 ,给出了几种具体的实施方案 ,并对这些方案进行了分析     

A partial scan design unifying structural analysis and testabilities

To overcome the large extra hardware overhead attendant in full scan design, the concept of partial scan designs has emerged with the virtue of less area and testability close to full scan. Two typical partial scan techniques, based on structural analysis and testabilities, are widely adopted. The structural analysis requires less searching time, however in general the fault coverage is lower. On the other hand, the techniques using testabilities result in higher fault coverage, but require an extraordinary amount of searching time. In this paper we have analysed and unified the strength of techniques using structural analysis and testabilities. The new partial scan design proposed not only reduces the time for selecting scan flip-flop but also preserves high fault coverage. Test results demonstrate the high fault coverage and remarkable reduction in time for most ISCAS89 benchmark circuits.     

Physical design of testable CMOS digital integrated circuits

A methodology for physical testability assessment and enhancement, implemented with a set of test tools, is presented. The methodology, which can improve the physical design of testable CMOS digital ICs, is supported in realistic fault-list generation and classification. Two measures of physical testability, weighted class fault coverage and fault incidence, and one measure of fault hardness are introduced. The testability is evaluated prior to fault simulation; difficult-to-detect faults are located on the layout and correlated with the physical defects which originate them; and suggestions for layout reconfiguration are provided. Several design examples are described, ascertaining the usefulness of the proposed methodology. The proposed methodology demonstrated that stuck-at test sets only partially cover the realistic faults in digital CMOS designs. Moreover, it is shown that classical fault models of arbitrary faults are insufficient to describe the realistic fault set. Simulation results have shown that the fault set strongly depends on the technology and on the layout style     

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