Построение тестов для неисправностей задержек робастно тестируемых путей для комбинационных схем, построенныхпокрытием BDD-графов.pdf Delay testing has become very important problem with development of nanometertechnologies. The objective of delay testing is to detect timing defects degrading theperformance of a circuit. Path delay fault model is considered more preferable for detectionof timing defects.To observe delay defects, it is necessary to generate and propagate transitions in thecircuit input. This requires application of a pair of vectors v1, v2. The first vector v1 stabilizesall signals in the circuit. The second vector v2 causes the desired transition on theinput of a circuit. Take into account that delays of falling transition and rising transitionalong the same path from a primary input to a primary output in a circuit may be different.In the general case it is necessary a pair of vectors v1, v2 for each kind of transitionsof a path. We will call a pair of vectors on which PDF manifests itself as PDF test pair(for the corresponding transition along the path). Single and multiple PDFs are distinguished.In accordance with the conditions of fault manifestation single PDFs are divided intorobust and non robust [1, 2]. PDF is robust if there is a test pair on which the fault manifestationdoes not depend on delays of other circuit paths.PDF is non robust if a manifestation of the fault on a test pair is possible only whenall other paths of a circuit are fault free.It is very important to provide testability during circuit design. Circuits derived fromBDDs as a rule are implemented with multiplexors. Their testability is investigated underdifferent fault models [3−6] but the approaches suggested did not provide100% testability.In the paper [7] simple transformation of a circuit is suggested that guarantees100% testability for both single stuck-at fault (SAF) and PDF models. The circuits arederived from BDDs with using multiplexors. The size of a circuit is directly proportionalto the given BDD size. Optimization connected with variable ordering directlytransfers to the circuit size. Disadvantage of this approach consists of using additionalinput.In the paper [8] circuits are derived by covering BDDs with CLBs. In this paper it isrevealed that each single stuck-at fault at the CLB pole is equivalent either single stuckatfault of the proper internal node of BDD or 10 (01) faults of edges coming from theinternal node. It is also determined that each single stuck-at fault at the CLB pole is detectable.It means that the circuit guarantees 100% testability under SAF. Moreover testfor all multiple stuck-at faults may be derived directly from test for single stack-atfaults. Test for multiple stuck-at faults is 2.5 times longer [8] than test for single stuckatfaults (at the average).In this paper we show that circuit obtained from BDD by covering CLBs guarantees100% testability for PDFs without an additional input. A size of the circuit is directlyproportional to the given BDD size. Optimization connected with variable ordering directlytransfers to the circuit size. Moreover the lengths of tests for all PDFs of circuitsconsidered in this paper and the numbers of three input elements of these circuits as arule less than ones in the circuits implemented with multiplexors [7]. In this paper incomparison with the paper [9] the experimental results are represented and proofs of thetheorems are given.In Section 2 a problem of deriving special combinational circuits is discussed. InSection 3 test pair is found on which PDF manifests itself as robust for rising and fallingtransitions. In Section 4 experimental results are given.1. A combinational circuit designIt is well known that BDD is a directed acyclic graph based on using Shannon decompositionin each non terminal node v:xi 0 xi1fv=xifv = +xifv = ,0xi ( 1,..., 0,..., )fv = = fv x xi = xn, (1)1xi ( 1,..., 1,..., )fv = = fv x xi = xn ).Here fv is the function corresponding to the node v, dashed edge points to xi 0fv = andsolid edge points to xi 1fv = . A BDD is called ordered if variables are encountered in thesame order on all paths connecting the BDD root with a terminal node. A BDD is reducedif it does not contain either isomorphic subgraphs nor nodes so thatxi 0 xi 1fv = = fv = . Reduced and ordered BDD is a canonical representation of Booleanfunction for the chosen order of variables [10].Any path that connects the BDD root with the 1 terminal node originates the productof the Disjoint Sum of Products (DSoP) of a function f that is represented with thisBDD. DSoP is a sum of products in which any two product cubes don't intersect.Let F = {f1,...,fm}, be the system of Boolean functions describing a combinationalcircuit behavior. Derive BDD using the same order of variables for each Boolean functionfrom F. Join isomorphic subgraphs in the different BDDs. Combine BDDs 1 terminalnodes into one 1 terminal node and their 0 terminal nodes into one 0 terminal node.Due to we obtain the graph with m roots and two terminal nodes. This graph jointly representsa system of m Boolean functions. It is called Shared BDD [10]. Without loss ofgenerality we will consider further system with one function.In Fig. 1 a BDD for one output Boolean function is shown. For each path connectingthe BDD root with the 1 terminal node define the product of the DSoP. The DSoP of thefunction f is as follows.1 2 3 1 2 3 4 5 1 2 3 4 5 1 2 4 5 1 2 4 5 1 2 4 51 2 4 5 1 2 3 4 5 1 2 3 4 5 1 2 3 5 .f x x x x x x x x x x x x x x x x x x x x x x x x xx x x x x x x x x x x x x x x x x x=         Eliminate from BDD all edges connected with0 terminal node and obtain the BDD representing acombinational circuit behavior. Call this BDD asCircuit BDD. Cover Circuit BDD with CLBs toget a combinational circuit executing that we usethe following rules [8].1. CLB output corresponds to either nonterminal node or the root of the Circuit BDD.2. CLB input corresponds to either output ofanother CLB or variable of the Boolean function.3. If two or more edges drop in a non terminalnode of the Circuit BDD then this node may besplit and covered with different CLBs.4. The Boolean function implementing by a CLB is represented with the part(subgraph) of a Circuit BDD that is covered by the CLB. This function is derived fromsubgraph as DSoP depending on internal and input variables of the combinationalcircuit.As a result we have got the combinational circuit C.Covering Circuit BDD in accordance with rules 1−4 we have to provide coincidenceof DSoPs system represented by the Circuit BDD with the DSoPs system derived fromthe combinational circuit C with substituting the proper DSoP of CLB instead of eachinternal variable of the combinational circuit C.Consider Circuit BDD obtained from theBDD in Fig. 1 with using 3 inputs CLBs.Subgraphs of covering CLBs are representedin Fig. 2. The circuit obtained isshown in Fig. 3.Thus for each CLB we have subgraph ofthe Circuit BDD and the correspondingDSoP. CLB output may be either output ofthe circuit or internal node of the circuit thatis input of another CLB.For example DSoP 2 1 2 3 xwxxw1x2x3corresponds to CLB3 derived from relevantsubgraph of Fig. 2. Here x2, x3 - variablescorresponding to the circuit inputs, and w1is internal circuit variable relating to the output of CLB1.Non terminal node of Circuit BDD corresponds to CLB output if the node is a rootof the CLB subgraph.2. Deriving test pair for PDF2 . 1 . P r e m i s e s o f t e s t p a i rWe will examine one output circuit and corresponding BDD. Consider path ƒ in thecircuit of Fig. 3 (thick line). It begins from input variable x4 and traverses the CLBs 1, 4,5. CLB5 output is output of the circuit.We suppose that delays of the different pathsfrom input to output of the same CLB are equalas CLB is LUT based. It means if a path ƒtraverses certain CLB we may include any pathof the CLB subgraph (connecting the subgraphroot with its proper leaf) into the path ƒ wheninvestigating delay of the path ƒ.Derive reduced disjoint sum of products(reduced DSoP) for each CLB traversed by thepath ƒ. Reduced DSoP is formed from the CLBDSoP with including either products that containthe input variable corresponding to thebeginning of the path ƒ or products that containthe internal variable corresponding to the outputof the previous CLB traversing with the path ƒ.For the chosen path ƒ in Fig. 3 we have thefollowing reduced and non reduced DSoPs ( Fig. 2).Reduced DSoP of CLB1: : x4x5 x4x5 , non reduced DSoP of CLB1 is the same.Reduced DSoP of CLB4: x2w1, non reduced DSoP of CLB4: x2w2 x2w1.Reduced DSoP of CLB5: x1w4, non reduced DSoP of CLB5: x1w3 x1w4.Move along the path ƒ from the output of the circuit to the beginning of the path ƒ.Substitute reduced DSoPs of the corresponding CLBs instead of internal nodes traversedand remove brackets. If obtained sum of products has internal variables corresponding tothe outputs of CLBs that are not traversed with the path ƒ, then substitute instead of thesevariables the corresponding non reduced DSoPs and remove brackets till a set of internalvariables becomes empty. Denote derived set of products as Kƒ.Notice that we will consider any set of products here and further also as sum of theseproducts (SoP).For the path ƒ in our example we have the result of the first substitution: x1x2w1.Then after the second substitution we have got Kƒ: x1x2x4x5  x1x2x4x5 . Take intoconsideration that if we would derive Equivalent Normal Form (ENF) from the circuitconsidered [12] then each literal of the sum of products would be supplied withsequence of numbers of elements corresponding to the proper circuit path.Let products that contain literal ENF marked with the path ƒ be called connectedwith the path ƒ.If we exclude in ENF sequences representing paths from all literals then Kƒ obtainedabove is a set of products connected with the path ƒ.Theorem 1. A set Kƒ contains all products connected with the path ƒ. Kƒ is DSoP.Proof. Each product from Kƒ contains either literal xi or literal xi that corresponds tothe beginning of the path ƒ and path ƒ itself as each product is obtained withsubstitutions along the path ƒ. By the construction Kƒ contains all productscorresponding to the path ƒ. Kƒ is DSoP as changing in any DSoP some internal variablefor corresponding DSoP originates also DSoP [13]. The theorem is proved.Take into account that each BDD path connecting its root with 1 (0) terminal nodeoriginates the product. If the path traverses the internal node marked with i and solid(dashed) edge then the originated product contain xi ( xi ).Any path connecting two internal BDD nodes originates the product in the similarway.For example the path of Fig. 1 (thick lines) originates product x1x2x4x5 and part ofthis path connecting nodes 2 and 5 originates product x2x4.Theorem 2. For each product from Kƒ there exists the path from the root of BDD toits 1 terminal node that originates this product.Proof. From covering Circuit BDD with CLBs follows that we have got all productsof DSoPs as a result of all substitutions of the proper CLB DSoPs instead of circuitinternal variables. It means that we have got all products of DSoP for each function ofthe system. For the path ƒ we execute part of substitutions, excluding internal variablesto obtain all products connected with the path ƒ. Consequently each product connectedwith the path ƒ is among the BDD products corresponding to the one output circuitconsidered. The theorem is proved.One test pattern from a test pair detecting robust PDF of both rising and fallingtransitions [14] has to turn into 1 product K from Kƒ possibly together with otherproducts from Kƒ. In our case the circuit behavior is represented with DSoP.Consequently this test pattern turns into 1 only product K. This product contains eitherxi, or xi .Let K be obtained from K with changing literal xi(xi) for the inversion literal. CallK as an addition of K.Another test pattern of a test pair has to turn into 1 K and into 0 DSoP derived fromBDD [13] of the circuit considered. Denote this DSoP as Dd. Let u be minimal cubecovering v1 ,v2 and ku product representing u.To detect robust PDF it is necessary to provide the condition: product ku isorthogonal to products of Dd excluding product K.Take into consideration that input variable xi corresponding to the beginning of thepath ƒ is correlated (in general case) to several nodes of BDD covered by the CLBtraversed with the path ƒ. These nodes are marked with the same variable xi. To find testpair we may choose any of them [8]. Denote the chosen node as v.For example if we would consider the path traversing the same CLBs that the path ƒ,but beginning from the input variable x5 we have got two nodes of BDD covered byCLB1 and marked with the variable x5.Let ƒ be path from the BDD root into chosen node v. It originates the product kƒ.Derive from Kƒ the products corresponding to the path ε that is products containing kƒ.Exclude from them variables of kƒ. Denote the result as K*.In the example considered a set of products corresponding to the path ƒ is as follows:kƒ = x1x2 , 4 5 4 5K* =x x x x .Divide a set K* into two subsets. Products of one subset have the literal xi, andanother - the literal xi . Exclude from them these literals and denote obtained subsetsi*xK , i*xK correspondingly. These subsets represent functions implemented in nodes thatare incidental to right (solid) and left (dashed) edges ofthe node v (Fig. 4). These functions are different by theconstruction of BDD (in this paper we always meansROBDD)In the example ple we have: i 5*xK = x , and i 5*xK = x .Subsets i*xK ,i*xK are determined with the pole vand do not depend on the chosen path ƒ (Fig. 4).As the subsets represent different functions thenthere exists Boolean vector ƒ on which they take different values. Let ƒ turns into 1 i*xKand into 0i*xK , k* is a product representing ƒ.In the example considered subsets i*xK ,i*xK depend on the only variable x5. Thenwe have:5ƒ 0x= , *k =x5 .First add literal xi to k* and then the product kƒ. Denote the result K , * i K k xkƒ =is absorbed by the only product K from Kƒ . It follows from the theorem 1 and theconstruction of Boolean vector ƒ. Let K be addition of K relative to xi , then K isabsorbed by K . It follows from the construction of Boolean vector ƒ and K . In theexample: K = x1x2x4x5, K = x1x2x4x5. Here K, K coincide with K , K .Two products are orthogonal if their cubes don't intersect.A product k is orthogonal to the sum of products (SoP) if k is orthogonal to eachproduct of the SoP.Theorem 3. K is orthogonal to Dd.Proof. We have to show that K is orthogonal to products of K* that are obtainedfrom Kƒ with using path ƒ in above mentioned way. Remind that K containssubproduct kƒ. Product K is orthogonal to set of productsi*xK under construction.Product K is also orthogonal to set of products i*xiKx hence K is orthogonal to K* .The theorem is proved.Let Boolean vectors ƒ*, ƒ* turns into 1 products K, K correspondingly and thesevectors don't differ with variables that are absent in the products K, K . Let u beminimal cube covering these vectors and ku - product representing this cube.Theorem 4. Boolean vectors ƒ*, ƒ* comprise test pairs detecting robust PDF of thepath ƒ for both rising and falling transitions.Proof. Vector ƒ* turns into 1 product K (K from Kƒ) as K absorbs K and vector ƒ*turns into 1 product K as K absorbs K . Except ƒ* turns into 0 Dd. Product ku isorthogonal to products of Dd that does not contain kƒ as subproduct. Except (by theconstruction) ku is orthogonal to a set of products i*xK and a set of products i*xK withoutthe product K. It means [13] that on vectors ƒ*, ƒ* PDF of ƒ manifests itself as robustfor both falling and rising transitions. The theorem is proved.2 . 2 . A l g o r i t hm o f d e r i v i n g t e s t p a i rRemind that each path connecting two nodes of BDD is related to the productoriginated by the path. Two paths are compatible if their originated products are notorthogonal.The algorithm is partly (steps 1−5) based on results represented in [8] and connectedwith finding test pattern for single stuck-at fault of the circuit obtained by coveringBDD with CLBs. We mean single stuck-at fault of the CLB pole directly connectedwith a circuit input.1. Consider a path that begins from the node in which edge corresponding to xi (solidedge) goes from the node v and ends into 1 terminal node of the BDD. Denote the pathas ƒ.2. Look through paths that begin in the node in which edge corresponding g to xi(dashed edge) goes from the node v and ends into 0 terminal node of BDD in order tofind path compatible with ƒ. If we find such path then go to step 5. Otherwise return tostep 1. If all paths ƒ have looked through go to step 3.3. Consider a path that begins from the node in which edge corresponding to xi(dashed edge) goes from v and ends into 1 terminal node of BDD. Denote the path as ƒ.4. Look through paths that begin in the node in which edge corresponding to xi (solidedge) goes from v and ends into 0 terminal node of BDD in order to find pathcompatible with ƒ. If we find such path then go to step 5. Otherwise return to step 3.5. Obtained path denote as ƒ. Conjunction of products originated by the paths ƒ, ƒ,represents ƒ.6. Derive Boolean vectors ƒ*, ƒ* in above mentioned way. These vectors have toturn into 1 the proper products K, K . Except, the Boolean vectors ƒ*, ƒ* do not differwith variables that are absent in products K, K .In the example:ƒ* 1 2 3 4 50 0 0 1 0= x x x x x , ƒ* 1 2 3 4 50 0 0 0 0= x x x x x , K = x1x2x4x5, K = x1x2x4x5.In the products K, K variable x3 is absent. In the Boolean vectors ƒ*, ƒ* this variabletakes the 0 value.In Fig. 5 thick lines represent paths correspondingto ƒ*, ƒ* .To detect robust PDF of ƒ for rising and fallingtransitions we need triplets v1, v2, v1 or v2, v1, v2.Integrating triplets of all circuit paths we derive testT for all path delay faults.Theorem 5. Test T detects any PDF of a circuit(single and multiple).Proof. As test T consists of pairs on which PDFmanifests itself as robust and includes test pair foreach path of a circuit then each single PDF isdetectable with test T. As each single PDF manifests itself as robust on the proper pairof test T consequently any multiple PDF is detectable at the expense of single PDFcomprising multiple fault. The theorem is proved.X2X3X41X5 X5X2X3f0X1Fig. 5. Representing ƒ*, ƒ*Notice that all results derived for BDD easily may be spread to Shared BDD.3. Experimental resultsFor the experiments we used the benchmarks LGSynth'91 [15].In Table 1, the names of the benchmarks are given in the first column. The numbersof inputs and outputs are given in the second and the third columns, respectively.In section MUX-map, the results are given for a direct mapping of BDDs bymultiplexors as described in [6]. The number of nodes in BDD (NoN), the number ofpaths (NoP), and the PDF coverage (PDFC) are given in corresponding columns. Thistechnique doesn't provide the 100% PDF covering. To provide 100% PDF covering forcircuits in the frame of this technique it is necessary an additional input [7]. Using anadditional input increases the number of nodes in BDD (and consequently the numberof multiplexors) and the number of paths [7] for the same benchmark.In section LUT-map, the results are given for the technique described above for 3inputs CLBs. The number of CLBs in the circuit (NoC), the number of paths (NoP), andthe PDF coverage (PDFC) are given in corresponding columns.Experimental resultsMUX-map Name in out NoN NoP PDFC NoC LUNTo-mP ap PDFC5xpl 7 10 90 273 89.0 69 175 100.0C17 5 2 12 22 68.1 6 12 100.0alu2 10 6 259 873 86.9 246 929 100.0b9 41 21 237 1773 64.6 141 380 100.0clip 9 5 256 954 79.4 235 597 100.0conl 7 2 20 47 74.4 9 18 100.0count 35 16 251 2248 66.1 199 642 100.0il 25 13 60 137 74.4 41 85 100.015 133 66 313 44198 61.3 169 941 100.0t481 16 1 34 4518 86.1 26 1226 100.0tcon 17 16 34 40 100.0 16 32 100.09sym 9 1 35 328 72.5 27 195 100.0f51m 8 8 72 326 99.3 58 139 100.0z4ml 7 4 66 175 77.1 50 118 100.0x2 10 7 75 188 72.3 61 251 100.0Experimental results showed that the number of CLBs and the number of paths areas a rule less then the number of multiplexers and the number of paths for the samebenchmark.ConclusionSpecial combinational circuits are investigated. They are derived by covering BDDswith LUT based CLBs. It is found out that PDF of each path of such circuits manifestsitself as robust. Except for delays of rising and falling transitions of the same path thereexist triplets v1, v2, v1 or v2, v1, v2 detecting these delays. Triplets are found with BDDanalyses based on finding test pattern for single stuck-at fault of CLB input directlyconnected with a circuit input. Experimental results showed that lengths of tests forPDFs of investigated circuits and the numbers of three input elements of these circuitsas a rule less than ones in circuits implemented with multiplexors. Investigated circuitsdo not demand additional input to provide 100% testability for robust PDFs.

Скачать электронную версию публикации