E-raamat: Random Testing of Digital Circuits: Theory and Applications

Foreword iii(2) Thomas W. Williams Preface v(12) Notation xvii 1 Random Testing and Built-In Self-Test 1(14) 1.1 TESTING OF DIGITAL CIRCUITS 1(6) 1.1.1 Testing needs 1.1.2 Scan design 1.1.3 Some fundamental difficulties leading to BIST 1.2 BUILT-IN SELF-TEST 7(5) 1.2.1 On-line BIST 1.2.2 Off-line BIST 1.3 SOME QUESTIONS 12(2) NOTES and REFERENCES 14(1) 2 Models for Digital Circuits and Fault Models 15(26) 2.1 NOTATIONS AND MODELS FOR DIGITAL CIRCUITS 15(11) 2.1.1 Combinational circuits 2.1.2 Sequential circuits 2.1.2.1 Synchronous sequential machine 2.1.2.2 Asynchronous sequential machine 2.1.2.3 Formal models 2.1.3 Sequences of vectors 2.1.3.1 Input language and output language 2.1.3.2 Equivalent machines 2.2 BASIC FAULT MODELS 26(9) 2.2.1 Levels of modelling 2.2.2 Defects, faults and errors 2.2.3 Basic fault models 2.2.3.1 Classical models 2.2.3.2 Specific models 2.2.3.3 Functional models 2.3 FUNCTIONAL AND STRUCTURAL TESTING 35(4) 2.3.1 Functional testing 2.3.2 Structural testing 2.3.3 Exhaustive testing NOTES and REFERENCES 39(2) 3 Basic Concepts and Test Generation Methods 41(42) 3.1 COMBINATIONAL CIRCUITS 41(16) 3.1.1 Comparison between faulty and fault-free circuits 3.1.2 Propagation through sensitized paths 3.1.2.1 Illustration of the principle 3.1.2.2 About reconverging fanout and backtracking 3.1.3 Algebraic method 3.1.4 Relations between faults 3.1.4.1 Fault collapsing 3.1.4.2 Checkpoints 3.1.4.3 Redundancy and masking 3.1.4.4 Fault coverage 3.2 SEQUENTIAL CIRCUITS 57(23) 3.2.1 Initialization and evasive faults 3.2.1.1 Initialization 3.2.1.2 Compatible initial states and evasive faults 3.2.2 Comparison between faulty and fault-free circuits: Observers 3.2.2.1 The initial state of the faulty circuit is known 3.2.2.2 The initial state of the faulty circuit is not known 3.2.3 Propagation 3.2.4 Relations between faults 3.2.4.1 Fault collapsing 3.2.4.2 Fault detectability 3.2.4.3 Generation of a test sequence for a set of faults NOTES and REFERENCES 80(3) 4 Performance Measurements for a Test Sequence 83(24) 4.1 DEFECT LEVEL 83(3) 4.2 FAULT MODELS AND FAULT COVERAGE 86(2) 4.3 RELATION BETWEEN FAULT COVERAGE AND DEFECT LEVEL 88(2) 4.4 MEASUREMENTS OF THE CONFIDENCE LEVEL FOR RANDOM TESTING 90(15) 4.4.1 Measurements derived from deterministic concepts 4.4.2 Measurements specific to random testing 4.4.3 Some properties 4.4.3.1 Relations between measurements 4.4.3.2 Relations between faults in the context of random testing NOTES and REFERENCES 105(2) 5 Basic Principles of Random Testing 107(28) 5.1 PRINCIPLE OF RANDOM TESTING 107(2) 5.2 ALL THE SPECIFIED CASES AND ONLY THE SPECIFIED CASES SHOULD BE TESTED 109(8) 5.2.1 Example of combinational circuit 5.2.2 Example of asynchronous sequential circuit 5.2.3 Example of synchronous sequential circuit 5.2.4 Example of partly synchronous and partly asynchronous circuit 5.2.5 Conclusion on specification 5.3 ABOUT DETECTION POWER OF RANDOM TESTING 117(12) 5.3.1 Markov chains associated with the observer 5.3.1.1 The initial state of the faulty machine is known 5.3.1.2 The initial state of the faulty machine is unknown 5.3.1.3 Generalized distribution 5.3.2 Limits of random testing 5.3.3 Limits of deterministic testing 5.3.4 Conclusion on detection power 5.4 FIRST DETECTION AND MEMORY EFFECT 129(4) 5.4.1 Combinational fault 5.4.2 Sequential fault NOTES and REFERENCES 133(2) 6 Random Test Length for Combinational Circuits 135(32) 6.1 RANDOM TEST LENGTH 135(12) 6.1.1 Random test length for a fault 6.1.1.1 Detection probability 6.1.1.2 Random test length 6.1.2 Random test length for a set of faults 6.1.2.1 Expected fault coverage 6.1.2.2 Worst case: minimum testing probability 6.2 COMPUTATION OF THE DETECTION PROBABILITY 147(15) 6.2.1 Detection probability of a fault 6.2.1.1 Detection function 6.2.1.2 Extended Cutting Algorithm 6.2.2 Detection probabilities for a set of faults 6.2.2.1 Controllability, observability, and activity 6.2.2.2 Simulation 6.2.2.3 Lower bounds on detectability 6.3 NUMERICAL RESULTS 162(2) NOTES and REFERENCES 164(3) 7 Random Test Length for Sequential Circuits 167(26) 7.1 ASYNCHRONOUS AND SYNCHRONOUS TESTS 167(2) 7.2 TEST LENGTH FOR A FAULT 169(8) 7.2.1 Example of exact calculation 7.2.2 Accurate approximation for a large test length 7.2.3 Obtaining the test length L(XXX) 7.3 APPROXIMATE METHODS 177(11) 7.3.1 Minimal detecting transition sequence (MDTS) 7.3.1.1 Detecting transition sequence 7.3.1.2 Detection set 7.3.2 Single transition faults 7.3.2.1 Approximate random test length 7.3.2.2 Topics not taken into account 7.4 NUMERICAL RESULTS 188(2) NOTES and REFERENCES 190(3) 8 Random Test Length for RAMs 193(28) 8.1 MODELS 193(4) 8.1.1 Models of RAMs 8.1.2 Fault models 8.1.2.1 Faults in the decoder and read/write logic 8.1.2.2 Faults in the memory cell array 8.2 TEST LENGTH FOR SINGLE FAULTS 197(12) 8.2.1 Stuck-at fault of a memory cell 8.2.1.1 Influence of the distribution XXX 8.2.1.2 Influence of initialization 8.2.1.3 Influence of the number of cells 8.2.1.4 Influence of the confidence level 8.2.1.5 Concluding remarks 8.2.2 Faults in address decoding and read/write logic 8.2.3 Faults in the memory cell array 8.2.3.1 Length coefficient for toggling fault 8.2.3.2 Other faults 8.3 EXTENSION TO OTHER MODELS 209(4) 8.3.1 Word-oriented memory 8.3.1.1 All the cells involved belong to different words 8.3.1.2 PSFs such that some involved cells belong to the same word 8.3.1.3 Coupling of bits in a single word 8.3.2 Multiple faults 8.4 POWER OF RANDOM TESTING FOR RAMs 213(7) 8.4.1 Linearity of test length as a function of the number of cells 8.4.2 Comparison with deterministic testing 8.4.3 Example of application to a batch of RAMs NOTES and REFERENCES 220(1) 9 Random Test Length for Microprocessors 221(28) 9.1 FUNCTIONAL MODELS 221(7) 9.1.1 Functional model of a microprocessor 9.1.2 Fault models 9.1.2.1 Faults in the registers 9.1.2.2 Faults in the operators 9.1.2.3 Faults in the register decoding function 9.1.2.4 Faults in instruction decoding and control function 9.2 MARKOV CHAINS AND MDTS 228(5) 9.2.1 First example 9.2.2 Second example 9.3 TEST LENGTH FOR FAULTS IN THE DATA PROCESSING SECTION 233(6) 9.3.1 Faults in the registers 9.3.2 Faults in the operators 9.4 TEST LENGTH FOR FAULTS IN THE CONTROL SECTION 239(2) 9.5 TEST LENGTH FOR A MICROPROCESSOR 241(6) 9.5.1 Example microprocessor 9.5.1.1 Faults in the registers 9.5.1.2 Faults in the operators 9.5.1.3 Fault in the control section 9.5.1.4 Fault in the whole microprocessor 9.5.2 Microprocessor Motorola 6800 9.5.2.1 Basic results 9.5.2.2 Further results NOTES and REFERENCES 247(2) 10 Generation of Random Test Sequences 249(28) 10.1 NEEDS 249(5) 10.1.1 Set of vectors for combinational faults 10.1.1.1 Equal likelihood of all the input vectors 10.1.1.2 Constant but not equally likely distribution 10.1.2 Set of subsequences for sequential faults 10.1.2.1 Synchronous test 10.1.2.2 Asynchronous test (adjacent vectors) 10.1.2.3 Generalized distribution 10.2 SOFTWARE GENERATION 254(3) 10.2.1 Constant distribution 10.2.2 Generalized distribution 10.2.3 Comments on software generation 10.3 HARDWARE GENERATION 257(19) 10.3.1 Basic properties of LFSRs and M-sequences 10.3.2 Constant Distribution 10.3.2.1 Equally likely distribution 10.3.2.2 Weighted test vectors 10.3.3 Sequence of adjacent vectors 10.3.4 Generalized distribution. Example for the Motorola 6800 microprocessor 10.3.4.1 General description of the random test machine 10.3.4.2 Principle of the input sequence generation 10.3.4.3 Hardware test pattern generator NOTES and REFERENCES 276(1) 11 Experimental Results 277(22) 11.1 TTL CIRCUITS 277(4) 11.1.1 Batch of 61 circuits reference 483 E 11.1.2 Memory effect in sequential circuits 11.2 LSI CMOS CIRCUITS 281(2) 11.3 MOTOROLA 6800 MICROPROCESSOR 283(7) 11.3.1 Experimental results for a set of 60 microprocessors 11.3.2 Experiments versus theory 11.4 OTHER EXPERIMENTAL RESULTS 290(6) 11.4.1 Experiments by W. Luciw: Intel 8080 microprocessor 11.4.2 Experiments by A. Laviron et al.: Motorola 6800 microprocessor 11.4.3 Experiments by R. Velazco et al.: Motorola 6800 microprocessor 11.4.4 Experiments by D.A. Wood et al.: multiprocessor cache controller NOTES and REFERENCES 296(3) 12 Signature Analysis 299(38) 12.1 GENERAL FEATURES 299(7) 12.1.1 Aliasing and non-revelation 12.1.2 General property 12.1.3 Choice of k 12.2 SINGLE INPUT SIGNATURE ANALYSERS 306(16) 12.2.1 Counting methods 12.2.2 Signature by linear feedback shift register 12.2.3 Properties of SISR 12.2.4 Cost of signature analysis 12.3 MULTIPLE INPUT SIGNATURE ANALYSERS 322(12) 12.3.1 Space dependent and time dependent errors 12.3.2 MISR if m is less than or equal to k 12.3.3 MISR if m is greater than or equal to k 12.3.4 SISR for periodic errors NOTES and REFERENCES 334(3) 13 Design For Random Testability 337(16) 13.1 DESIGN FOR TESTABILITY IN GENERAL 337(1) 13.2 EXTENDED SPECIFICATION 338(4) 13.3 DECORRELATION BY EXOR GATES 342(5) 13.4 FACTORIZATION IN COMBINATIONAL FUNCTIONS 347(4) NOTES and REFERENCES 351(2) Postface 353(4) Appendices 357(54) A Random Pattern Sources 357(4) B Calculation of a Probability of Complete Fault Coverage 361(2) C Finite Markov Chains 363(2) D Black-Box Fault Model 365(6) E Exact Calculation of Activities 371(4) F Comparing Asynchronous and Synchronous Test 375(4) G Proofs of Properties 7.1, 7.2, and 12.3 379(6) H Microprocessor Motorola 6800 385(4) I Pseudorandom Testing 389(4) J Random Testing of Delay Faults 393(4) K Subsequences of Required Lengths 397(4) L Diagnosis from Random Testing 401(6) M Conjectures on Multiple Faults 407(4) Exercises 411(14) Solutions to exercises 425(22) Bibliography 447(16) Index 463

Rene David is a Research Director at the Centre National de la recherche Scientififique working at the Instuit National Polytechnique de Grenoble, France.