This paper presents a new feedback shift register-based method for embedding deterministic test patterns on-chip suitable for complementing conventional BIST techniques for in-field testing. Our experimental results on 8 real designs show that the presented approach outperforms the bit-flipping approach by 24.7 on average. We also show that it is possible to exploit the uneven distribution of don't care bits in test patterns in order to reduce the area required for storing deterministic test patterns more than 3 times with less than 2 fault coverage drop.
The problem of constructing a binary machine with the minimum number of stages generating a given binary sequence is addressed. Binary machines are a generalization of nonlinear feedback shift registers (NLFSRs) in which both connections, feedback and feedforward, are allowed and no chain connection between the register stages is required. An algorithm for constructing a shortest binary machine generating a given periodic binary sequence is presented. 1. Introduction.- 1.1 Design Styles for VLSI Systems.- 1.2 Automatic Logic Synthesis.- 1.3 PLA Implementation.- 1.4 History of Logic Minimization.- 1.5 ESPRESSO-II.- 1.6 Organization of the Book.- 2. Basic Definitions.- 2.1 Operations on Logic Functions.- 2.2 Algebraic Representation of a Logic Function.- 2.3 Cubes and Covers.- 3. Decomposition and Unate Functions.- 3.1 Cofactors and the Shannon Expansion.- 3.2 Merging.- 3.3 Unate Functions.- 3.4 The Choice of the Splitting Variable.- 3.5 Unate Complementation.- 3.6 SIMPLIFY.- 4. The ESPRESSO Minimization Loop and Algorithms.- 4.0 Introduction.- 4.1 Complementation.- 4.2 Tautology.- 4.2.1 Vanilla Recursive Tautology.- 4.2.2 Efficiency Results for Tautology.- 4.2.3 Improving the Efficiency of Tautology.- 4.2.4 Tautology for Multiple-Output Functions.- 4.3 Expand.- 4.3.1 The Blocking Matrix.- 4.3.2 The Covering Matrix.- 4.3.3 Multiple-Output Functions.- 4.3.4 Reduction of the Blocking and Covering Matrices.- 4.3.5 The Raising Set and Maximal Feasible Covering Set.- 4.3.6 The Endgame.- 4.3.7 The Primality of c+.- 4.4 Essential Primes.- 4.5 Irredundant Cover.- 4.6 Reduction.- 4.6.1 The Unate Recursive Paradigm for Reduction.- 4.6.2 Establishing the Recursive Paradigm.- 4.6.3 The Unate Case.- 4.7 Lastgasp.- 4.8 Makesparse.- 4.9 Output Splitting.- 5. Multiple-Valued Minimization.- 6. Experimental Results.- 6.1 Analysis of Raw Data for ESPRESSO-IIAPL.- 6.2 Analysis of Algorithms.- 6.3 Optimality of ESPRESSO-II Results.- 7. Comparisons and Conclusions.- 7.1 Qualitative Evaluation of Algorithms of ESPRESSO-II.- 7.2 Comparison with ESPRESSO-IIC.- 7.3 Comparison of ESPRESSO-II with Other Programs.- 7.4 Other Applications of Logic Minimization.- 7.5 Directions for Future Research.- References.