Selection of the flip-flops for partial enhanced scan techniques.pdf IntroductionDelay testing has become very important problem in nanometer technologies.Structural scan based delay testing is used for detecting the circuit delays. Because ofthe architectural limitations not each pair v1, v2 can be applied by a scan delay test. Enhancedscan techniques were developed to remove the restrictions on vector pairs. Unfortunatelythese techniques have rarely been used in practice because of the near doublingof the flip-flop area. Most promising are partial enhanced scan approaches that arebased on selection of the proper flip-flops for including them in enhanced scan chains[1]. In the paper [2] it is suggested to include in scan chains flip-flops with low estimationsof the 0 values of the corresponding state variables (low controllability) but facilitiesof propagation of changing signal values from the input to the output (observability)are not considered. In the paper [3] were suggested deriving estimations of both controllabilityand observability. We suggest to appreciate flip-flop controllability as sumof 01 transition probability and 10 transition probability for the corresponding statevariable. The flip-flop observability is appreciated as a probability of robust PDF manifestationfor the paths of the same state variable. The algorithms of controllability andobservability calculation are developed.In Section 1 the problem of calculation 01(10) transition probability for the statevariable is discussed. In Section 2 the method of calculation of robust PDF manifestationprobability for the paths corresponding to a state variable is suggested.1. Calculation of a probability of 01(10) transitions of state variablesLet we have a synchronous circuit (Fig. 1) in which x1,…,xn are input variables,y1,…,yp are state variables, z1,…,zm are output variables, and d1,…,dp are flip flops.Random input sequence of a sequential circuit is describedwith the probability distribution ρ(x1),…,ρ(xn). Hereρ(xi), i=1…n, is the probability of 1 value of input variablexi. Let assume that the probability distribution ρ(y1),…,ρ(yp)of state variables is also known. Here ρ(xi), i=1…n, is theprobability of 1 value of input variable xi.We want to calculate the probability 01(10) transitionfor a state variable yi. For that consider the 2-length combinationalequivalent of Fig. 2.Having the structural description of a combinationalequivalent copy we may represent the copy functions correspondingto the combinational circuit C2 by the shared BDD which roots correspondto the state variables 2y1′ ,…, 2p y′ . These functions depend on the input variablesx12,…,xn2 and the state variables y12,…,yp2 (Fig. 2).Select root correlating with the variable 2yi′ . All paths connecting this root with the1-terminal node of the shared BDD represent the corresponding function ψi2 (x12,…,xn2,y12,…,yp2) as a disjoint sum of products (DSoP) Di that is as a sum in which products areorthogonal each other. All paths connecting this root with 0-terminal node represent aninversion of this function as DSoP Di in the same way.Two products are orthogonal if some variable appears in one product without inversionand in another - with inversion.x11xn1…z11zm1…y11yp1…x12xn2…z12zm2…ψ11ψp1…y12yp2 …ψ12ψp2…2y1′2p y′C 1C 2Fig. 2. 2-length combinational equivalent1 . 1 . 0 1 t r a n s i t i o n p r o b a b i l i t yExtract a product K from the Di that either contains literal 2yi or variable yi2 is absentin K. In the last case we add literal 2yi to product K. This product encloses in generalcase both the input and the state variables.Notice that the state variables correspond to the transition functions ψ11,…,ψp1 thatdepend on the input variables x11,…,xn1 and the state variables y11,…,yp1 and all thesevariables are statistically independent on the input variables x12,…,xn2 [2]. It means thatwe may substitute instead of the variables x12,…,xn2 of the product K their probabilitiesand do that with each product from the Di, selected above mentioned way. We have gotthe following sum: j jHere bj is result of multiplications of the probabilities ρ(x1),…,ρ(xn) of the proper inputvariables from a set {x12,…,xn2} and kj consists of some state variables (possiblywith inversions) from a set {y12,…,yp2}. The different functions corresponding to thestate variables of the product kj (they are represented with the C1 copy) in general casedepend on the same variables and these functions are statistically dependent.Represent corresponding to the product kj conjunction of the state variable functionswith the BDD-graph.We may calculate a probability of this conjunction using the given probability distributionfor the input and the state variables.Multiply the result by bj. Execute this with each product K from the Di. Summing resultswe calculate the 01 transition probabilities.1 . 2 . E x a m p l e o f c a l c u l a t i n g0 1 t r a n s i t i o n p r o b a b i l i t yConsider an example to illustrate the above mentioned results. The transition functionsof a copy of the combination equivalent are represented with the following sharedBDD (Fig. 3). For simplicity we don't use upperindexes of variables.Let probabilities of the 1 value of the internaland the state variables be the same andequal to 1/2: ρ(x1) = ρ(x2) = ρ(y1) = ρ(y2) = 1/2.Select the state variable 2yi′(Fig. 2). Extractthe corresponding DSoP from the sharedBDD (Fig. 3). Here we take into considerationupper indexes: 2 2 2 2 2y1 x1x2 x1 y2′= ∨ .All products do not contain y12. Consequentlywe need add the literal y 12 to eachproduct. As a result we have got DSoP D*:2 2 2 2 2 2x1x2y1 ∨ x1 y1 y2 .Substitute probabilities instead of the variables x12, x22 and obtain the following result:2 2 21 1 21 4y ∨1 2y y .Extract the functions 1 11, 2 ψ ψ , corresponding to the 2y1 ,y22 from the shared BDD (Fig. 2 and 3):2 1 1 1 1y1 =x1y2∨x1x2 ;ρ( 2y1 ) = 1/4+1/4 = 1/2;2 1 1 1 1y2 =x1 ∨x1y1y2 .The conjunction of these functions is represented withthe expression: 1 1 1 1 1 1 1 11 2 1 2 1 1 1 2 (x y ∨x x)∧(x ∨ x y y ) .The BDD of this expression is represented on Fig. 4.Extract DSoP, representing the conjunction 2 2y1 y2:1 1 1 1 1 11 2 1 2 1 2 x y∨x x y y =1 4+1 16 = 5 16 .y1 y2x1x2x1y2 y2y10 1Fig. 3. Shared BDDx21 y21x111 0y11y21Fig. 4. BDD representationof the conjunction 2 2y1 y2We could calculate ρ( 2 2y1 y2) directly from the BDD of Fig. 4.Substitute into the expression marked with (*) the obtained probabilities and calculatethe probability of 01 transition: ρ (01) = 1/4*1/2 + 1/2*5/16 = 9/32.1 . 3 . 1 0 t r a n s i t i o n p r o b a b i l i t yTo calculate 10 transition probabilities we need obtain DSoP of iD from sharedBDD selecting root that correlates with the variable 2yi′. Then we choose the productsfrom iD with the literal yi and the products that does not contain the variable yi addingto the last products the literal yi. For each chosen product we execute the steps of thepoint A.2. A probability calculation of manifestation of robust PDFs for state variableConsider the problem of probability calculation of manifestation of robust PDFs forstate variable. First we consider robust PDF test pair properties [3]. For that we will examinethe equivalent normal form (ENF) of a combinational equivalent copy.2 . 1 . R o b u s t P D F t e s t p a i r p r o p e r t i e sAn equivalent normal form represents the function implementing with the circuitand all the circuit paths. Each ENF literal is supplied with the index sequence enumeratingthe gates of the path. It should be noted that a literal with the same index sequencemay appear in different ENF products. The ENF of the circuit (Fig. 5) is as follows (1).98542 6137еbacdFig. 5. The combinational circuit 1459 59 59 59 23459 3459 59 a b e∨b c d e∨14689 789 234689 14689 234689 789 ∨a b c ∨a c d ∨14689 789 34689 14689 34689 789 a b d ∨a d dIf literals have the same index sequences but their variables are opposite in sign thenwe call them as opposite literals. The same variables i, ix x being opposite in sign wecall opposite variables. Opposite literals are absent in an ENF but opposite variablesmay present. We will spread all operations on products of a SoP (Sum of Products) onENF products. We call an ENF product empty if it contains opposite variables. Noticethat an ENF empty product consists of different literals.Examine non-empty products of ENF. Any such product turns into SoP product afterelimination of index sequences from literals followed with elimination of repeated variables.Sum of obtained products is SoP representing the function f. Non empty ENFproduct call implicant of the function f.We consider single robust PDF of the path α in the circuit for the appropriate transitionsalong the path [3] as the temporary ap (bp)-fault of the ENF literal xiα. This faultlasts during time ω, ω>τ. Here τ is the time passing between adjacent synchronizingsignals of the circuit.The literal xiα is changed for the constant 1 (bp-fault) in ENF products when the correspondingPDF activates the 1 value instead of the expected 0 value on the relevantcircuit output and a vector v2.This PDF corresponds to falling transition.The literal xiα is changed for the constant 0 (ap-fault) in ENF products when the correspondingPDF activates the 0 value instead of the expected 1 value on the relevantcircuit output and a vector v2. This PDF corresponds to rising transition.A test pattern v2 in the PDF test pair v1, v2 is a test pattern for bp(ap)-fault of ENF.Let K be ENF product (in partly K may be empty ENF product). K is expansiblewith the literal xiα if elimination of this literal gives rises to product K * that is implicantof the function f. Otherwise K is not expansible with the xiα.Elimination of the literal from a product modifies the given ENF (K changes for K*). If K * is non-empty product and K * is non implicant of the function f, then f changesalong with ENF. It means that the 1 value area of the function f increases.K * is the result of glue of products K and K . Here K is obtained from K withchanging the literal xiα for opposite literal. We will call K as addition of K .We suppose that the variable xi in the literal xiα doesn't have an inversion. First considerbp-fault of the literal xiα.Let K be a set of ENF products so that each product does not contain xiα.Divide the rest ENF products into two sets: one of them rxiK consists of products sothat each of them has repeating variable xi (the same variables with the same sign of inversionand the different index sequences). Products of rxiK don't change the functionf when bp-fault takes place and consequently not generate test pattern vb for bp-fault.Another set sxiK consists of the products (empty and non-empty) without repeatingvariable xi.Let K be non-empty product from sxiK . If K is non-expansible product by literal xiαthen changing that literal for the constant 1 in K alters the function f. That may be detectedwith a test pattern vb which turns into 1 the product K and turns into 0 fault freeENF. This test pattern is at the same time test pattern v2 from a test pair v1, v2 for thecorresponding PDF. Notice that vb turns into one the product K * possibly together withother products derived from sxiK by changing the literal xiα for the constant 1.If K is expansible product by literal xiα then changing that literal for the constant 1does not alter the function f. It means that there is no test pattern vb for bp-fault originatedby the product K.bp-faultConsider bp-fault of the literal xiα and test pattern vb that satisfies above mentionedconditions. Variable ix take the 1 value on v2.Denote as u the minimal cube covering v1, v2 and as k(u) - the product representing u.Theorem 1. To derive robust PDF test pair v1, v2 corresponding to bp-fault we needthe following.1. v2 is a test pattern for bp-fault;2. Variable xi in v1, v2 takes the opposite values;3. k(u) is orthogonal to each product from K ;4. Test pattern v1 turns into 1 product K from sxiK that generates test pattern vb .Corollary 1. The function f takes the 0 value on v2 and takes the 1 value on v1.Corollary 2. Empty product K from sxiK doesn't originate robust PDF test pair.Corollary 3. v1 is a test pattern for ap-fault.As k(u) is orthogonal to all products of K then v1 is orthogonal to all products of Kbut v1 turns into 1the function f. It means that v1 is a test pattern for ap-fault.ap-faultNow consider ap-fault of the literal xiα. All products from K remain in the faultENF.The rest products of the fault free ENF are divided into two sets: one of them exiKconsists of the empty products and another nexiK consists of the non-empty products.The products of exiK do not change the function f when ap-fault takes place and consequentlynot generate test pattern va .Consider the set nexiK . All its products disappear when ap-fault takes place. If itchanges the function f then there exists a test pattern va that detects ap-fault. The testpattern turns into 1 some products from nexiK and turns into 0 the rest products of thefault free ENF. The test pattern va also turns into 1 the variable xi.Theorem 2. To derive robust PDF test pair v1, v2 corresponding to ap-fault we needthe following.1. v2 is a test pattern for ap-fault;2. Variable xi in v1, v2 takes the opposite values;3. k(u) is orthogonal to each product from K ;4. There exists product K from nexiK that does not contain repeated variable xi sothat values of the variables of the cube representing this product and values of the variablesof test patterns v1, v2 (except variable xi) coincide.Corollary 1. The function f takes the 1 value on v2 and takes the 0 value on v1.Corollary 2. v1 is a test pattern for bp-fault.As k(u) is orthogonal to all products of K then v1 is orthogonal to all products of Kand by the construction v1 turns into 1 the addition of the product K. It means that v1 is atest pattern for bp-fault.2 . 2 . A p r o b a b i l i t y c a l c u l a t i o no f r o b u s t P D F m a n i f e s t a t i o n f o r t h e g i v e n p a t hRepresent as the DSoP all robust test pairs for the given path originated by oneproduct of ENF. For that we have to find product K from nexiK that does not containrepeated variable xi and obtain the SoP D from the set K fixing the variables of theproduct K except xi. All roots of the equation D = 0 are represented either as ROBDD orFree BDD. Each path from the root till the1-terminal nodearises to the product, corresponding to 2n−1−r robust testpairs consisting of neighboring Boolean vectors. Here r is arank of the product and n is the number of ENF variables.(Notice that the variable xi is absent in the product). Havinggot the BDD for each K from nexiK that does not containrepeated variable xi and corresponds to the same path α wemay execute disjunction operation on these BDDs and obd0 1Fig. 6. BDD representationof the product dtain BDD representing all robust test pairs. Using the last BDD we may calculate aprobability of the robust PDF manifestation for the path α substituting instead of thevariables their probabilities from the probability distribution.Illustrate that procedure by an example. Let the variable c be a state variable. Firstconsider the literal c234689. Take into consideration that for the product abc , k(u) = a b ,and the corresponding D, D = d∨dd. The BDD represents the only product d.Consider forth product of the ENF that contains the literal c234689. In this caseK = ac d , k(u) = a d , D = b ∨1 = 1.The equation D = 0 has no roots.Consequently a probability of robust test pair manifestation for the path α correspondingto the literal c234689 is represented by the formula abd and is equal to1/2*1/2*1/2 = 1/8.Here we suppose 1 value probability of each variable is equal to 1/2.2 . 3 . A p r o b a b i l i t y c a l c u l a t i o no f r o b u s t P D F m a n i f e s t a t i o n f o r s t a t e v a r i a b l eWhen we consider a state variable we have to regard all paths (literals) connectedwith this variable. Derive for each path a probability of robust PDF manifestation in theabove mentioned way. Then we have to summarize these probabilities.Notice that a test pair for one path does not change the signal values of other pathcorresponding to the same variable as all products representing another paths are containedin a set K formed for the path considered. It means that sensitizations of differentpaths of the same variable are statistically non-compatible events.Let c be state variable. We additionally have to find a probability of robust PDFmanifestation for the path corresponding to the literal23459с . Then K = b c de,k(u) = bde, D = a .BDD originates the only root: product a. Consequently a probability of robust PDFsmanifestation for the path corresponding to the literal23459с is represented by the formulaabde. It is equal to 1/2*1/2*1/2*1/2 = 1/16. Then a probability of manifestation ofrobust PDFs for the state variable c is as follows: 1/8+1/16 = 3/16.We have got the following experimental results.Controllability Pc and observability Po have been calculated for each state variablefor some benchmarks. Flip-flops corresponding to state variables with low controllabilityor/and observability can be selected for including in enhanced scan chains. The additionalinvestigations are necessary for choosing the threshold values for probabilityand observability We may only say that flip-flops with zero observability must not beincluded in enhanced scan chains.The algorithm of estimation calculation of flip-flop observability is based on ENFanalysis and using BDDs. ENF is very complicate formula for real circuits. It is possibleto use OR/AND tree to present all paths of a circuit [6]. These trees are used for findingthe estimations for benchmarks of the Table 1.We may use for description of the ENF of a circuit the system OR-AND trees. Thecomplexity of the system is linear function of the number of the circuit gates [6]. To acceleratethe calculation of flip-flop observability it is possible to joint application of thesystem OR-AND trees and the corresponding system SSBDDs [7]. We hope that thesetechniques will allow calculating flip-flop observability for more complicate circuits.Experimental results on Iscas89 benchmarksCircuit Flip-flops State Variable Pc Pos27 3 G11 0.172 0.125G10 0.457 0.063G13 0.344 0.250s344 15 ACVG3VD1 0.331 0.219ACVG2VD1 0.260 0.219AM3 0.125 0.875ACVG4VD1 0.180 0.219CNTVG2VD 0.188 0.375AM2 0.281 0.875CNTVG3VD 0.188 0.500AM1 0.281 0.875AM0 0.281 0.875MRVG3VD 0.500 0.125MRVG4VD 0.641 0.125MRVG1VD 0.406 0.125MRVG2VD 0.406 0.125CNTVG1VD 0.594 0.375ACVG1VD1 0.280 0.219s444 21 G58 0.209 0.141G112 0.335 0.000G49 0.063 0.063G111 0.224 0.000G45 0.094 0.188G41 0.125 0.125G113 0.130 0.000G162BF 0.129 0.453G80 0.133 0.343G70 0.091 0.186G101 0.375 0.500G66 0.113 0.275G110 0.233 0.000G62 0.119 0.230G109 0.099 0.000G84 0.120 0.382G92 0.108 0.362G155 0.375 0.500G88 0.115 0.402G114 0.026 0.000G37 0.578 0.000ConclusionThe special estimations of flip-flop controllability and observability are developed.They may be used for including flip-flops into partial enhanced scan chains. Possibilitiesof their application to more complicate circuits are noted.

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