PROCEEDINGS
OF THE TOMSK POLYTECHNIC INSTITUTE
OF THE ORDER OF THE OCTOBER REVOLUTION AND THE ORDER OF THE RED BANNER OF LABOR
named after S. M. Kirov

Vol. 294　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　1976

FORMALIZED DESCRIPTION OF A DIGITAL DEVICE AND ITS MODEL

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

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

Known methods of analysis [1, 2] of digital devices (DD) use a representation of the object under study in the form of a synchronous or asynchronous model, which does not always make it possible to solve pressing practical problems connected with evaluating the design quality of complex DDs.

In the present work, questions of studying DDs by means of pulse-potential asynchronous modeling are considered, which makes it possible to significantly broaden the class of objects under study.

Basic Definitions

First of all, we shall give definitions of a logical network, of which a DD is a realization.

We shall call a logical network a set of elements together with a set of connections. The elements of the network are \((K, l)\)-poles—elementary converters of discrete information. A connection is understood to be the identification of two poles of the network. Two output poles of an element cannot be connected. In the network, the sets \(X\) of its input poles and \(Y\) of its output poles are distinguished.

The variables assigned to the input poles of the network will be called its input variables, and those assigned to the output poles—output variables. A set of values of the input variables of the network will be called an input vector, and a set of values of the output variables—an output vector.

Finding the sequence of output vectors into which the network transforms a given sequence of input vectors is called modeling the network.

As noted in [2], all modeling methods are divided into two classes: binary and ternary modeling, each of which, in turn, may be either synchronous or asynchronous. With the aid of the chosen modeling, one may completely investigate the object by transforming all possible sequences of input vectors into sequences of output vectors. It is possible to investigate the object partially, by transforming into outputs a certain number of input sequences selected in a probabilistic manner.

In the present work, a method of binary asynchronous modeling is considered. Such a method makes it possible to model the broadest class of objects, including pulse-potential ones.

Modeling the Transient Process

We shall call a transient process the process that takes place in a network over the time interval between the moment an input vector enters the network and the moment a new (stable) output vector is obtained.

Modeling the transient process means obtaining the order and results of the firing of elements during the transient process.

Let \(r(\alpha_i)\) be the delay of element \(\alpha_i\). Let also \(\alpha_j\) be the element in the network with the minimum delay \(\tau_0\). Then the delays of the elements can conventionally be expressed by the integers

\[ \left[\frac{\tau(\alpha_i)}{\tau_0}\right], \quad i = 1, 2, \ldots \]

We shall consider that an element has fired if the value of the variable assigned to its output pole has changed. Obviously, if an element has fired, then there will be an element that fired \(\tau(\alpha_i)\) earlier, whose output pole is connected to one of the input poles of \(\alpha_i\).

In pulse-potential networks, pulses are represented by potential signals of length 0.5.

Let \(A\) be the set of network elements that must fire after the expiration of their assigned delays. Then the algorithm for modeling the transient process will be as follows:

1. Enter into \(A\) the network elements that must fire as a result of changes in the values of the input variables of the network.

2. If \(A = \varnothing\), then go to step 4; otherwise decrease by 1 the delays of all elements in \(A\).

3. Search in \(A\) for elements with zero delay. If there are none, then go to step 2; otherwise change the values of the output variables of the elements found, remove them from \(A\), after which add to \(A\) the elements that must fire as a result of the firing of the removed elements. Go to step 2.

4. The values of the output variables of the elements that are output variables of the network form the required output vector.

It should be noted that \(A\) may simultaneously contain several identical elements, but with different delays.

The algorithm is presented in the form of a program in the LYAPAS language [3]. The program works with potential and pulse-potential networks consisting of elements implementing the functions AND, OR, NOT AND, NOT OR, sum modulo 2, and equivalence of variables assigned to their input poles, as well as the elements three-input trigger, 0 → 1 difcept, 1 → 0 difcept, and delay.

Representations of Information in a Computer

In the machine, a network is specified by a complex \(B\), divided into subcomplexes numbered by the numbers \(0, 1, \ldots, n\); \(n\) is the number of elements of the network. The zero subcomplex specifies the partition of \(B\) into subcomplexes in such a way that its \(i\)-th element specifies the beginning of the \(i\)-th subcomplex. The cardinality of the zero subcomplex is \(n + 2\). The last element of the zero subcomplex specifies the cardinality of the complex \(B\). The first subcomplex of the complex \(B\) specifies the input pole of the counter, if it exists. The numbering of the remaining elements is arbitrary. The \(j\)-th subcomplex of the complex \(B\) specifies the \(j\)-th element of the network (the input poles of the network are conventionally considered elements (0,1)—poles). The first element of the subcomplex is called its header; in its first bit the value of the element’s output variable is recorded. In bits 8 through 16 the numerical value of the element’s delay is recorded, and in bits 17 through 22 the type of the element, where the input pole has

type 0, count input — 1, difcell \(1 \to 0\) — 2, difcell \(0 \to 1\) — 3, NOT-AND — 4, AND — 5, NOT-OR — 6, OR — 7, sum modulo two — 10, equivalence — 11, flip-flop — 12. Further, under the header, in arbitrary order, the numbers of the elements “feeding” the given element are listed (in digits from 0 to 15). In the subcomplex specifying a flip-flop, the number of the element feeding the one input is indicated first, the count input second, and the zero input third. Unused flip-flop inputs are marked by zeros.

The set \(A\) is specified by the complex \(\underline{A}\), consisting of the headers of the corresponding elements.

Modeling a faulty circuit — modnes

1. A network \(C\), consisting of OS and SK, is given. It is required to carry out potential-pulse asynchronous modeling of the network \(C\), when the latter contains faulty elements.

2. External operands:

\[ \alpha_\kappa : C, \]

\[ \beta_n \text{ — end of the working field,} \]

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

Subroutines: input, fault, double, model.

1. Modeling of the network is carried out twice. The first time the fault-free network is modeled. The correct state is stored. The investigated fault is introduced into the network, after which modeling of the faulty network is carried out.

4.

\[ * \; 054\; 001 \]

\[ \begin{aligned} \S\;0\;& a_\alpha + b_\alpha \Rightarrow a_0\ \beta - a_0 > 1 \Rightarrow a\\ & *\ \text{input}\ \alpha A //\ 0c1 \Rightarrow d \ne \to 1\ 7 \Rightarrow b \ne \to 2\\ & c \le \Rightarrow d \ne \to 1\\ & *\ \text{fault}\ \alpha A //\ 5 \Rightarrow b \ne \to 2 \to 4\\ \S\;1\;& *\ \text{double}\ \overline{\alpha cd}//!\\ \S\;2\;& *\ \text{model}\ \alpha \underline{A}\ 3ab//!\\ \S\;3\;& d_0\ \text{print}\ 03\\ \S\;4.& \end{aligned} \]

Formation of the set of changed inputs of the network — input

1. Find the set \(D\) of input variables of circuits \(C\) that have changed their value.

2. External operands:

\[ \alpha_\kappa :: C, \]

\[ \beta_\kappa :: D. \]

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

3.

\[ * \; 054\; 013 \]

\[ \begin{aligned} \S\;0\;& c_{20} - c_{26} \Rightarrow a\ 0a\ 0b\\ \S\;1\;& \Delta a\ \alpha_a \Rightarrow c\ a_c \land a_0 \to 2 \oplus c_{26}\ \vdash \to 3\\ \S\;2\;& a_c > 1 \oplus a_c \land c_1 \circ \to 1\ \alpha_c \Rightarrow \beta_b\ \Delta b \to 1\\ \S\;3\;& b \Rightarrow b_\beta. \end{aligned} \]

Formation of the set of faulty elements — fault

1. Find the set \(\varepsilon\) of faulty elements of the network \(C\).

2. External operands:

\[ \alpha_\kappa :: C, \]

\[ \beta_\kappa :: \underline{\varepsilon}. \]

Given: \(a_{\alpha},\ b_{\alpha},\ a_{\beta}\).

1. \(*\ 054\ 014\)

\[ \begin{aligned} \S\ 0\quad &0a\ 0c\ c_{5}\vee c_{6} => \underline{a}\\ \S\ 1\quad &\Delta a\ a_{\alpha}\oplus b_{\alpha}\circ\to 2\quad \alpha_{a} => b\ a_{b} > 11\\ &\wedge\ 77\oplus 1\circ\to 3a_{b}\wedge \underline{a}\circ\to 1\\ \S\ 3\quad &a_{b} => \beta_{c}\ \Delta c\to 1\\ \S\ 2\quad &c => b_{\beta}. \end{aligned} \]

Remembering the proper state of a circuit — duplicate

1. A network \(C\) is given, in some proper state. It is required to remember this state of the network.

2. External operands: \(\alpha_{n} :: C\)

\(\beta_{n}\) — the number of the bit position of the caps of the elements representing their state;

\(\gamma_{n}\) — the number of the bit position of the caps of the elements into which the values of the proper states of the elements are entered.

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

1. \(*\ 054\ 003\)

\[ \begin{aligned} \S\ 0\quad &0a\\ \S\ 1\quad &\Delta a\ a_{\alpha}\oplus b_{\alpha}\circ\to 3\quad a_{\alpha} => b\ a_{b}\wedge c_{\beta}\circ\to 2\\ & a_{b}\vee c_{\gamma} => a_{b}\to 1\\ \S\ 2\quad &a_{b}\vee c_{\gamma}\oplus c_{\gamma} => a_{b}\to 1\\ \S\ 3.\quad & \end{aligned} \]

Potential-pulse simulation — model

1. A set \(D\) of input variables of the network \(C\) that have changed their value is given. It is required to carry out potential-pulse asynchronous simulation of the network \(C\).

2. External operands:

\[ \alpha_{\kappa} :: C, \qquad \beta_{\kappa} :: D, \]

\(\gamma_{r}\) — an additional output pole, realized when memory is insufficient;

\(\delta_{n}\) — the maximum possible capacity of the complex \(\beta\);

\(\varepsilon_{n}\) — simulation mode.

Note. This program permits simulation of networks with faults. In this case \(\varepsilon = 5\). When simulating a proper network, \(\varepsilon\) must be equal to 7.

Given \(a_{\alpha},\ b_{\alpha},\ a_{\beta},\ b_{\beta}\).

Subprograms: element, parity.

1. The algorithm is given above.

2. \(*\ 054005\)

\[ \begin{aligned} \S\ 0\quad &a_{\beta}+\delta => a_{0}\to 5\\ \S\ 1\quad &\Delta a\oplus b_{\beta}\circ\to 4\quad 0f\ \beta_{a}\to c_{20} => \beta_{a} => \underline{a} > 17\wedge 177\\ &|\to 3\beta_{a}\wedge F_{7} => b+1 => i\ a_{b} => c\ a_{c}\oplus c_{1} => \alpha_{c} > 11\wedge 77\\ &\circ\to 2-4|\to 2\beta_{a}+c_{11} => \beta_{a}\wedge c_{10}|\to 2\\ &c_{20}+\beta_{a} => a1 - f\to 3\\ \S\ 2\quad &\Delta c\oplus \alpha\circ\to 1\quad \bar{a}_{c} > 22\circ\to 1 => d\ 1 => f => i\\ &*\ \text{element}\ ad10_{\delta}\ /\ 0j\\ \S\ 10\quad &\alpha_{d} => d\ a_{d} => \underline{a} \end{aligned} \]

\[ \begin{gathered} * \ \text{parity } Aa\kappa \ // \ j \oplus \kappa \mid \to 2\\ \S\ 3\quad a \Rightarrow a_e\quad \Delta e \Rightarrow b_0 - \delta \mid \to \gamma\quad f \circ \to 1 \to 2\\ \S\ 4\quad a_\beta \Leftarrow a_0\quad b_0 \Rightarrow b_3\\ \S\ 5\quad 0b_0\quad 0l\quad 0a\ b_3 \circ \to 7 - 1 \Rightarrow c\\ \S\ 6\quad \Delta a \oplus c \circ \to 7\quad \beta_a > 11 \land 77 \circ \to 6 - 4 \mid \to 6\beta_a\\ \qquad \Leftarrow \beta_c\ \Delta a\ \Delta c \to 6\\ \S\ 7\quad 0a\quad b_3 \mid \to 1. \end{gathered} \]

Modeling an element — element

1. Let \(i\) be the number of an element of the network \(C\), the variables of whose input poles have changed their value. It is required to determine whether its output variable will change value.

2. External operands:

\[ \begin{gathered} a_\kappa :: c,\\ [\beta_i] = i, \end{gathered} \]

\(\gamma\) — an additional output pole, realized if the value of the output variable does not change.

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

Subprograms: diffchain, NOT AND, NOT OR, two-input, equal, trigger.

3.

4.

\[ * \ 054007 \]

\[ \begin{aligned} \S\ 0\quad & a_\beta \Rightarrow a\quad 0ba_a > 11 \land 77 - 3 \circ \to 2 - 1 \circ \to 1\\ &\qquad - 1 \circ \to 4 - 1 \circ \to 3 - 1 \circ \to 6 - 1 \circ \to 5 - 1 \circ \to 7 - 1 \circ \to 10 \to 11\\ \S\ 1\quad & \Delta b\\ \S\ 2\quad & *\ \text{diffchain } a\beta\ 12\ 13\ //\\ \S\ 3\quad & \Delta b\\ \S\ 4\quad & *\ \text{NOT AND } a\beta\ 12\ 13\ //\\ \S\ 5\quad & \Delta b\\ \S\ 6\quad & *\ \text{NOT OR } a\beta\ 12\ 13\ //\\ \S\ 7\quad & *\ \text{two-input } a\beta\ 12\ 13\ //\\ \S\ 10\quad & *\ \text{equal } a\beta\ 12\ 13\ //\\ \S\ 21\quad & \to \gamma\\ \S\ 11\quad & *\ \text{trigger } a\beta\ 12\ 13\ 21\ //\ a_a \land c_\delta \circ \to 20 \to \gamma\\ \S\ 12\quad & b \mid \to 15 \to 14\\ \S\ 13\quad & b \circ \to 15\\ \S\ 14\quad & a_a \land c_\delta \mid \to 17 \to 16\\ \S\ 15\quad & a_a \land c_\delta \circ \to 17\\ \S\ 16\quad & a_a \land c_1 \circ \to \gamma \to 20\\ \S\ 17\quad & a_a \land c_1 \mid \to \gamma\\ \S\ 20.\quad & \end{aligned} \]

Computing the value of an element’s output variable

1. Compute the value of the output variable of the \(i\)-th element of the network \(C\).

2. External operands:

\[ \begin{gathered} a_\kappa :: c;\\ [\beta_n] = i; \end{gathered} \]

\(\gamma\) — an additional output pole, realized if the value of the output variable is equal to 0;

\(\delta\) — an additional output pole, realized if the value of the output variable is equal to 1.

Given: \(a_a\).

3.

1. Diffchain

\[ \begin{gathered} *\,054002\\ \S\,0\ \alpha_\beta+1=>a\alpha_a\land F_7=>a\alpha_a=>a\alpha_a\land c_1\\ \circ\to\delta\to\gamma\\ \text{NOT AND} \end{gathered} \]

\[ \begin{gathered} *\,054004\\ \S\,0\ \alpha_\beta=>a\beta+1=>c\\ \S\,1\ \Delta a\oplus a_c\circ\to\gamma\alpha_a\land F_7\circ\to\gamma=>b\alpha_b=>b\alpha_b\land c_1|\to1\to\delta\\ \text{NOT AND, OR} \end{gathered} \]

\[ \begin{gathered} *\,054006\\ \S\,0\ \alpha_\beta=>a\beta+1=>c\\ \S\,1\ \Delta a\oplus a_c\circ\to\delta\alpha_a\land F_7\circ\to\delta=>b\alpha_b=>b\alpha_b\land c_1\circ\to1\to\gamma\\ \text{two-input modulo} \end{gathered} \]

\[ \begin{gathered} *\,054010\\ \S\,0\ \alpha_\beta+1=>a\beta+1=>c0a\\ \S\,1\ \alpha_a\land F_7\circ\to2=>b\alpha_b=>b\alpha_b\oplus\underline{a}=>\underline{a}\Delta a\oplus a_c|\to1\\ \S\,2\ a\land c_1\circ\to\gamma\to\delta.\\ \text{equal} \end{gathered} \]

\[ \begin{gathered} *\,054011\\ \S\,0\ \alpha_\beta=>a\beta+1=>c\overline{0}d\\ \S\,1\ \Delta a\oplus a_c\circ\to\delta\alpha_a\land F_7\circ\to\delta=>b x_b=>b\Delta d\circ\to2\\ \alpha_b\oplus \underline{a}\land c_1\circ\to1\to\gamma\\ \S\,2\ \alpha_b=>a\to1.\\ \text{trigger} \end{gathered} \]

\(\varepsilon\) is an additional output pole, realized if the output variable does not change its value.

\[ \begin{gathered} *\,054012\\ \S\,0\ \alpha_\beta=>a\overline{0}b\\ \S\,1\ \Delta a\Delta b\oplus3\circ\to\varepsilon\alpha_a\land F_7\circ\to1=>c\alpha_c=>c\\ \alpha_c\land c_1\circ\to1b\circ\to\gamma\oplus2\circ\to\delta. \end{gathered} \]

Finding the parity of the number of operations of an element — parity

1. A set \(\varepsilon\) of operated elements of the network \(C\) is given. It is required to determine the parity \(l\) of the number of operations of the element with number \(i\).

2. External operands:

\[ \begin{gathered} \alpha_k::\varepsilon;\\ \beta_n::i;\\ [\gamma_n]=l. \end{gathered} \]

Given: \(a_a,\ b_a\).

1. \(\qquad *\,050\ 777\)

\[ \begin{gathered} \S\,0\ 0a\overline{0}b\ \beta\land77=>a\\ \S\,1\ \Delta b\ b_a\circ\to2\alpha_\beta\ b\land77\oplus \underline{a}|\to1\Delta a\to1\\ \S\,2\ a\land1=>\gamma. \end{gathered} \]

REFERENCES

1. A. A. Utkin. Modeling of relay circuits. In the collection: “A logical language for representing algorithms for the synthesis of relay devices.” Moscow, Nauka, 1966.

2. Design of digital computers. Edited by S. A. Maiorov. Moscow, Vysshaya shkola, 1972.

3. A. D. Zakrevskii. Algorithms for the synthesis of discrete automata. Moscow, Nauka, 1971.