Digital Logic Testing and Simulation, 2nd Edition

zhang1998

Contents

Preface xvii
1 Introduction 1
1.1 Introduction 1
1.2 Quality 2
1.3 The Test 2
1.4 The Design Process 6
1.5 Design Automation 9
1.6 Estimating Yield 11
1.7 Measuring Test Effectiveness 14
1.8 The Economics of Test 20
1.9 Case Studies 23
1.9.1 The Effectiveness of Fault Simulation 23
1.9.2 Evaluating Test Decisions 24
1.10 Summary 26
Problems 29
References 30
2 Simulation 33
2.1 Introduction 33
2.2 Background 33
2.3 The Simulation Hierarchy 36
2.4 The Logic Symbols 37
2.5 Sequential Circuit Behavior 39
2.6 The Compiled Simulator 44
2.6.1 Ternary Simulation 48
vi
CONTENTS
2.6.2 Sequential Circuit Simulation 48
2.6.3 Timing Considerations 50
2.6.4 Hazards 50
2.6.5 Hazard Detection 52
2.7 Event-Driven Simulation 54
2.7.1 Zero-Delay Simulation 56
2.7.2 Unit-Delay Simulation 58
2.7.3 Nominal-Delay Simulation 59
2.8 Multiple-Valued Simulation 61
2.9 Implementing the Nominal-Delay Simulator 64
2.9.1 The Scheduler 64
2.9.2 The Descriptor Cell 67
2.9.3 Evaluation Techniques 70
2.9.4 Race Detection in Nominal-Delay Simulation 71
2.9.5 Min–Max Timing 72
2.10 Switch-Level Simulation 74
2.11 Binary Decision Diagrams 86
2.11.1 Introduction 86
2.11.2 The Reduce Operation 91
2.11.3 The Apply Operation 96
2.12 Cycle Simulation 101
2.13 Timing Verification 106
2.13.1 Path Enumeration 107
2.13.2 Block-Oriented Analysis 108
2.14 Summary 110
Problems 111
References 116
3 Fault Simulation 119
3.1 Introduction 119
3.2 Approaches to Testing 120
3.3 Analysis of a Faulted Circuit 122
3.3.1 Analysis at the Component Level 122
3.3.2 Gate-Level Symbols 124
3.3.3 Analysis at the Gate Level 124
CONTENTS
vii
3.4 The Stuck-At Fault Model 125
3.4.1 The AND Gate Fault Model 127
3.4.2 The OR Gate Fault Model 128
3.4.3 The Inverter Fault Model 128
3.4.4 The Tri-State Fault Model 128
3.4.5 Fault Equivalence and Dominance 129
3.5 The Fault Simulator: An Overview 131
3.6 Parallel Fault Processing 134
3.6.1 Parallel Fault Simulation 134
3.6.2 Performance Enhancements 136
3.6.3 Parallel Pattern Single Fault Propagation 137
3.7 Concurrent Fault Simulation 139
3.7.1 An Example of Concurrent Simulation 139
3.7.2 The Concurrent Fault Simulation Algorithm 141
3.7.3 Concurrent Fault Simulation: Further Considerations 146
3.8 Delay Fault Simulation 147
3.9 Differential Fault Simulation 149
3.10 Deductive Fault Simulation 151
3.11 Statistical Fault Analysis 152
3.12 Fault Simulation Performance 155
3.13 Summary 157
Problems 159
References 162
4 Automatic Test Pattern Generation 165
4.1 Introduction 165
4.2 The Sensitized Path 165
4.2.1 The Sensitized Path: An Example 166
4.2.2 Analysis of the Sensitized Path Method 168
4.3 The D-Algorithm 170
4.3.1 The D-Algorithm: An Analysis 171
4.3.2 The Primitive D-Cubes of Failure 174
4.3.3 Propagation D-Cubes 177
4.3.4 Justification and Implication 179
4.3.5 The D-Intersection 180
viii
CONTENTS
4.4 Testdetect 182
4.5 The Subscripted D-Algorithm 184
4.6 PODEM 188
4.7 FAN 193
4.8 Socrates 202
4.9 The Critical Path 205
4.10 Critical Path Tracing 208
4.11 Boolean Differences 210
4.12 Boolean Satisfiability 216
4.13 Using BDDs for ATPG 219
4.13.1 The BDD XOR Operation 219
4.13.2 Faulting the BDD Graph 220
4.14 Summary 224
Problems 226
References 230
5 Sequential Logic Test 233
5.1 Introduction 233
5.2 Test Problems Caused by Sequential Logic 233
5.2.1 The Effects of Memory 234
5.2.2 Timing Considerations 237
5.3 Sequential Test Methods 239
5.3.1 Seshu’s Heuristics 239
5.3.2 The Iterative Test Generator 241
5.3.3 The 9-Value ITG 246
5.3.4 The Critical Path 249
5.3.5 Extended Backtrace 250
5.3.6 Sequential Path Sensitization 252
5.4 Sequential Logic Test Complexity 259
5.4.1 Acyclic Sequential Circuits 260
5.4.2 The Balanced Acyclic Circuit 262
5.4.3 The General Sequential Circuit 264
5.5 Experiments with Sequential Machines 266
5.6 A Theoretical Limit on Sequential Testability 272
CONTENTS
ix
5.7 Summary 277
Problems 278
References 280
6 Automatic Test Equipment 283
6.1 Introduction 283
6.2 Basic Tester Architectures 284
6.2.1 The Static Tester 284
6.2.2 The Dynamic Tester 286
6.3 The Standard Test Interface Language 288
6.4 Using the Tester 293
6.5 The Electron Beam Probe 299
6.6 Manufacturing Test 301
6.7 Developing a Board Test Strategy 304
6.8 The In-Circuit Tester 307
6.9 The PCB Tester 310
6.9.1 Emulating the Tester 311
6.9.2 The Reference Tester 312
6.9.3 Diagnostic Tools 313
6.10 The Test Plan 315
6.11 Visual Inspection 316
6.12 Test Cost 319
6.13 Summary 319
Problems 320
References 321
7 Developing a Test Strategy 323
7.1 Introduction 323
7.2 The Test Triad 323
7.3 Overview of the Design and Test Process 325
7.4 A Testbench 327
7.4.1 The Circuit Description 327
7.4.2 The Test Stimulus Description 330
x
CONTENTS
7.5 Fault Modeling 331
7.5.1 Checkpoint Faults 331
7.5.2 Delay Faults 333
7.5.3 Redundant Faults 334
7.5.4 Bridging Faults 335
7.5.5 Manufacturing Faults 337
7.6 Technology-Related Faults 337
7.6.1 MOS 338
7.6.2 CMOS 338
7.6.3 Fault Coverage Results in Equivalent Circuits 340
7.7 The Fault Simulator 341
7.7.1 Random Patterns 342
7.7.2 Seed Vectors 343
7.7.3 Fault Sampling 346
7.7.4 Fault-List Partitioning 347
7.7.5 Distributed Fault Simulation 348
7.7.6 Iterative Fault Simulation 348
7.7.7 Incremental Fault Simulation 349
7.7.8 Circuit Initialization 349
7.7.9 Fault Coverage Profiles 350
7.7.10 Fault Dictionaries 351
7.7.11 Fault Dropping 352
7.8 Behavioral Fault Modeling 353
7.8.1 Behavioral MUX 354
7.8.2 Algorithmic Test Development 356
7.8.3 Behavioral Fault Simulation 361
7.8.4 Toggle Coverage 364
7.8.5 Code Coverage 365
7.9 The Test Pattern Generator 368
7.9.1 Trapped Faults 368
7.9.2 SOFTG 369
7.9.3 The Imply Operation 369
7.9.4 Comprehension Versus Resolution 371
7.9.5 Probable Detected Faults 372
7.9.6 Test Pattern Compaction 372
7.9.7 Test Counting 374
7.10 Miscellaneous Considerations 378
7.10.1 The ATPG/Fault Simulator Link 378
CONTENTS
xi
7.10.2 ATPG User Controls 380
7.10.3 Fault-List Management 381
7.11 Summary 382
Problems 383
References 385
8 Design-For-Testability 387
8.1 Introduction 387
8.2 Ad Hoc Design-for-Testability Rules 388
8.2.1 Some Testability Problems 389
8.2.2 Some Ad Hoc Solutions 393
8.3 Controllability/Observability Analysis 396
8.3.1 SCOAP 396
8.3.2 Other Testability Measures 403
8.3.3 Test Measure Effectiveness 405
8.3.4 Using the Test Pattern Generator 406
8.4 The Scan Path 407
8.4.1 Overview 407
8.4.2 Types of Scan-Flops 410
8.4.3 Level-Sensitive Scan Design 412
8.4.4 Scan Compliance 416
8.4.5 Scan-Testing Circuits with Memory 418
8.4.6 Implementing Scan Path 420
8.5 The Partial Scan Path 426
8.6 Scan Solutions for PCBs 432
8.6.1 The NAND Tree 433
8.6.2 The 1149.1 Boundary Scan 434
8.7 Summary 443
Problems 444
References 449
9 Built-In Self-Test 451
9.1 Introduction 451
9.2 Benefits of BIST 452
9.3 The Basic Self-Test Paradigm 454
xii
CONTENTS
9.3.1 A Mathematical Basis for Self-Test 455
9.3.2 Implementing the LFSR 459
9.3.3 The Multiple Input Signature Register (MISR) 460
9.3.4 The BILBO 463
9.4 Random Pattern Effectiveness 464
9.4.1 Determining Coverage 464
9.4.2 Circuit Partitioning 465
9.4.3 Weighted Random Patterns 467
9.4.4 Aliasing 470
9.4.5 Some BIST Results 471
9.5 Self-Test Applications 471
9.5.1 Microprocessor-Based Signature Analysis 471
9.5.2 Self-Test Using MISR/Parallel SRSG (STUMPS) 474
9.5.3 STUMPS in the ES/9000 System 477
9.5.4 STUMPS in the S/390 Microprocessor 478
9.5.5 The Macrolan Chip 480
9.5.6 Partial BIST 482
9.6 Remote Test 484
9.6.1 The Test Controller 484
9.6.2 The Desktop Management Interface 487
9.7 Black-Box Testing 488
9.7.1 The Ordering Relation 489
9.7.2 The Microprocessor Matrix 493
9.7.3 Graph Methods 494
9.8 Fault Tolerance 495
9.8.1 Performance Monitoring 496
9.8.2 Self-Checking Circuits 498
9.8.3 Burst Error Correction 499
9.8.4 Triple Modular Redundancy 503
9.8.5 Software Implemented Fault Tolerance 505
9.9 Summary 505
Problems 507
References 510
10 Memory Test 513
10.1 Introduction 513
CONTENTS
xiii
10.2 Semiconductor Memory Organization 514
10.3 Memory Test Patterns 517
10.4 Memory Faults 521
10.5 Memory Self-Test 524
10.5.1 A GALPAT Implementation 525
10.5.2 The 9N and 13N Algorithms 529
10.5.3 Self-Test for BIST 531
10.5.4 Parallel Test for Memories 531
10.5.5 Weak Read–Write 533
10.6 Repairable Memories 535
10.7 Error Correcting Codes 537
10.7.1 Vector Spaces 538
10.7.2 The Hamming Codes 540
10.7.3 ECC Implementation 542
10.7.4 Reliability Improvements 543
10.7.5 Iterated Codes 545
10.8 Summary 546
Problems 547
References 549
11
I
DDQ
551
11.1 Introduction 551
11.2 Background 551
11.3 Selecting Vectors 553
11.3.1 Toggle Count 553
11.3.2 The Quietest Method 554
11.4 Choosing a Threshold 556
11.5 Measuring Current 557
11.6
I
DDQ
Versus Burn-In 559
11.7 Problems with Large Circuits 562
11.8 Summary 564
Problems 565
References 565
xiv
CONTENTS
12 Behavioral Test and Verification 567
12.1 Introduction 567
12.2 Design Verification: An Overview 568
12.3 Simulation 570
12.3.1 Performance Enhancements 570
12.3.2 hdl Extensions and C++ 572
12.3.3 Co-design and Co-verification 573
12.4 Measuring Simulation Thoroughness 575
12.4.1 Coverage Evaluation 575
12.4.2 Design Error Modeling 578
12.5 Random Stimulus Generation 581
12.6 The Behavioral ATPG 587
12.6.1 Overview 587
12.6.2 The RTL Circuit Image 588
12.6.3 The Library of Parameterized Modules 589
12.6.4 Some Basic Behavioral Processing Algorithms 593
12.7 The Sequential Circuit Test Search System (SCIRTSS) 597
12.7.1 A State Traversal Problem 597
12.7.2 The Petri Net 602
12.8 The Test Design Expert 607
12.8.1 An Overview of TDX 607
12.8.2 DEPOT 614
12.8.3 The Fault Simulator 616
12.8.4 Building Goal Trees 617
12.8.5 Sequential Conflicts in Goal Trees 618
12.8.6 Goal Processing for a Microprocessor 620
12.8.7 Bidirectional Goal Search 624
12.8.8 Constraint Propagation 625
12.8.9 Pitfalls When Building Goal Trees 626
12.8.10 MaxGoal Versus MinGoal 627
12.8.11 Functional Walk 629
12.8.12 Learn Mode 630
12.8.13 DFT in TDX 633
12.9 Design Verification 635
12.9.1 Formal Verification 636
12.9.2 Theorem Proving 636
CONTENTS
xv
12.9.3 Equivalence Checking 638
12.9.4 Model Checking 640
12.9.5 Symbolic Simulation 648
12.10Summary 650
Problems 652
References 653
Index 657