Avoiding linear dependencies in LFSR test pattern generators

Linear Feedback Shift Registers (LFSRs) constitute a very efficient mechanism for generating pseudoexhaustive or pseudo-random test sets for the built-in self-testing of digital circuits. However, a well-known problem with the use of LFSRs is the occurrence of linear dependencies in the generated patterns. In this paper, we show for the first time that the amount of linear dependencies can be controlled by selecting appropriate characteristic polynomials and reordering the LFSR cells. We identify two classes of such polynomials which, by appropriate LFSR cell ordering, guarantee that a large ratio of linear dependencies cannot occur. Experimental results show significant enhancements on the fault coverage for pseudo-random testing and support the theoretical relation between minimization of linear dependencies and effective fault coverage.This work was partially supported by NSF grant MIP-9409905, a 1993–94 ACM/IEEE Design Automation Scholarship and a grant from Nissan Corporation. A preliminary version of this work appeared in A Class of Good Characteristic Polynomials for LFSR Test Pattern Generators, in Proc. of IEEE International Conference on Computer Design, Oct. 1994, pp. 292–295, where it received the ICCD'94 Best Paper Award.     

Recursive Pseudo-Exhaustive Two-Pattern Generation

Pseudo-exhaustive pattern generators for built-in self-test (BIST) provide high fault coverage of detectable combinational faults with much fewer test vectors than exhaustive generation. In $(n, k)$-adjacent bit pseudo-exhaustive test sets, all $2^{k}$ binary combinations appear to all adjacent $k$-bit groups of inputs. With recursive pseudoexhaustive generation, all $(n, k)$-adjacent bit pseudoexhaustive tests are generated for ${k}leq{n}$ and more than one modules can be pseudo-exhaustively tested in parallel. In order to detect sequential (e.g., stuck-open) faults that occur into current CMOS circuits, two-pattern tests are exercised. Also, delay testing, commonly used to assure correct circuit operation at clock speed requires two-pattern tests. In this paper a pseudoexhaustive two-pattern generator is presented, that recursively generates all two-pattern $(n, k)$-adjacent bit pseudoexhaustive tests for all ${k}leq{n}$. To the best of our knowledge, this is the first time in the open literature that the subject of recursive pseudoexhaustive two-pattern testing is being dealt with. A software-based implementation with no hardware overhead is also presented.      

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     

LFSR Reseeding-Oriented Low-Power Test-Compression Architecture for Scan Designs

Massive test data volume and excessive test power consumption have become two strict challenges for very large scale integrated circuit testing. In BIST architecture, the unspecified bits are randomly filled by LFSR reseeding-based test compression scheme, which produces enormous switching activities during circuit testing, thereby causing high test power consumption for scan design. To solve the above thorny problem, LFSR reseeding-oriented low-power test-compression architecture is developed, and an optimized encoding algorithm is involved in conjunction with any LFSR-reseeding scheme to effectively reduce test storage and power consumption, it includes test cube-based block processing, dividing into hold partition sets and updating hold partition sets. The main contributions is to decrease logic transitions in scan chains and reduce specified bit in test cubes generated via LFSR reseeding. Experimental results demonstrate that the proposed scheme achieves a high test compression efficiency than the existing methods while significantly reduces test power consumption with acceptable area overhead for most Benchmark circuits.     

Partitioning algorithm to enhance pseudoexhaustive testing ofdigital VLSI circuits

This brief introduces a partitioning algorithm, which facilitates pseudoexhaustive testing, to detect and locate faults in digital VLSI circuits. The algorithm is based on an analysis of circuit's primary input cones and fanout (PIFAN) values. An invasive approach is employed, which creates logical and physical partitions by automatically inserting reconfigurable test cells and multiplexers. The test cells are used to control and observe multiple partitioning points, while the multiplexers expand the controllability and observability provided by the test cells. The feasibility and efficiency of our algorithm are evaluated by partitioning numerous ISCAS 1985 and 1989 benchmark circuits containing up to 5597 gates. Our results show that the PIFAN algorithm offers significant reductions in overhead and test time when compared to previous partitioning algorithms     

Partitioning sequential circuits for pseudoexhaustive testing

In this paper, we present an algorithm for partitioning sequential circuits. This algorithm is based on an analysis of a circuit's primary input cones and fanout values (PIFAN), and it uses a directed acyclic graph to represent the circuit. An invasive approach is employed, which creates logical and physical partitions by automatically inserting reconfigurable test cells and multiplexers. The test cells are used to control and observe multiple partitioning points, while the multiplexers expand the controllability and observability provided by the test cells. The feasibility and efficiency of our algorithm are evaluated by partitioning numerous standard digital circuits, including some large benchmark circuits containing up to 5597 gates. Our algorithm is based upon pseudoexhaustive testing methods where fault simulation is not required for test-pattern generation and grading; hence, engineering design time and cost are further reduced     

一种高效的混合Test-Per-Clock测试方法

该文提出了一种基于内建自测试(BIST)的Test-Per-Clock混合模式向量产生方法。测试由两个部分组成：自由线性反馈移位寄存器(LFSR)伪随机测试模式和受控LFSR确定型测试模式。伪随机测试模式用于快速地检测伪随机易测故障,减少确定型数据存储。受控LFSR测试模式采用直接存储在ROM中的控制位流对剩余故障产生确定型测试。通过对提出的BIST混合模式测试结构理论分析,提出了伪随机向量的选取方法以及基于受控线性移位确定型测试生成方法。基准电路的仿真结果表明,该方法可以获得完全单固定型故障覆盖率,其测试产生器设计简单且具有良好的稳定性,与其他方法相比,具有较低的测试开销和较短的测试应用时间。     

A new reconfigurable Test Vector Generator for built-in self-test applications

This paper proposes a new approach to designing a BIST Test Vector Generator (TVG) for random vector-resistant circuits based on reconfigurable Cellular Automata Registers (CARs). Each CAR configuration is constructed by combining rules 90 and 150 and the same approach can also be applied to the Linear Feedback Shift Register (LFSR). The TVG thus designed is able to produce 100% fault coverage with short test time at the cost of low area overhead. To achieve this objective, a new method called the Rank Order Clustering (ROC) method, is introduced in order to fix a number of inputs at certain values when generating pseudorandom vectors. It is shown that the ROC method is very simple and efficient in fixing inputs at these values in terms of complexity. Experimental results have been conducted to demonstrate the applicability of the proposed approach in terms of hardware size and test application time.     

A New Scan Architecture for Both Low Power Testing and Test Volume Compression Under SOC Test Environment

A new scan architecture for both low power testing and test volume compression is proposed. For low power test requirements, only a subset of scan cells is loaded with test stimulus and captured with test responses by freezing the remaining scan cells according to the distribution of unspecified bits in the test cubes. In order to optimize the proposed process, a novel graph-based heuristic is proposed to partition the scan chains into several segments. For test volume reduction, a new LFSR reseeding based test compression scheme is proposed by reducing the maximum number of specified bits in the test cube set, s _max, virtually. The performance of a conventional LFSR reseeding scheme highly depends on s _max. In this paper, by using different clock phases between an LFSR and scan chains, and grouping the scan cells by a graph-based grouping heuristic, s _max could be virtually reduced. In addition, the reduced scan rippling in the proposed test compression scheme can contribute to reduce the test power consumption, while the reuse of some test results as the subsequent test stimulus in the low power testing scheme can reduce the test volume size. Experimental results on the largest ISCAS89 benchmark circuits show that the proposed technique can significantly reduce both the average switching activity and the peak switching activity, and can aggressively reduce the volume of the test data, with little area overhead, compared to the previous methods.

基于双模式LFSR的低功耗BIST结构

传统的BIST结构中,由于LFSR产生大量的测试矢量在测试过程中消耗了大量的功耗。为了减少测试矢量的数目而不影响故障覆盖率,我们提出了一种新的基于双模式LFSR的低功耗BIST结构。首先介绍了功耗模型和延迟模型的基础知识,然后给出了用于生成双模式LFSR的矩阵,并介绍了解矩阵方程式的算法。随后说明了新的BIST结构和用于矢量分组的模拟退火算法。最后,基于Benchmark电路的实验证明这种结构可以在不降低故障覆盖率的同时减少70％的功耗。     

LFSR Characteristic Polynomials for Pseudo-Exhaustive TPG with Low Number of Seeds

A fully scanned digital circuit can be tested pseudo-exhaustively by first introducing a number of extra bypass storage cells to limit the test-phase input dependency of each test-phase output and then using a Linear Feedback Shift Register (LFSR) to feed the chain of the original scan cells and the extra cells. For the design of the LFSR, the goal is to minimize the pseudo-exhaustive test length with low hardware overhead. If the LFSR uses a primitive characteristic polynomial then it requires only one seed, but the candidate primitive polynomials may all fail to satisfy the target test length. In this paper, we present a methodology that enlarges the list of candidate polynomials, if the prescribed number of seeds is more than one. Experimental results show that the new candidate polynomials are often instrumental in satisfying the given test length and seed restriction.     

基于动态覆盖率提高门槛值的种子计算方法

为了向可重复播种的LFSR结构提供种子,提出一种基于动态覆盖率提高门槛值(Dynamic Coverage Im-provement Threshold,DCIT)的种子计算方法.使用该方法计算得到的种子进行重复播种,能够截断对提高故障覆盖率效率低的测试码序列.每个种子可以得到长度固定的伪随机测试序列.以ISCAS85基准电路实验结果表明,该方案能够在不降低故障覆盖率的前提下,减少测试矢量长度、缩短测试时间和降低测试功耗.     

Bit-swapping LFSR for low-power BIST

A modified linear feedback shift register (LFSR) is presented that reduces the number of transitions at the inputs of the circuit-under-test by 25% using a bit-swapping technique. Experimental results on ISCAS'85 and 89 benchmark circuits show up to 45% power reduction during test. They also show that the proposed design can be combined with other techniques to achieve a very substantial power reduction of up to 63%.     

An efficient design of embedded memories and their testability analysis using Markov chains

This article presents a design strategy for efficient and comprehensive random testing of embedded random-access memory (RAM) where neither are the address, read/write and data input lines directly controllable nor are the data output lines externally observable. Unlike the conventional approaches, which frequently employ on-chip circuits such as linear feedback shift register (LFSR), data registers and multibit comparator for verifying the response of the memory-under-test (MUT) with the reference signature of a fault-free gold unit, the proposed technique uses an efficient testable design, which helps accelerate test algorithms by a factor of 0.5n, if the RAM is organized into an n×1 array and improve the test reliability by eliminating the LFSR that is known to have aliasing problems. Another serious problem in embedded memory testing by random test patterns is the problem of memory initialization, which has been tackled here by adding word-line flag registers. The paper has made indepth empirical studies of the functional faults such as stuck-at, coupling, and pattern-sensitive by suitably representing these faults by Markov chains and by simulating these chains to derive various test lengths required for detecting these faults. The simulation results conclusively show that, in order to test a IM-bit RAM for detecting the common functional faults, the proposed technique needs only one second as opposed to about an hour needed by the conventional random testing where memory cells are tested sequentially.An abridged version of this article was published in the IEEE International Conference on Wafer-Scale Integration, January 1989. This research was partially supported by the NSF under grant number MIP-9013092 and by ONR under grant number 85-K-0716.     

A Note on the Periodicity and the Output Rate of Bit Search Type Generators

In this paper, the bit-search type irregular decimation algorithms, that are used within linear-feedback shift register (LFSR)-based stream ciphers, are investigated. In particular, bit-search generator (BSG) and and its variant ABSG are concentrated on and two different setups are considered for the analysis. In the first case, the input is assumed to be an m-sequence; it is shown that all possible output sequences can be classified into two sets, each of which is characterized by the equivalence of their elements up to shifts. Furthermore, it is proved that the cardinality of each of these sets is equal to the period of one of its elements and subsequently the (upper and lower) bounds on the expected output period (assuming that no subperiods exist) are derived. In the second setup, we work in a probabilistic framework and assume that the input sequence is evenly distributed (i.e., independent and identically distributed (i.i.d.) Bernoulli process with probability 1/2). Under these assumptions, closed-form expressions are derived for the distribution of the output length and the output rate, which is shown to be asymptotically Gaussian-distributed and concentrated around the mean with exponential tightness.     

一种新的低功耗内建自测法 􀀂 􀀂 􀀂 线性反馈移位寄存器结构的更改

本文提出了一种通过改变线性反馈移位寄存器（LFSR）的结构实现低功耗内建自测试方法。在伪随机测试方式下，随着测试的进行，测试矢量的效率大幅降低。通过改变线性反馈移位寄存器的结构滤掉无效的测试矢量从而实现低功耗测试。实践证明，改变线性反馈称位寄存器的结构的方法是有效的并且对故障覆盖率没有影响。     

Design of test sequences for VLSI self-testing using LFSR

Consider a shift register (SR) of length n and a collection of designated subsets of {0,1, . . ., n-1}. The problem is how to add feedback to the SR such that the resulting linear feedback shift register (LFSR) exercises (almost) exhaustively each of the designated subsets and is of small period. Several previously known results for maximum-length LFSR are extended to more general LFSR, and in particular a previously known algorithm is simplified and extended. Applications to the problems of VLSI self-testing are discussed and illustrated     

Testing of multiple-output domino logic (MODL) CMOS circuits

Techniques for testing MODL circuits are presented. It is shown that, due to the greater observability of MODL circuits, their test sets can be considerably small than those derived for the conventional domino CMOS circuits. Tests for faults are derived from a comprehensive fault model which includes stuck-at, stuck-open, and stuck-on faults. Test sets for MODL circuits are inherently robust in the presence of circuit delays and timing skews at the inputs. They are also well-protected against the charge distribution problem. It is thus concluded that MODL is an attractive CMOS logic technique     

Testing of differential cascade voltage switch (DCVS) circuits

The problem of testing differential cascode voltage switch (DCVS) circuits is analyzed. These circuits have several potential applications in fault-tolerant, highly available system design due to their inherent self-checking capability. It is shown how concurrent (online) testing of DCVS circuits, which is very effective under single transistor fault assumptions, can be performed. The impact of multiple faults of DCVS circuits is examined, and analytical results are derived. These results indicate that periodic offline tests on DCVS circuits are necessary in order to achieve high multiple-fault coverage. Single-fault test sets and/or pseudorandom vectors were successfully used in the offline tests to detect many of the multiple faults which reduce the efficiency of online tests. The results show the need for a comprehensive mixed-test strategy combining offline and online tests for DCVS circuits     

Multifault and delay-fault testability of multilevel circuits

This paper investigates the relationship between test sets for multiple stuck-at faults and robust path-delay-fault tests in multilevel combinational circuits. It is shown that, in multilevel circuits, a complete robust path-delay-fault test set may not detect all multiple stuck-at faults. We also show that the detectability of the former does not imply the detectability of the latter, as suggested in a recent paper. The presence of undetectable or untested multiple stuck-at faults may invalidate some path delay tests.Supported in part by NSF Grant MIP-9320886.