Simplification of fully delay testable combinational circuits and finding of PDF test pairs.pdf Path delay fault (PDF) model is considered as more preferable at delay testing. In accordance with the conditions of fault manifestation, single PDFs are divided into robust testable faults and non robust testable faults. PDF is robust testable if there is a test pair fault manifestation of which does not depend on delays of other circuit paths. PDF is non robust testable if fault manifestation is possible only when all other paths of a circuit are fault-free. PDF testing has become a very important problem along with development of nanometer technologies. It is very important to provide testability for robust PDF during circuit design. Circuits derived from ROBDDs are usually implemented using multiplexors (MUXs). Their testability is investigated under different fault models [1-4] but the approaches suggested do not provide 100% testability. In [5] simple transformation of a circuit is suggested that guarantees 100% testability for both single stuck-at fault (SAF) and PDF models. These circuits are derived from ROBDDs using multiplexors. A size of a circuit is proportional to the given ROBDD size. The major disadvantage of this approach is the use of additional input. In [6] it is shown that a circuit constructed from BDD by covering CLBs guarantees 100% testability for robust PDFs without an additional input. In [7] the combinational circuits constructed from ROBDDs by Invert-AND-XOR implementation of the formula fv = xj*'=0 © xj*'=1 corresponding to an internal node v are considered. In this formula, the operation "©" is implemented by XOR gate. It is revealed that each path delay fault of the resulted circuit manifests itself either as robust testable fault or as validatable non robust testable one. When applying the test pairs in the definite order, we may detect any PDF of the circuit. This means that the circuits considered guarantee 100% testability for PDFs without an additional input. In this paper the combinational circuits constructed from ROBDDs by covering some internal nodes with Invert-AND-OR sub-circuits implementing the formula fv = xf* 0 vxj* 1 and covering the rest internal nodes with Invert-AND-XOR sub-circuits implementing the formula fv = xj*'=0 © xj*' = are considered. When using this approach, it is possible to cut path lengths of the combinational circuits and cut the number of OR, AND, NOT gates if we implement XOR as a sub-circuit from these gates. It is revealed that PDFs in the resulted circuits (similar circuits are considered in [7]) manifest themselves either as robust testable or as validatable non robust testable ones. When applying test pairs in the definite order, we may detect any PDF of the circuit. This means that the circuits suggested in this paper (as the circuits in [7]) guarantee 100% testability for PDFs without an additional input. The experimental results showed that the suggested circuits as a rule were simpler than the ones in [Ibid.]. In Section II the problem of deriving the proper combinational circuits is discussed. In Section III an algorithm of ROBDD internal node analysis is suggested. In Section IV the properties of the formula originated by the circuit are investigated. In Section V algorithms of finding test pairs on which PDF manifests itself either as robust testable or validatable non robust testable one are proposed. In Section VI the experimental results are given. 1. A combinational circuit design It is well known that Binary Decision Diagram (BDD) is a directed acyclic graph based on Shannon decomposition in each non terminal node v: Г rX; =0 rX; =1 fv = X;fv V X;fv , fv' = 0 = fv (x1,..., X- = O- Xn X fV=1 = fv (x1,..., xi = Xn ). Here fv is the function corresponding to the node v, dashed edge points to fV' 0 and bold edge points to fV' =1 (Fig. 1). BDD is called ordered if variables are encountered in the same order on all paths connecting the BDD root with the terminal node. BDD is reduced if it does not contain either isomorphic sub-graphs or nodes such that fX = fX . Reduced and ordered BDD (ROBDD) is a canonical representation of Boolean function for the chosen order of variables [8]. Any path that connects the BDD root with the 1 terminal node creates the product of the Disjoint Sum of Products (DSoP) of a function f represented by this ROBDD. DSoP is a sum of products in which any two product cubes do not intersect. Fig. 1. Gate implementation of the formula fr° fT Fig. 2. Gate implementation of the formula fv=xjr°®^frl Let F - {fj,..., fm}, be a system of Boolean functions describing combinational circuit behavior. Derive ROBDD using the same order of variables for each Boolean function from F. Join isomorphic sub-graphs in the different ROBDDs. Combine the 1 terminal nodes of the different ROBDDs into one 1 terminal node and their 0 terminal nodes into one 0 terminal node. As a result, we obtain the graph with m roots and two terminal nodes. This graph represents the system of m Boolean functions. It is called Shared ROBDD. Without loss of generality, we further consider systems with one function. The ROBDD for one output Boolean function is shown in Fig. 1. Find the product (cube) of the DSoP for each path connecting the ROBDD root with the 1 terminal node. The DSoP of the function f is as follows. f - x^ x2 x3 v хц x2 x3 x4 x5 v хц x2 x3 x4 x5 v хц x2 x4 x5 v v хц х2 х4 х5 v хц х2 х4 х5 v хц х2 х4 х5 v хц х2 х3 х4 х5 v v хц х2 х3 х4 х5 v хц х2 х3 х5. Eliminate from the ROBDD all edges connected with the 0 terminal node and obtain the ROBDD representing combinational circuit behavior. Call this ROBDD as a Circuit ROBDD. Cover each node of the Circuit ROBDD with either Invert-AND-OR sub-circuit implementing the formula fv = xf=0 Vx,fvx'=1 or Invert-AND-XOR sub-circuit implementing the formula fv = ~,fvx'=0 © x,fvx'=1. Note that both these formulae represent the same Boolean function. The condition f*'=0 Ф f*' =1is satisfied for each internal node v of the ROBDD. This means that there exists the Boolean vector у on which either fx' =1(y) = 1 and fx'=°(y) = 0 or fx'=1(y) = 0 and fx'=°(y) = 1. If for the internal node v there exists the Boolean vector у on which fx 1(y) = 1 and fx °(y) = 0 and the Boolean vector S on which fx (5) = 0 and fvx'=°(5) = 1 we cover this node with Invert-AND-OR sub-circuit (Fig. 2). Unfortunately sometimes only one condition pointed above is satisfied. The latter is possible when one of the functions fx'=0, fx'=1 is implicant of another one: either fx'=0 < fx'=1 or fx'=1 < fx'=0. In that case, we cover the corresponding internal node with Invert-AND-XOR sub-circuit (Fig. 3). 2. Internal node analysis Verify one of conditions fx'=1(y) = 1, fx'=0(y) = 0 and fx'=1(5) = 0, fx'=0(5) = 1. Let us verify the first condition. For that we execute the following steps. Algorithm 1. Form the ROBDD implementing the function fx=1 for the given internal node v. Call it as a ROBDD (fx=1). Its root is the internal node in which the bold edge from v runs. The terminal nodes of the ROBDD (fx=1) coincide with the terminal nodes of the ROBDD off When forming the ROBDD (fvx'=0), we do the same. Its root is the internal node in which the dashed edge from v runs. 2. To get the ROBDD (fvx'=0) we rearrange the terminal nodes of the ROBDD (fvx'=0). 3. Multiply the ROBDD (fx'=1) and the ROBDD (fx'=0). Denote the result as a ROBDD R*. 4. If the ROBDD R* is not empty, we consider any path from the R* root till its 1 terminal node. Note the corresponding product as k. The Boolean vector that turns k into 1 call the vector y. Note that the vector 5 may be found in the similar way, that is, by multiplication of the ROBDD (fx'=0) and the ROBDD (fx'=1). If the results of both multiplications are not empty we cover the internal node v with Invert-AND-OR sub-circuit. Otherwise, one of the functions fx' 1, fx' 0 is implicant of another one. In that case, we cover the internal node v with Invert-AND-XOR sub-circuit. Apply the suggested procedure for the ROBDD in Fig. 1. For right internal node marked x2 we have: fy^ = xg x4 x5 V xg x4 x5 V xg, fv 2 x4 x5 V x4 x5 . This means that /*2 1 is implicant of /^ 0. Consequently, we must cover the corresponding node with Invert-AND-XOR sub-circuit. For right internal node marked x3 we have: /v 3 - /v 3 - X4 X5 V X4 X5 . This means that /V3 is implicant of /,X3-0. Consequently, we must cover the corresponding node with Invert-AND-XOR sub-circuit. .^^fsop (- xj x2 x3 xj x2 x3 x4 x5 'v xj x2 x3 x4 x5 xj x2 x4 x5 'v 2 3 4 5 j 2 3 5 '^v Xо X^ xc Xо Xc. Л*2 *5 X\ Fig. 4. Circuit C For the rest internal nodes the results of both above mentioned multiplications are not empty. It means that the corresponding nodes may be covered with Invert-AND-OR sub-circuit. As a result of covering the circuit ROBDD we have combinational circuit C (Fig. 4). Derive the formula from circuit C substituting the proper gate functions for circuit internal variables and eliminating brackets. Literal permutations and any simplifications are forbidden. In obtained formula some products are connected each other with operation OR ( v ) others - with operation XOR (©). (As the products obtained in the course of substitutions are pairwise orthogonal, then the expressions like (a © b) v c is similar to the expression a © (b v c) and, consequently, brackets in both of them may be deleted). Call this formula as mixed SoP (MSoP). The formula is as follows: determines the corresponding path in circuit C. Moreover, the sequence of literals is also represented by the ROBDD path (Fig. 1). In [9] path delay faults are considered as temporary stuck-at faults of the corresponding ENF literals. This means that all literals satisfying to the same path are changed for the same constant. Instead of ENF of circuit C we may consider the MSoP created by circuit C. Note that for each literal of a MSoP product the brief information about the sequence is represented by the literals of this product forgoing to the considered literal. In order to find all MSoP products that contain the literal x, corresponding to the certain path a we need the following. Find ROBDD path s running from ROBDD root to node v marked with the literal x,. The bold edge corresponding to the beginning of the path a runs from the node v. Call the corresponding to the path s product as ks. Continue the ROBDD path s through the bold edge to the 1 terminal node of the ROBDD. Find all prolongations and consequently all products containing the literal x, corresponding to the beginning of the path a. These products comprise a set Ka [9]. Note that the products of the MSoP that contain the literal x corresponding to the path opposite to a have the same sub-product ks. Let the literal x, be equal to the constant 0 in each product of Ka. Theorem 1. The Boolean vector p is a test pattern for the fault x, = 0 in each product of Ka if it turns the certain product K from Ka into 1. Proof. As all products of the MSoP are pairwise orthogonal then K is the only product of the fault-free MSoP that is turned intolon the vector p. When x, is equal to 0 the fault MSoP is turned into 0 on the vector p. The theorem is proved. Let the literal x, be equal to the constant lin each product of Ka. Theorem 2. For the fault x, = 1 in each product of Ka there exists the test pattern p. Proof. Consider two cases. The first case. The literal x, corresponds to the input of Invert-AND-OR sub-circuit covering the internal node v marked with the variable x,. In that case, there exists the test pattern у that turns f x 1 into 1 and fx 0 into 0. Represent this test pattern with the product kY. Form the product kskY. Let the product obtained from kskY by adding arbitrary (n-1) literals except xi, xt be k* (y originates k*). Here n is a number of input variables of circuit C. Let vector p be represented by the product k*xt. This vector turns all products of Ka into 0. The rest of the products of fault-free MSoP are also turned into 0. When the MSoP is fault, that is, from each product of Ka the literal x, is excluded, one of such product is turned into1on p. This is the product K of the MSoP corresponding to the function fx 1 (the product K is originated by the product k of fx 1 MSoP, which is turned into 1 on y). f* 1 MSoP is formed by the ROBDD whose root is the node in which a bold edge runs from v. The product K is the only one product as all products of the MSoP are pairwise orthogonal. The second case. The literal x, corresponds the input of Invert-AND-XOR sub-circuit covering the internal node v marked with the variable x,. Consider the situation when there is no the test pattern у that turns fx 1 into 1 and fx 0 into 0. Then there exists the test pattern у that turns fx 1 into 1 and fx 0 into 1. Form the vector p in the above mentioned way. It turns into 1 the certain product from the MSoP namely the product K originated by the fx 0 MSoP (we take in mind the product k from the fx 0 MSoP which is turned into 1 on у). The vector p turns into 0 the rest products of the fault-free MSoP. Thus the vector p turns into 1 the fault-free MSoP. When the MSoP is fault, that is, from each product of Ka the literal x, is excluded, one of Ka products is turned into 1 on p (we take in mind the product K originated by the k from fx 1 MSoP which is turned into 1 on y). At the same time the vector p turns into 1 the product originated by fx 0 MSoP (we refer to the product from the fx MSoP which is turned into 1 on y). The vector y turns into 1 only one product from fx MSoP and only one product from fx = MSoP as all products of ft MSoP and fx MSoP are pairwise orthogonal. Thus, two products are turned into 1 in the fault MSoP. The rest of the products are turned into 0 on the vector p. As we use Invert-AND-XOR sub-circuit for covering the internal node v marked with xu then for the node v and the fault considered we have the expression: ke ( fx 1 © XifVx=0 ). After substitution of the vector p we get 1 © 1. This means that the vector p turns the fault MSoP into 0. Consequently, the vector p is a test pattern. The theorem is proved. Thus, both faults of the MSoP: x, = 0 in all products of Ka and x, = 1 in all products of Ka are detectable. 4. Finding test pairs for robust testable and validatable non robust testable faults Finding test pairs for robust testable and validatable non robust testable faults is based on the approach suggested in [7]. It is necessary to justify its application for the circuits that originate MSoPs instead of Reed-Muller expressions in [7]. In [9] the conditions of robust path delay fault manifestation for test pairs extracted from an ENF are formulated. The first condition is existence of a test pattern for the corresponding constant fault of the ENF literal. This test pattern is a vector v2 of a test pair. The next condition is: the variable x, that marks the node v takes the opposite values for vb v2 vectors. Evidently, (Section 3) both conditions are feasible for the considered faults of MSoP. Let k(u) be minimal cube covering vectors vb v2 of a test pair. Note as K the product that differs from the product K only by inversion of the variable x,. Remind that as we consider ROBDD, then for each node v the condition f*'=0 Ф f vx' =1 is executed. Let у be a test pattern on which these functions are different and fx J(y) = 1, fx=°(y) = 0. Represent this test pattern as we have done before with the product kY. Form the product kekY and k * in the above mentioned way. Theorem 3. The product k * represents the test pair of robust testable fault for the path a and its rising and falling transitions if the beginning of the path is marked with the literal x, and the condition fvx J(y) = 1, fx=0(y) = 0 is executed. Proof. The product xtk* represents the Boolean vector v2 that turns the product K from Ka into1. This means v2 is a test pattern for the fault x, = 0 in all products of Ka. Actually this vector turns fx 0 MSoP into 0 and turns fx 1 MSoP into 1. Moreover, this vector turns into 1 the only product K from Ka originated by fV 1 MSoP. Consequently, this vector turns the fault-free MSoP into 1on the same product K and only on this product. As well this vector turns the fault MSoP into 0. The product x,k* represents the vector v1 of the proper test pair. This vector is a test pattern for the fault x, = 1 in all products of Ka. Actually the vector vi turns fx=0 MSoP into 0 and turns fx' MSoP into 0. Consequently, the vector turns the fault-free MSoP into 0. At the same time this vector turs into 1the fault MSoP because it turns into 1 the product K and the product K* obtaind from K (K from Ka) when the considered fault occurs. The fault MSoP turns into 1 on the only product K*. Thus the vector represented by product xtk* is the vector v2 for rising transition of the path a and the vector represented by product xtk* is the vector v2 for the falling transition of the path a. Note that k(u) is orthogonal to all products of the MSoP except products of Ka. Actually k(u) is orthogonal to the products of the MSoP that does not contain sub-product ke. The product k(u) is also orthogonal to the products of the MsoP containing sub-product ke xt as kY is orthogonal to fx =0. Moreover, any product of the fault free MSoP does not contain repeated literals. Thus all conditions [9] of robust testable manifestation for rising and falling transition of the path a are fulfilled. The theorem is proved. Corollary. If there exist a vector у for which fVx J(y) = 1, fx=0(y) = 0 and a vector 5 for which fVx J(5) = 0, fVx=°(5) = 1, then for both paths that begin at the same input and marked with the literals xt and xt PDFs manifest themselves as robust testable for rising and falling transitions. Fig. 5 is an illustration of the above mentioned corollary. Note that sometimes only one condition pointed in the corollary is executed. Then the corresponding path has a test pair on which PDF manifests itself as robust testable one in both directions. This path must be tested first and then we proceed to test opposite path. Let opposite path be a. Let у be a Boolean vector on which the condition fVx J(y) = 1, fVx=°(y) = 1 is executed. The product k * is formed in the above mentioned way. Theorem 4. The product k* represents the test pair of non robust testable PDF for the path a and its rising and falling transitions if the beginning of the path is marked with the literal xt and the condition fVx J(y) = 1, fv'=0(y) = 1 is executed. Proof. The product xik* represents the Boolean vector v2 that turns the product K from Ka into 1. This means v2 is a test pattern for constant fault xt = 0 in all products of Ka. The product xik* represents vector v1 of this test pair. The test pair detects rising transition of the path a. Theorem 2 should be taken to conclude that v1 is a test pattern for the fault x' = 1 in all products of Ka. The latter means that v1 is as well as v2 for the fault x' = 1 in all products of Ka, that is, xik* is a test pattern for falling transition. Note that k(u) is orthogonal to all products of MSoP that does not contain sub-product ke. The product k(u) is not orthogonal to some product K' containing ke and x' as ky is not orthogonal to f^' 0. The theorem is proved. Thus when the conditions of the above mentioned corollary is not executed we have robust testable PDF for the path that begins at the input marked with the variable xi and validatable non robust testable PDF for the opposite path. Fig. 6 is illustration of robust testable PDF and validatable non robust testable PDF for paths that begin at the input marked with the variable xi. Remind that the product obtained from kekY by adding arbitrary (n-1) literals except xi, xt, represents the test pair either for robust testable PDF or for validatable non robust testable PDF. In the first case, the vector y, for which fx J(y) = 1, fx=0(y) = 0, is represented by any path from ROBDD R* obtained with the algorithm of Section III. In the second case, the vector y, for which fx 1 (y) = 1, fx 0 (y) = 1, is represented by any path of the ROBDD (fx=1) (ROBDD (fx=0)) that is an implicant of the ROBDD (fx=0)(ROBDD (fx=1)). The relation of implication is determined by the same algorithm. Note that the algorithm implementation has a polynomial complexity as the algorithm is based on multiplication of two ROBDDs extracted from the circuit ROBDD. Finding the vector у was out of consideration in the paper [7]. As for ke it is originated by the path a connecting the circuit ROBDD root corresponding to the path output and the internal node v corresponding to the path input. It means that algorithm of finding test pairs has a polynomial complexity. In order to detect validatable non robust PDF of the path and its rising and falling transitions, we must first deliver the test pair to detect robust testable PDF for the opposite path. If the opposite path is fault-free, we may detect validatable non robust PDF of rising and falling transitions of the considered path. 5. Experimental results In Table 1 the information about combinational circuits investigated (MCNC) is given. We have got representation of each combinational circuit by the Shared ROBDD using BuDDy system. For the Shared ROBDD the number of internal nodes are counted (second column of Table 2). T a b l e 1 Benchmark description benchmark inputs outputs C3540 49 22 С1908 33 25 C1355 41 32 C880 62 26 pair 173 137 frg2 143 139 k2 45 45 x3 135 99 T a b l e 2 Benchmark results benchmark node count or nodes percentage old area new area area reduction C3540 672 435 513528 76,4% 5379480 3 325 368 39,2% С1908 49 323 39238 79,6% 394584 237 632 39,8% C1355 50 682 45393 89,6% 405456 223 884 44,8% C880 346 688 225196 67% 2773504 1 872 720 32,5% pair 51 414 790 1,5% 411312 408 152 0,8% frg2 1542 79 5,1% 12336 12 020 2,6% k2 698 341 48,9% 5584 4 220 24,4% x3 543 38 7% 4344 4 192 3,5% Then we found the nodes that may be covered by sub-circuit of Fig. 3 (third column of Table 2). The percentage of such sub-circuits among all ones was calculated (forth column of Table 2). We appreciated the complexity of the circuits obtained from the Shared ROBDD [9] by covering internal nodes with sub-circuit of Fig. 3 and the circuits obtained by the method suggested here. For that the numbers of two inputs and one input gates of the circuits are computed. The results are given in the sixth and seventh columns, correspondingly. The last column of Table 2 describes the simplification of circuits on account of using the suggested method (in percentage terms). We see that always more simple circuits are derived and often essential simplification is possible. Conclusion New synthesis method of fully delay testable circuits is suggested that as a rule derives more simple circuits of this kind than in [9]. The simplification is based on multiplications of sub-circuit ROBDDs (these operations have the polynomial complexity). The circuits obtained originate new type of formulae called MSoPs in which products are separated either by symbol "©" or "v". The investigation of the formulae properties insured formulating the algorithms of finding PDF test pairs that also have a polynomial complexity.

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