Quantitative analysis for linear hybrid cellular automata and LFSR as built-in self-test generators for sequential faults

This paper presents a combinatorial method of evaluating the effectiveness of linear hybrid cellular automata (LHCA) and linear feedback shift registers (LFSR) as generators for stimulating faults requiring a pair of vectors. We provide a theoretical analysis and empirical comparisons to see why the LHCA are better than the LFSRs as generators for sequential-type faults in a built-in self-test environment. Based on the concept of a partner set, the method derives the number of distinctk-cell substate vectors which have 2^2k , 1k[n/2], transition capability for ann-cell LHCA and ann-cell LFSR with maximum length cycles. Simulation studies of the ISCAS85 benchmark circuits provide evidence of the effectiveness of the theoretrical metric.This work was supported in part by Reserach Grants No. 5711 and No. 39409 and a Strategic Grant from the Natural Sciences and Engineering Research Council of Canada and by an equipments loan from the Canadian Microelectronics Corporation.A preliminary version of this paper is partially presented at theIEEE ISCAS'94, May 1994.     

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     

Fast correlation attacks on certain stream ciphers

Suppose that the output of a running key generator employed in a stream cipher is correlated to a linear feedback shift register sequence (LFSR sequence) a with correlation probabilityp>0.5. Then two new correlation attacks (Algorithms A and B) are presented to determine the initial digits of a, provided that the numbert of feedback taps is small (t<10 ifp0.75). The computational complexity of Algorithm A is of orderO(2^ck), wherek denotes the length of the LFSR andc<1 depends on the input parameters of the attack, and Algorithm B is polynomial (in fact, even linear) in the lengthk of the LFSR. These algorithms are much faster than an exhaustive search over all phases of the LFSR, and are demonstrated to be successful against shift registers of considerable lengthk (typically,k=1000). On the other hand, for correlation probabilitiesp0.75 the attacks are proven to be infeasible against long LFSRs if they have a greater number of taps (roughlyk100 andt10).This work was supported in part by GRETAG Ltd., Regensdorf, Switzerland.     

Overcoming Test Setup Limitations by Applying Model-Based Testing to High-Precision ADCs

Test setup limitations, such as noise and parasitics, increasingly impede repeatable and accurate linearity measurements in high-volume production testing of high-precision data converters. Model-based testing has been shown to reduce the adverse effects of noise [14].In this work, we present two enhancements of the linear model-based approach: one is a change of the modeling strategy in order to account for measurement errors induced, for example, by parasitics associated with the device contactor, and another is a Design-for-Test feature that significantly improves the models ability to reduce the effect of measurement noise on the accuracy of the test outcome.The authors acknowledge the support by Analog Devices B.V., Limerick, Ireland and Enterprise Ireland under the Strategic Research Grant ST/00/26.Carsten Wegener has been awarded the academic degree of a Diplom-Ingenieur in Electronic Circuits and Systems by the Technical University of Dresden, Germany, in 1997. During a period of two years, 1996 through 1998, he attended the lecture series for the Vordiplom in Mathematics at Humboldt-University at Berlin, Germany.In Spring 1998, he moved permanently to Ireland, where he started to work with the Test Department of Analog Devices B.V. in Limerick. In Autumn of the same year he took up his PhD-studies with Dr M.P. Kennedy in the area of model-based testing of mixed-signal integrated circuits. He has been awarded the PhD degree by the National University of Ireland in December 2003.He has contributed to numerous conferences, publishing works in areas of nonlinear oscillator dynamics and mixed-signal testing. In Ireland, he has taught MATLAB courses to design and test engineers at Analog Devices B.V., and graduate courses on Digital Design-for-Test and Mixed-signal Test and Testability at the Department of Microelectronic Engineering, University College Cork.Michael Peter Kennedy received the B.E. degree in electronics from the National University of Ireland in 1984, and the M.S. and Ph.D. degrees from the University of California at Berkeley (UC Berkeley) in 1987 and 1991, respectively, for his contributions to the study of neural networks and nonlinear dynamics.He worked as a Design Engineer with Philips Electronics, a Postdoctoral Research Engineer with the Electronics Research Laboratory, UC Berkeley, and as a Professeur Invité with the EPFL, Switzerland. He returned to University College Dublin in 1992 as a College Lecturer in the Department of Electronic and Electrical Engineering. He was appointed Professor of Microelectronic Engineering at University College Cork in 2000.He has published 200 articles in the area of nonlinear circuits and systems and has taught courses on nonlinear dynamics and chaos. His research interests are nonlinear circuits and systems for applications in communications and signal processing. Since 1995 he has been active in research into algorithms for mixed-signal testing. Since 1994, he has led international basic and applied research projects on chaotic communications valued at over USD 2M.Dr. Kennedy was elected a Fellow of the IEEE in 1998. He received the Third Millenium Medal from the IEEE in 2000, the IEEE Circuits and Systems Society Golden Jubilee Medal, and the inaugural Parsons Award for excellence in Engineering Sciences from the Royal Irish Academy in 2001.     

Computation of simple and group factors of multivariate polynomials

This paper generalizes a recent result onsimple factorization of 2-variable (2-v) polynomials to simple andgroup factorization ofn-variate (n-v), (n3) polynomials. The emphasis is on developing a reliablenumerical technique for factorization. It is shown that simple as well as group factorization can be achieved by performing singular value decomposition (SVD) on certain matrices obtained from the coefficients of the givenn-v polynomial expressed in a Kronecker product form. For the polynomials that do not have exact simple and/or group factors, the concepts of approximate simple and group factorization are developed. The use of SVD leads to an elegant solution of an approximaten factorization problem. Several nontrivial examples are included to illustrate the results presented in this paper.Research supported by WRDC grant F33615-88-C-3605, NSF grant ECS-9110636, and NSERC of Canada grant A1345.     

Quality Determination for Gate Delay Fault Tests Considering Three-State Elements

Most industrial digital circuits contain three-state elements besides pure logic gates. This paper presents a gate delay fault simulator for combinational circuits that can handle three-state elements like bus drivers, transmission gates and pulled busses. The well known delay faults--slow-to-rise and slow-to-fall--are considered as well as delayed transitions from isolating signal state high impedance to binary states 0 and 1 and vice versa. The presented parallel delay fault simulator distinguishes between non-robust, robust and hazard free tests and determines the quality of a test. Experimental results for ISCAS85/89 benchmark circuits are presented as well as results for industrial circuits containing three-state elements.     

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

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

Scaling Analysis of On-Chip Power Grid Voltage Variations in Nanometer Scale ULSI

This paper presents a detailed scaling analysis of the power supply distribution network voltage drop in DSM technologies. The effects of chip temperature, electromigration and interconnect technology scaling (including resistivity increase of Cu interconnects due to electron surface scattering and finite barrier thickness) are taken into consideration during this analysis. It is shown that the voltage drop effect in the power/ground (P/G) distribution network increases rapidly with technology scaling, and that using well-known countermeasures such as wire-sizing and/or decoupling capacitor insertion which are typically used in the present design methodologies may be insufficient to limit the voltage fluctuations over the power grid for future technologies. It is also shown that such voltage drops on power supply lines of switching devices in a clock distribution network can introduce significant amount of skew which in turn degrades the signal integrity.This work was done when the author was with the Dept. of EESystems, University of Southern California.Amir H. Ajami received his B.S. degree in electrical engineering from the University of Tehran, Tehran, Iran in 1993. He received his M.S. and Ph.D. degrees in electrical engineering from the University of Southern California, Los Angeles, CA, in 1999 and 2002, respectively.He is currently a member of consulting staff in research and development division at MagmaDesign Automation, Inc., Santa Clara, CA. He has previously held positions at Cadence Design Systems, Inc., andMagma Design Automations, Inc., in 1999 and 2000, respectively. His research interests are in the area of technology scaling issues in high-performance VLSI designs with emphasis on full-chip thermal analysis, thermalaware timing and power optimization methodologies, and signal integrity. He has coauthored several papers on the modeling and analysis of the effects of substrate thermal gradients on performance degradation and development of thermal-aware physical-synthesis optimization algorithms.Dr. Ajami is a member of Association of Computing Machinery (ACM) and IEEE. HE serves on the technical program committee of the 2005 IEEE International Symposium on Quality Electronics Design.Kaustav Banerjee received the Ph.D. degree in electrical engineering and computer sciences from the University of California at Berkeley in 1999. He was with Stanford University, Stanford, CA, from 1999 to 2002 as a Research Associate at the Center for Integrated Systems. In July 2002, he joined the faculty of the Electrical and Computer Engineering Department at the University of California, Santa Barbara, as an Assistant Professor. From February 2002 to August 2002 he was a Visiting Professor at the Circuit Research Labs of Intel in Hillsboro, Oregon. In the past, he has also held summer/visiting positions at Texas Instruments Inc., Dallas, Texas, Fujitsu Labs and the Swiss Federal Institute of Technology (EPFL). His present research interests focus on a wide variety of nanometer scale issues in high-performance VLSI and mixed-signal designs, as well as on circuits and systems issues in emerging nanoelectronics. He is also interested in some exploratory interconnect and circuit architectures including 3-D ICs. At UCSB, Dr. Banerjee mentors several doctoral and masters students. He also co-advises graduate students at Stanford University, University of Illinois at Urbana-Champaign and EPFL-Switzerland. He has co-directed two doctoral dissertations at Stanford University and the University of Southern California. Dr. Banerjee served as Technical Program Chair of the 2002 IEEE International Symposium on Quality Electronic Design (ISQED 02), and is the General Chair of ISQED 05. He also serves or has served on the technical program committees of the IEEE International Electron Devices Meeting, the IEEE International Reliability Physics Symposium, the EOS/ESD Symposium and the ACM International Symposium on Physical Design. His research has been chronicled in over 100 journals and refereed international conference papers and a book chapter. He has also co-edited a book titled Emerging Nanoelectronics: Life with and after CMOS by Kluwer in 2004. Dr. Banerjee has been recognized through the ACM SIGDA Outstanding New Faculty Award (2004) as well as a Best Paper Award at the Design Automation Conference (2001). He is listed in Whos Who in America and Whos Who in Science and Engineering.Massoud Pedram received a B.S. degree in Electrical Engineering from the California Institute of Technology in 1986 and M.S. and Ph.D. degrees in Electrical Engineering and Computer Sciences from the University of California, Berkeley in 1989 and 1991, respectively. He then joined the department of Electrical Engineering, Systems at the University of Southern California where he is currently a professor. Dr. Pedram has served on the technical program committee of a number of conferences, including the Design automation Conference (DAC), Design and Test in Europe Conference (DATE), Asia-Pacific Design automation Conference (ASP-DAC), and International Conference on Computer Aided Design (ICCAD). He served as the Technical Co-chair and General Co-chair of the International Symposium on Low Power Electronics and Design (SLPED) in 1996 and 1997, respectively. He was the Technical Program Chair and the General Chair of the 2002 and 2003 International Symposium on Physical Design. Dr. Pedram has published four books, 60 journal papers, and more than 150 conference papers. His research has received a number of awards including two ICCD Best Paper Awards, a Distinguished Citation from ICCAD, a DAC Best Paper Award, and an IEEE Transactions on VLSI Systems Best Paper Award. He is a recipient of the NSFs Young Investigator Award (1994) and the Presidential Faculty Fellows Award (a.k.a. PECASE Award) (1996).Dr. Pedram is a Fellow of the IEEE, a member of the Board of Governors for the IEEE Circuits and systems Society, an associate editor of the IEEE Transactions on Computer Aided Design, the IEEE Transactions on Circuits and Systems, and the IEEE Circuits and Systems Society Distinguished Lecturer Program Chair. He is also an Advisory Board Member of the ACM Interest Group on Design Automation, and an associate editor of the ACM Transactions on Design Automation of Electronic Systems. His current work focuses on developing computer aided design methodologies and techniques for low power design, synthesis, and physical design. For more information, please go to URL address: .     

An Efficient Deterministic Test Pattern Generator for Scan-Based BIST Environment

To obtain satisfactory fault coverage for testing a logic circuit, linear feedback shift registers (LFSRs) have been used to generate not only the pseudorandom, but also the deterministic patterns in the scan-based built-in self-test environment. However, like other scan-based methods, the LFSR based pattern generation schemes take a long test application time to feed deterministic patterns from the LFSR into a scan chain. In this paper we derive a general relationship between the bits in the scan chain and the states of the LFSR and show that any bit to be generated by an LFSR in any future clock cycle can be pre-generated by a linear function of the current LFSR state. With this relationship, we can divide a scan chain into multiple sub-chains and use one LFSR-based multiple sequence generator to simultaneously generate all the subsequences required by the sub-chains, hence can greatly reduce the test application time for deterministic patterns. Moreover, due to the scan time reduction, test power wasted during the scan operation can also be significantly reduced.     

Counter-based compaction: An analysis for BIST

According to some recently published results, counter-based compaction outperforms compaction by linear feedback shift registers. These results, however, are based on oversimplified assumptions. In this paper, we discuss an error model to describe the behavior of a faulty circuit under test. We study the three most popular counter-based compaction schemes, (i.e., one's counting, transition counting and edge counting). Using Markov processes we derive equations for iterative computations of exact aliasing probability for any test session length and determine the asymptotic probability of aliasing. For one's counting, we also present a closed form expression that, for any test session length, gives the exact aliasing probability. Finally, we present some examples to compare the aliasing in the counter-based compaction and compaction by a linear feedback shift register. These examples indicate that aliasing by LFSRs is more predictable than aliasing by counters.     

Sub-exponential Solutions of Multidimensional Difference Equations

We shall prove that practically any recursive solutionof a linear multidimensional difference equation increases sub-exponentially.If all the steps of the recursive procedure are of the samedirection, useful growth estimates can be given. The resultsare also generalized to some cases of non-linear difference equationsand sequences in the linear normed space.     

Time‐varying modeling of a nonstationary signal

In this paper, a method for modeling a nonstationary signal using timevarying parameters by considering that the signal is generated by a linear, timevarying (LTV) system with a stationary white noise input is presented. This method is based on the Wold–Cramer (WC) representation of a nonstationary signal. Because the relationship between the generalized transfer function of an LTV system and the timevarying coefficients of the difference equation of a discretetime system is not addressed so far in the literature, therefore, in this paper a solution to this problem is proposed. A simple relationship between the system generalized transfer function and the timevarying parameters of the system is derived, then an MLS algorithm is developed to solve for the system timevarying parameters. Computer simulation illustrating the effectiveness of our algorithm is presented.     

Linear transformation shift registers

In order to exploit word-oriented operations for linear-feedback shift registers (LFSRs), Tsaban and Vishne [2002] introduced the notion of linear transformation shift registers (TSRs). An implementation of their primitive TSR generating algorithm shows that the LFSR are paired for all transformations. We prove that the characteristic polynomials of a pair of LFSRs are either both irreducible or both reducible for all transformations. This allows some time improvement when finding primitive TSRs. The authors give a full enumeration of all primitive TSRs with transformations of order 8 and LFSRs of order 3, 4, 5, and 6.     

On Time Optimal Implementation of Uniform Recurrences onto Array Processors via Quadratic Programming

Many important algorithms can be described by n-dimensional uniform recurrences. The computations are then indexed by integral vectors of length n and the data dependencies between computations can be described by the difference vector of the corresponding indexes which are independent of the indexes. This paper addresses the following optimization problem: Given an n-dimensional uniform recurrence whose computation indexes are mapped by a linear function onto the processors of an array processor embedded in k-space (1 k n). Find an optimal linear function for the computation indexes. We study a continuous approximation of this problem by passing from linear to quasi-linear timing functions. The resultant problem formulation is then a quadratic programming problem which can be solved by standard algorithms for quadratic or general nonlinear optimization problems. We demonstrate the effectiveness of our approach by several nontrivial test examples.     

Fault Models and Test Generation for OpAmp Circuits—The FFM

The analog VLSI technology processes are reaching the matureness, nevertheless, there is a big constraint, regarding their use on complex electronic products: the test. The Design for Testability paradigm was developed to permit the test plan implementation early in the design cycle. However to succeed onto this strategy, the fault simulation should be carried out in order to evaluate appropriate test patterns, fault grade and so forth. Consequently adequate fault models must be established. Due to the lack of fault models, suitable to fault simulation on OpAmps, we propose in this work a methodology for Functional Fault Modeling-FFM, and some methods for test generation. A fault dictionary for OpAmps is built and a procedure for compact test vector construction is proposed. The results have shown that high level OpAmp requirements, as slew-rate, common mode rejection ration etc., can be checked by this approach with good compromise between the fault modeling problem, the analog nature of the circuit and the circuit complexity by itself.     

Thermal Noise Random Number Generator Based on LFSR

With the rapid development of cryptography, the strength of security protocols and encryption algorithms consumedly relies on the quality of random number. In many cryptography applications, higher speed is one of the references required. A new security random number generator architecture is presented. Its philosophy architecture is implemented with FPGA, based on the thermal noise and linear feedback shift register（LFSR）. The thermal noise initializes LFSRs and is used as the disturbed source of the system to ensure the unpredictability of the produced random number and improve the security strength of the system. Parallel LFSRs can produce the pseudo-random numbers with long period and higher speed. The proposed architecture can meet the requirements of high quality and high speed in cryptography.     

Incorporating I DDQ Testing with BIST for Improved Coverage: An Experimental Study

In this paper we present an experimental study on the effectivenessof incorporating at-speed I _DDQ testing with traditionalBIST for improved test coverage. The high speed I _DDQtesting is conducted using the differential built-in on-chip current sensor(BICS) that we have recently developed. Two test chips were designed andfabricated implementing a CMOS version of the 74181 ALU chip. In copies ofthis circuit we included the capability of activating 45 differentrealistic CMOS faults: inter- and intra-layer shorts andopens. We examine the fault coverage of both Boolean (voltage) testing andI _DDQ testing for these realistic faults. An interestingfinding of our study is that I _DDQ testing also detectedseveral of the open faults. Moreover, these include precisely those openfaults for which two pattern voltage tests can get invalidated because oftransient switching states. Our results show that combining both Boolean andcurrent testing does enhance test coverage in a BIST environment.     

Relations between thek-dimensional unconstrained and linear phase FIR Wiener filters

In this note, we show that thek-dimensional linear phase FIR Wiener filter can be obtained from the unconstrained filter with a simple reverse and add operation. The relation between the linear phase and unconstrained phase filters is obtained also in the case of a multichannelk-dimensional system. In this case, the properties of the autocorrelation matrix do not allow the simplifications noted for the single channel case.     

A framework for delivering multicast messages in networks with mobile hosts

To accommodatemobile hosts (MHs) within existing data networks, the static network is augmented with mobile support stations (MSSs) that communicate directly with MHs, usually via wireless links. Connectivity of the overall network changes dynamically as MHs connect to the static network from different locations (MSSs) at different times. Compared to their desktop counterparts, mobile hosts face a new set of constraints namely, low bandwith of the wireless links, tight constraints on power consumption and a significantly lower computing capability. Thus, even without considering failures, integration of mobile computer within existing networks pose a new set of problems. In this paper, we look at the problems associated with delivering multicast meassages to mobile hosts. First, we identify how a mobile host's ability to connect to different MSSs at different times, affects delivery of multicast messages and present schemes to deliver multicast messages to MHs fromatleast-one location, fromatmost-one location, and fromexactly-one location. Next, we introduce multicast groups of mobile hosts wherein each multicast group is associated with a host view, a set of MSSs representing theaggregate location information of the group. A host-view membership algorithm is then presented and combined with the multicast scheme for exactly-once delivery. As a result, to deliver a multicast message to a specified group, copies of the message need be propagated only to the MSSs in the group's host-view.This work was done while the author was a graduate student at Rutgers University.This research work was supported in part by ARPA under contract number DAAH04-95-1-0596, NSF grant numbers CCR 95-09620, IRIS 95-09816 and sponsors of WINLAB.     

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.