PROCEEDINGS
OF THE TOMSK POLYTECHNIC INSTITUTE NAMED AFTER S. M. KIROV,
ORDER OF THE OCTOBER REVOLUTION AND ORDER OF THE RED BANNER OF LABOR

Vol. 294

1976

ANALYSIS OF METHODS FOR AUTOMATED TEST SYNTHESIS

P. P. GRIGOR'EV, N. P. BAIDA

(Submitted by the scientific seminar of the Department of Computer Engineering)

The greatest efficiency of checks in the program control of digital devices is achieved by solving the following principal problems [1]:

1. Constructing a mathematical model of the device being controlled that makes it possible to find a minimal set of input actions with which a specified completeness of checking or localization of faults can be guaranteed.

2. Developing methods for finding the indicated set of input actions, using the mathematical model and not requiring enumeration of all possible variants of faults, since such enumeration for complex devices is difficult even when high-speed digital computers are used.

3. Ordering the sequence of input actions found for the given device in order to optimize the control procedure.

4. Developing technical means for implementing the checks found and for analyzing their results (developing devices that generate test sequences of input signals, and indicator devices).

While the solution of the third and fourth problems presents no special difficulties, the solution of the second problem and of the first problem associated with it encounters considerable difficulties.

The main reason for the difficulty of solving the first and second problems of test synthesis for digital devices is the high dimensionality of these problems. There are two sources of high dimensionality: the large number of all possible input actions (input patterns or input sequences) and the large number of all possible faults, especially multiple faults. Moreover, the amount of difficulty depends substantially on the type of circuits that make up the digital device (whether they are combinational or sequential). The problems of test synthesis have been solved to a greater extent for combinational circuits.

Combinational Circuits

There are three approaches to solving the problems of test synthesis for combinational circuits: structural, functional, and analytical [2]. When the functional approach is used, it is assumed that a list of stable logical faults is given, and a fault-function table (FFT) is constructed. In this table, for all possible patterns, the value of the output signals of the fault-free

circuits and circuits corresponding to each fault from the given list. TFNs are the initial material for obtaining test input sets.

The method has a number of advantages. Its universality makes it possible to solve a variety of problems: to obtain strictly minimal sets of diagnosing and checking tests, to detect and localize faults in digital block objects, to obtain a minimal number of control points, etc. The method is fully formalized and can be easily implemented on a digital computer.

However, the excessive bulkiness of the algorithms does not allow this method to be used for circuits having more than 8–10 inputs and 100 elements, even with machine implementation.

Nevertheless, this method is widely used for automated test synthesis for simple circuits and in combination with other methods of test synthesis. All existing simple algorithms for test synthesis by this method can be reduced to four [3], of which the algorithm proposed by S. V. Yablonskii [4] has major advantages, since it makes it possible to obtain tests with a very small spread in test length. The essence of the algorithm is as follows:

1. From the TFN an expression is constructed, called by S. V. Yablonskii an “expression of the PΣ form.”

2. In PΣ, a set is selected that occurs in the greatest number of factors (if there are several such factors, one of them is selected).

3. From the expression PΣ, the factors that include this set are crossed out.

For the remaining part of PΣ, the procedure is repeated until all factors have been crossed out.

This algorithm, in combination with the Seshu and Freeman algorithm [5], was used by V. A. Danilchenko for automated synthesis of tests for digital computers, the description complexity of which amounts to \(4 \cdot 10^3\) letters.

In the structural approach [2], the basis for constructing tests is the logical circuit of the device. The basic concept explaining the essence of this approach is the concept of sensitization. Moreover, it is necessary to distinguish between local and global sensitization. The concept of local sensitization is applicable to an individual logical component of a circuit. Suppose that a logical component realizes some Boolean function \(f(x_1, \ldots, x_n)\) of \(n\) arguments. The input \(x_i\) is sensitive (or the function \(f(x_1, \ldots, x_n)\) is sensitive to the input variable \(x_i\)) under the set \(\delta_i = x_1^{\alpha_1} x_2^{\alpha_2} \ldots x_n^{\alpha_n}\), where \(\alpha = 0\) or \(\alpha = 1\), if

\[ f(x_1^{\alpha_1}, \ldots, x_i^{\alpha_i}, \ldots, x_n^{\alpha_n}) \ne f(x_1^{\alpha_1}, \ldots, \bar{x}_i^{\alpha_i}, \ldots, x_n^{\alpha_n}), \]

i.e., a change in the value of the variable \(x_i\) leads to a change in the value of the output of the logical component. The concept of global sensitization is applied to the circuit as a whole. A circuit is sensitive to the input variable \(x_i\) under the set \(\delta_i = x_1^{\alpha_1}, \ldots, x_i^{\alpha_i}, \ldots, x_n^{\alpha_n}\), if a change in the value of the variable \(x_i\) leads to a change in the signal at one of the outputs of the circuit. The concept of sensitization for a certain internal line of a circuit is reduced to the concept of sensitization of an input variable. Suppose that a cut is made at the place of the line \(a_i\), and the part of the circuit for which \(a_i\) is an output is discarded. Now \(a_i\) is an input variable, and the above definition of sensitization can be applied to it. Having ensured sensitization of the circuit to the output of the given element, it is possible to check it by means of a set of elementary tests of elements.

A large number of algorithms for the structural approach to test synthesis are known in the literature. It should be noted that, whereas in the functional approach there is a certain stabilization in the definitions used in synthesis, in assessments of the advantages and disadvantages of the approach, in the structural approach the opposite is observed: there are no identical definitions (in the works of Eldred and Roth [6]—the path-activation method; among a number of Soviet authors—the method of essential paths [7], the method of ascent and descent to the outputs and inputs of a circuit [8], etc.). The situation is analogous with assessments of the advantages and disadvantages of the method.

Most of the algorithms for automated test synthesis proposed in the literature are either insufficiently formalized for implementation on a computer, or have been applied to circuits with significant restrictions (circuits without redundancy, non-reconvergent circuits, and others), or are too complex and cannot be applied to large circuits (several dozen inputs and several hundred elements). Among algorithms that to a considerable extent overcome these shortcomings one may name the algorithm described in [2]. The algorithm is applicable to the synthesis of a locally optimal set of checking tests for combinational circuits without branching. The algorithm is easily implemented on a computer and is applicable to large circuits.

Another algorithm for automated test synthesis is the algorithm proposed in [9]. In developing the algorithm, the principal results of the works of Amar and Armstrong [10, 11] were used.

The essence of the method consists in activating a path from the input of a circuit to its output. The scheme of the algorithm for finding test sets for a given path is as follows:

1. It is assumed that the given path has been activated and that the components of the path have been set to the values P0 or P1. For unset inputs, such values are assigned for which the path becomes active.

2. If there are actively set components with unset inputs, then their inputs are set. If the set input values for an unset component determine its value, then the component is set according to these values. Only input components of inactively set components remain unset.

3. If contradictions are obtained at step 2, then the path cannot be activated for the given value and one should proceed to another value of it, or, if all values have been exhausted, to another path.

4. \(j := 1\).

5. If at level \(\kappa - j\) there are no inactively set components, then proceed to step 9.

6. A binary matrix \(A_{\kappa-j}\) is formed, whose columns correspond to the inactively set components of level \(\kappa-j\), and whose rows correspond to the input components for the column components. The matrix element \(a_{pq} = 1\) if component \(q\) corresponds to the column; otherwise \(a_{pq} = 0\).

7. The operator \(\Sigma(A_{\kappa-j})\) is computed in order to obtain the next solution. If there is no solution, proceed to step 10.

8. The components corresponding to the rows of the solution under the operator \(\Sigma(A_{\kappa-j})\) are assigned the values of the corresponding components of the columns of the matrix \(A_{\kappa-j}\). Step 2 is performed. If a contradiction is obtained, then the components set in this step are made unset and the procedure goes to step 7.

9. \(j := j + 1\). If \(j \ne \kappa\), then proceed to step 6; if \(j = \kappa\), then a test set has been obtained, i.e., all inputs of the circuit determine the test set; in this case the unset inputs may be assigned any value. Exit from the algorithm.

1. If $j = 1$, then the path cannot be activated for this value of it, or for any other path.

2. The settings of the components set by the operator $\Sigma(A_{k-j}),\ j := j - 1$ are removed, and the transition is made to step 7. With the aid of this algorithm, tests were synthesized [9] for a real circuit having 34 inputs, 57 components, and 88 paths. The program occupies 500 cells of the RAM of the Razdan-3 computer, and the solution time is 70 sec. However, this algorithm is effective for circuits in which the number of paths is much smaller than the number of all possible input combinations.

The third approach to automated test synthesis is the analytical one. This line of work was initiated by Armstrong’s papers [11], in which he proposed a structural-analytical description of a circuit in the form of an equivalent normal form (ENF) of the circuit output function. The essence of the method is as follows:

1. The ENF of the circuit is constructed.
2. On the basis of Armstrong’s theorem, a test for the circuit is found.

Armstrong’s theorem states the following: “A certain test for a letter appearing in the ENF activates the corresponding path in the circuit. Thus, if one can choose a certain set of letters corresponding to paths which, taken together, contain all the vertices of the circuit, and if one can find a certain set of tests that checks at least one occurrence of each letter for faults ($\equiv 1$) and ($\equiv 0$), then this set of tests detects any fault in the circuit.”

In his work Armstrong assumed that the ENF method is an algorithm and can be programmed and used in automated test synthesis. But this method has a significant drawback: it is applicable to circuits with a limited number of branches, and for large circuits encountered in practice the number of occurrences of letters becomes so large that it is difficult to process on a digital computer. The advantage of this method is the possibility of analyzing the behavior of the circuit simultaneously for several sets of faults, which reduces the bulk of the computations performed in constructing tests.

In subsequent works [6, 7] the ENF method underwent a number of changes. It was shown that, in Armstrong’s formulation, it does not always make it possible to construct tests for circuits, and, accordingly, after this shortcoming was eliminated, the method became more universal and applicable for finding tests on a digital computer.

The equivalent normal form is a disjunction of ENF letters. Each ENF letter consists of an input variable with an index, which is a sequence of the numbers of the elements through which the signal passes from the input denoted by this variable to the output of the circuit. The developed technique for automated test synthesis [14] first provides for constructing, on the basis of ENF analysis, tests for single-output combinational subcircuits (fragments) into which the tested multi-output circuit is preliminarily divided, and then obtaining combined tests for the entire circuit.

The initial data for constructing the ENF are information about which logical functions are implemented by the elements of the fragment, and how these elements are connected with one another, with the input and output of the fragment. In preparing the initial data, the circuit is divided into fragments, and the elements of the fragments are numbered consecutively with octal numbers; the first number is assigned to the output element of the fragment, and the inputs of the fragment are denoted by Latin letters without indices.

The algorithm for constructing the DNF of the output function of a fragment is based on the substitution principle, which consists in the following: into the expression for the output function of the fragment’s output element, written with respect to the inputs, one successively substitutes expressions representing the output functions of the corresponding elements of the fragment, likewise written with respect to the inputs of these elements. The substitution process ends when an expression has been obtained for the output function of the fragment’s output element that depends only on the input variables of the fragment, i.e., contains no digits.

A drawback of this algorithm is its large memory consumption, even when synthesizing tests for circuits of medium complexity.

Recently, graph-analytic methods of test synthesis have become widespread. The essence of these methods is as follows: a combinational circuit is represented in the form of a Boolean graph. The initial information for test synthesis is either an incidence matrix [1] or a path matrix. One of the algorithms using the graph-analytic method is the algorithm proposed by Mikoni [15].

The proposed method for synthesizing checking tests (CT) is based on the following principle:

A CT test for a circuit must detect faults of all logical elements included in the given circuit.

All faults of a logical element are detected by its minimal test. Consequently, a checking test for a combinational circuit can be constructed on the basis of a composition of minimal tests of logical elements. In doing so, the following conditions must be observed. For the element being checked, it is necessary not only to construct all test patterns from its minimal test, but also to ensure that the fault detected by each pattern affects the monitored output of the circuit. Thus, in order to obtain a monitored test of a circuit, it is necessary to know the minimal tests (MT) of the logical elements of the circuit and the paths along which faults of the elements propagate to the outputs of the circuit. The MT of an element is determined by its logical function, and the paths of fault propagation are determined by the structure of the connections of the logical elements in the circuit.

A combinational circuit is represented as a Boolean graph. The graph is specified in the form of a path matrix. On the basis of the path matrix, two matrices of controlling chains, \(C\) and \(C_d\), are constructed: the direct and the supplementary. The direct and supplementary matrices of controlling chains contain the necessary and supplementary information for constructing all variants of checking and diagnostic tests. The method is specially oriented toward the use of a digital computer, since the computation of tests is based on a matrix method of computation.

The method is applicable only to combinational circuits consisting of elements that implement monotone and inverse functions.

Sequential circuits

As was mentioned above, the problem of test synthesis for sequential circuits is more difficult than test synthesis for combinational circuits. A formal approach to this problem is to try to develop an algorithm in exactly the same way as was done for combinational circuits.

This approach did not have particular success (except in the case of very small sequential circuits) because of the following difficulties. First, every possible checking input, as a rule, must be computed for every possible state of the circuit. Consequently,

each memory element contained in the circuit doubles the amount of computation required to find a test.

Secondly, there is the problem of initial setting. Before applying a certain test to a sequential circuit, it is necessary to set it to a known fixed state, or, in the worst case, we must know what state it is in. An alternative approach consists in having special circuits for carrying out such an operation. For all these reasons, algorithmic methods have not been particularly successful for large sequential circuits.

The second approach consists in physically opening the feedback circuits of the object during its checking [6], i.e., transforming the circuit into a combinational one.

This approach held promise for synchronous circuits; however, there are difficulties in applying it to asynchronous circuits.

Finally, heuristic methods have been developed for sequential circuits. These methods can be used for fairly large circuits. They are applicable to both synchronous and asynchronous circuits. However, they in no way guarantee the obtaining of optimal checking sequences. In fact, they may even fail to yield a complete checking sequence. As a typical example of the algorithmic approach one may cite the works of Podge and McCluskey [6]. The beginning of the heuristic approach was laid by the works of Seshu [16]. Among recent works devoted to automated test synthesis, work [17] may be named. The method of test synthesis implemented in [17] is based on the principle of forming a test sequence by means of logical modeling and local optimization, first described by Seshu and Freeman [5]. Method [17] is intended for implementation on the M-220 electronic digital computer with a main-memory capacity of 16K words. The method provides synthesis and analysis of tests for circuits containing up to 1000 logic elements of the types AND, OR, AND-NOT, OR-NOT, with a total number of specified faults up to 1500.

Conclusions

1. Despite the relatively large number of algorithms for automated test synthesis, the problem of automated test synthesis requires further development.

2. Of all the approaches to automated test synthesis, the structural approach to synthesis should be noted.

3. The authors consider the use of graph theory for automated test synthesis to be promising.

4. In synthesizing tests for sequential circuits, the greatest results have been achieved with the aid of heuristic methods.

REFERENCES

1. Detection and correction of errors in discrete devices. Edited by V. S. Tolstyakov. Moscow, “Sovetskoe radio,” 1972.

2. S. E. Enin. Method for constructing a locally optimal set of checking tests for combinational circuits. In: Computing Technology and Machine Building. Minsk, ITK AN BSSR, 1971.

3. V. A. Danilchenko. Minimization of checking tests. Comparison of algorithm efficiency. In: Computing Technology in Machine Building. Sverdlovsk, UPI Publishing House, 1971.

4. I. A. Chegis, S. V. Yablonskii. Logical methods for the control of electrical circuits. Proceedings of the V. A. Steklov Mathematical Institute, vol. 51. USSR Academy of Sciences Publishing House, 1958.

5. S. Seshu, D. Freeman. The diagnosis of a synchronous Sequential Switching Systems, TRE Trans on El Computers, EC-11 (4), 1962.

1. G. Chzhen, E. Menning, G. Metz. Diagnosis of Failures in Digital Computing Systems. Moscow, “Mir,” 1972.

2. P. P. Parkhomenko. Basic problems of technical diagnostics. In: Technical Diagnostics. Moscow, “Nauka,” 1972.

3. G. A. Mironov, D. E. Fedotova. Compilation of tests for logic circuits. In: Digital Computing Technology and Programming. Issue 3. Moscow, “Sov. Radio,” 1967.

4. E. A. Lazaren. An algorithm for finding tests for the control and diagnosis of large combinational circuits. Questions of Radio Electronics, EVT series, 1970, No. 10.

5. V. Atan, N. Candulmanu. Diagnosis of Large Combinations Networks. IEEE Trans. on El. Comp., EC-16, 1967.

6. D. Armstrong. On Finding a Nearly Minimal Set of Fault Detection Tests. IEEE Trans. on El. Comp., EC-15, 1966.

7. V. P. Chilulis. On the construction of tests for monitoring combinational circuits. Automation and Remote Control, 1970, No. 10.

8. R. S. Goldman, V. P. Chilulis. On the diagnosis of faults in combinational circuits. Automation and Remote Control, 1971, No. 3.

9. V. S. Kretov. Estimation of the complexity of the structural-analytical description of circuits in equivalent normal form. Questions of Radio Electronics. EVT series. 1972, No. 10.

10. S. V. Mikoni. A method for constructing tests for combinational circuits. Automation and Computer Engineering, 1969, No. 9.

11. S. Seshu. On an Improved Diagnosis Program. IEEE Trans. on Electronic Computers, EC-14 (1), 1965.

12. V. M. Karasik, P. P. Aleksakhina, M. P. Atureva, N. D. Romanchikova. A system for automatic synthesis and analysis of tests for asynchronous sequential circuits. Questions of Radio Electronics, EVT series, 1972, No. 3.