UBC Theses and Dissertations

UBC Theses Logo

UBC Theses and Dissertations

On fault coverage and fault simulation for multiple signature analysis BIST schemes Zhang, Chun 1993

Your browser doesn't seem to have a PDF viewer, please download the PDF to view this item.

Item Metadata

Download

Media
831-ubc_1993_fall_zhang_chun.pdf [ 3.84MB ]
Metadata
JSON: 831-1.0065141.json
JSON-LD: 831-1.0065141-ld.json
RDF/XML (Pretty): 831-1.0065141-rdf.xml
RDF/JSON: 831-1.0065141-rdf.json
Turtle: 831-1.0065141-turtle.txt
N-Triples: 831-1.0065141-rdf-ntriples.txt
Original Record: 831-1.0065141-source.json
Full Text
831-1.0065141-fulltext.txt
Citation
831-1.0065141.ris

Full Text

ON FAULT COVERAGE AND FAULT SIMULATION FOR MULTIPLESIGNATURE ANALYSIS BIST SCHEMESByChun ZhangB. A. Sc. Guilin Institute of Electronic Technology, P.R. ChinaA THESIS SUBMITTED IN PARTIAL FULFILLMENT OFTHE REQUIREMENTS FOR THE DEGREE OFMASTER OF APPLIED SCIENCEinTHE FACULTY OF GRADUATE STUDIESELECTRICAL ENGINEERINGWe accept this thesis as conformingto the required standardTHE UNIVERSITY OF BRITISH COLUMBIAJune 1993© Chun Zhang, 1993In presenting this thesis in partial fulfilment of the requirements for an advanceddegree at the University of British Columbia, I agree that the Library shall make itfreely available for reference and study. I further agree that permission for extensivecopying of this thesis for scholarly purposes may be granted by the head of mydepartment or by his or her representatives. It is understood that copying orpublication of this thesis for financial gain shall not be allowed without my writtenpermission.(Signature) a&cirica, &VI/leer/fruDepartment ofThe University of British ColumbiaVancouver, CanadaDate ^77;---iy -2_ , /993DE-6 (2/88)AbstractFault coverage and fault simulation issues related to multiple signature analysis (MSA)built-in self-test (BIST) schemes are treated here. A model to predict the fault coverageis presented. Based on this model, the nature of the fault coverage for MSA is discussed.The fault coverage of MSA is a function of both the signature sizes and the schedulings.The problem of optimal signature scheduling in MSA to minimize fault simulation timeis discussed. Using the developed model, for an arbitrary circuit under test (CUT), giventhe optimal scheduling positions, given the fault coverage data before data compaction,and given an aliasing threshold, the optimal MSA for the CUT can be readily designedin terms of signature sizes and number of signatures. Analysis and experimental resultsare presented.Table of ContentsAbstractList of Tables^ viList of Figures viiiAcknowledgement1 Introduction^ 11.1 Design for Testability  ^21.2 Pseudorandom Testing  ^31.3 Conventional IC Testing With Automatic Test Equipments  ^41.4 Built-In Self-Test  ^41.5 Multiple Signature Analysis  ^61.5.1 Hassan's MSA  ^71.5.2 Lee's MSA  ^81.5.3 Generalized MSA  ^81.6 Test Quality Measure ^  101.6.1 Fault Model  ^101.6.2 Fault Coverage  ^101.7 Motivation of This Thesis  ^101.7.1 Necessity of Exact Fault Coverage After Compaction  ^101.7.2 Necessity of a. Fault Coverage Loss Model for MSA  ^112^1.8^Thesis Organization ^Multiple Signature Fault Coverage Loss Model^2.1^Notations and Preliminaries ^2.1.1^Notations ^2.1.2^Signature Bit Partitions ^^2.2^Fault Coverage Model With Signature Analysis1415151517182.2.1^Basic Definitions ^ 192.2.2^Fault Coverage of Random Vectors ^ 192.2.3^Estimated Fault Coverage with Single Signature Analysis 202.2.4^Fault Coverage with Intermediate Signature Analysis ^ 212.3 A Simplified Fault Coverage Model for Multiple Signature Analysis 222.4 Signature Bits Distribution vs. Fault Coverage ^ 262.5 Experimental Results 332.5.1^ISCAS'85 Benchmark Circuits ^ 332.5.2^Experimental Cases ^ 342.5.3^Results ^ 352.5.4^Fault Coverage Loss Model Accuracy ^ 462.6 Conclusions ^ 553 Multiple Signature Fault Simulation Time Model 563.1 Preliminaries and Definitions 563.1.1^Basic Definitions ^ 573.2 Time Model ^ 583.2.1^Fault Simulation Time Model for Multiple Signature Analysis 583.2.2^Normalized Fault Simulation Time Model ^ 603.2.3^Justification of the Normalized Fault Simulation Model ^ 60iv3.3 Equidistant Scheduling & Even Partitioning MSA ^  613.3.1 Number of Signatures vs. Fault Simulation Time ^ 643.4 Optimal Scheduling of Multiple Signature Analysis  663.4.1 Recursive Relationship  ^663.4.2 Optimal Scheduling vs. Aliasing  ^673.4.3 Fault Simulation Time vs. Scheduling ^  763.5 Fault Coverage Loss vs. Fault Simulation Time  793.6 Conclusions ^  844 Conclusions^ 854.0.1 Future Work^  86Bibliography^ 87List of Tables1.1 Comparison of Aliasing Probability ^  132.2 Number of Partitions for k = 16  192.3 Possible Signature Bit Partitions  ^192.4 Hardware Cost Analysis for Multiple Signature Schemes ^ 292.5 ISCAS'85 Benchmark Circuit Characteristics ^  332.6 Fault Coverages for (16,16; 1,^, 1; 2048) MSA  ^382.7 Fault Coverages for (16,8; 2, ... , 2; 2048) MSA  ^382.8 Fault Coverages for (16,4; 4, ... , 4; 2048) MSA  ^392.9 Fault Coverages for (16,2; 8, 8:2048) MSA  ^392.10 Fault Coverage Comparison for (16, 8; 1, . , 1, 9; 2048) MSA and (16, 8; 9,1,, 1; 2048) MSA ^  402.11 Fault Coverage Comparison for (16, 4; 1, 1, 1,13; 2048) MSA, and (16, 4;13, 1, 1, 1; 2048) MSA  ^402.12 Fault Coverage Comparison for (16, 2;1,15; 2048) MSA and (16, 2; 15, 1;2048) MSA ^  412.13 Fault Coverages for (16,16;1,. . 1:2048; 0 ; aliasing) MSA and (16,16;1,^ ,1;2048; 0; no aliasing) MSA ^  412.14 Fault Coverages for (16,8;2,... . 2;2048; 0 ; aliasing) MSA and (16,8;2,^, 2;2048;0; no aliasing) MSA  ^422.15 Fault Coverages for (16,4;4,4, -1,4;2048; 0; oliasing) MSA and (16,4;4,44,4;2048; 0; no aliasing) MSA  ^42Vi2,16 Fault Coverages for (16,2;8,8;2048; 0; aliasing) MSA and (16,2;8,8;2048;0;no abasing) MSA^  463.17 Fault Simulation Time Model Justification for c432, c499, c880, c1355, c1908 623.18 Fault Simulation Time Model Justification for c2670, c3540, c5315, c6288,c7552 ^  633.19 Fault Simulation Time at Equidistant Scheduling Cases ^ 653.20 Optimal Scheduling of Signatures for c432, c499, c880, c1355, c1908 forMSA ^  723.21 Optimal Scheduling of Signatures for c2670, c3540, c5315, c6288, c7552for MSA ^  733.22 Delta Scheduling Vectors bSV for c432, c499, c880, c1355, c1908  ^743.23 Delta Scheduling Vectors 6SV for c2670, c3540, c5315, c6288, c7552 . .  ^753.24 Fault Simulation Time Saving Comparison for c432, c499, c880, c1355, c1908 773.25 Fault Simulation Time Saving Comparison for c2670, c3540, c5315, c6288,C7552 ^  783.26 Fault Coverage Data Before Compaction for c1355 ^ 803.27 Fault Coverage Loss vs. Total Number of Signature Bits ^ 81ViiList of Figures1.1 A Generic BIST Scheme  ^51.2 Hassan's MSA Model  ^71.3 Lee's MSA Model  ^81.4 A Generalized MSA Model  ^92.5 Balls and Dividers  ^182.6 Multiple Signature Analysis Fault Coverage ^  242.7 Hardware Cost Analysis ^  312.8 Fault Coverage Comparison for (16, 8; 1,^, 1, 9; 2048), (16, 8; 9,1, . , 1; 2048),and (16,8; 2, ... ,2; 2048) MS.A  ^432.9 Fault Coverage Comparison for (16,4; 1, 1, 1, 13; 2048), (16,4; 13, 1, 1, 1; 2048),and (16,4; 4, ... , 4; 2048) MSA  ^442.10 Fault Coverage Comparison for (16, 2; 1, 15; 2048), (16, 2; 15,1; 2048), and(16, 2; 8, . , 8; 2048) MSA   452.11 Fault Coverage Before Compaction for c432, c499, c880, c1355, and c1908 472.12 Fault Coverage Before Compaction for c2670, c3540, c5315, c6288 and c7552 482.13 Fault Coverage Errors for (a) (16. 16; 1, . , 1; 2048) MSA; (b) (16, 8; 2, ... , 2;2048) MSA ^  502.14 Fault Coverage Errors for ( c) (16,4; 4, . , 4; 2048) MSA; (d) (16,2; 8,8;2048)MSA ^  51viii2.15 Fault Coverage Comparison for MSA and SSA: (a) (16,16; 1,^, 1; 2048)MSA and (16,1; 16; 2048) SSA; (b) (16,8; 2,..., 2; 2048) MSA and (16,1;16;2048) SSA ^  522.16 Fault Coverage Comparison for MSA and SSA: (a) (16,4; 4, ... , 4; 2048)MSA and (16, 1; 16; 2048) SSA; (b) (16, 2; 8,8; 2048) MSA and (16, 1; 16; 2048)SSA ^  532.17 Fault Coverage Comparison for Different n ^  543.18 Optimal Scheduling of the First Signature of two signatures ^ 683.19 Optimal Scheduling Algorithm ^  693.20 The Movement of Optimal Scheduling  703.21 Fault Coverage Loss vs. k and n ^  83AcknowledgementI would like to thank Dr. Andre Ivanov for being as approachable a supervisor as anyonecould hope for, for the frequent discussions with him on various aspects of VLSI testing,for his patient reading and correcting mistakes in this thesis, and for his continuousencouragement and support. I also benefited greatly from the productive discussionswith Yuejian Wu and the valuable suggestions from him. I am also indebted to my closefriends Ellen and Carly for their consistent moral support and help. I owe a very specialthanks to my parents and my dear husband for their love and encouragement throughmy most difficult time.Chapter 1IntroductionSince the 1970s, a revolution in the field of digital circuit testing has been taking place.This is a revolution that has not ceased, due to the increasing density of integratedcircuits (ICs). Pre-1970 circuit packages had perhaps one gate for each two or threepackage pins. By 1980 the gate-to-pin ratio had not only reversed but also approached20 gates per pin or more. At present, it is not unusual to find 100 gates or more behindevery pin [4]. The increase in package density causes a dramatic reduction per circuitcost, but the percentage of those costs consumed by testing stubbornly increases [4] dueto the following reasons:• Test generation for ICs becomes more and more expensive and difficult as thedensity of the ICs increases. The test generation algorithms developed for smallscale integrated (SSI) or medium scale integrated (MSI) circuits, such as the D-algorithm, are no longer suitable for very large scale integrated (VLSI) circuits.• Test sequence length required becomes longer and longer as the density of the ICsincreases. The increase in test sequence length causes the increase in the requiredstorage for test pattern sets.• The volume of test output response expands as the test sequence length increases.The increase in the volume of test output response causes the increase in the storagerequired for the output response, and as well as the increase in the complexity ofoutput response evaluation.1Chapter 1. Introduction^ 2• It is common for the number of memory elements in ICs to increase as the densityof ICs increase. The complexities of setting up the memory elements and observingtheir logic values increase. Although test generation techniques for combinationalcircuits are relatively mature, test generation techniques for sequential circuits arestill struggling.In order to overcome the difficulties of VLSI testing, research on various aspects ofVLSI testing, such as test generation [15][20][21][25][56] and output response evaluation[45][50][13][62], has been conducted actively for over two decades and is still of muchinterest. From these efforts, the discipline known as design for testability (DFT) [57] hasemerged.1.1 Design for TestabilityIn 1975, Phillip Writer of the Test Equipment Technical in San Diego first proposed [4]the concept of DFT. DFT design techniques use a set of design constraints which leadto more testable designs, especially in the case of sequential circuits. Since then, DFTtechniques have rapidly developed.DFT techniques can be classified into (i) ad hoc design techniques; (ii) structured designtechniques. Ad hoc design techniques are just a collection of good design methods thatare manually applied with the judgement and skill of the designer. None of these ad hocmethods completely solves the problem of testing sequential circuits or even combina-tional circuits. For this reason, much more attention has been paid to structured DFTtechniques [58][38][18][11]. The most common structured DFT requires compliance to aset of ground rules centered around a uniform design method for latches, generally knownas "scan design". The power of scan is that if the states of all latches can be controlledChapter 1. Introduction^ 3to any specific value and observed easily, then test generation and fault simulation of asequential circuit reduce to that of combinational logic. A control signal can switch thememory elements from their normal mode of operation to a mode that makes them con-trollable and observable. Known scan techniques are level sensitive scan design (LSSD)[10], scan path [16], scan/set logic [51] and random-access scan [3].With scan design, the test generation of sequential circuits can be reduced to the testgeneration of combinational circuits. However, the test generation for combinationalcircuits of VLSI complexity is still very expensive in terms of computing efforts. Ithas been shown that the test generation problem for combinational circuits belongs tothe class of NP-complete problems [24]. In the worst case, problems of this class areexposed to exponential increases in solution time as the size of the problem increases.Pseudorandom testing is one of the possible ways used to avoid the test pattern generationproblem.1.2 Pseudorandom TestingPseudorandom testing is the testing method which uses pseudorandomly generated testvectors as test patterns. The pseudorandom test patterns can be generated by an au-tonomous linear feedback shift register (ALFSR.) circuit or by a program simulating anALFSR [39]. Pseudorandom testing can be used to test both combinational and se-quential networks. McCluskey et al. [39] discussed combinational circuit pseudorandomtesting. Losq [34] discussed sequential circuit pseudorandom testing. Pseudorandomtesting can be used either with external automatic test equipment (ATE) testing or withself testing.Chapter 1. Introduction^ 41.3 Conventional IC Testing With Automatic Test EquipmentsIn the age of SSI and MSI circuits, the task of testing ICs was mainly fulfilled by ATEs.Testing ICs using ATE includes several steps. First, a test pattern generation algorithm,such as the D-algorithm [6], PODEM [20] or FAN [15], is employed to generate testpatterns for each possible modeled fault in the CUT. Second, the previously generatedtest patterns are applied to the CUT and the resulting outputs are captured by the ATE.Last, the outputs of the CUT are compared with the pre-calculated fault-free outputvalues to decide if the CUT is fault-free. While such test systems can yield excellentperformance, they tend to be self-obsolescent since (i) they are extremely expensive,especially for the ATEs designed for circuits of VLSI complexity; (ii) they are made fromthe same generic integrated circuits that they are designed to test. Hence, by the timethey are designed and built by their manufacturers, and purchased and installed by theusers, the leading edge of the integrated circuit technology has moved on, creating a testsystem requirement that the "new" test system can only marginally satisfy. Based onthese factors, Bardell, et al. [4] pointed out that the test technology for VLSI must beextended to include BIST in order for progress to continue.1.4 Built-In Self-TestBIST refers to those testing techniques in which additional hardware is added to a designso that testing is accomplished without the aid of external test equipment. In BIST, boththe function of test pattern generation and the function of output response evaluation areincorporated into the CUT. In order to avoid manipulating huge volumes of output data,BIST uses compaction techniques to compact the output data. Examples of compactiontechniques include syndrome compaction [45], parity checking [50], signature analysis[13].Chapter 1. Introduction^ 5PASS/FAIL TPG CUT ODC CMP FFS.eT\ STCFigure 1.1: A Generic BIST SchemeFig. 1.1 illustrates a generic BIST scheme. The CUT is driven by the test patterngenerator (TPG) which generally consists of an ALFSR. The output response of the CUTis compacted by an output data compactor (ODC). If the ODC consists of a parallel toserial converter as well as a linear feed back shift register (LFSR) or a multiple inputshift register (MISR), the output response is shifted into the LFSR serially or into theMISR in parallel. After the whole output sequence of the CUT is shifted into the LFSRor MISR, the content of the LFSR or MISR forms the signature of the output response.At the end, the signature is compared through a comparator (CMP) with the fault freesignature (FFS), which is prestored in on-chip memory elements, such as a ROM, tomake the final pass or fail decision.BIST techniques can alleviate the problems of external testing schemes. First, since testpatterns are usually generated by an on-chip TPG, the time-consuming effort of testpattern generation is avoided in the design cycle. An additional benefit of the built-in TPG is that the internal nodes of the circuit under test are easily accessed by theChapter 1. Introduction^ 6generator and hence a higher fault coverage and shorter test time can be achieved [4].Moreover, since the output responses are compacted first and the signature is comparedonly once, the difficulty of storage and analysis of huge volume of both test pattern dataand pre-calculated fault-free test response data can be avoided. Thus, BIST can eliminatethe use of expensive external test equipment. BIST has another important advantage inthat the CUT is fed with test patterns at normal functional clock rate. Hence, BIST isespecially suitable for achieve high speed testing.BIST approaches have been successfully applied to commercial products such as micro-computers [30], signal processing chips [32], and have proved to be a very promisingtechnique. However, BIST is not perfect, and inevitably has weaknesses. Three maindrawbacks are:1. Employing a compactor introduces aliasing, the phenomenon of a fault escapingdetection after compaction. Test effectiveness is degraded by aliasing.2. Generally, BIST uses pseudorandom test patterns. Such test sets tend to be longin order to achieve high test quality.3. Due to compaction, required fault simulation efforts increase tremendously com-pared to the case of no compaction.Multiple signature analysis (MSA) has been proposed to overcome the above drawbacks[22] [31] [33].1.5 Multiple Signature AnalysisIn [22], Hassan and McCluskey proposed a IVISA scheme to increase test quality. In [33] ,Lee proposed a scheme of checking intermediate signatures to reduce the average testingChapter 1. Introduction^ 7time. In [31], Lambidonis et al. proposed a scheme of checking intermediate signaturesto reduce the fault simulation efforts for HIST drastically.The concept of MSA proposed in [22] is different from that of intermediate signatureproposed in [33]. We review these schemes next, and then give a more general definitionof MSA.1.5.1 Hassan's MSAThe MSA proposed in [22], referred to as Hassan's MSA here, is a signature analysisscheme which checks two signatures from the same signature analyzer resulting from twodifferent input sequences. Fig. 1.2 illustrates the scheme. The CUT is driven by theinput sequences IS1 and IS2 serially. The resulting output sequence of IS1 is compactedthrough the ODC to generate the signature of the output sequence. Then the signatureis compared by the comparator CMP with predetermined fault free signature FFS1. Ifthe two signatures differ, then the "fail" decision will be made and the test is completed.If they are the same, the same process for IS1 will be repeated for IS2. Final "fail" or"pass" decision will be made. Note that in Hassan's MSA scheme, the input sequencesIS1 and IS2 are two different sequences. The output sequences share the same ODC.Figure 1.2: Hassan's MSA ModelChapter 1. Introduction^ 81.5.2 Lee's MSAThe intermediate signature analysis scheme proposed in [33] is a scheme which checksmore than one signature from the same signature analyzer at different stages of the testprocess. Fig. 1.3 gives an example.Figure 1.3: Lee's MSA ModelIn Lee's MSA model, the input sequences are segments of one single pseudorandom testsequence generated by a LFSR. Input sequence segment ISS1 is applied to the CUT first,the output sequence of ISS1 is compacted through the ODC to generate the signature ofthe output sequence. Then the signature is compared through CMP with the prestoredfault free signature FFS1. If the two signatures differ, then a "fail" decision is made andthe test completes. If they are the same, then the same process will repeat for ISS2 andso on until either a "fail" decision is made or the whole test process completes with a"pass" decision. Similar to Hassan's MSA model, Lee's MSA model has only one physicalODC as well.1.5.3 Generalized MSAGeneralized MSA scheme defined here is a. scheme which checks multiple signatures fromdifferent signature analyzers at different stages of the test process. As illustrated inChapter I. Introduction^ 9Fig. 1.4, for the generalized MSA, multiple FFSs (FFS1,^FFSn) are predeterminedand prestored in an on-chip ROM or in other forms of storage. The position of thesignatures, referred to as checkpoints [60], are predetermined as well. Whenever thetest session reaches a checkpoint, the signature of the output sequence from a certainsignature analyzer is compared to the related FFS, and a pass or fail decision is made. Ifa fail decision is made, the test is terminated; otherwise, the test continues until eithera fail decision is made or the whole test is completed. Similar to Lee's MSA model, theinput sequences (ISS1, ISS2, ISSn) for a generalized MSA model are segments of onesingle pseudorandom test sequence generated by a pseudorandom TPG. For generalizedMSA model, it is assumed that there are n physical ODCs, ODC1, ODC2, ODCn.If the number of signature analyzer is one, the generalized MSA model becomes Lee'sMSA model.Figure 1.4: A Generalized MSA ModelChapter 1. Introduction^ 101.6 Test Quality Measure1.6.1 Fault ModelIn order to perform functional testing, fault modeling is needed. Fault modeling refers toa set of methodologies through which physical failures are represented by logic models.The logic models used to represent physical failures are called fault models. The mostoften used fault model is the single stuck-at model which allows any node to be stuck-atlogical zero (s-a-0) or stuck at logical one (s-a-1) [6].1.6.2 Fault CoverageOne of the most commonly used test quality measure to evaluate testing schemes is faultcoverage. Fault coverage is defined as the percentage of modeled faults known to bedetected [38].As mentioned in Sec. 1.4, compaction techniques are employed in almost all the BISTtechniques. Once compaction is introduced, the fault coverage before and after com-paction generally differs due to the compaction information loss. Fault coverage beforecompaction is performed is referred to as fault coverage before compaction. Fault coverageafter compaction is performed is referred to as fault coverage after compaction.1.7 Motivation of This Thesis1.7.1 Necessity of Exact Fault Coverage After CompactionIn general, a fault goes undetected if none of the input test patterns produces an incorrectcircuit output in the presence of the fault. With output response compaction, it is alsopossible for a fault to fail detection even though the output response differs from thefault-free response. This is known as aliasing, i.e., the case where the output responseChapter 1. Introduction^ 11from a faulty circuit produces a signature that is identical to the signature of a fault-freecircuit.Due to aliasing, the quality evaluation problem of the test techniques with compaction isdifferent from that of the test techniques without compaction. The effect of compactionis traditionally characterized by aliasing probability [4], i.e., the probability that a faultdetected before compaction will escape detection after compaction. Different models havebeen proposed for characterizing the aliasing behavior of various compaction schemes[9][13][26][27][50][59].Conventionally, the evaluation of the test quality after compaction is achieved by thefault coverage before compaction and the aliasing probability of compaction. This causesstatistical uncertainty in the evaluation of test quality. It may be wasteful to spendconsiderable hardware and software resources towards achieving a certain known faultcoverage before compaction and still end up with uncertainty of the fault coverage aftercompaction [31]. Thus, Lambidonis et al. [31] proposed a methodology towards thecomputation of exact fault coverage for signature analysis schemes. The results givenin [31] show that the proposed methodology can reduce the fault simulation time withcompaction significantly. Hence, exact fault coverage after compaction can be calculatedwith feasible computation efforts.1.7.2 Necessity of a Fault Coverage Loss Model for MSAThe MSA that the strategy in [31] exploits implies a higher hardware cost. In practice, theallowable HIST overhead limits the total number of signature bits. Given the allowablehardware overhead limit in terms of total number of allowable signature bits, a largenumber of choices can arise in partitioning the total number of signature bits amongvarious intermediate signatures. The optimal partition of the total number of signatureChapter 1. Introduction^ 12bits is required such that the fault simulation time with compaction is minimized andfault coverage is maximized. However, before we can meet the requirements, we needto explore the MSA aliasing behavior further since existing models for MSA aliasingbehavior [5] are inadequate.In BIST with single signature analysis (SSA) [4], to compact an output sequence of length/, the sequence is shifted bit by bit into a signature analyzer of size k. At the end ofthe test process, the contents of the signature analyzer form the signature. Under theassumption of the equally likely error model [4], the aliasing probability Pa is:91—k^1When 1 k, Pa 2-k.Similarly, in BIST with MSA, assume that n signatures of sizes kl, k2,^kn, are checkedat check points 11, 12, ..., 4,. The total number of signature bits is k, i.e.,^ki = k.Under the assumption of the equally likely error model [4], the aliasing probability forthe MSA is:n 9li—kiPa =1-1 ^9/, _1 (1.2)When /i ki for i = 1, , n, the aliasing probability for the MSA 2- E:-.1 = 2-k.The 2-k result is inadequate for some of the multiple signature analysis cases. In order toillustrate this, an small experiment was done. Consider a case where only two signaturesare taken, the total number of signature bits is 4, the total test length is 213 = 8192,the first signature taken at 28 = 256, and the second signature taken at the end of thetest. Fault simulation was done for two different signature bit distributions. For the firstsignature bit distribution, both signatures are assigned 2 bits. For the second signaturebit distribution, the first signature has 1 bit, and the second signature has 3 bits. TheChapter 1. Introduction^ 13D2(ki, k2) P. PG:D2(2,2) 0.0780 0.0625D2 (1, 3) 0.0668 0.0625Table 1.1: Comparison of Abasing Probabilityfault simulation results are presented in Table 1.1. D2(k1, k2) represents the signaturebit partition for a MSA scheme when the total number of signatures is 2. k1 denotes thelength of the first signature, and k2 denotes the length of the second signature. Pa is theprobability of aliasing and is calculated as the ratio of the total number of faults escapedafter compaction to the total number of faults detected after compaction. The Pa isthe average of ten trials for the ten ISCAS'85 (International Symposium on Circuits andSystems) benchmark circuits [7] and _/=) is the aliasing probability calculated by using2-k, which is given in [5].From the results, we can see that the aliasing probabilities for the two experiments differeven though the total number of signature bit is the same for the two experiments, i.e.,k = 4.In order to further explore MSA schemes, more accurate models are needed to depict thealiasing behavior of the MSA schemes. In [61], one such model is developed. Althoughthe model developed in [61] accurately models the aliasing behavior of MSA schemes,the density function of detection probabilities of the faults in a circuit is also required.Usually, it is expensive to obtain a precise detection probability density function forlarge circuits. In this thesis, a simplified model that only requires the fault coverageinformation of a circuit without compaction is developed.Chapter 1. Introduction^ 141.8 Thesis OrganizationThis thesis proposes a model to predict the fault coverage of MSA. This model allows usto discuss the aliasing behavior of MSA. Furthermore, the model enables the discussionof the relationship between the aliasing behavior of MSA and the latter's acceleration offault simulation. The remainder of the thesis is organized as follows. Chapter 2 presentsa model to predict aliasing and the fault coverage for MSA. Chapter 3 presents a faultsimulation time model for MSA. Based on the model, a forward dynamic programmingalgorithm is developed to yield the optimal signature scheduling to achieve minimal faultsimulation time. From the fault coverage prediction model presented in Chapter 2 andthe fault simulation time model presented in Chapter 3, trade-offs arise between faultsimulation time gain and the fault coverage. Chapter 4 concludes the thesis and pointsout some directions for future work.Chapter 2Multiple Signature Fault Coverage Loss Model2.1 Notations and Preliminaries2.1.1 Notations(k , n;^, ky;^. . ,1) MSA SchemeA (k, n; kl,^, kr,;^,172) MSA scheme represents the following testing scheme: nsignatures are checked at the predetermined check points 11,12,^, /„, and that the sig-natures are of sizes k1 , k2,^, kn, respectively. The total number of signature bits isk.(k , n;^, kn; 1) MSA SchemeA (k, n;^. , kn; 1) MSA scheme represents the following testing scheme: n signaturesare checked at equidistantly scheduled check points^, ;I, and that the signaturesare of sizes 101, k2,^, kyi, respectively. The total number of signature bits is k.(k,n;ki, , kn; 1; 0) MSA SchemeA (k, n;^. . ,k; 1; 0) MSA scheme represents the following testing scheme: n signaturesare checked at optimal scheduled n check points, and that the signatures are of sizesk2, , k , respectively. The optimal scheduled check points are calculated using theoptimal scheduling algorithm developed in chapter 3. The total number of signature bitsis k.15Chapter 2. Multiple Signature Fault Coverage Loss Model^ 16(k ,n;^, kn; 1; 0; aliasing) MSA SchemeA (k, n;^. . . , kn; 1; 0; aliasing) MSA scheme represents the following testing scheme: nsignatures are checked at optimal scheduled n check points, and that the signatures are ofsizes kl, k2, . . , km, respectively. The optimal scheduled check points are calculated usingthe optimal scheduling algorithm developed in chapter 3. Aliasing effect is consideredwhen calculating the optimal scheduling. The total number of signature bits is k.(k, n;^• • • , kn; 1; 0; no aliasing) MSA SchemeA (k, n; kl,^, 42;1; 0; no aliasing) MSA scheme represents the following testing scheme:n signatures are checked at optimal scheduled n check points, and that the signaturesare of sizes k1 , k2, , km, respectively. The optimal scheduled check points are calculatedusing the optimal scheduling algorithm developed in chapter 3. Aliasing effect is notconsidered when calculating the optimal scheduling. The total number of signature bitsis k.(k, 1; k; 1) SSA. SchemeA (k, 1; k; 1) SSA scheme represents the following testing scheme: a single k-bit signatureis checked at the end of test of length 1.k2, . , kn) PartitionA Dn(ki, k2,^, kn) partition denotes the signature bit partition for the case where nsignatures are taken and the n signatures are of sizes 471, k2, . . , km, respectively.for a total of k signature bits and a total of n signatures checkpoints is(k —1n — 1Chapter 2. Multiple Signature Fault Coverage Loss Model^ 172.1.2 Signature Bit PartitionsThere are a number of ways to partition the signature bits among a number of sig-natures. For example, if the total number of signatures n = 8 and the total numberof signature bits k = 16, the number of possible signature partitions is 6435. For a(k, n; k1,. • • , kri; li,. • . ,1,2) MSA scheme, the problem of finding the number of bit par-titions is equivalent to determining how many different combinations of k'is exist whichsatisfy the conditions:• ki E {1 , 2, . . . , k } ,^1,9^• ki = k;• n < k.The first condition gives a constraint on the length of each signature analyzer, i.e., thelength of each signature analyzer has to be an integer within range [1, id. The secondcondition implies that the total number of signature bits is fixed. The third conditiongives a constraint on the total number of checked signatures.Theorem 1: The number of possible partitions of signature sizes k1 , k2,^, k, (ki > 1)Proof: Imagine k balls in a straight line with 1,7 — 1 spaces between those balls (see Fig.2.5). We need to divide the k balls into Tt groups. Therefore, n — 1 dividers should beput between the k balls under the constraint that for each space, at most one dividercan be put in. Then the number of ways of putting (n — 1) dividers in the (k — 1)spaces between k balls equals the number of all possible partitions of signature lengthsChapter 2. Multiple Signature Fault Coverage Loss Model^ 18k2,. , kn. Obviously, the number of ways of putting (n — 1) dividers in the (k — 1)spaces between k balls is ( k 1 ) .n — 1n-1 - 2Dividers0- I^0- ^0^ I.^0-^ •-0^0n-1 = 2^ ballsDividers k - 6Figure 2.5: Balls and DividersEach ball in the proof above represents one signature bit. The number of balls betweenany two adjacent dividers represents the number of signature bits allocated to somesignature, say, ki.From Theorem 1, given k and n, the number of all possible partitions of kJ., k2,..., kn is— 1)!— 1)!(k — n)!.(2.3)Table 2.2 gives the number of partitions for different 71. with k = 16. Table 2.3 gives all15 possible partitions for the k = 16, n = 2 case. k1 is the size of the first signature andk2 is the size of the second signature.2.2 Fault Coverage Model With Signature AnalysisIn this section, we introduce some definitions and briefly review some results presentedin [49] and [61].Chapter 2. Multiple Signature Fault Coverage Loss Model^ 19n # of Partitions n # of Partitions1 1 9 64352 15 10 50053 105 11 30034 455 12 13655 1365 13 4553003 14 1057 5005 15 158 6435 16 1Table 2.2: Number of Partitions for k = 16Possible Signature Bit Partitions (k = 16, n = 2)k1k2115214313412511610798897106115124133142151Table 2.3: Possible Signature Bit Partitions for n = 2 and k = 16.2.2.1 Basic DefinitionsDefinition 1: The detection probability of a fault is the probability of detecting anexisting fault by a single random test vector [49].Detection probabilities of faults in a circuit can be represented by a density functionor distribution p(x) such that p(x)dx corresponds to the fraction of testable faults withdetection probability between x and x dx. Since x represents a probability, therefore:p(x)dx = 1.^ (2.4)2.2.2 Fault Coverage of Random VectorsFor the sake of completeness, we review a derivation from [49] next. Since there arep(x)dx faults with detection probability .c, the mean coverage among these faults by aChapter 2. Multiple Signature Fault Coverage Loss Model^ 20random vector is xp(x)dx [49]. Suppose we apply a sequence of random vectors to theCUT. The mean coverage by the first vector is:1Jo xp(x)dx.^ (2.5)Actual coverage by a random vector might be different from the mean by a randomquantity. However, the variance will be small for almost all circuits [49]. After removingthe faults detected by the first vector, the normalized number of the remaining undetectedfaults UDT is:UDT = 1 — xp(x)dxJo (1 — x)p(x)dx.^ (2.6)Therefore, the distribution of detection probabilities of the remaining faults is (1—x)p(x).Thus, the coverage of two random vectors is:Y2 =^x(1 — x)p(x)dx= f x[l + (1 — x)ip(x)dx.^ (2.7)Similarly, we can find the coverage of 1 vectors to be:= jo x[1 +(1 — x) (1 — x)2 . . . (1 — x)11p(x)dx1 — f (1 — x)1 p(s)clx= 1 — I(1),^ (2.8)where I(1)^— x)1 p(x)dx.2.2.3 Estimated Fault Coverage with Single Signature AnalysisAssuming a k-bit signature is checked after applying 1 random vectors to a CUT, theasymptotic aliasing probability is p = 2-k under the equally likely error sequences as-sumption [5]. If we denote the probability of no aliasing by ,13, i.e., j3 = 1 — p, then theChapter 2. Multiple Signature Fault Coverage Loss Model^ 21fault coverage, FC*, after compaction when checking a single signature is:FC* = i3y/FC* = /3[1 — f(1 — x)1p(x)dx]=^ (1 — I(1)).^ (2.9)This result has been been verified experimentally by Rajski in [43].2.2.4 Fault Coverage with Intermediate Signature AnalysisFor a (k, n;^, kn,^,in) MSA scheme, assume that the aliasing probabilities as-sociated with the n signature analyzers are • Prz, respectively, and the corre-sponding probabilities of no aliasing are 3 3,- ,-2, • • • , 13n, where pi =^, 3j = 1 — pi andi^1, 2, . . . , n. Then, similar to the analysis in Sec. 2.2.3, the expected fault coverageafter checking the first signature at 11 is:FC1 =FC1 = /31[1 —^(1 — x)i'p(x)dad^= 131[1 — I(l1)]. (2.10)The proportion of faults that remain undetected after checking the first signature is:UDT1 = 1 — FC1= 1 — 31(1 — f (1 — x)11p(x)dx)=^[1 —3i + /31(1 — x)I1]p(x)dx.^(2.11)The new distribution of the detection probabilities of the remaining faults can be repre-sented by pi(x) = [1 — 3i + ,31(1— x)lp(x). Therefore, the fault coverage after checkingChapter 2. Multiple Signature Fault Coverage Loss Model^ 22the second signature at check point 12 is:FC2^FC1 +132[UDT1 —1 (1 — x) 12 p1(x)]dx= FC1 + /32 { UpTi^(1 — r)12 [1 — 131 + /31(1 — x)11]p(x)dx}= [132 +131(1 - /32)] - 0 1 (1 -132 )1(10 -02 (1 - )31)1(12) - /3021(11 + 12). (2.12)Similarly, we can find the distribution of the detection probabilities of the remainingfaults, and the fault coverage after checking the third signature, and so forth. In general,the fault coverage after checking the nth signature is:n-1FC =^+^Pi II (1^+^E^. • • t3i,Pik+i • •^+^+^(2.13)i=1^j=i+1 k=1 Akwhere Ak^{(il, • • • ik ,ik+1) • • • in); 1 <z1,< • • •^n, 1 < ik+1) < • • • < in, < nand^• • • , ik) ik+1, • • • , in) is a permutation of (1, 2, ..., n)}. For example, if n = 4, k = 2,then A2 =A(1,2,3,4),(1,3,2,4),(1,4,2,3), (2,3,1,4), (2,4,1,3),(3,4,1,211.2.3 A Simplified Fault Coverage Model for Multiple Signature AnalysisIn Sec. 2.2.4 a model for predicting the fault coverage for MSA is given. The model isbased on the knowledge of a density function of detection probabilities of the faults in acircuit. Usually, it is expensive to obtain a precise detection probability density functionfor large circuits. In [43], it has been shown that fault coverage with single signatureanalysis can be well estimated by using the fault coverage before data compaction andthe aliasing performance of the signature analyzer. In this section, we present a simplifiedmodel for predicting the fault coverage for MSA. As in [43], this model is also based onthe fault coverage before data compaction and the aliasing performance of the signatureanalyzers.Chapter 2. Multiple Signature Fault Coverage Loss Model^ 23For a (k, n;^,^,in) MSA scheme, assume that the corresponding aliasingprobabilities associated with the n signature analyzers are P1, P2,•• • , pn, respectively.Further, assume that, at the check points, the corresponding fault coverage before datacompaction is known to be F2, . Fri. The portion of additional faults detectedduring the segment [/i_i, /i] of test patterns is thus Fi — F1_1, for i 1, 2, ... , n, withF0 0. For example, at the check point 11, the percentage of faults detected is F1 —F0 =F1, and the faults detected during segment [4,12] is F2 - F1 (see Fig. 2.6). Accordingto [43], if a signature is checked at l, Fipi of the faults detected in the segment [la, /1]would be aliased. Assume that all the aliased faults will be redetected by the test vectorsduring the segments [4_1, /i] for i = 2, 3, ... ,n. Consequently, after checking the secondsignature at 12, the number of faults from F1 escaping detection due to the aliasing of thetwo signatures would be F1p1p2. Thus, the portion of faults from F1 that would escapedetection after checking n signatures is:riFcL,^H pi.^ (2.14)Similarly, for the (F2 — F1) faults first detected in segment [4,12], after checking thesecond signature at 12, (F2 — F1)p2 of the faults would he aliased due to data compaction.Note that the aliasing of the first signature checked at 11 has no impact on the faultsdetected after 11. Again, assuming that these aliased faults will be redetected by the testvectors during segments /i], for i = 3, 4, , n, the portion of faults aliased from(F2 — F1) when n signatures are checked is:FCL2 = (F2 — Fi) H pj.^ (2.15)In general, for the (F1—F1_1) faults first detected during the segment^lib the portionof the faults aliased from these after taking 11 signatures is:FCLi =(F1 —^H 7 ^ i = 1,2,...,n.^(2.16)F •^ Test Lengthii1- 1Fn_.2(a)1. 1n-1^• Test Lengthin100.00Chapter 2. Multiple Signature Fault Coverage Loss Model^ 24Figure 2.6: (a) Solid curve represents the fault coverage before data compaction. F1denotes the fault coverage before data compaction at check point 11. F2 denotes the faultcoverage before data compaction at check point 12, and so on. (b) FCLi is the faultcoverage loss on (Fi — Fz_1) segment due to the n signatures. The total fault signatureloss FCL =E7,1_,FCL,Chapter 2. Multiple Signature Fault Coverage Loss Model^ 25Therefore, the total fault coverage loss, FCL, with n signatures is:FCL = FCLii= 1(Fi — Fi-1)11Pi.^ (2.17)i=1Since the final fault coverage before data compaction is Fri, the fault coverage, FC, forMSA is:FC = Fn— FCL=^—^(Fi Fi-1) 11 Pi•^(2.18)i= 1Eqn.2.18 gives a prediction for the fault coverage with multiple signature analysis. Thismodel is solely based on the knowledge of the fault coverage before data compaction andthe estimated statistical performance of the signature analyzer. The efforts needed tocalculate fault coverage before data compaction are much less than the efforts to calculateexact detection probability. Thus, Eqn.2.18 is much simpler to compute compared to themodel discussed in Sec. 2.2.4. However, this simplified model is optimistic since weassume that all the faults aliased by a signature at a check point /i are redetected duringlater segments ii] for j = (i +1), (i +2), , n. In practice, this assumption may notbe true. Some faults aliased at 1 , may be redetected in some of the later segments, butnot necessarily in all of the segments. Some faults aliased at /i may not be redetected atall. Check points are usually scheduled as ( /i — /ii) < (li+i — /i) for i = 1, , n, so asto minimize either the required fault simulation time [31] or the average test time [33],most faults detected in segment ii] are likely to be redetected in later segments.Experimental results in Sec. 2.5.3 show that this model holds very well.Chapter 2. Multiple Signature Fault Coverage Loss Model^ 262.4 Signature Bits Distribution vs. Fault CoverageAs Eqn.2.18 implies, the final fault coverage achieved with checking n signatures of sizesk2,. , Ion depends on the scheduling of the check points 11,12,^, in and the signaturesizes k1 , k2,^, kn, i.e.,FC = f^k„, ii, l2, . . ,^ (2.19)Theorem 2: The expected fault coverage loss FC L for a. (k, n; kl,^,^, lri) MSAscheme is greater than that for the (k,1;k;1) SSA scheme.Proof: Assume that at the check points 11,12,^,L, the corresponding fault coveragebefore data compaction is known to be F1, F2, .. , Fn, with F0 0.According to Eqn. 2.17, the fault coverage loss, FCL*, after checking a single signatureat the end of test is:FCL^F H p ,^ (2.20)and, the fault coverage loss, FC L, for checking n signatures is:FC L =^Li=171 (Fi —^11 Pi-^ (2.21)i=1^j=iHence,FCL — FC L* = (E(Fj —^fl p) — (Fn MJ=i^i=11=1^ 1=2^ j=1E(Fi^1-;.--1)(11P:1i-1(Fi —^pi(1 —^p.)^H pi > O.Z =^3=1^•=1^3=1(2.22)Chapter 2. Multiple Signature Fault Coverage Loss Model^ 27The equality holds when n =Theorem 2 reveals that when checking multiple signatures at distinct check points toeither calculate the exact fault coverage of multiple signature analysis [31], or to reducethe average test time [33], fault coverage is sacrificed if the same amount of hardwareoverhead, i.e., measured in number of signature bits, is used.Theorem 3: Given that the n check points are predetermined for a (k, n; k,^. . , kn; 11, 12,MSA scheme, FCL for the MSA scheme is minimized when k1 = k2 ==1 and kr, = k — n 1.Proof: By Eqn. 2.17, we have,T1.FCL^)FCLi=1—where pi =^, j = 1, 2, . . . , 72 .LetHp',.7=t(2.23)- Fi ^i^1,...,n.^ (2.24)Since fault coverage is monotonic in test length, ci > 0 for i = 1, . , n. Also since thecheck points are predetermined, ci is fixed for i = 1,^, n.Lettii^1, 9, . . . , n.^ (2.25)Since k > 1 for jAlso, we have,(2.28)(2.27)Ti> i — 1 +E kiJ=1^J=1= i — 1.kTiChapter 2. Multiple Signature Fault Coverage Loss Model^ 28By Eqn. 2.24 and 2.25, we have:FCL = E eiti.^ (2.26)Therefore,— i^1,^i = 1, ... ,n. (2.29)The equality holds when k1 -=- k2 =^= ki_i = 1. kti => 9 -(k-i+1)(2.30)Since ci > 0,Therefore,citi > c12-(k-i+1). = 1,...,n.^(2.31)(2.32)Equality holds when k1 =^=^= 1.Chapter 2. Multiple Signature Fault Coverage Loss Model^ 29Dn(ki, k2,. . . , km) #o f D FF FCLD,(1,1,...,k - n +1) 2k - n + 2 E7-1(Fi - Fi-i) f17=i PiDi(k) 2k 2-kTable 2.4: Hardware Cost Analysis for Multiple Signature SchemesSince k1 k2^= k, FCL is minimized when kJ. = k2 =^= kri_i = 1, andkn k - n + 1. 0Theorem 3 gives the optimal partition for a total number of k signature bits when nsignatures are checked, assuming that the check points are predetermined and fixed.An example of the application of Theorem 3 follows. Let #ofDFF denote the number ofmemory elements (flip-flops) required to implement the signature analyzers and to storethe FFSs. Checking a total of k bits of signature requires storing k bits of information.This requires k latches or flip flops. Table 2.4 reports the fault coverage and hardwarerequirements for the above optimal scheme and the single signature scheme.From Table 2.4, we see that the fault coverage loss (FCL) of a (k, n; 1,1, ... , 1, k - n +MSA scheme is greater than that of a (k, 1; k; l) SSA scheme, where pi =2-kiHowever, the hardware cost of the former, measured in terms of the number of memoryelements, is less than the hardware cost of the latter as long as n > 2. For example, ifk = 16 and n = 5, the hardware cost of the (16,5; 1, 1, 1, 1,12; 11, , /5) MSA scheme is29 D flip-flops, while the hardware cost of the (16, 1; 16;15) SSA scheme is 32 D flip-flops.The hardware saving is 9%. Hardware saving is achieved at the expense of fault coverageloss if the number of checked signatures is increased. If we embed the single-bit signatureanalyzer in the k - n + 1 bit signature analyzer. then we can further decrease the numberof D flip-flops used by the (k, n; 1,1, . . . , 1, k - n + 1; /1,. , In) MSA scheme by 1, andthe hardware cost becomes 2k - 72 + 1. As long as 72 > 1, the hardware cost of theChapter 2. Multiple Signature Fault Coverage Loss Model^ 30(k, n; 1, 1, . . . , 1, k — n^1; 4,^, lm) MSA scheme is smaller than that of the (k,1; k; ln)SSA scheme.Fig. 2.7 shows a single-bit signature analyzer embedded in a k —n+ 1 signature analyzer.Fig. 2.7(a) and Fig. 2.7(b) show the 1-bit signature analyzer and the k-bit signatureanalyzer, respectively. Fig. 2.7(c) shows a k-bit signature analyzer where any D flip-flop(DFF) can be used as a 1-bit signature analyzer. The second DFF is arbitrarily chosenas the embedded single-bit signature analyzer. It is easy to show that the asymptoticaliasing probability of an embedded 1-bit signature analyzer is the same as the 1-bitsignature analyzer shown in Fig. 2.7 (a).Theorem 4: Given a (k, n; k,. , km;^, I„) MSA scheme, the fault coverage loss atthe end of the test FCL is maximized when ki = k — n +1, k2 = k3 =^= kr, =1.Proof: By Eqn. 2.17, we have,FCL = FCLii = 1— (2.33)where pi = ^= 1, 2, . . . , 72.Letci = F —^1,^,n. (2.34)Since fault coverage is monotonic in test length, ci > 0 for i = 1,^,n. Also since thecheck points are predetermined, ci is fixed for i^1.. , n.Letii =DFFk-2DFF ^k -1DFF^DFF •--2—Chapter 2. Multiple Signature Fault Coverage Loss Model^ 31(a) Single Bit Signature AnalyzerDFF(b) k-bit Signature AnalyzerDFF^DFF1DFF DFFk-2DFF ^k -3For example, arbitrarily chose thesecond DFF as the single-bit signatureanalyzer to form na embedded single-bitsignature analyzer.(c) k-bit and 1-bit Embeded Signature AnalyzerFigure 2.7:^This figure shows the hardware costs to implement a(k^n — 1, n;1,1,..., k; 11, . . . ,1,) MS A scheme. (a) is the block diagram of a singlebit signature analyzer. (b) is the block diagram of a k-bit signature analyzer. (c) showshow to embed a single bit signature analyzer into a k-bit signature analyzer. DFF is aD flip-flop.Chapter 2. Multiple Signature Fault Coverage Loss Model^ 32=^2-ki= 2- i= 1,2,...,n.^(2.35)By Eqn. 2.34 and 2.35, we have:FCL =^C^ (2.36)i=1Since ki > 1 for j = 1,^, n,1=7n — i + 1. (2.37)The equality holds when ki = k14.1 =-^=^=Therefore,ti , 2- Ein=k3 < = 2, ... , n.^(2.38)(2.39)Since ci > 0,citi < ci2-(91-7+1),i = 9,3,^, n.Therefore,FCL = F12-ki F12-ki^ (2.40)Equality holds when k2 =^= k„ = 1.Since k1 k2^k, FCL^citi is maximized when k1 = k — n 1,k2 =^= kn = 1. 0Theorem 4 states that if k bits of signature are to be distributed among n signatures,then the worst choice of distributions is where the first signature is of size k — n + 1 andthe remaining n — 1 signatures are of size 1. This would yield minimal expected faultcoverage.Chapter 2. Multiple Signature Fault Coverage Loss Model^ 33CircuitNameCircuitFunctionTotalGatesInputsLinesOutputFaultsStuck-atFaultsc432 Priority Decoder 160(18 EXOR) 36 7 864c499 ECAT 202(104 EXOR) 41 32 998c880 ALU and Control 383 60 26 1760c1355 ECAT 546 41 32 2710c1908 ECAT 880 33 25 3168c2670 ALU and Control 1193 233 140 4448c3540 ALU and Control 1669 50 22 6188c5315 ALU and Selector 2307 178 123 9400c6288 16-bit Multiplier 2406 32 32 12576c7552 ALU and Control 3512 207 108 13048Table 2.5: ISCAS'85 Benchmark Circuit Characteristics2.5 Experimental ResultsMost of the fault simulators that have been implemented use the stuck-at fault model[55] [35] [36]. In the experiments presented here, we only consider single stuck-at faultsas well. A single stuck-at fault assumes a circuit failure corresponding to one line of thecircuit being permanently fixed at the logic value 0 or 1. A circuit with p lines thus has2p possible single stuck-at faults. In our experiments, no fault collapsing [6] is done.2.5.1 ISCAS'85 Benchmark CircuitsThe combinational circuits used in our experiments are from the ISCAS'85 benchmarkcircuits [7]. The characteristics of the ten benchmark circuits are given in Table 2.5.The stuck-at faults in the last column of Table 2.5 is the complete set of single stuck-atfaults in the circuit. No equivalent fault collapsing is done. Circuit c499 and c1355 arefunctionally equivalent. c499 uses XOR gates. while c1355 uses 4-NAND gates to realizedthe XOR function.Chapter 2. Multiple Signature Fault Coverage Loss Model^ 342.5.2 Experimental CasesIn this section, fourteen experiment cases are defined. Experiments on the fourteenexperiment cases were conducted and the results are reported in Sec. 2.5.3. The fourteenexperimental cases are:1. (16,16; 1,^, 1; 2048) MSA2. (16,8; 2,... , 2; 2048) MSA3. (16,4; 4,... ,4;2048) MSA4. (16,2; 8,8; 2048) MSA5. (16,8; 1,^, 1, 9; 2048) MSA6. (16,4; 1,1, 1, 13;2048) MSA7. (16,2; 1,15; 2048) MSA8. (16, 8; 9, 1,^, 1; 2048) MSA9. (16,4; 13,1, ... , 1; 2048) MSA10. (16,2; 15, 1; 2048) MSA11. (16, 16; 1,^, 1; 2048; 0) MSA12. (16,8; 2, ... , 2; 2048; 0) MSA13. (16, 4; 4, ... , 4; 2048; 0) NISA14. (16,2; 8,8; 2048; 0) MSAChapter 2. Multiple Signature Fault Coverage Loss Model^ 352.5.3 ResultsIn this section, the experimental results on the ten ISCAS'85 benchmark circuits for thefourteen experimental cases are presented. The experimental results are listed in Tables2.6 - 2.9, Tables 2.10 - 2.12 and Tables 2.13- 2.16. The definitions of the symbols usedin those tables are as follows:• FCsinip denotes the fault coverage predicted by the simplified fault coverage modelfor (k,n; ki,^, kn; 1) MSA.• FCblia84 denotes the fault coverage predicted by the model presented in [5] for(k, n;^, kn; 1) MSA.• FCrns denotes the exact fault coverage determined by fault simulation for (k, n;. . kn; 1) MSA.• FC,isik denotes the exact fault coverage determined by fault simulation for(k, n; 1, . , k — n + 1;1) MSA.• FCmski denotes the exact fault coverage determined by fault simulation for(k, n; k — n + 1,1, ... , 1; 1) MSA.• FC,7,301 denotes the exact fault coverage determined by fault simulation for(k, n;^kn; 1; 0; aliasing) MSA.• FC,,„2 denotes the exact fault coverage determined by fault simulation for(k,n;^kri; 1; 0; no aliasing) NISA.• FC„ denotes the fault coverage obtained by fault simulation for (16,1; 16; 0 SSA.• FC„ denotes the exact fault coverage before compaction.Chapter 2. Multiple Signature Fault Coverage Loss Model^ 36• Errsimp is the absolute value of the difference between FCsimp and FC,,,, i.e.,Errsimp =1 ECsimp — FCms• Errbha84 is the absolute value of the difference between FC bha84 and FCms, i.e.,Errbha84^FCbha84 — FC,,„• AveErrsimp is the average of Errsimp over the ten benchmark circuits.• AveErrbha84 is the average of Errbhu84 over the ten benchmark circuits.All the fault coverages obtained by fault simulation reported in this chapter are theaverage of three trials. In the figures presented in this chapter, wherever it is appropriate,cl denotes c432, c2 denotes c499, e3 denotes c880, c4 denotes c1355, c5 denotes c1908,c6 denotes c2670, c7 denotes c3540, c8 denotes c5315, c9 denotes c6288, and c10 denotesc7552.Table 2.6 reports the fault coverage predicted by various models as well as the faultcoverage obtained by fault simulation for case 1. Table 2.7 presents the experimentalresults for case 2, Table 2.8 for case 3, and Table 2.9 for case 4.From the Errsimp and Errbha84 columns of Tables 2.6-2.9, the average difference betweenErrsim,p and Errbh„84 is 0.0684% for (16.16; 1,^, 1; 2048) MSA, the average differencebetween Errsimp and Errbh„84 is 0.0469%, for (16,8; 2,^,2; 2048) MSA, the averagedifference between Err., mp and E7'rbh°84 is 0.0060%, for (16, 4; 4, ... , 4; 2048) MSA, theaverage difference between Errsimp and Errbh,84 is 0.0013%, for (16, 2; 8, 8; 2048) MSA.Although for small circuits, the difference is not significant, for large circuits, e.g., circuitswhich have stuck-at faults over 10, 000, the difference can be significant. Figs. 2.13-2.14present Errsimp and Errbh,84 for the ten benchmark circuits graphically. Also note thatas n increases, the model presented here gives better prediction than that model in [5].Chapter 2. Multiple Signature Fault Coverage Loss Model^ 37Table 2.10 presents the experimental results for case 5 and 8. Table 2.11 reports theexperimental results for case 6 and 9. Table 2.12 gives the experimental results for case7 and 10. Tables 2.13-2.16 report the experimental results for case 11, 12, 13 and 14,respectively.Comparing the fault coverage reported in FC, columns in Tables 2.6-2.9, FCniskicolumns in Tables 2.10-2.12, FC771301 and FCr1302 columns in Tables 2.13-2.16 with thefault coverages reported in FC„ column in Table 2.6, we Can see that the fault coveragefor (k, n; k1,... , kri; 1) MSA is less than that for (k, 1; k; 1) SSA, which supports the claimin Theorem 2.Comparing the fault coverages in FC mslk column in Tables 2.10-2.12 with that in FC,.„,,column in Tables 2.6-2.9, FC„„ki column in Tables 2.10-2.12, FC,,,,„1 and FC,,.9,2 columnsin Tables 2.13-2.16, we can see that the fault. coverage of (k, n; 1, . . . , 1, k — n 1; 1) MSAare better than that obtained by other various MSA, which supports the claim in Theo-rem 3.Comparing the fault coverages in FC„,ski column in Tables 2.10-2.12 with that in FC„„column in Tables 2.6-2.9, FC,sik column in Tables 2.10-2.12, FC„,„1 and FC„,,„2 columnsin Tables 2.13-2.16, we can see that the fault coverage of (k, n; k — n + 1,1, . . . ;1) MSAare less than that obtained by other various MSA, which supports the claim in Theorem4.Comparing the fault coverages in the FC1301 columns in Tables 2.13-2.16 with that inthe FC„,s02 columns in Tables 2.13-2.16, and the FC,,,,s columns in Tables 2.6-2.9, wecan see that the fault coverage for a MSA is the function of signature scheduling.Figs. 2.15 and 2.16 presents FC„, and FC„ for the four experimental cases. From thefigures we can see that given k, in 24 out of 40 trials, FC„is is less than FC„. In 5 outChapter 2. Multiple Signature Fault Coverage Loss Model^ 38CircuitNameFCsimp(%)FCblia84(%)FC,,,,(%)FC88(%)FCnc(%)Errsimp(%)Errblza84(%)c432 98.8409 98.8411 98.6111 98.8426 98.8426 0.2298 0.2300c499 99.1958 99.1969 96.3929 99.1984 99.1984 2.8029 2.8040c880 97.3353 97.5932 97.3864 97.5947 97.5947 0.0511 0.2068c1355 99.3515 99.3958 97.8844 99.3973 99.3973 1.4671 1.5114c1908 98.1052 98.4413 95.9701 98.4007 98.4428 2.1351 2.4712c2670 82.2073 82.2079 81.3699 82.2092 82.2092 0.8374 0.8380c3540 94.8512 94.9458 94.3816 94.9095 94.9472 0.4696 0.5642c5315 99.2545 99.2645 99.1986 99.2660 99.2660 0.0559 0.0659c6288 99.4578 99.4578 99.4407 99.4593 99.4593 0.0171 0.0171c7552 93.0237 93.0653 92.8342 93.0667 93.0667 0.1895 0.2311AveErr mp = 0 8256%,^AveErrbha84 = 0.8940%Table 2.6: Fault Coverages for (16, 16; 1,^, 1; 2048) MSACircuitNameFCsim,(%)FCblza84(%)FCms(%)FCss(%)FCric(%)Errsimp(%)Errbham(%)c432 98.8410 98.8411 98.8040 98.8426 98.8426 0.0370 0.0371c499 99.1963 99.1969 99.0648 99.1984 99.1984 0.1315 0.1321c880 97.4635 97.5932 97.3863 97.5947 97.5947 0.0772 0.2069c1355 99.3540 99.3958 99.1882 99.3973 99.3973 0.1658 0.2076c1908 98.2257 98.4413 97.7378 98.4007 98.4428 0.4879 0.7035c2670 82.2074 82.2079 82.0669 82.2092 82.2092 0.1405 0.1410c3540 94.8831 94.9458 91.5697 94.9095 94.9472 3.3134 3.3761c5315 99.2581 99.2645 99.2660 99.2660 99.2660 0.0079 0.0015c6288 99.4578 99.4578 99.4566 99.4593 99.4593 0.0012 0.0012c7552 93.0414 93.0653 93.0257 93.0667 93.0667 0.0157 0.0396AveErrsimp = 0 4378%,^AveErrbh.84 = 0.4847%Table 2.7: Fault Coverages for (16.8; 2,^, 2; 2048) MSAChapter 2. Multiple Signature Fault Coverage Loss Model^ 39CircuitNameFCsini,p(%)FCbha84(%)FCrris(%)FCss(%)FC'n,(%)Errsimp(%)Errbha84(%)c432 98.8411 98.8411 98.8426 98.8426 98.8426 0.0015 0.0015c499 99.1965 99.1969 99.1984 99.1984 99.1984 0.0019 0.0015c880 97.5528 97.5932 97.5947 97.5947 97.5947 0.0419 0.0015c1355 99.3716 99.3958 99.3973 99.3973 99.3973 0.0257 0.0015c1908 98.3199 98.4413 98.3270 98.4007 98.4428 0.0071 0.1142c2670 82.2078 82.2079 82.1493 82.2092 82.2092 0.0585 0.0586c3540 94.9170 94.9458 93.9190 94.9095 94.9472 0.9980 1.0268c5315 99.2610 99.2645 99.2553 99.2660 99.2660 0.0057 0.0092c6288 99.4578 99.4578 99.4593 99.4593 99.4593 0.0015 0.0015c7552 93.0568 93.0653 93.0667 93.0667 93.0667 0.0099 0.0014AveErrsimp = 0 1152%,^AceE 'rbha84 ,--- 0.1218%Table 2.8: Fault Coverages for (16, 4; 4,^, 4; 2048) MSACircuitNameFCsimp(%)FCbha84(%)FC,,,s(%)FCss(%)FCric(%)Errsimp(%)Errbha84(%)c432 98.8411 98.8411 98.8426 98.8426 98.8426 0.0015 0.0015c499 99.1969 99.1969 99.1984 99.1984 99.1984 0.0015 0.0015c880 97.5898 97.5932 97.5947 97.5947 97.5947 0.0049 0.0015c1355 99.3903 99.3958 99.3973 99.3973 99.3973 0.0070 0.0015c1908 98.4240 98.4413 98.2744 98.4007 98.4428 0.1496 0.1669c2670 82.2079 82.2079 82.2092 82.2092 82.2092 0.0013 0.0013c3540 94.9402 94.9458 94.9095 94.9095 94.9472 0.0307 0.0363c5315 99.2637 99.2645 99.2589 99.2660 99.2660 0.0048 0.0056c6288 99.4578 99.4578 99.4593 99.4593 99.4593 0.0015 0.0015c7552 93.0639 93.0653 93.0667 93.0667 93.0667 0.0028 0.0014AveErrsimp = 0 0206%,^AvcErrbha84 = 0.0219%Table 2.9: Fault Coverages for (16, 2; 8, 8; 2048) MSAChapter 2. Multiple Signature Fault Coverage Loss Model^ 40CircuitNameFCrnslk(%)FCmskl(%)432 98.8426 97.8781499 99.1984 97.5284880 97.5947 96.66671355 99.3973 98.43791908 98.4007 96.91712670 82.2092 81.42993540 94.9095 94.38705315 99.2660 99.04616288 99.4593 99.23937552 93.0667 92.7039Table 2.10: Fault Coverage Comparison for (16,8; 1,^, 1, 9; 2048) MSA and (16,8; 9,1,, 1; 2048) MSACircuitNameF Critslk(%)F C rnskl(%)432 98.8426 95.5633499 99.1984 95.5244880 97.5947 94.16671355 99.3973 96.12551908 98.4007 94.70752670 82.2092 78.62713540 94.9095 91.82295315 99.2660 96.34046288 99.4593 96.19657552 93.0667 89.9908Table 2.11: Fault Coverage Comparison for (16, 4; 1. 1, 1,13; 2048) MSA, and (16,4; 13,1, 1, 1; 2048) MSAChapter 2. Multiple Signature Fault Coverage Loss Model^ 41CircuitNameFCmsik(%)FCrnskl(%)432 98.8426 88.3102499 99.1984 86.5063880 97.5947 85.13261355 99.3973 87.67531908 98.4007 85.33252670 82.2092 70.91583540 94.9095 82.96175315 99.2660 86.78376288 99.4593 86.68367552 93.0667 81.3381Table 2.12: Fault Coverage Comparison for (16, 2;1,15; 2048) MSA and (16, 2; 15, 1;2048) MSACircuitNameFCmsoi(%)FCm802(%)432 n/a n a499 96.2926 96.4262880 96.4015 96.59091355 97.2448 97.83521908 95.6860 95.98062670 80.8603 80.88283540 93.6813 94.37625315 98.7624 99.06746288 n/a n/a7552 92.7601 92.7958Table 2.13: Fault Coverages for (16,16;1,... , 1;2048;0; aliasing) MSA and (16,16;1,...,1;2048;0; no aliasing) MSA. For c432 and c6288, no optimal schedulings are availablefor n = 16 and 1 = 2048. This will be dicussed in chapter 3.Chapter 2. Multiple Signature Fault Coverage Loss Model^ 42Circuit FCrnsoi FCmso2Name (%) (%)432 98.6497 98.6883499 98.4302 98.4302880 96.9129 96.98861355 98.8315 99.06521908 97.0749 97.44322670 81.9169 82.00693540 91.4135 90.58395315 98.6809 99.07806288 n/a n/a7552 92.8316 92.8904Table 2.14: Fault Coverages for (16,8; 2,^, 2;2048; 0; aliasing) MSA and (16,8; 2, ..., 2; 2048; 0; no aliasing) MSA. For 6288, no optimal schedulings are available for n = 8and 1 = 2048. This will be discussed in chapter 3.CircuitNameFCrnsol(%)FC„so2(%)432 98.7269 98.7269499 98.9980 99.1984880 97.5379 97.53791355 98.8684 98.92991908 98.3376 98.33762670 82.1193 82.11933540 92.9379 92.93795315 98.8759 98.95756288 99.4063 99.43287552 92.8520 92.9542Table 2.15: Fault Coverages for (16,4:4.-1. 4.4:2048: 0; aliasing) MSA and (16,4;4,44,4;2048; 0; no aliasing) MSAChapter 2. Multiple Signature Fault Coverage Loss Model^ 43Figure^2.8:^Fault^Coverage^Comparison^for^(16,8; 1,^, 1,9; 2048),(16, 8; 9, 1, . , 1; 2048), and (16, 8; 2,^, 2; 2048) MSA(i)95+ n=4 and k=16; k1=...=k3=1 and k4=13* n=4 and k=16; k1=13, k2=...=k4=1o n=4 and k=16; k1=...=k4=48580Chapter 2. Multiple Signature Fault Coverage Loss Model^ 44c 1^c2^c3^c4^c5^c6^c7^c8^c9^c10ISCAS45 Benchmark CircuitsFigure 2.9: Fault Coverage Comparison for (16,4; 1, 1, 1, 13; 2048), (16, 4; 13, 1, 1, 1; 2048),and (16, 4; 4, .. . , 4; 2048) MSAChapter 2. Multiple Signature Fault Coverage Loss Model^ 45Figure 2.10: Fault Coverage Comparison for (16,2; 1, 15; 2048), (16,2; 15, 1; 2048), and(16,2; 8,... ,8;2048) MSAChapter 2. Multiple Signature Fault Coverage Loss Model^ 46CircuitNameFCrnsol(%)FCm802(%)432 98.7655 98.7655499 99.1650 99.1650880 97.4432 97.44321355 98.3850 98.38501908 98.0430 98.04302670 82.0444 82.04443540 94.6563 94.65635315 98.9397 98.93976288 99.2896 99.28967552 92.7575 92.7575Table 2.16: Fault Coverages for (16,2;8,8;2048; 0; aliasing) MSA and (16,2;8,8;2048;0;no aliasing) MSAof 40 trials, FCms is the same as FC,. In 11 out of the 40 trials, FCms is greater thanFC„. When n is large, FCms has a better chance to be less than FCss•Fig. 2.17 presents the FC,, for the four experimental cases. From Fig. 2.17, we can seethat when n = 16 and n = 8, FC,„ for 71 = 16 is less than that for n = 8 for 9 out of theten circuits, i.e., except for circuit c3540. FC,„ for n = 4 is very close to that for n = 2.2.5.4 Fault Coverage Loss Model AccuracyThe fault coverage loss model for a MSA scheme presented in Sec. 2.3 is:FCL =FCLE(Fi — Fi-011Pj= E(Fi —^H2-ki•— F71-1)9—(kn—l+k")^(F"— Fn_2)9—(k11-2+kn-1+kn)Chapter 2. Multiple Signature Fault Coverage Loss Model^ 47(F2 - F1)2_ 2+..+k) F19-k. (2.41)As we can see from Eqn. 2.41, if F1 = F2 = • • = Fn, then FCL = F7,2-k, whichis the model presented in [5]. In other words, the FCL model presented in Sec. 2.3 issensitive to the fault coverage before compaction for the CUT, but the model presentedin [5] is not. Given a signature scheduling, when the fault coverage before compaction forthe CUT increases slowly, the FCL model gives a better prediction. Given a signaturescheduling, when the fault coverage before compaction for the CUT increases rapidly,the FCL model and the model presented in [5] give similar predictions.Test Length (1/32)Figure 2.11: Fault Coverage Before Compaction for c432, c499, c880, c1355, and c1908Chapter 2. Multiple Signature Fault Coverage Loss Model^ 48Test Length (1/32)Figure 2.12: Fault Coverage Before Compaction for c2670, c3540, c5315, c6288 and c7552Chapter 2. Multiple Signature Fault Coverage Loss Model^ 49Figures 2.11 and 2.12 give the fault coverage before compaction for the ten ISCAS'85benchmark circuits. As we can observe from the figures, the fault coverage before com-paction for circuits c880, c1908 and c1355 increase relatively slowly. The fault coveragebefore compaction for circuit c6288 increases most rapidly among the ten circuits. FromTable 2.6, the Errsimp's for c880, c1908, and c3540 are 0.0511%, 2.1351% and 0.4696%,respectively, while the Errbh„84's for the three circuits are 0.2065%, 2.4291% and 0.5642%,respectively. The differences between Errsimp and Errbh,84 for these three circuits aresignificant comparing to the differences for other circuits. From Table 2.7, similar con-clusion can be drawn. Since the fault coverage before compaction for c6288 increasesmost rapidly among the ten circuits, from Tables 2.6-2.9 we can see that the Errsimp andErrbh„84 are the same for all the four cases.Chapter 2. Multiple Signature Fault Coverage Loss Model^ 50Figure 2.13: Fault Coverage Errors for (a) (16, 16; 1, ... 1; 2048) MSA; (b) (16,8; 2, ... , 2;2048) MSA* Simp Modelo Bha84 Modelc4^c5^c6^c7(c) n=4 and k=16; k1=...=k4=4p0.8g0.6cl) 0.40.= 0.2asu_Fc10i.;;:■ 0.2LI-10.15a)as 0.10 0.05u_c16c2^c3^c4^c5^c6^c7(d) n=2 and k=16; k1 =k2=8* Simp Modelo Bha84 Modeloa • IISc10c8 c9Chapter 2. Multiple Signature Fault Coverage Loss Model^ 51Figure 2.14:^Fault Coverage Errors for (c) (16, 4; 4,^, 4; 2048) MSA; (d)(16, 2; 8, 8; 2048) MSAQ.) 95085100m^a, 95_C3)>.°) 900▪ 85as* n=16 and k=16; k1=...=k16=1o n=1 and k=16; k1=k=16Chapter 2. Multiple Signature Fault Coverage Loss Model^ 52O* n=16 and k=16; k1=...=k16=1o n=1 and k=16; k1=k=1680c1^c2^c3^c4^c5^c6^c7^c8(a) <n=16 and k=16> vs. <n=1 and k=16>80c1^c2^c3^c4^c5^c6^c7^c8^C9^c10(b) <n=8 and k=16> vs. <n=1 and k=16>Figure 2.15: Fault Coverage Comparison for MSA and SSA: (a) (16,16;1,... ,1;2048)MSA and (16,1;16;2048) SSA; (b) (16.8: 2 ,^ 9' 2048) MSA and (16,1;16; 2048) SSA C9 c10Chapter 2. Multiple Signature Fault Coverage Loss Model^ 53100m• • •G, 95 * n=4 and k=16; k1 =...=k4=4o n=1 and k=16; k1=1600=▪ 85as80c1^c2^c3^c4^c5^c6^c7^c8^c9^c10(c) <n=4 and k=16> vs. <n=1 and k=16>* n=2 and k=16; k1 =k2=8o n=1 and k=16; ki =16080c1^c2^c3^c4^c5^c6^c7^c8^c9^c10(d) <n=2 and k=16> vs. <n=1 and k=16>Figure 2.16: Fault Coverage Comparison for MSA and SSA: (a) (16,4;4,...,4;2048)MSA and (16,1;16;2048) SSA; (b) (16.2;8,8;2048) MSA and (16,1;16;2048) SSAChapter 2. Multiple Signature Fault Coverage Loss Model^ 54100989694 + n=16 and k=16; k1=...=k16=1* n=8 and k=16; k1=...=k8=2o n=4 and k=16; k1=...=k4=4x n=2 and k=16; k1=k2=886848280c1^c2^c3^c4^c5^c6^c7^C8^C9^c10ISCAS85 Benchmark CircuitsFigure 2.17: Fault Coverage Comparison for Different nChapter 2. Multiple Signature Fault Coverage Loss Model^ 552.6 ConclusionsA prediction model for fault coverage of multiple signature schemes has been presentedin this chapter. From the model and the experimental results presented in this chapter,the following conclusions can be drawn:• The fault coverage for multiple signature analysis based schemes is a function ofboth signature scheduling and signature size associated with each signature ana-lyzer. Hence, when designing a IVISA BIST scheme, the signature scheduling andsignature sizes need to be considered.• When the fault coverage before compaction for the CUT increases slowly, the modelpresented in this chapter gives better fault coverage loss prediction than the modelpresented in [5]. When the fault coverage before compaction for the CUT increasesrapidly, the model presented in this chapter gives similar prediction as the modelin [5].• When the total number of signature bits are fixed, on average the fault coverageloss increases with the number of signatures.• When both the total number of signature bits and the number of signatures arefixed, the partition of D(1, 1, ... 1, k — n + 1) yields the smallest total aliasing.• When the total number of signature bits is fixed, taking a single signature at theend of the test on average gives the best fault coverage.Chapter 3Multiple Signature Fault Simulation Time ModelThe complexity of fault simulation in terms of the CPU time and the memory require-ments is known to grow at least as the square of the number of gates in the circuit [29].For VLSI circuits this may be a serious limitation. However, research has been done onmethods of reducing fault simulation time [2][28][54]. Circuit structure oriented methodstake advantage of the characteristics of circuit structure to improve fault simulation time[41] [36]. On the other hand, modeling-oriented methods use a fault simulation timemodel dependent on the nature of the fault simulator, and apply an optimal algorithmto reduce fault simulation time [31][33]. In [31] such a fault simulation time model waspresented. The fault simulation time model was used in a recursive relationship to de-termine the optimal schedulings for MSA schemes. However, the fault simulation timemodel in [31] did not take abasing into account. In this chapter, we present a faultsimulation time model for MSA schemes which takes abasing into account. With thepresented fault simulation time model, the relationship between optimal scheduling andaliasing for MSA schemes can be discussed.3.1 Preliminaries and DefinitionsIn this section, we introduce some definitions and briefly review some of the resultspresented in [31].56Chapter 3. Multiple Signature Fault Simulation Time Model^ 573.1.1 Basic DefinitionsDefinition 1: The detection constant T is the average simulation time per pattern andper fault for a given fault simulation algorithm.Definition 2: Full fault simulation Tf„ii is the process of fault simulation without faultdropping, i.e., a fault is dropped from further consideration as soon as it is detected bythe fault simulator.The full fault simulation time, Tfull, is:Tfuti = UT,^ (3.42)where 1 is the total number of test patterns applied to the CUT and f is the number offaults simulated.Definition 3: No compaction fault simulation To is the fault simulation process withoutcompaction but with fault dropping.Definition 4: The first detection constant rd. is the average fault simulation time perpattern to simulate one fault until it is detected for the first time.The no compaction fault simulation time To is given byTo^rd^[1 — F(. )1dx^ (3.43)Jo Fwhere F(x) denotes the fault coverage obtained after x patterns have been applied tothe CUT, and Td is the average time per pattern to simulate one fault until it is firstdetected.Chapter 3. Multiple Signature Fault Simulation Time Model^ 58Definition 5: Multiple signature compaction fault simulation is the fault simulationprocess with multiple signature compaction and fault dropping.The multiple signature compaction fault. simulation time, T , is:7,1 (1 - F(0) (1i+1 - li)^(3.44)i=0n-1^= TdRin^— E F(ii)( ^-^Td[l —^F(ii)(41 —where 11,12,^, in are check points. Obviously, in equals 1 since the last signature ischecked at the end of the test.3.2 Time ModelThe fault simulation time model is a function of the fault simulation process. Differentfault simulation schemes will yield different fault simulation time models. The faultsimulation process used in this section is parallel pattern single fault propagation(PPSFP)[55J[54].3.2.1 Fault Simulation Time Model for Multiple Signature AnalysisGiven a (k,n; kl, . , kn;^,in) MSA scheme. assume that the corresponding aliasingprobabilities for each signature analyzer are pi, p2,^, pn, respectively, and that thecorresponding fault coverage before data compaction is known to be F1, F2,..., Fn at thecheck points. Let the total number of faults of interest be f. Initially, there are f faultsto be simulated during the segment [10, /1]. Hence, the fault simulation time FST duringthe segment [lo, id is:(3.45)Chapter 3. Multiple Signature Fault Simulation Time Model^ 59where /0 = 0, 11 corresponds to the first check point.Since a signature of length k1 is taken at check point 11, f(Fi. — FCL1) faults will havebeen detected after the first signature is checked at check point 11, by Eqn. 2.17. Thatis, f (Fi — FC Li) faults will be dropped after the first signature is checked at check point11, and f(1 — FC Li) remaining faults will be simulated during the segment /2].Therefore, the fault simulation time for the segment Eli, /2] is:FST2 = fr(12 - 11)(1 - F1 + FCL1).^(3.46)Similarly,^— FCLi_i faults will be detected after the (i _ i\th) signature is checked.Only f(1 — FC L _1) faults need to be simulated during segment [4_1, lib and thefault simulation time for the segment [li_1, 4] isFSTi^fr(li —^— Fi_1+ FCLi),^i^1,2,...^(3.47)The total fault simulation time, FST, needed after n signatures have been checked at11,12,^, 4, check points is:FST^FSTi-1fr{/9, —^(41 — /i)Fi^(41 — /i)FCLil.^(3.48)i=1The first component in Eqn. 3.48 represents the fault simulation time needed if only onesignature was checked at the end of the test. The second component represents the faultsimulation time saving due to the fact that multiple signatures are checked and hencepartial fault dropping can be performed. The last component represents the impact ofaliasing due to multiple signature analysis.Eqn. 3.48 predicts fault simulation time with multiple signature analysis. The modelis based only on fault coverage before compaction and the aliasing characteristics of thesignature analyzers used.n-= -i= 1n-- li)Fi^(li+1 — li)FCLi.^(3.49)=1+Chapter 3. Multiple Signature Fault Simulation Time Model^ 603.2.2 Normalized Fault Simulation Time ModelIn Sec. 3.2.1, a fault simulation time model is given. The total number of faults in thefault set, f, and the average simulation time per fault and per pattern required until afault is first detected, r, are used as parameters of the model.Definition 6: The normalized fault simulation time is the ratio of the fault simulationtime to the product of the number of faults in the fault set f and the detection constantr.By Eqn. 3.48, the normalized fault simulation time ,lst, is:F STi fTf stSubstituting Eqn. 2.17 into Eqn. 3.49, we haven-1^ n-1fst =1, —^- oFi +^-^(F.; - Fj_1) JJ Pk.^(3.50)i=1 i=1 k=jThe normalized fault simulation model from Eqn. 3.50 predicts the fault simulation timewith multiple signature analysis, given the fault coverage at the check points before datacompaction and the aliasing characteristics of the signature analyzers. In Sec. 3.2.3,experimental results to justify this fault. simulation model are presented.3.2.3 Justification of the Normalized Fault Simulation ModelIn Sec. 3.2.2, a normalized fault simulation time model is given. Here, the concept offault simulation time ratio is introduced to validate the normalized fault simulation timemodel.Chapter 3. Multiple Signature Fault Simulation Time Model^ 61Definition 7: Fault simulation time ratio FSTratio is the ratio of the FST for a(k, n;^. • , km;^• • • , l) MSA scheme to the FST for a (k, no;^• • • , /ono;^• • • ,lno)MSA. no can be arbitrarily chosen as long as no < k. Note that once we have selected no,the FST for (k, no; k1,. . • , kno;11, • • • MSA becomes the standard, FST's for otherMSA schemes should compare with it.FSTrajjo can be used as a measure of the accuracy of the fault simulation time model.By defining FSTratio, we can avoid the problem of determining the detection constant Tas well.Tables 3.17 and 3.18 report FSTrajo's calculated from the normalized fault simulationtime model presented in Eqn. 3.48 and FSTratio's calculated from the exact fault sim-ulations. We chose the FST for k = 16 and no = 16 as the denominator of FSTraiio.The ratios are calculated for the n 16. 71 = 8, n. = 4, and n = 2 cases. The "Pre-diction" columns report the FST„tio's calculated from the normalized fault simulationtime mode, while the "Actual" columns report the FSTratio's calculated from the exactfault simulation. From the results presented in Tables 3.17 and 3.18 we can see that thenormalized fault simulation time model in Eqn. 3.48 gives a relatively good predictionof fault simulation time ratios.3.3 Equidistant Scheduling & Even Partitioning MSAOne possible way to schedule a IVISA scheme is to separate the check points evenly. Thisis called equidistant scheduling. Meanwhile, the easist signature bit partition is evenpartitioning. This is called even partitioning. One of the advantages of an equidistantscheduling and even partitioning MSA is its associated implementation simplicity. Wediscuss the fault simulation time for a special case of equidistant scheduling and equalpartitioning.Chapter 3. Multiple Signature Fault Simulation Time Model^ 62Circuit n Prediction Actualc432 16 1.0000 1.00008 1.2655 1.13154 1.9425 1.78952 3.5635 3.3475c499 16 1.0000 1.00008 1.2195 1.06894 1.7877 1.53542 3.2193 2.8128c880 16 1.0000 1.00008 1.2535 1.21081.8849 1.87302 3.3919 3.4172c1355 16 1.0000 1.00008 1.2389 1.12214 1.8459 1.67922 3.2975 3.0148c1908 16 1.0000 1.00008 1.1625 1.07864 1.5996 1.47152 2.6802 2.5018Table 3.17: This table lists the fault simulation time ratios for n = 16, n = 8, n = 4, andn = 2. The preselected case is no = 16. The results are for the 5 ISCAS'85 benchmarkcircuits c432, c499, c880, c1355, c1908. The third column is the fault simulation timeratio calculated from the normalized fault simulation time model in Eqn. 3.48, and thelast column is the fault simulation time ratio calculated from the fault simulation results.All the results are averages of three trials.Chapter 3. Multiple Signature Fault Simulation Time Model^ 63Circuit n Prediction Actualc2670 16 1.0000 1.00008 1.1650 1.04824 1.3712 1.31202 2.0143 1.9296c3540 16 1.0000 1.00008 1.1159 1.24414 1.4440 1.49412 2.2915 2.2890c5315 16 1.0000 1.00008 1.2428 1.01584 1.8776 1.38053.4028 2.4750c6288 16 1.0000 1.00008 1.2548 1.04294 1.9713 1.60132 3.6630 2.9930c7552 16 1.0000 1.00001.1912 1.18464 1.6607 1.65662 2.7789 2.7791Table 3.18: This table lists the fault simulation time ratios for n = 16, n = 8, n = 4, andn = 2. The preselected case is n o = 16. The results are for the 5 ISCAS'85 benchmarkcircuits c2670, c3540, c5315, c6288, c7552. The third column is the fault simulation timeratio calculated from the normalized fault simulation time model in Eqn. 3.48, and thelast column is the fault simulation time ratio calculated from the fault simulation results.All the results are averages of three trials.Chapter 3. Multiple Signature Fault Simulation Time Model^ 64Definition 8: Dual even MSA is a equidistant scheduling and even partitioning multiplesignature analysis scheme.3.3.1 Number of Signatures vs. Fault Simulation TimeAssume that n signatures are checked, that the total number of signature bits is k, andthat 1 test patterns are applied to the CUT. For dual even signature analysis, n signaturesof length are checked at i, = 1,2, ... , n.Example 1: Assume that the total number of signature bits k = 16 and that thetest length 1 = 2048. There are four possible dual even multiple signature analysiscombinations:• n = 16, ki^k2^= ki6 = 1. /1 = 128, /2 = 256,^,^= 1920,46 = 2048;• n = 8, k1 = k2 = . = ks = 2. 11 = 256, 12 = 512,...,l7 = 1792, 18 = 2048;• n = 4, k1^k2= k3= k4 = 4. 14 = 512, 12 = 1024, 13 = 1536, 14 = 2048;• n = 2, lc]. = k2 = 8. /1 = 1024, 12 = 2048.Let FST(n,k,l) denote the fault simulation time for the case where dual even multiplesignatures are used with n signatures, k signature bits, and test length 1. Table 3.19 liststhe experimental results of fault simulation time for the above four dual even multiplesignature cases. The experiments were conducted on the ISCAS'85 benchmark circuits.The results are averages of three trials. From the results of Table 3.19, we can see thatFST(16, 16, 2048) < FST(8,16, 2048) < FST(4, 20.48) < FST(2, 2048).Chapter 3. Multiple Signature Fault Simulation Time Model^ 65Circuits n F ST(n, k, 1)(sec) Circuits n FST(n, k, 1)(sec)c432 16 n/a c2670 16 6818 12 8 7254 19 4 9152 36 9 1367c499 16 21 c3540 16 7788 23 8 10304 35 4 12762 65 2 2056c880 16 48 c5315 16 16268 58 8 19834 85 4 30262 155 9 5624c1355 16 103 c6288 16 n/a8 116 8 n/a4 173 4 43082 311 2 7934c1908 16 180 c7552 16 37548 195 8 44484 264 4 62202 449 2 10434Table 3.19: Fault simulation time for four dual even multiple signature analysis cases.The total number of signature bits k = 16, test length 1 = 2048. Fault simulation timeis in cpu seconds on a SPARC 2 workstation.Chapter 3. Multiple Signature Fault Simulation Time Model^ 663.4 Optimal Scheduling of Multiple Signature AnalysisIn [31], a backward dynamic programming based recursive relationship for fault simu-lation time prediction is presented. It is used to determine the optimal scheduling ofsignatures. In this section, a similar dynamic programming based recursive relationshipfor fault simulation time is presented. Unlike [31], it takes into account the effect ofaliasing by using a forward, instead of backward, dynamic programming based recursiverelationship.3.4.1 Recursive RelationshipWe now present a recursive relationship to determine the optimal scheduling of j 1signatures based on the optimal scheduling of j signatures. The recursive relationship isderived via a dynamic programming approach [12].Assume that we have 1 test vectors labeled 1, 2, ... , /. We need to find the minimalfault simulation time Topt[q, j 1] when j+ 1 signatures are optimally scheduled betweenvectors 1 and q, and the (j +1)th signature is scheduled at vector q. lithe jth signature isoptimally scheduled at vector Po, then Topt[q, j 1] is the summation of two terms. Thefirst term is the minimal fault simulation time Topt[po, j] when j signatures are optimallyscheduled between vectors 1 and po, and the jth signature is scheduled at vector po.The second term is the fault simulation time FST[po, q] to simulate 1 — F(p0) FC Lifaults between vectors Po and q without fault dropping. The possible scheduling for theith signature is at vectors j,j 1, ... — 1. The scheduling for ith signature whichyields the minimal value among Topt[j , j] F ST[j. q], T„t[j + 1,j] F ST[j + 1, q], . .Topt[q — 1,j] F ST[q — 1, q], is the optimal scheduling Po for the jth signature. Theminimal value is Tut [po, j] F ST[po, q], i.e., Topt[q, j + 1]. In summary:q -1Topt[q, j^1] = min{ Topt[p, j]^F ST[p, q]).p=3(3.51)Chapter 3. Multiple Signature Fault Simulation Time Model^ 67This recursive relationship is illustrated by Fig. 3.18 To use the above recursive relation-ship, we start with j = 1. • For j 1, Topt[q, 1] = FST[1,q], where 1 < q <1. The optimalscheduling is at vector q. To calculate FST[q, l] for 1 < q < 1, we need to perform Ifault simulations. For j 2, Topt[q, 2] is the minimal value of Topt[p, 1] F ST[p, q] for1 < p < q — 1, where 2 < q < l. The value of p which corresponds to the minimalsummation is the optimal scheduling for the first signature. The second signature isscheduled at q. To determine Topt[q, 2] for each q E [2,1], we need q —I fault simulations.Similarly, for j = 3, ... , n, we can determine Topt[q,i + 1] and the optimal scheduling forthe jth signature.The algorithm to calculate optimal scheduling is summarized as follows. Let Popt[q, j 1]denote the optimal scheduling for the jth signature between vectors 1 and q with the(j +1)th signature scheduled at vector q. The pseudo-code of the algorithm is presentedin Fig. 3.18.The computation complexity of the fin dopt algorithm is 0(7212), while the computation/complexity of an exhaustive algorithm would be^. When l >> n, the latterTi -would be 0(/(n-1))^0(/').3.4.2 Optimal Scheduling vs. AliasingIn the algorithm from [31], no aliasing effect was taken into account. In Sec. 3.4.1,we presented a forward dynamic programming based algorithm that considers aliasing.With the effect of aliasing, some of the optimal schedulings move towards the startingpoint of the test as shown in Fig. 3.20.To measure the movement quantitatively, we need to define a delta scheduling vector.Definition 9: The scheduling vector SV for a (k, n;^ MSA schemeTopt[q,1] = ST[1,q]Checkpoint1E•1■1 FST[p,q] Droptheront 1 Checkpoint 2DetectedF1Chapter 3. Multiple Signature Fault Simulation Time Model^ 68Test Patterns(a) Taking one signature at the end of test q. Theoptimal fault simulation time Topt[q,1] equalsthe fault simulation time for a single signaturetaken at the end of the test. q is in the range of[1, I], where 1 is the total test length.Test Patterns(b) Taking two signatures, one is taken between vector1 and q, the other is taken at the end of test q. Thep value which yields the shortest fault simulationtime is the optimal point for the first check point.The range of q is [2,1], since the first signatureshould be checked at least at vector 1..9,gE 8Figure 3.18: Optimal Scheduling of the First Signature of two signaturesChapter 3. Multiple Signature Fault Simulation Time Model^ 69findopt(Fi,n,k,I,FCLi).for(q=1 to 1) doT0pt[q,1] = FST[q,1];endforfor(j=1 to n-1) dofor(q=j-1-1 to 1) dotmpmin = 99999999; /* temporary storage */for(p,j to q-1) doTopt[q, 1 + 1] = Topt[p, j] + (1 — Fp + FCLi)(q — p);if(tmpmin > Topt[q,i 1]) thentrnp,,„r, = Topt[q,^1];Po = P;endifendforPopt[q,i + 1] = Po;Topt[q, j^1] = tmp„ii„;endforendforendfindoptFigure 3.19: Optimal Scheduling AlgorithmChapter 3. Multiple Signature Fault Simulation Time Model^ 70c1355 k=16 n=16 18161412108642o with aliasing* without aliasing500^1000^1500^2000Test VectorsFigure 3.20: This figure presents the movement of optimal scheduling positions whenaliasing is taken into account. The horizontal axis represents the test vectors. Thevertical axis represents the numbering of signatures, e.g., value i in the vertical axisrepresents the ith signature.Chapter 3. Multiple Signature Fault Simulation Time Model^ 71is the vector (4,12, , ln). The delta scheduling vector (5SV is the difference betweenthe SV for an optimal scheduled MSA SV with aliasing taken into account and theSV for an optimally scheduled MSA without aliasing taken into account. The optimalscheduling for a MSA is obtained using the algorithm shown in Figure 3.19.Tables 3.20 and 3.21 list the SV's with abasing for 1/ = 16, n = 8, n = 4, and n = 2. Thesignature partitioning is even signature partitioning and the total number of signaturebits is 16. Since we use a PPSFP fault simulator with 32 parallel patterns, the earliestscheduling of signatures is at test vector 32. From Tables 3.20 and 3.21, we can seethat the check points for the first signature is always at 32. The reason is that the firstsignature should be checked at a very early stage of the test so that a big portion ofmodeled faults can be dropped early. If we used a non-parallel pattern fault simulator,the first check point could be at a test vector earlier than 32. Some of the scheduling is notavailable for some circuits with n = 16 and/or n = 8. This is due to the constraint we putfor searching for the optimal scheduling. The constraint is that the check points have tobe scheduled at a test vector on which at least one more fault has been detected comparedto the previous check points. If such points are less than the number of signatures n,then there isn't an optimal scheduling for the given n.Tables 3.22 and 3.23 report the 6SV's and the average SV's for the ten ISCAS'85benchmark circuits. The average 6SV equals to the summation of all the elements of the6SV divided by the dimension of the 6SV. For example, if 6SV = (0,0,0,0,0,32,384,0),(0+0+0+0+0+32+384+0) -the average 6SV _ 02. The average 6SV gives a measure on the8overall movement of the optimal scheduling. The SSV's in Tables 3.22 and 3.23 are allpositive, i.e., the optimal schedulings with abasing move towards the starting point ofthe test compared to that without abasing. When 71 increases, the movements becomemore significant for most of the circuits. When n decreases, the movements become lessChapter 3. Multiple Signature Fault Simulation Time Model^ 72Circuit n SV (with alia,sing)c432 16 n/ a8 32, 64, 96, 128, 160, 224, 448, 204832, 64, 128, 204832,2048c499 16 32, 64, 96, 128, 160,192, 224, 256,288, 320, 352, 384, 480, 512, 704, 20488 32, 64, 96, 128, 192, 288,480, 20484 32, 96, 192, 20482 32,64c880 16 32, 64, 96, 128, 160, 192, 224, 256,288, 320, 352, 384, 480, 640, 864, 20488 32, 64, 96, 128, 224,320,480, 20484 32, 128, 384, 20482- 32, 2048c1355 16 32, 64, 96, 128, 160, 192, 224, 256,288, 320, 352, 416, 512, 704, 1088, 20488 32, 64, 96, 128, 288,448; 704, 20484 32, 96, 384, 204832, 2048c1908 16 32, 64, 96, 128, 160, 192, 224, 256,288, 384,544, 704, 928, 1344, 1696, 20488 32, 64, 96, 224, 512, 736, 1248, 20484 32, 128. 736, 20482 32, 2048Table 3.20: Optimal Scheduling of Signatures for c432, c499, c880, c1355, c1908 for MSAChapter 3. Multiple Signature Fault Simulation Time Model^ 73Circuit n SV (with aliasing)c2670 16 32,64,96,128,160,192,224,256,288,320,384,448,480,544,672,20488 32,64,96,128,160,224,384,20484 32,96,384,20482 32,2048c3540 16 32,64,96, 128,160,192,224, 256,288,320,352,448,544,672,1120,20488 32,64,96,160,352,576,1120,204832,160,512,20482 32,2048c5315 16 32, 64, 96, 128, 160, 192, 224, 256,288, 320, 352, 384, 416, 512, 832, 20488 32,64, 96, 128, 160, 288,512, 20484 32,96,352,20482 32,2048c6288 16 n/a8 n/a4 32, 64, 96, 20482 32,2048c7552 16 32,64,96,128,160,192,224,256,288,320,352,384,512,640,1088,204832,64,96,128,160,288,640,20484 32,96,280,20482 32,2048Table 3.21: Optimal Scheduling of Signatures for c2670, c3540, c5315, c6288, c7552 forMSA.Chapter 3. Multiple Signature Fault Simulation Time Model^ 74Circuit n SSV Average 6SVc432 16 n/ a n/ a8 0, 0, 0, 0, 0, 32, 384, 0 524 0,0,0,0 02 0,0 0c499 16 0,0,0,0, 32,32,32, 64,64,64,64,128,128,128,192,64,0608 0,0,0,0,0,0,0,0 04 0,32,128,0 402 0,0 0c880 16 0, 0, 0, 0, 0, 32, 32, 32,32,64,128,160, 160, 224,96, 0608 0, 0, 32, 96, 96, 64,160, 0 564 0,0, 0, 0 02 0,0 0c1355 16 0, 0, 0, 0, 32, 32, 64, 96,128,192,256,288, 256,384,320, 01288 0, 0, 32,160, 128, 256,384, 0 1204 0, 32, 32, 0 162 0,0 0c1980 16 0, 0, 0, 0, 64, 96, 160, 288384,352,384,416,320,128,128,01708 0,32,192,320, 224,384,448,0 2004 0,96,0,0 242 0,0Table 3.22: Delta scheduling vectors (SV for circuits c432, c499, c880, c1355, c1908.Chapter 3. Multiple Signature Fault Simulation Time Model^ 75Circuit n SSV Average SSVc2670 16 0, 0, 0, 0, 0, 0, 0, 0,0,0,0,32,64,128,64,0188 0,0,0,32,64,160,288,0 684 • 0,0,0,0 02 0,0 0c3540 16 0, 0, 0, 0, 0, 0, 64, 96200,192,320,480,640,736,608,02088 0,0,0,0,0,64,64,0 164 0,0,0,0 02 0,0 0c5315 16 0, 0, 0, 0, 0, 0, 0, 32,64,96,160,256,416,416,448,01188 0, 0, 0, 32, 128, 128, 320, 0 764 0,32,0,0 82 0,0 0c6288 16 n/a n/a8 n/a n/a4 0,64,256,0 802 0,0 0c7552 16 0, 0, 0, 0, 0, 0, 0, 0,32,64,160,256.332,448,352,01048 0,0,0, 32.96,96,0,0 984 0, 32, 104, 0 342 0,0 0Table 3.23: Delta Scheduling Vectors 8SV for c2670, c3540, c5315, c6288, c7552Chapter 3. Multiple Signature Fault Simulation Time Model^ 76significant, and even becomes zero for n = 2. The most significant average movementoccurs for the circuit c3540 when n = 16, and the average movement is 208 vectors.3.4.3 Fault Simulation Time vs. SchedulingFrom Eqn. 3.48, the fault simulation time FST is a function of signature scheduling,signature bit partitions, number of signatures and test length. We next briefly discussthis relationship for three special cases:1. Optimal scheduling with aliasing taken into account;2. Optimal scheduling without aliasing taken into account;3. Dual even MSA.The second case is equivalent to the case discussed in [31] except that the check pointsare confined to multiples of 32 test vectors.Tables 3.24 and 3.25 report fault simulation time savings compared to the fault simulationtime for single signature of size 16 taken at the end of the test. All the fault simulationsare conducted on a SPARC 2 workstation. The table entry is the average of three trials.fstsa, denotes the fault simulation time saving in the case of optimal scheduling withaliasing taken into account, fsts' denotes the fault simulation time saving in the caseof optimal scheduling without aliasing taken into account, which is the case discussedin [31], and fstesci, denotes the fault simulation time saving in the case of equidistantscheduling.According to the results listed in Table 3.24 and 3.25, we can draw the following conclu-sions:Chapter 3. Multiple Signature Fault Simulation Time Model^ 77Circuit n f st say (%) f st's,,,(%) f stL,(%)c432 16 n/a n/a n/a8 95.25 95.09 83.574 94.35 94.29 73.962 72.29 72.29 50.59c499 16 90.88 91.16 84.018 93.45 93.26 82.604 90.27 91.85 73.772 58.62 58.62 50.66c880 16 91.02 91.23 84.008 91.71 91.85 80.504 89.42 89.42 71.372 58.62 58.62 48.05c1355 16 90.44 90.90 83.238 91.53 91.98 81.184 88.99 89.19 71.842 54.18 54.18 49.43c1908 16 84.03 84.30 78.508 84.88 84.06 76.8183.09 81.13 68.842 39.53 39.53 46.22Table 3.24: Comparisons of fault simulation time saving for (i) optimal scheduling withaliasing taken into account; (ii) optimal scheduling without aliasing taken into account;(iii) equidistant scheduling. Note that f, ,Sisav < f 81'sav in some cases. This is because thatthe FCL model under or over estimating the fault coverage loss in those cases. Resultsfor ISCAS'85 benchmark circuits c432, c499, c880, c1355, c1908 are presented.Chapter 3. Multiple Signature Fault Simulation Time Model^ 78Circuit n fsts„,(%) ists'av(%) MLA)c2670 16 76.87 76.58 70.038 77.65 77.96 68.074 76.47 76.15 59.172 30.18 30.18 39.83c3540 16 85.10 85.42 78.968 81.75 81.31 72.144 79.83 79.90 65.492 32.83 32.83 44.38c5315 16 90.41 90.42 84.598 89.58 89.35 81.214 82.12 86.08 71.362 77/a n/ a n/ac6288 16 77/a n/a n/a8 n/a n/a n/a4 95.92 95.99 70.912 37.94 37.94 46.42c7552 16 86.86 86.80 79.848 86.91 86.98 76.114 84.45 84.38 66.602 17.28 n/a 46.93Table 3.25: Fault simulation time saving results for the ISCAS'85 benchmark circuitsc2670, c3540, c5315, c6288, c7552.Chapter 3. Multiple Signature Fault Simulation Time Model^ 791. With the PPSFP fault simulator, optimal scheduling yields 70 — 90% fault simula-tion time saving compared to the fault simulation time of a single signature takenat the end of test.2. Optimal scheduling gives better fault simulation time than the case where no opti-mal scheduling is performed regardless of whether abasing is taken into account ornot. With the PPSFP fault simulator, optimal scheduling yields an average of 7%more savings than equidistant scheduling for the case with aliasing.3. Although aliasing has some impact on the optimal scheduling, the impact in termsof fault simulation time is not significant.3.5 Fault Coverage Loss vs. Fault Simulation TimeUsing the fault coverage loss model given by Eqn. 2.17 and the normalized fault simu-lation time model captured by Eqn. 3.49, we can discuss the relationship between faultcoverage loss and fault simulation time. We need to use the normalized fault simulationtime model presented in Eqn. 3.48 here. The equation is rewritten as:n-1fst = in — — li)Fi _ li)FCLi. (3.52)The second term is only a function of check points and F. The third term is a functionof check points and FCLi. FCLi is a function of F , the checkpoints, and signaturebit partitions. An example is given next to illustrate the relationship between fst andFCL. The relationship can be used to determine 11 and kis for a MSA scheme given thefollowing conditions:1. The FCL for the MSA scheme is less than a FCL threshold.2. The hardware cost should be minimized.Chapter 3. Multiple Signature Fault Simulation Time Model^ 80Example 2: We arbitrarily choose one of the ISCAS'85 benchmark circuits c1355 as anexample. The test length used in the example is 2048. Table 3.26 gives the fault coveragedata before compaction for c1355.test length fault coverage(%)128 88.3026256 92.2017384 93.6285512 94.8831640 96.0640768 97.0480896 97.46621024 97.98281152 98.46251280 98.64701408 99.02831536 99.08981664 99.33581792 99.33581920 99.39732048 99.3973Table 3.26: Fault coverage data before compaction for c1355 circuit.The signature scheduling used in this example is equidistant scheduling and the signaturebit partitions are even partitions. We discuss the fault simulation time and fault coverageloss for the following four cases.• n = 16, 2048 = 1 1616• n = 8, 1, = i 4( 2048 , s.8• n =_  4, i_^* , = , 4.20448• n = 2,=^* 2048^• = 1,2.2Chapter 3. Multiple Signature Fault Simulation Time Model^ 81Using the fault coverage loss model from Eqn. 2.17, and using the fault coverage databefore compaction listed in Table 3.26, we calculate the fault coverage losses for the totalnumber of signature bits k = 16,32, 64,128 for the four cases. The results are shown inFig. 3.21 and Table. 3.27.k n FCL(%)16 16 0.0463188 0.0439964 0.0257482 0.00702032 16 0.0049798 0.0049244 0.0012182 3.293386e — 1064 16 2.440702e — 042.440146e — 044 4.692333e — 062 7.668017e — 20128 16 9.384729e — 078 9.384722e — 074 7.159540e — 112 4.156841e — 39Table 3.27: FCL vs. k and n for c1355.Suppose that we need to design a MSA scheme. We require that the FCL of the MSAscheme is at most equal to the FCL of a k-bit (e.g., k = 16) SSA scheme, i.e., we needto choose the fault coverage threshold such that,FCL < (FC„ at vector2018) * 2-k^(3.53)(FC„, at cector204S)* 9- 16= 0.001516(%).Chapter 3. Multiple Signature Fault Simulation Time Model^ 82By looking at Fig. 3.21 and Table 3.27, we can see that the following cases satisfy thecondition in Eqn. 3.54:• When k = 16, none of the signatures satisfy the condition given in Eqn. 3.54.• When k = 32, n = 4 and n = 2 would satisfy the condition given in Eqn. 3.54. n2 partition will give a better fault coverage than n = 4 partition, but n = 4 partitionwill yield shorter fault simulation time from the simulation results presented inTables 3.24-3.25.• When k = 64, n = 16, n = 8, n = 4 and n = 2 will all satisfy the condition given inEqn. 3.54. From the simulation results presented in Tables 3.24-3.25, and analysispresented in chapter 2, the n = 2 partition will give the highest fault coverageamong these four case, but the longest fault simulation time, and n = 16 will givethe fastest fault simulation time among these four cases, but will give the lowestfault coverage.• Whenk = 128: n = 16, n = 8, n = 4 and 11 = 2 will all satisfy the condition givenin Eqn. 3.54. n = 2 partition will give the highest fault coverage comparing to thatfor n = 16, n = 8, and n = 4. However the n = 2 partition will yield the longestfault simulation time. The n = 16 will give the shortest fault simulation time, butwill yield the lowest fault coverage.When designing a MSA scheme, we need to consider (i) required fault coverage, (ii)hardware overhead, (iii) fault simulation time. By giving the fault coverage thresholdin Eqn. 3.54, we set up the minimum acceptable fault coverage. Among some possiblechoices, there are 10 out of 16 cases where the fault coverage is higher than the minimumacceptable fault coverage. We need to design a test scheme that minimizes hardware over-head and fault simulation time, and yet. satisfy the minimum acceptable fault coverageChapter 3. Multiple Signature Fault Simulation Time Model^ 83condition.To obtain the shortest fault simulation time, we need n as large as possible. So, we selectn = 16. There are only two choices that remaining, k = 64, n = 16 and k = 128, n = 16.Both choices satisfy the condition in Eqn. 3.54, but k = 64, n = 16 gives less hardwareoverhead. Therefore, the best choice is k = 64, n = 16, i.e., checking 16 4-bit signatures.Figure 3.21: Fault Coverage Loss vs. k and n. The horizontal axis represents the numberof signatures n, the vertical axis represents the logarithm of fault coverage loss.Chapter 3. Multiple Signature Fault Simulation Time Model^ 843.6 ConclusionsA fault simulation time model which takes into account the aliasing effect of signatureanalyzers was developed in this chapter. There are at least two ways to schedule mul-tiple signature analysis: (i) equidistant check points and (ii) optimally scheduled checkpoints. In this thesis, we have discussed these cases. For the equidistant scheduled mul-tiple signatures, for fixed k, the fault simulation time decreases as n increases. For theoptimally scheduled multiple signature analysis, aliasing affects the optimally scheduledcheck points slightly, but according to the experimental results, the impact on the faultsimulation time is generally less than 5%. Thus, aliasing effects when finding the optimalscheduling check points can be ignored.Chapter 4ConclusionsThe fault coverage model for multiple signature analysis (MSA) proposed previously inthis thesis allows us to predict the fault coverage for MSA more accurately than theexisting model derived from the assumption of equally likely error model especially forlarge circuits. With the model, some interesting conclusions towards MSA can be drawnand the conclusions are supported by fault simulation results. Furthermore, the modelcan be used to aid the design of MSA schemes.The fault coverage model for MSA developed in this thesis leads to the following con-clusions. First, fault coverage for MSA schemes is a function of both checked pointsscheduling and the signature lengths. Second, when the total number of signature bits isfixed, aliasing increases when the number of signatures increases. Third, when both thetotal number of signature bits and the number of signatures are fixed, the signature bitpartition of lc, k2 kn-1 — 1, kr, k — n + 1 yields the smallest aliasing.The fault simulation time model developed in this thesis takes the aliasing effect ofsignature analyzers into account. Two ways to schedule multiple signature analysis are:(i) schedule the multiple signatures at equidistant check points, (ii) schedule the multiplesignatures at optimally scheduled check points. For the equidistantly scheduled multiplesignatures, fault simulation time decreases as the number of signatures increases for agiven total number of signature bits. For the optimally scheduled multiple signatureanalysis, aliasing affects the optimally scheduled check points slightly, but the impact on85Chapter 4. Conclusions^ 86the fault simulation time is generally less than 5% according to the experimental results.Therefore, aliasing has negligible effects on finding the optimal scheduling check points.If we only need to find the optimal scheduling check points for a MSA scheme, we canuse the fault simulation time model developed in [31].4.0.1 Future WorkThe basic ideas used in this thesis to develop the fault coverage prediction model formultiple signature based schemes can be used to analyze other multiple compactionschemes, such as multiple one's counting schemes, multiple partial syndrome schemes,and even the hybrid multiple compaction schemes such as simultaneous signature andsyndrome compaction [44].Bibliography[1] M. Abramovici, P. R. Menon and D. T. Miller, "Critical Path Tracing: An Alter-native to Fault Simulation," IEEE Design & Test of Computers, February 1984,pp. 83-92.[2] M. Abramovici, B. Krishnamurthy, R. Mathews, B. Rogers, etc. "What is the Pathto Fast Fault Simulation? (A Panel Discussion)" Proc. IT 1988, pp. 183-192.[3] H; Ando, "Testing VLSI with random access scan," Dig. Papers Compcon 80,February 1980, pp. 50-52.[4] P. H. Bardell, W. H. McAnney and J. Savir, Built-In Test for VLSI: Pseudorandom• Techniques, John Wiley & Sons, 1987.[5] D. Bhavsar and B. Krishnamurthy, "Can We Eliminate Fault Escape in Self-Testingby Polynomial Division (Signature Analysis)?" Proc. ITC, October 1984, pp. 134-139.[6] M. A. Breuer, and A. D. Friedman, Diagnosis 6 Reliable Design of Digital Systems,Computer Science Press, INC., 1976.[7] F. Brglez and H. Fujiwara, "A neutral netlist of 10 combinational benchmark cir-cuits and a target translator in FORTRAN," Proc. IEEE hit. Symp. Circuits andSystems, 1985 pp. 151-158.[8] W. C. Carter, "The Ubiquitous Parity Bit," Proc. FTCS-82, 1982, pp. 289-296.[9] H. Cox, A. Ivanov, V. K. Agarwal and J. Rajski, "On Multiple Fault Coverage andAliasing Probability Measures," Proc. ITC, 1988, pp. 314-321.[10] S. DasGupta, E. B. Eichelberger, and T.W. Williams, "LSI chip design for testa-bility," Dig. Tech. Papers, 1978 Int. Solid State Circuits Conf., February 1978, pp.216-217.[11] B. I. Dervisoglu, "Scan-Path Architecture for Pseudorandom Testing," IEEE De-sign & Test of Computers, 1989, pp. 32-48.[12] S. E. Dreyfus, and A. M. Law, The Art and Theory of Dynamic Programming,Academic Press, 1977.87Bibliography^ 88[13] R. A. Frohwerk, "Signature Analysis: A New Digital Field Service Method,"Hewlett-Parkard J., May 1977, pp. 2-8.[14] H. Fujiwara and S. Toida, "The Complexity of Fault Detection Problem for Com-binational Logic Circuits," IEEE Trans. on Comput., Vol. C-31, No. 6., June 1982,pp. 555-560.[15] H. Fujiwara and T. Shimono, "On the acceleration of test generation algorithms,"IEEE Trans. on Comput., Vol. C-32, December 1983, pp. 1137-1144.[16] S. Funatsu, N. Wakatsuki, and T. Arima, "Test generation systems in Japan,"Proc. 12th Design Auto. Symp., June 1975, pp. 114-122.[17] M. Carey and D. Johnson, Computers and Intractability: A Guide to the Theoryof NP-Completeness, W.H. Freeman, San Francisco, 1978.[18] C. S. Gloster and F. Brglez, "Boundary Scan with Built-in Self-Test," IEEE DesignTest of Computers, 1989, pp. 36-44.[19] S. K. Gupta and D. K. Pradhan, "A New Framework for Designing Si AnalyzingBIST Techniques: Computation of Exact Aliasing Probability," Proc. ITC, 1988,pp. 329-342.[20] P. Goel, "An Implicit Enumeation Algorithm to Generate Tests for CombinationalLogic Circuits," IEEE Trans. on Comput. Vol. C-30, No. 3, March 1981, pp. 215-222.[21] L. H. Goldstein and E. L. Tigpen, "SCOAP: Sandia Controllability ObservabilityAnalysis Program," Proc. of 16th Design Automation Conf., June 1979, pp. 190-196.[22] S.Z.Hassan and E.J.McCluskey, "Increase Fault Coverage Through Multiple Sig-natures," Proc. 14th Int. Syrn. Fault - Tolerant Comp., 1984, pp. 354-359.[23] D. Harvel, "Is There Hope for Linear Time Fault Simulationi: Proc. FTCS-87,1987, pp. 28-33.[24] 0. H. Ibarra and S. K.Sahni, "Polynomially Complete Fault Detection Problems,"IEEE Tran. on Comput., Vol. C-24. No. 3, March 1975, pp. 242-249.[25] A. Ivanov and V.K. Agarwal, "Testability Measures - What Do They Do forATPG?" Proc. 1986 Int. Test Conf., 1986, pp. 129-138.[26] A. Ivanov and V.K. Agarwal, "An Iterative Technique for Calculating AliasingProbability of Linear Feedback Signature Registers," Proc. FTCS-88, June 1988,pp. 70-75.Bibliography^ 89[27] A. Ivanov, and V.K. Agarwal, "An Analysis of the Probabilistic Behavior of LinearFeedback Signature Registers," IEEE Trans. on CAD, Vol. 8, No. 10, October.1989, pp. 1074-1088.[28] S.K. Jain and V.D. Agrawal, "STAFAN: An Alternative to Fault Simulation," Proc.of the 21st Design Auto. Conf., 1984, pp. 18-23.[29] S.K. Jain and V.D. Agrawal, "Statistical Fault Analysis," IEEE Design e4 Test,Vol. 2, No. 1, February 1985, pp. 38-44.[30] J.R.Kuban and W.C.Bruce,"Self-Testing the Motorola MC6804P2," IEEE Design& Test, Vol. 1 No. 2, May 1984, pp. 33-41.[31] D. Lambidonis, V. K. Agarwal, A. Ivanov, and D. Xavier, "Computation of ExactFault Coverage for Signature Analysis Schemes," Proc. ISCAS, June 1991, pp.1873-1876.[32] J.J.LeBlanc, "LOCST: A Built-In Self-Test Techniques," IEEE Design e.4 Test, Vol.1, No. 4, November 1984, pp. 45-52.[33] Y.-H. Lee, and C.M.Krishna, "Optimal Scheduling of Signature Analysis for VLSITesting," Proc. ITC, 1988, pp. 443-449.[34] J. Losq, "Efficiency of Random compact testing," IEEE Tran. on Comput., Vol.C-27, June 1978, pp. 516-525.[35] F. Maamari and J. Rajski, "A Reconvergent Fanout Analysis for Efficient ExactFault Simulation of Combinational Circuits," Proc. FTCS-88, 1988, pp. 122-127.[36] F. Maamari and J. Rajski, "A Method of Fault Simulation Based on Stem Region,"IEEE Trans. on CAD, Vol. 9, No. 2, February 1990, pp. 212-220.[37] E. J. McCluskey, "Built-In Self-Test Techniques," IEEE Design Test of Comput-ers, April 1985, pp. 21-28.[38] E. J. McCluskey, "Built-in Self-Test Structures," IEEE Design & Test of Comput-ers, April 1985, pp. 29-36.[39] E. J. McCluskey, S. Makar, Samiha Mourad, and K. D. Wagner, "ProbabilityModels for Pseudorandom Test Sequences," IEEE Tran. on CAD, Vol. 7, No. 1,January 1988, pp. 68-74.[40] A. Miczo, Digital Logic Testing and Simulation, Happer & Row, Publishers, NewYork, 1986.Bibliography^ 90[41] H. B. Min and W. A. Rogers, "Search Strategy Switching: An Alternative toIncrease Backtracking," Proc. ITC, 1989, pp. 803-811.[42] R. Raina and P. N. Marinos, "Signature Analysis with Modified Linear FeedbackShift Register (M-LFSR)," Proc. FTCS-91, pp. 88-95.[43] J. Rajski and J. Tyszer, "Experimental Analysis of Fault Coverage in Systems withSignature Registers," Proc. ETC, 1991, pp. 45-48.[44] J. R. Robinson and N. R. Saxena, "Simultaneous Signature and Syndrome Com-pression," IEEE Trans. on CAD, Vol. 7, No. 5, May 1988.[45] J. Savir, "Syndrome-Testable Design of Combinational Circuits," IEEE Trans. onComput., Vol. C-29, No. 6, January 1980, pp. 442-450.[46] J. Savir, G.S. Ditlow and P.H. Bardell, "Random Pattern Testability," IEEE Trans.on Comput., Vol. C-33, Jan. 1984, pp. 79-90.[47] J. Savir and W.H. McAnney, "On the Masking Probability with One's Count andTransition Count," Proc. ICAD, November 1985, pp.[48] N. R. Saxena, P. Franco, and E. J. McCluskey, "Bounds on Signature AnalysisAliasing for Random Testing," Proc. FTCS-91, 1991, pp. 104-111.[49] S. C. Seth and V.D.Agrawal, "A Theory of Testability with Application to FaultCoverage Analysis," Proc. ETC, 1989, pp. 139-143.[50] J. E. Smith, "Measures of the Effectiveness of Fault Signature Analysis," IEEETrans. on Comput., Vol. C-29, No. 6, June 1980, pp. 510-514.[51] J. H. Stewart, "Future testing of large LSI circuit cards," Dig. Papers 1977 Semi-conductor Test Symp., October 1977, pp. 6-17.[52] A. P. StrOle and H. -J. Wunderlich, "Signature Analysis and Test Scheduling forSelf-Testable Circuits," Proc. FTCS-91, 1991, pp. 96-103.[53] K. D. Wagner, C. K. Chin, and E. J. McCluskey, "Pseudorandom Testing," IEEETrans. Comput., Vol. C-36, No. 3. March 1987, pp. 332-343.[54] J.A. Waicukauski, E.B. Eichelberger, D.O. Forlenza, E. Lindbloom and T. Mc-Carthy, "A Statistical Calculation of Fault Detection Probabilities by Fast FaultSimulation," Proc. ITC, 1985, pp. 779-784.[55] J. A. Waicukauski, E. B. Eichelberger, D. 0. Forlenza, E. Lindbloom and T. Mc-Carthy, "Fault Simulation for Structured VLSI," VLSI Systems Design, December1985, pp. 20-32.Bibliography^ 91[56] R.-S Wei and A.L.Sangiovanni-Vincentelli, "New Front- End and Line JustificationAlgorithm for Automatic Test Generation," Proc. 1986 mt. Test Conf., 1986, pp.122-128.[57] T. W. Williams and K. P. Parker, "Design for Testability - A Survey," IEEE Trans.on Comput., Vol. C-31, No. 1, January 1982, pp. 2-16.[58] T. W. Williams, "VLSI Testing." Computer. Oct. 1984, pp. 126-136.[59] T. W. Williams, W. Daehn, M. Gruetzner and C.W. Starke, "Comparison of Alias-ing Errors for Primitive and Non-Primitive Polynomials," Proc. ITC, September1986, pp. 282-288.[60] Y. Wu and A. Ivanov, "A Minimal Hardware Overhead BIST Data CompactionScheme," Proc. Mt. Conf. ASIC, September 1992, pp.[61] Y. Wu, C. Zhang, and A. Ivanov, "On Fault Coverage for Multiple SignatureAnalysis," in preparation.[62] Y. Zorian, and V.K.Agarwal, "A general Scheme to Optimize Error Masking inBuilt-In Self-Testing," Proc. 18th Int. Symp. on Fault-Tolerant Computing, July1986, pp. 410-415.[63] Y. Zorian, "Automated Built-In Self-Test for Embedded Macrocells," Proc. ATEand Instrumentation, January 1991, pp. 57-62.

Cite

Citation Scheme:

        

Citations by CSL (citeproc-js)

Usage Statistics

Share

Embed

Customize your widget with the following options, then copy and paste the code below into the HTML of your page to embed this item in your website.
                        
                            <div id="ubcOpenCollectionsWidgetDisplay">
                            <script id="ubcOpenCollectionsWidget"
                            src="{[{embed.src}]}"
                            data-item="{[{embed.item}]}"
                            data-collection="{[{embed.collection}]}"
                            data-metadata="{[{embed.showMetadata}]}"
                            data-width="{[{embed.width}]}"
                            async >
                            </script>
                            </div>
                        
                    
IIIF logo Our image viewer uses the IIIF 2.0 standard. To load this item in other compatible viewers, use this url:
http://iiif.library.ubc.ca/presentation/dsp.831.1-0065141/manifest

Comment

Related Items