Volume 294　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　1976

A Universal Algorithm for Investigating Digital Devices with Hardware Monitoring

I. P. Abramov, N. P. Baida, Yu. M. Komarov, V. B. Lipskii,
V. M. Tanaseichuk

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

When investigating digital devices (DD) with hardware monitoring (HM) by the method of digital simulation [1], faults in the hardware can be specified by directed or probabilistic enumeration. However, in works [1, 2] only the algorithm of directed enumeration is considered in detail, suitable for simple DDs of the decoder, counter, adder, etc. type.

The present work considers the problem of developing a universal algorithm for investigating DDs with HM of arbitrary complexity by the probabilistic method on the basis of a formalized representation of the object in the form of a potential-pulse asynchronous model [3].

Basic Definitions

The object of our investigation is networks [4] that can be divided into two parts: the main network MN and the monitoring network (MNt). We shall conventionally assume that the network \(C\), consisting of MN and MNt, contains a single output pole \(y_1\), at which a function is realized that determines, with some reliability [5], the presence of a fault [6] in the network \(C\).

Denote by \(\underline{X}\), \(\underline{Y}\), and \(\underline{P}\) the sets of combinations of values of the input variables, output variables of the network \(C\), and output variables of the elements of the latter, respectively. The elements of \(\underline{X}\), \(\underline{Y}\), and \(\underline{P}\) will be called input vectors, output vectors, and complete internal states of the network \(C\).

The set of faults [6] of the network \(C\) will be denoted by \(N\), and the network \(C\) with fault \(n_j \in N\) by \(C_j\).

Definition. An input vector \(x_i \in \underline{X}\) reveals a fault \(n_j \in N\) from the complete internal state \(p_k \in \underline{P}\) if, under the action of \(x_j\), the networks \(C\) and \(C_j\) pass from one and the same complete internal state \(P_k\) into different complete internal states.

Denote by \(N^i_{p_k}\) the set of faults of the network \(C\) revealed by the input vector \(x_i\) from the complete internal state \(p_k\).

The Monitoring Function and Its Effectiveness

It is clear that the monitoring function \(L\) implements the mapping

\[ L:\underline{X} \times N' \times \underline{P} \to \{0,1\}, \quad N' = N \cup \{n_0\}, \]

where \(\times\) is the operation of the Cartesian product of sets, and \(n_0\) is a fictitious fault whose presence in network \(C\) does not disturb the correct operation of the latter.

The ideal checking function \(L\) is defined as follows:

\[ L(x_i,n'_j,p_k)=1 \leftrightarrow n'_j \in N^i_{p_k}. \]

Obviously,

\[ \forall x_i \in X\ \forall p_k \in P\ (L(x_i,n_0,p_k)=0). \]

Denote by \(L_1\) and \(L_0\) the regions of unit and zero values of the function \(L\).

Theorem. The ideal checking function cannot be practically implemented.

To prove the assertion, it is sufficient to indicate that a fault of type \(\equiv 0\) at the output of a checking network implementing any checking function cannot produce a unit value at this same output.

Definition. A checking function \(\widetilde{L}\) is called correct (real) if \(\widetilde{L} \supset L_0\), that is, if the region of its zero values contains the region of zero values of the corresponding ideal function.

Since checking networks implement correct checking functions, there arises a need to estimate the effectiveness of the latter [5, 7] for the purpose of the most advantageous use of the checking networks under consideration.

Quantitatively, the effectiveness \(K_{\widetilde{L}}\) of a correct checking function \(\widetilde{L}\) is found as follows:

\[ K_{\widetilde{L}}=\frac{\widetilde{L}_1}{L_1}, \tag{1} \]

where \(L\) is the region of unit values of this checking function under the assumption that it is ideal.

Obviously, for all correct checking functions \(K_{\widetilde{L}} < 1\).

The problem of finding the exact value of the effectiveness of a checking function can be solved using the following algorithm.

1. It is assumed that the checking function implemented by the given checking network is ideal. The set \(L_1\) is constructed.

2. For each element \(l_i \in L_1\), the network with the given checking network is simulated and the value of the checking-network output is checked. If a one is realized at the output of the checking network, then \(l_i\) is included in \(\widetilde{L}_1\); otherwise \(l_i\) is not included in \(\widetilde{L}_1\).

3. The effectiveness of the checking function is computed by formula (1).

For real networks, enumeration of all \(l_i \in L_1\), unfortunately, is impossible, and therefore the effectiveness of the checking function can be computed only approximately, by restricting consideration to \(l_i \in L_1^* \subset L_1\).

In this case the cardinality of the set \(L_1^*\) determines the accuracy with which the value of the approximate effectiveness of a correct checking function

\[ K_{\widetilde{L}}^*=\frac{\widetilde{L}_1^*}{L_1^*} \]

approaches the true value \(K_{\widetilde{L}}\).

In practice, less comprehensive effectiveness criteria are often required, for example, the effectiveness of detecting failures of multiplicity 1 in the OS, failures of multiplicity 2 in the OS and in the checking network, etc.

It is not difficult to see that all these criteria are special cases of the effectiveness of the control function and are obtained from the latter by imposing restrictions on the set \(N\).

The algorithm for finding the effectiveness of the control function is presented in the form of a program in the LYAPAS language [4]. The program has been debugged and tested on a number of real CUs with AC. A description of the program is given below.

Representation of Information in the Computer

The initial information for the program implementing the algorithm for determining the effectiveness of the control function is the complex \(A\), specifying the network under study, and the fault vector \(\varepsilon\). The complex \(A\) has the same structure as the analogous complex described in [3], but the following restrictions are imposed on the numbering order: the counting input, if it exists, must always have number 1; then, in order, the input poles, the principal elements of the OS, the principal elements of the CK, and, finally, the auxiliary elements of the OS and CK are numbered. An element is considered principal if faults are specified in it. Otherwise it is considered auxiliary. In addition, in the headers of subcomplexes the zero digit carries information about the state of the outputs of the corresponding elements at the preceding instant of time: a one in the 5th digit indicates that the element has failed; a one in the 6th digit indicates that the element has suffered a malfunction. A unit value of the 4th digit indicates that the output of the element under consideration is an output of the CK. The headers of the subcomplex principal elements have ones in the 3rd digit. The zero element of the complex \(A\) has also been changed. In digits 27 through 37 the number of the first element of the CK is recorded.

The fault vector \(\varepsilon\) is a Boolean vector having the following structure: digits 13 through 15 specify the multiplicity of failures in the OS, digits 16 through 20 specify the multiplicity of failures in the CK, digits 21 through 23 specify the multiplicity of malfunctions in the OS, digits 24 through 26 specify the multiplicity of malfunctions in the CK, and digits 27 through 37 specify the sample size, equal to the cardinality of the set.

Subroutine Library

Study of the effectiveness of the CK.

1. Given: a network \(C\), consisting of the OS and CK, and a fault vector \(\varepsilon\). It is required to find the value of the effectiveness of the control function of the \(CK\), for the faults specified by the vector \(\varepsilon\).

2. External operands:

\[ \alpha_k :: C; \]

\[ \beta_n :: \varepsilon; \]

\[ \gamma_n \text{ — end of the working field.} \]

Note: memory allocation is performed automatically, and the end of the working field makes it possible to detect an emergency situation arising when memory is insufficient.

Specified: \(\alpha_a, \varepsilon_a\).

Subroutines: preparation, modver.

1. The algorithm is set out above.

4.

\[ * \ 052\ 001 \]

\[ \$ \ 0 \qquad *\ \text{preparation } \alpha\ a\ || \]

\[ **\ \text{modver } \alpha\ \beta\ \gamma\ \underline{a}\ ||; \]

Preparation for modeling — preparation.

1. A network \(C\), consisting of OS and CK, is given. It is required to determine the number of basic elements in the network, the number of input poles of the network, and the number of the output element of CK.

2. External operands:

\[ a_k :: C; \]

\(\beta_n\) — a Boolean vector having the following structure: in positions 5 through 15 the number of the output element of the circuit is recorded, in positions 16 through 26 the number of input poles is recorded, and in positions 27 through 37 the number of basic elements of the circuit is recorded.

Given: \(a_\alpha, \beta_\alpha\).

4.

\[ * \ 052\ 004 \]

\[ \begin{aligned} \S\ 0\quad &0a\quad 0c\quad 0\beta\\ \S\ 1\quad &\Delta a a_\alpha => b \oplus b_\alpha \circ \to 2x_b \land c_4 \vdash \to 2x_b > 11 \land 77 \vdash \to 1\Delta c \to 1\\ \S\ 2\quad &a < 11 \lor c < 11 \lor \beta => \beta \overline{0}a\\ \S\ 3\quad &\Delta a a_\alpha => b \oplus b_\alpha \circ \to 4a_b \land c_3 \circ \to 3\Delta\beta \to 3\\ \S\ 4\quad &\Delta\beta . \end{aligned} \]

Probabilistic modeling — modver.

1. Given: a network \(C\), consisting of OS and CK, and a fault vector \(v\). It is required to carry out modeling of the network \(C\), repeatedly applying a random input action to its inputs and introducing into it, in random fashion, a fault of the specified multiplicity and specified type (failures, malfunctions). Count the number of simulations for which a one was realized at the output of CK.

2. External operands:

\[ \begin{aligned} a_k &:: C;\\ \beta_n &:: v;\\ \gamma_n &\text{ — end of the working field;}\\ \delta_n &\text{ — number of basic elements of OS and CK, number of input poles}\\ &\quad \text{and number of the element that is the output of CK.} \end{aligned} \]

Given: \(a_\alpha, v_\alpha\).

Subprograms: udastan, neispravnost, genvkhos, modnes.

1. The algorithm is set forth above.

4.

\[ * \ 052\ 010 \]

\[ \begin{aligned} \S\ 0\quad &a_\alpha + b_\alpha -- \gamma \circ \to 1\quad 0b \to 4\\ \S\ 1\quad &a_\alpha => a\overline{0}b\beta \land f_7 => a\\ &\delta > 22 \land f_7 => c\\ \S\ 2\quad &\Delta b \oplus a \circ \to 4\\ &*\ \text{udastan } a\ /\ a => x_a\gamma => b x_c => \alpha\\ &*\ \text{neispravnost } \alpha\beta\delta\ /\ 0a_0\\ &*\ \text{genvkhos } \alpha\beta\ /\\ &*\ \text{modnes } ab\ /\ b \circ \to 3x_d \land c_1 \circ \to 2\\ &\beta + c_{12} => \overline{\beta} \to 2\\ \S\ 3\quad &\Delta b\gamma => b\beta - c_{37} => \beta \land f_7 \vdash \to 2\quad 0\beta\\ \S\ 4\quad &a => a_0 . \end{aligned} \]

Removal of investigated faults — uneis.

1. A network \(C\) is given, in which the faulty elements are marked. It is required to remove the faults from the network.

1. External operands:

\[ \alpha_k :: C. \]

Given: \(a_\alpha, \varepsilon_\alpha\).

1. Zeros are entered in the 5th and 6th digits of the headers of all elements of the circuit, which indicates the absence of faults in the corresponding elements.

4.

\[ * \ 052\ 011 \]

\[ \begin{aligned} \S\ 0\quad &0a\ c_5 \vee c_6 \dashv \Rightarrow a\\ \S\ 1\quad &\Delta a\ \alpha_a \Rightarrow b \oplus b_a \circ \to 2.\\ &\alpha_b \wedge a \Rightarrow \alpha_b \to 1\\ \S\ 2.\quad& \end{aligned} \]

Fault assignment — fault.

1. Given: a network \(C\), consisting of OC and CK, a fault vector \(\underline{b}\) and a variable \(\underline{a}\), carrying information about the network. It is required to introduce into the network \(C\), at random, failures and faults of a specified multiplicity.

2. External operands:

\[ \begin{aligned} \alpha_k &:: C;\\ \beta_n &:: \underline{b};\\ \gamma_n &:: \underline{a}. \end{aligned} \]

Given: \(a_\alpha, b_\alpha\).

Subroutines: failures, faults.

4.

\[ * \ 052\ 005 \]

\[ \begin{aligned} \S\ 0\quad &\beta > 11 \wedge 77 \dashv \to 1\beta > 17 \wedge 77 \circ \to 3 \to 2\\ \S\ 1\quad &*\ \text{faults}\ \alpha\beta\gamma // \beta > 17 \wedge 77 \circ \to 3\\ \S\ 2\quad &*\ \text{failures}\ \alpha\beta\gamma //\\ \S\ 3.\quad& \end{aligned} \]

Failure assignment — failures.

1. Given: a network \(C\), consisting of OC and CK, a fault vector \(\underline{b}\) and a vector \(\underline{a}\), carrying information about the network. It is required, according to a specified multiplicity of failures, to mark at random the “failed” elements of OC and CK or OC and CK.

2. External operands:

\[ \begin{aligned} \alpha_k &:: C;\\ \beta_n &:: \varepsilon\\ \gamma_n &:: \underline{a}. \end{aligned} \]

Given: \(a_\alpha, \varepsilon_\alpha\).

Subroutines: random.

4.

\[ * \ 052\ 0c2 \]

\[ \begin{aligned} \S\ 0\quad &0a\gamma \wedge f_7 \Rightarrow a\gamma > 11 \wedge f_7 + 2 \Rightarrow b_{\chi 0} \wedge f_7\\ &\Rightarrow c \Rightarrow d\beta > 11 \wedge 7 \Rightarrow e \circ \to 1 \ne \to 2\\ \S\ 1\quad &0ad \Rightarrow a\bar{b} \Rightarrow c\beta > 14 \wedge 7 \Rightarrow e\\ &\circ \to 3 \ne \to 2 \to 3\\ \S\ 2\quad &*\ \text{random}\ acb \parallel a_b \Rightarrow c\alpha_c \wedge c_b \dashv \to 2\\ &\alpha_c \vee c_b \Rightarrow \alpha_c \Delta a \oplus e \dashv \to 2!\\ \S\ 3.\quad& \end{aligned} \]

Failure assignment — failures.

1. Given: a network \(C\), consisting of OS and CK, a fault vector \(v\), and a variable \(a\) carrying information about the network \(C\). It is required, for the specified multiplicity of failures, to mark the “failed” elements OS, CK, or OS and CK.

2. External operands:

\[ \begin{aligned} \alpha_k &:: C;\\ \beta_n &:: v;\\ \gamma_n &:: a. \end{aligned} \]

Specified: \(a_\alpha,\ b_\alpha\).

Subprograms: random.

4.

\[ * \ 052\ 003 \]

\[ \begin{aligned} \S\ 0\quad &0a\gamma \land f_7 \Rightarrow a\gamma > 11 \land f_7 + 2 \Rightarrow b\\ & a_0 \land \overline{f}_7 \Rightarrow c \Rightarrow d\beta > 17 \land 7 \Rightarrow e\\ & \circ \to 1 \ne \to 2\\[2mm] \S\ 1\quad &0ad \Rightarrow ab \Rightarrow c\beta > 22 \land 7 \Rightarrow e \circ \to 3 \ne \to 2 \to 3\\ \S\ 2\quad &* \ \text{random}\ acb \parallel \alpha_b \Rightarrow c\\ & \alpha_c \land c_5 \vdash \to 2x_c \lor c_5 \Rightarrow a_c \Delta a \oplus e \vdash \to 2!\\[2mm] \S\ 3.& \end{aligned} \]

Random-number generator — random.

1. Given two numbers \(v\) and \(c\). It is required to obtain, at random, a number \(d\) from the interval \([v,c]\).

2. External operands:

\[ \begin{aligned} [\alpha_n] &= v;\\ [\beta_n] &= c;\\ [\gamma_n] &= d. \end{aligned} \]

1. Random numbers are obtained using the random-number sensor \(ya\).

4.

\[ * \ 052\ 007 \]

\[ \S\ 0\quad \alpha - \overline{\beta}xya + \beta \Rightarrow \gamma. \]

Generation of input states — genvkhos.

1. Given: a network \(C\) and a variable \(a\) carrying information about the network. It is required to obtain an input vector at random.

2. External operands:

\[ \begin{aligned} \alpha_k &:: C;\\ \beta_n &:: a. \end{aligned} \]

Specified: \(a_\alpha,\ b_\alpha\).

Subprograms: random.

4.

\[ * \ 052\ 006 \]

\[ \begin{aligned} \S\ 0\quad &\bigcirc\, a\beta > 11 \land f_7 \Rightarrow a \circ \to 3\Delta a \ *\ \text{random}\ a \bigcirc b \ //\\ \S\ 1\quad &a_a \Rightarrow b\ c_1 \neg \land a_b \Rightarrow a_b \Delta a \oplus a \vdash \to 1 \overline{\bigcirc}\, a\\ \S\ 2\quad &\Delta a \oplus b \circ \to 3 \ *\ \text{random}\ a\ 1\ c \ //\ a_c \Rightarrow b\\ & a_b \lor c_1 \Rightarrow a_b \to 2\\[2mm] \S\ 3\quad &a_1 \Rightarrow b\ a_b > 11 \land f_7 \circ \to 4a_b \lor c_1 \Rightarrow a_b\\ \S\ 4.& \end{aligned} \]

Conclusions

1. The concept of a control function has been introduced, generalizing possible methods for evaluating the effectiveness of control.

2. A universal algorithm has been proposed for simulating a digital device with hardware control in order to estimate quantitative values of criteria for the quality of control.

3. The algorithm is presented in the form of a program in the LYAPAS language and has been debugged on the M-220 computer.

References

1. N. P. Baida, L. A. Lyadunkina, V. M. Razin. Investigation of digital devices with hardware control by the method of digital simulation. Izvestiya LETI. Issue 118, Part I, Leningrad, 1972.

2. N. P. Baida, L. A. Lyadunkina, V. M. Razin. Simulation of digital devices with hardware control in the LYAPAS language. Izvestiya TPI, Vol. 277 (in press).

3. I. P. Abramov, N. P. Baida, Yu. M. Komarov, V. B. Lipskii, V. M. Razin. Formalized description of a digital device and its model. The present collection.

4. A. D. Zakrevskii. Algorithms for the Synthesis of Discrete Automata. Moscow, “Nauka,” 1971.

5. N. P. Baida, V. M. Razin. On quality indicators of hardware-control circuits of digital devices. Reliability and Quality Control. (Supplement to the journal Standards and Quality), 1972, No. 6.

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

7. N. P. Baida. Efficiency and reliability of hardware control of digital devices. Izvestiya TPI, Vol. 202, Tomsk, TSU Publishing House, 1973.