Вычисление наблюдаемоститриггеров в рамках LOS техники сканирования состояний схемы.pdf Because of architectural limitations not an each test pair v1, v2 can be appliedthrough a scan delay test. Enhanced scan techniques were developed to remove theserestrictions on vector pairs. Unfortunately these techniques have rarely been used inpractice because of the near doubling of the flip-flop area. Most promising are partialenhanced scan approaches based on proper selection of flip-flops for including them inenhanced scan chains [1].In the paper [2] it was suggested to include flip-flops with low estimations ofcontrollability of corresponding state variables in scan chains. Facilities of signalchange propagation from an input to an output of a circuit (observability) are notconsidered. In the paper [3] estimations oriented to cutting the test length and improvingthe test coverage were developed for both controllability and observability. In bothpapers estimations are related to providing the constant value for the state variable butnot to providing the change of its value.1. Calculation of observability estimation of a state variableSuppose 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. CircuitC is a combinational part of a sequential circuit.Random input sequence of a sequential circuit is described with a probabilitydistribution ƒ(x1),…,ƒ(xn). Here ƒ(xi), i = 1,…,n, is a probability an input variable xitakes the 1 value on a random input vector. Assume that a probability distributionƒ(y1),…,ƒ(yp) of state variables is also known.The problem of probability calculation of robust PDF manifestation (calculation ofobservability estimation) for the state variable was considered in the paper [4] undersuggestion that the vector v1 of the test pair is a unit ofrandom sequence with the given probabilitydistribution of 1 values of input and state variables.Moreover each test pair v1, v2 can be applied through adelay test. The algorithm of observability estimationis based on deriving a ROBDD representation of allrobust PDF test pairs for the path. Remind thatROBDD paths from its root to the 1 value terminalnode represent a Disjoint Sum of Products (DSoP). Ina DSoP all products are pairwise orthogonal. Whenthe LOS technique is applied we also consider that thevector v1 in the test pair is a unit of the randomsequence but the vector v2 is obtained by single rightcyclic shift among state variables of the vector v1. The latter means that not an each testpair v1, v2 can be applied in the frame of the LOS technique. In that case we first suggestderiving a ROBDD representation of all robust PDF test pairs for each product (of theEquivalent Normal Form) that generates test pairs. Then we derive prime products foreach function represented by a ROBDD. After that we correct prime products in orderto provide existence of test pairs in the frame of the LOS technique.Consider ENF products containing the literal representing the path ƒ. In line withtheorems 1, 2 [4] such products may originate robust PDF test pairs. Find all robust testpairs both for rising and falling transitions of the given path originated by one productof ENF [4]. For that we have to find product K that does not contain repeated variablexi. Analyzing ENF we don't pay attention to index sequences of literals representingpaths of the circuit. All roots of the special equation [4] D = 0 are represented asROBDD R. R is compact description of a disjoint sum of products (DSoP). Exclude thevariable xi from K and obtain the product K*. Represent the expression K*&DSoP asROBDD R*. Each path of R* from the root till the 1 terminal node represents theproduct corresponding to 2n−r−1 robust test pairs consisting of neighboring Booleanvectors. Here r is a rank of the product originated by the R* path and n is the number ofENF variables.Extract from the R* sum of all prime products and denote it as a SoPP. Any productof the SoPP represents conditions for forming test pairs: each test pair must have samevalues a) among variables of K* (theorems 1, 2, point 4, [4]) and b) among subset of therest variables (except xi) which provide orthogonality to products of the set K (theorems1, 2, point 3[4]). Notice that all minimal subsets are represented with prime products ofthe SoPP and we need them all in order to keep all test pairs. Experimental resultsshowed that SoPPs as a rule are rather simple.Let Kj be the product of the SoPP. Consider the following proposals.Proposal 1. Product Kj from the SoPP with literals yk yk +1 ( ykyk +1 ), ki-1, doesnot originate robust test pairs (if k = n, then k+1 = 1).Proof. Really both vectors v1, v2 must turn the product Kj into the 1 but it isimpossible if the Kj contains literals ykyk+1 ( ykyk+1 ), ki-1, as v2 is obtained from v1by single right cyclic shift among state variables. The proposal is proved.Proposal 2. The product Kj from the SoPP with literals yi−1yi+1 (yi−1yi+1) does notoriginate robust test pairs. If i = n we should consider literals yn−1y1 (yn−1y1), if i = 1 -literals yny2 ( yny2 ).Proof. Really both vectors v1, v2 must turn the product Kj into the 1 and at the sametime provide the value change of the variable yi. But it is impossible if the Kj containsabove mentioned literals as v2 is obtained from v1 by single right cyclic shift amongstate variables. The proposal is proved.If a product K* in accordance with proposals 1 and 2 does not originate robust testpairs it must be excluded from the consideration. Consider K* that may originate robusttest pairs.Find the proper R* and the SoPP. Exclude from the SoPP products which don'toriginate robust test pairs. Denote the result as the SoPP*. Consider the SoPP* and findall test pairs originated by these products when the LOS technique is used. Representthem as a ROBDD R(Kj). For that we have to do the following.1. If a literal yk−1 is absent in the Kj from the SoPP* but a literal yk is present, ki, k-1i then add the literal yk−1 into the Kj so that signs of inversions of both these literalsare the same (if k = 1, then k − 1 = n). This procedure provides turning the product Kjinto the 1 by both vectors v1, v2 when the LOS technique is used.Recall that any product Kj does not contain the variable yi. Add this variable to generaterobust test pair providing the state variable value change.2. If variables yi−1, yi+1 are both present in the Kj add the variable yi with the samesign of inversion that the variable yi+1 has.3. If the variable yi+1 is present in the Kj but yi−1 is absent add the variable yi with thesame sign of inversion that the variable yi+1 has and add yi−1 with the opposite sign ofinversion.4. If the variable yi+1 is absent in the Kj but yi−1 is present add variables yi, yi+1 withthe opposite sign of inversion that the variable yi−1 has.5. If variables yi−1, yi+1 are absent in the product Kj we generate two products fromthe Kj. One is obtained by appending yi yi+1 without an inversion and the variable yi−1with an inversion. Another one by appending yi yi+1 with an inversion and yi−1 withoutan inversion.If i = n (i = 1) the similar 2−5 conditions may be formulated for variables yn−1, y1(yn, y2).Points 2−5 provide conditions for turning the product Kj into the 1 on vectors v1, v2and for the value change of the state variable yi in the test pair. After executing points1−5 for all products of the SoPP* we obtain the SoP*. We should additionally checkproducts of the SoP* against proposals 1, 2, because of boundary conditions may not besatisfied after appending some variables in points 1−5. After exclusion someincompatible products we obtain SoP**. Its products may not be prime products buteach of them provides generation of robust test pairs which turns into the 1corresponding product of the SoPP*.Execute disjunction of all SoPs** corresponding to different ENF products relatedto the path ƒ and represent this disjunction as a ROBDD Rα.It should be noted that in special case, when n≤3 (number of state variables is lessthan or equal to 3) all observabilities are equal to 0 because of incompatibility withproposals 1, 2.Theorem 1. When using the LOS technique the robust test pair exists if and only ifthe vector v1 is absorbed with a product contained in the ROBDD Rƒ.Proof. Let the vector v1 be absorbed with one product K from the DSoPcorresponding to the Rƒ. Show that v1 forms the robust test pair when the LOS techniqueis used. From the construction of the DSoP we conclude that the variable yi changes itsvalue to opposite one on the vector v2. As the K is absorbed by at least one product fromthe SoPP* (proper Kj) then vectors v1, v2 keep values of variables of the product K*(theorems 1, 2, point 4) and vectors v1, v2 are orthogonal to the set K (theorems 1, 2,point 3). It means that v1 and v2 form robust PDF test pair together.Let we have the robust test pair so that the vector v2 is built in the frame of the LOStechnique. Show that the vector v1 of this test pair is absorbed with a product from theDSoP corresponding to the Rƒ. The construction of the ROBDD corresponding to the Rƒlet us forming v2 from any possible v1: we have in the proper SoP** all necessaryminimal subsets of variables for providing the orthogonality to products of the set K.The ROBDD Rƒ contains functions represented by all necessary SoPs** andconsequently v1 is absorbed with a product of the DSoP of the Rƒ. The theorem isproved.Using Rƒ and the probability distribution of input and state variables we maycalculate a probability of the robust PDF manifestation (observability estimation) alongthe path ƒ.We can calculate observability estimation Po(LOS) of the state variable yi for onecircuit output by deriving ROBDDs for each path started at yi and terminated at thiscircuit output. For that we must summarize observability estimations for each pathcorresponding to the state variable and the circuit output as products representing testpairs for different paths terminated at one output are orthogonal.To obtain more representative results we should calculate average observabilityestimation Po,avg(LOS) of the state variable yi per all circuit outputs. In the similar way itis possible to calculate observability estimations for all state variables of the sequentialcircuit. We have got the following experimental results.2. Experimental resultsThe suggested approach is based on ENF analysis and ROBDD application. ENF isvery complicate formula for real circuits. It is possible to use OR-AND trees to presentall paths of a circuit C [5], one OR-AND tree for each output of a combinational part ofa sequential circuit. These trees were used for finding estimations for benchmarks of theTable.Experimental results of observability estimations for ISCAS89 benchmarks setCircuit Inputs Outputs State Variables Po,avg(LOS)*10000s208 11 2 Y_8; Y_7; Y_4; Y_3; Y_2;Y_1; Y_6; Y_50; 0; 21; 25; 20; 53;0; 4;s298 3 6 G18; G14; G12; G10; G11;G13; G23; G22; G15; G20;G16; G19; G21; G170; 41; 24; 51; 14;27; 83; 63; 62; 0;4; 0; 4; 0;s344 9 11 ACVQN0; CT0; CT1; CT2;MRVQN0; MRVQN1;MRVQN2; MRVQN3; AX0;AX1; ACVQN1; AX2;ACVQN2; AX3; ACVQN311; 110; 24; 52;2; 24;12; 24; 43;42; 5; 48;7; 49; 10;s349 9 11 CT2; CT0; CT1; MRVQN0;MRVQN1; MRVQN2;MRVQN3; AX0; ACVQN0;AX1; ACVQN1; AX2;ACVQN2; AX3; ACVQN375; 52; 6; 2;24; 24;24; 39; 12;42; 5; 42;5; 48; 5;T a b l e c o n t i n u e dCircuit Inputs Outputs State Variables Po,avg(LOS)*10000s382 3 6 OLATCH_G1L; C3_Q2;UC_17; UC_9; UC_10;UC_11; UC_8; TESTL;UC_18; UC_19; UC_16;C3_Q1; C3_Q0; C3_Q3; FML;OLATCH_FEL;OLATCH_G2L;OLATCH_R1L;OLATCH_Y2L;OLATCHVUC_5;OLATCHVUC_60; 28;25; 6; 0;18; 7; 51;2; 9; 6;15; 21; 18; 46;32;0;0; 0;0;0;s386 7 7 v7; v9; v8; v10; v12; v11 0; 6; 0; 54; 0; 2s400 3 6 OLATCH_G2L;OLATCH_FEL; FML; C3_Q3;TESTL; UC_8; UC_9; UC_10;UC_11; UC_16; UC_17;UC_18; UC_19; C3_Q2;C3_Q1; C3_Q0;OLATCH_Y2L;OLATCHVUC_5;OLATCH_G1L;OLATCHVUC_6;OLATCH_R1L0;33; 46; 23;48; 4; 6; 0;18; 4; 23;2; 9; 25;15; 29;0;0;0;0;0;s444 3 6 G27; G24; G19; G22; G20;G18; G15; G31; G14; G11;G12; G13; G16; G17; G21;G23; G29; G25; G28; G30;G260; 41; 16; 17; 16;6; 3; 46; 2; 3;6; 17; 9; 24; 27;46; 0; 0; 0; 0;0s510 19 7 st_0; st_1; st_3; st_4; st_5;st_20; 0; 0; 24; 24;24s526 3 6 G25; G13; G19; G11; G10;G14; G15; G16; G30; G17;G18; G12; G21; G20; G29;G22; G27; G23; G26; G28;G240; 50; 3; 23; 14;0; 0; 14; 61; 6;27; 39; 37; 8; 46;68; 0; 0; 0; 0;0s526n 3 6 G23; G13; G19; G11; G10;G14; G15; G16; G30; G17;G18; G12; G21; G20; G29;G22; G24; G25; G26; G27;G280; 52; 2; 23; 17;12; 6; 20; 64; 7;42; 62; 44; 8; 46;35; 0; 0; 0; 0;0s820 18 19 G42; G41; G39; G40; G38 0; 2; 0; 33; 0s832 18 19 G42; G41; G39; G40; G38 0; 0; 0; 33; 0s953 16 23 ReWhBufHS1; TgWhBufHS1;SeOutAvHS1; LdProgHS1;State_3; State_1; State_0;State_2; State_5; State_4;Mode2HS1; ReRtTSHS1;ShftIRHS1; NewTrHS1;Mode1HS1; ShftORHS1;ActRtHS1; Mode0HS1;TxHInHS1; LxHInHS1;NewLineHS1; ActBmHS1;GoBmHS1; LoadOHHS1;DumpIHS1; SeFullOHS1;GoRtHS1; LoadIHHS1; Se-FullIHS10; 0;0; 0;5; 8; 2;2; 6; 13;0; 0;0; 0;0; 0;0; 0;0; 0;0; 0;0; 0;0; 0;0; 0;0Flip-flops corresponding to state variables with low Po,avg(LOS) can be selected forincluding them in enhanced scan chains. The additional investigations are necessary forchoosing the threshold values for Po,avg.ConclusionThe method of observability estimation based on probability calculation of robustPDF manifestation of all paths connected with a state variable in the frame of the LOStechnique was developed. It allows grading state variables and including ones with lowPo,avg(LOS) in enhanced scan chains.

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