Digital Logic Testing and Simulation

Alexander Miczo9780471439950, 0471439959

Your road map for meeting today’s digital testing challengesToday, digital logic devices are common in products that impact public safety, including applications in transportation and human implants. Accurate testing has become more critical to reliability, safety, and the bottom line. Yet, as digital systems become more ubiquitous and complex, the challenge of testing them has become more difficult. As one development group designing a RISC stated, “the work required to . . . test a chip of this size approached the amount of effort required to design it. A valued reference for nearly two decades, Digital Logic Testing and Simulation has been significantly revised and updated for designers and test engineers who must meet this challenge.There is no single solution to the testing problem. Organized in an easy-to-follow, sequential format, this Second Edition familiarizes the reader with the many different strategies for testing and their applications, and assesses the strengths and weaknesses of the various approaches. The book reviews the building blocks of a successful testing strategy and guides the reader on choosing the best solution for a particular application. Digital Logic Testing and Simulation, Second Edition covers such key topics as: * Binary Decision Diagrams (BDDs) and cycle-based simulation * Tester architectures/Standard Test Interface Language (STIL) * Practical algorithms written in a Hardware Design Language (HDL) * Fault tolerance * Behavioral Automatic Test Pattern Generation (ATPG) * The development of the Test Design Expert (TDX), the many obstacles encountered and lessons learned in creating this novel testing approachUp-to-date and comprehensive, Digital Logic Testing and Simulation is an important resource for anyone charged with pinpointing faulty products and assuring quality, safety, and profitability.

---

Table of contents :
TeamLiB……Page 1
Cover……Page 2
Contents……Page 7
PREFACE……Page 19
1.1 INTRODUCTION……Page 25
1.3 THE TEST……Page 26
1.4 THE DESIGN PROCESS……Page 30
1.5 DESIGN AUTOMATION……Page 33
1.6 ESTIMATING YIELD……Page 35
1.7 MEASURING TEST EFFECTIVENESS……Page 38
1.8 THE ECONOMICS OF TEST……Page 44
1.9.1 The Effectiveness of Fault Simulation……Page 47
1.9.2 Evaluating Test Decisions……Page 48
1.10 SUMMARY……Page 50
PROBLEMS……Page 53
REFERENCES……Page 54
2.2 BACKGROUND……Page 57
2.3 THE SIMULATION HIERARCHY……Page 60
2.4 THE LOGIC SYMBOLS……Page 61
2.5 SEQUENTIAL CIRCUIT BEHAVIOR……Page 63
2.6 THE COMPILED SIMULATOR……Page 68
2.6.2 Sequential Circuit Simulation……Page 72
2.6.4 Hazards……Page 74
2.6.5 Hazard Detection……Page 76
2.7 EVENT- DRIVEN SIMULATION……Page 78
2.7.1 Zero- Delay Simulation……Page 80
2.7.2 Unit- Delay Simulation……Page 82
2.7.3 Nominal- Delay Simulation……Page 83
2.8 MULTIPLE- VALUED SIMULATION……Page 85
2.9.1 The Scheduler……Page 88
2.9.2 The Descriptor Cell……Page 91
2.9.3 Evaluation Techniques……Page 94
2.9.4 Race Detection in Nominal- Delay Simulation……Page 95
2.9.5 Min ¨C Max Timing……Page 96
2.10 SWITCH- LEVEL SIMULATION……Page 98
2.11.1 Introduction……Page 110
2.11.2 The Reduce Operation……Page 115
2.11.3 The Apply Operation……Page 120
2.12 CYCLE SIMULATION……Page 125
2.13 TIMING VERIFICATION……Page 130
2.13.1 Path Enumeration……Page 131
2.13.2 Block- Oriented Analysis……Page 132
2.14 SUMMARY……Page 134
PROBLEMS……Page 135
REFERENCES……Page 140
3.1 INTRODUCTION……Page 143
3.2 APPROACHES TO TESTING……Page 144
3.3.1 Analysis at the Component Level……Page 146
3.3.3 Analysis at the Gate Level……Page 148
3.4 THE STUCK- AT FAULT MODEL……Page 149
3.4.1 The AND Gate Fault Model……Page 151
3.4.4 The Tri- State Fault Model……Page 152
3.4.5 Fault Equivalence and Dominance……Page 153
3.5 THE FAULT SIMULATOR: AN OVERVIEW……Page 155
3.6.1 Parallel Fault Simulation……Page 158
3.6.2 Performance Enhancements……Page 160
3.6.3 Parallel Pattern Single Fault Propagation……Page 161
3.7.1 An Example of Concurrent Simulation……Page 163
3.7.2 The Concurrent Fault Simulation Algorithm……Page 165
3.7.3 Concurrent Fault Simulation: Further Considerations……Page 170
3.8 DELAY FAULT SIMULATION……Page 171
3.9 DIFFERENTIAL FAULT SIMULATION……Page 173
3.10 DEDUCTIVE FAULT SIMULATION……Page 175
3.11 STATISTICAL FAULT ANALYSIS……Page 176
3.12 FAULT SIMULATION PERFORMANCE……Page 179
3.13 SUMMARY……Page 181
PROBLEMS……Page 183
REFERENCES……Page 186
4.2 THE SENSITIZED PATH……Page 189
4.2.1 The Sensitized Path: An Example……Page 190
4.2.2 Analysis of the Sensitized Path Method……Page 192
4.3 THE D- ALGORITHM……Page 194
4.3.1 The D- Algorithm: An Analysis……Page 195
4.3.2 The Primitive D- Cubes of Failure……Page 198
4.3.3 Propagation D- Cubes……Page 201
4.3.4 Justification and Implication……Page 203
4.3.5 The D- Intersection……Page 204
4.4 TESTDETECT……Page 206
4.5 THE SUBSCRIPTED D- ALGORITHM……Page 208
4.6 PODEM……Page 212
4.7 FAN……Page 217
4.8 SOCRATES……Page 226
4.9 THE CRITICAL PATH……Page 229
4.10 CRITICAL PATH TRACING……Page 232
4.11 BOOLEAN DIFFERENCES……Page 234
4.12 BOOLEAN SATISFIABILITY……Page 240
4.13.1 The BDD XOR Operation……Page 243
4.13.2 Faulting the BDD Graph……Page 244
4.14 SUMMARY……Page 248
PROBLEMS……Page 250
REFERENCES……Page 254
5.2 TEST PROBLEMS CAUSED BY SEQUENTIAL LOGIC……Page 257
5.2.1 The Effects of Memory……Page 258
5.2.2 Timing Considerations……Page 261
5.3.1 Seshu¡¯s Heuristics……Page 263
5.3.2 The Iterative Test Generator……Page 265
5.3.3 The 9- Value ITG……Page 270
5.3.4 The Critical Path……Page 273
5.3.5 Extended Backtrace……Page 274
5.3.6 Sequential Path Sensitization……Page 276
5.4 SEQUENTIAL LOGIC TEST COMPLEXITY……Page 283
5.4.1 Acyclic Sequential Circuits……Page 284
5.4.2 The Balanced Acyclic Circuit……Page 286
5.4.3 The General Sequential Circuit……Page 288
5.5 EXPERIMENTS WITH SEQUENTIAL MACHINES……Page 290
5.6 A THEORETICAL LIMIT ON SEQUENTIAL TESTABILITY……Page 296
5.7 SUMMARY……Page 301
PROBLEMS……Page 302
REFERENCES……Page 304
6.1 INTRODUCTION……Page 307
6.2.1 The Static Tester……Page 308
6.2.2 The Dynamic Tester……Page 310
6.3 THE STANDARD TEST INTERFACE LANGUAGE……Page 312
6.4 USING THE TESTER……Page 317
6.5 THE ELECTRON BEAM PROBE……Page 323
6.6 MANUFACTURING TEST……Page 325
6.7 DEVELOPING A BOARD TEST STRATEGY……Page 328
6.8 THE IN- CIRCUIT TESTER……Page 331
6.9 THE PCB TESTER……Page 334
6.9.1 Emulating the Tester……Page 335
6.9.2 The Reference Tester……Page 336
6.9.3 Diagnostic Tools……Page 337
6.10 THE TEST PLAN……Page 339
6.11 VISUAL INSPECTION……Page 340
6.13 SUMMARY……Page 343
PROBLEMS……Page 344
REFERENCES……Page 345
7.2 THE TEST TRIAD……Page 347
7.3 OVERVIEW OF THE DESIGN AND TEST PROCESS……Page 349
7.4.1 The Circuit Description……Page 351
7.4.2 The Test Stimulus Description……Page 354
7.5.1 Checkpoint Faults……Page 355
7.5.2 Delay Faults……Page 357
7.5.3 Redundant Faults……Page 358
7.5.4 Bridging Faults……Page 359
7.6 TECHNOLOGY- RELATED FAULTS……Page 361
7.6.2 CMOS……Page 362
7.6.3 Fault Coverage Results in Equivalent Circuits……Page 364
7.7 THE FAULT SIMULATOR……Page 365
7.7.1 Random Patterns……Page 366
7.7.2 Seed Vectors……Page 367
7.7.3 Fault Sampling……Page 370
7.7.4 Fault- List Partitioning……Page 371
7.7.6 Iterative Fault Simulation……Page 372
7.7.8 Circuit Initialization……Page 373
7.7.9 Fault Coverage Profiles……Page 374
7.7.10 Fault Dictionaries……Page 375
7.7.11 Fault Dropping……Page 376
7.8 BEHAVIORAL FAULT MODELING……Page 377
7.8.1 Behavioral MUX……Page 378
7.8.2 Algorithmic Test Development……Page 380
7.8.3 Behavioral Fault Simulation……Page 385
7.8.4 Toggle Coverage……Page 388
7.8.5 Code Coverage……Page 389
7.9.1 Trapped Faults……Page 392
7.9.3 The Imply Operation……Page 393
7.9.4 Comprehension Versus Resolution……Page 395
7.9.6 Test Pattern Compaction……Page 396
7.9.7 Test Counting……Page 398
7.10.1 The ATPG/ Fault Simulator Link……Page 402
7.10.2 ATPG User Controls……Page 404
7.10.3 Fault- List Management……Page 405
7.11 SUMMARY……Page 406
PROBLEMS……Page 407
REFERENCES……Page 409
8.1 INTRODUCTION……Page 411
8.2 AD HOC DESIGN- FOR- TESTABILITY RULES……Page 412
8.2.1 Some Testability Problems……Page 413
8.2.2 Some Ad Hoc Solutions……Page 417
8.3.1 SCOAP……Page 420
8.3.2 Other Testability Measures……Page 427
8.3.3 Test Measure Effectiveness……Page 429
8.3.4 Using the Test Pattern Generator……Page 430
8.4.1 Overview……Page 431
8.4.2 Types of Scan- Flops……Page 434
8.4.3 Level- Sensitive Scan Design……Page 436
8.4.4 Scan Compliance……Page 440
8.4.5 Scan- Testing Circuits with Memory……Page 442
8.4.6 Implementing Scan Path……Page 444
8.5 THE PARTIAL SCAN PATH……Page 450
8.6 SCAN SOLUTIONS FOR PCBs……Page 456
8.6.1 The NAND Tree……Page 457
8.6.2 The 1149.1 Boundary Scan……Page 458
8.7 SUMMARY……Page 467
PROBLEMS……Page 468
REFERENCES……Page 473
9.1 INTRODUCTION……Page 475
9.2 BENEFITS OF BIST……Page 476
9.3 THE BASIC SELF- TEST PARADIGM……Page 478
9.3.1 A Mathematical Basis for Self- Test……Page 479
9.3.2 Implementing the LFSR……Page 483
9.3.3 The Multiple Input Signature Register ( MISR)……Page 484
9.3.4 The BILBO……Page 487
9.4.1 Determining Coverage……Page 488
9.4.2 Circuit Partitioning……Page 489
9.4.3 Weighted Random Patterns……Page 491
9.4.4 Aliasing……Page 494
9.5.1 Microprocessor- Based Signature Analysis……Page 495
9.5.2 Self- Test Using MISR/ Parallel SRSG ( STUMPS)……Page 498
9.5.3 STUMPS in the ES/ 9000 System……Page 501
9.5.4 STUMPS in the S/ 390 Microprocessor……Page 502
9.5.5 The Macrolan Chip……Page 504
9.5.6 Partial BIST……Page 506
9.6.1 The Test Controller……Page 508
9.6.2 The Desktop Management Interface……Page 511
9.7 BLACK- BOX TESTING……Page 512
9.7.1 The Ordering Relation……Page 513
9.7.2 The Microprocessor Matrix……Page 517
9.7.3 Graph Methods……Page 518
9.8 FAULT TOLERANCE……Page 519
9.8.1 Performance Monitoring……Page 520
9.8.2 Self- Checking Circuits……Page 522
9.8.3 Burst Error Correction……Page 523
9.8.4 Triple Modular Redundancy……Page 527
9.9 SUMMARY……Page 529
PROBLEMS……Page 531
REFERENCES……Page 534
10.1 INTRODUCTION……Page 537
10.2 SEMICONDUCTOR MEMORY ORGANIZATION……Page 538
10.3 MEMORY TEST PATTERNS……Page 541
10.4 MEMORY FAULTS……Page 545
10.5 MEMORY SELF- TEST……Page 548
10.5.1 A GALPAT Implementation……Page 549
10.5.2 The 9N and 13N Algorithms……Page 553
10.5.4 Parallel Test for Memories……Page 555
10.5.5 Weak Read ¨C Write……Page 557
10.6 REPAIRABLE MEMORIES……Page 559
10.7 ERROR CORRECTING CODES……Page 561
10.7.1 Vector Spaces……Page 562
10.7.2 The Hamming Codes……Page 564
10.7.3 ECC Implementation……Page 566
10.7.4 Reliability Improvements……Page 567
10.7.5 Iterated Codes……Page 569
10.8 SUMMARY……Page 570
PROBLEMS……Page 571
REFERENCES……Page 573
11.2 BACKGROUND……Page 575
11.3.1 Toggle Count……Page 577
11.3.2 The Quietest Method……Page 578
11.4 CHOOSING A THRESHOLD……Page 580
11.5 MEASURING CURRENT……Page 581
11.6 IDDQ VERSUS BURN- IN……Page 583
11.7 PROBLEMS WITH LARGE CIRCUITS……Page 586
11.8 SUMMARY……Page 588
PROBLEMS……Page 589
12.1 INTRODUCTION……Page 591
12.2 DESIGN VERIFICATION: AN OVERVIEW……Page 592
12.3.1 Performance Enhancements……Page 594
12.3.2 HDL Extensions and C++……Page 596
12.3.3 Co- design and Co- verification……Page 597
12.4.1 Coverage Evaluation……Page 599
12.4.2 Design Error Modeling……Page 602
12.5 RANDOM STIMULUS GENERATION……Page 605
12.6.1 Overview……Page 611
12.6.2 The RTL Circuit Image……Page 612
12.6.3 The Library of Parameterized Modules……Page 613
12.6.4 Some Basic Behavioral Processing Algorithms……Page 617
12.7.1 A State Traversal Problem……Page 621
12.7.2 The Petri Net……Page 626
12.8.1 An Overview of TDX……Page 631
12.8.2 DEPOT……Page 638
12.8.3 The Fault Simulator……Page 640
12.8.4 Building Goal Trees……Page 641
12.8.5 Sequential Conflicts in Goal Trees……Page 642
12.8.6 Goal Processing for a Microprocessor……Page 644
12.8.7 Bidirectional Goal Search……Page 648
12.8.8 Constraint Propagation……Page 649
12.8.9 Pitfalls When Building Goal Trees……Page 650
12.8.10 MaxGoal Versus MinGoal……Page 651
12.8.11 Functional Walk……Page 653
12.8.12 Learn Mode……Page 654
12.8.13 DFT in TDX……Page 657
12.9 DESIGN VERIFICATION……Page 659
12.9.2 Theorem Proving……Page 660
12.9.3 Equivalence Checking……Page 662
12.9.4 Model Checking……Page 664
12.9.5 Symbolic Simulation……Page 672
12.10 SUMMARY……Page 674
PROBLEMS……Page 676
INDEX……Page 681