Structure Design and Optimization of 2-D LFSR-Based Multisequence Test Generator in Built-In Self-Test

This paper addresses the optimization of very large scale integration testing systems, specifically the structure design and optimization of a built-in self-test (BIST) design based on two-dimensional (2D) linear feedback shift registers (LFSRs). The 2D LFSRs can generate both precomputed test patterns (for detecting random-pattern-resistant faults) and random patterns (for detecting random-pattern-detectable faults) and have the advantages of high fault coverage and at-speed testing. To guarantee solutions, it is necessary and desirable to generate subsequences of the precomputed test patterns through the 2D LFSRs, where these subsequences retain the order of the test patterns, particularly for testing sequential circuits. For the design and optimization of the 2D LFSRs, the following two problems need to be solved: 1) the good partitioning of the precomputed test patterns into disjoint subsequences in order to achieve a minimal hardware and 2) the structure design and optimization of the 2D LFSRs to generate the test patterns in each partitioned subsequence. The optimization of the 2D LFSRs is modeled as an integer program (a logic optimization model) that determines the coefficients of the recursive Boolean equations that govern the generation of the test patterns. For a sequence of the test patterns, this model finds the minimal-hardware implementation of the 2D LFSRs. This logic optimization model can be applied to both test-per-scan (serial BIST) and test-per-clock (parallel BIST). This paper presents how this model is embedded in a heuristic framework to partition the test patterns into subsequences from the configurable 2D LFSRs. The testing hardware is small as the configurable architecture allows the tester to incrementally generate the precomputed test patterns by modification to the feedback of the 2D LFSRs. Results of benchmark circuits show that significant hardware reduction and higher fault coverage are achieved. The resulting multisequence test gene- - rator is a regular structure and is easy to implement. The logic optimization model is applicable to both completely and partially specified test patterns and can be adopted for other LFSR-based structure design and optimization.