A method for constructing logic networks allowing~short single diagnostic tests

K. A. Popkov

Prikladnaâ diskretnaâ matematika, no. 4 (2019), pp. 38-57.

Résumé

Let $D^B(f)$ be the least length of a single diagnostic test for irredundant logic networks consisting of logic gates in a functionally complete basis $B$, implementing given Boolean function $f$, and having at most one fixed type fault at inputs or outputs of gates. Let $D^B(n)=\max D^B(f)$, where the maximum is taken over all Boolean functions $f$ in $n$ variables. Consider the bases $B_{(1)}=\{x_1 x_2 x_3\vee\overline x_1\overline x_2\overline x_3,\overline x\}$, $B_{(2)}=\{x\,x\oplus y,1\}$, $B_{(3)}=\{\eta(\tilde x^4),x_1\sim x_2,\overline x,0\}$, where $\eta(\tilde x^4)$ is an arbitrary non-self-dual Boolean function taking the value $\alpha$ on the tuple $(\alpha,\alpha,\alpha,\alpha)$ and the value $\overline\alpha$ on all $4$-tuples adjacent with it, for each $\alpha\in\{0,1\}$; $B_{(4)}=\{x\,\overline x,x\oplus y\oplus z\}$. The following inequalities are obtained: 1) $D^{B_{(1)}}(n)\leqslant 3$ for each $n\geqslant 0$ under stuck-at-$0$ faults at inputs and outputs of gates; 2) $D^{B_{(2)}}(n)\leqslant 3$ for each $n\geqslant 0$ under stuck-at-$1$ faults at outputs of gates; 3) $D^{B_{(3)}}(n)\leqslant 4$ for each $n\geqslant 0$ under stuck-at-$0$ and stuck-at-$1$ faults at inputs and outputs of gates; 4) $D^{B_{(4)}}(n)\leqslant 4$ for each $n\geqslant 1$ under stuck-at-$0$ and stuck-at-$1$ faults at outputs of gates; 5) $D^{B_{(2)}}(n)\leqslant 3$ for each $n\geqslant 0$ under inverse faults at inputs and outputs of gates. All inequalities are proved by the method of synthesis of logic networks implementing given Boolean functions and allowing short single diagnostic tests, based on the existence of short single fault detection tests for networks in the same basis under the same faults.

Détail

Keywords: logic network, Boolean function, stuck-at fault, inverse fault, single fault detection test, single diagnostic test.

Bibliographie

[1] Chegis I. A., Yablonskiy S. V., “Logical methods of control of work of electric circuits”, Trudy Mat. Inst. Steklov, 51, 1958, 270–360 (in Russian) | MR | Zbl

[2] Yablonskiy S. V., “Reliability and verification of control systems”, Materialy Vsesoyuznogo seminara po diskretnoy matematike i ee prilozheniyam (Moscow, 31 Jan.–2 Feb. 1984), MSU Publ., M., 1986, 7–12 (in Russian)

[3] Yablonskiy S. V., “Some questions of reliability and verification of control systems”, Matematicheskie Voprosy Kibernetiki, 1, Nauka Publ., M., 1988, 5–25 (in Russian)

[4] Red'kin N. P., Circuits Reliability and Diagnostics, MSU Publ., M., 1992, 192 pp. (in Russian)

[5] Red'kin N. P., “On single diagnostic tests for one-type stuck-at faults at outputs of logic gates”, Vestnik MSU, Ser. 1, 1992, no. 5, 43–46 (in Russian)

[6] Popkov K. A., “On the exact value of the length of the minimal single diagnostic test for a particular class of circuits”, J. Appl. Industr. Math., 11:3 (2017), 431–443 | DOI | MR | Zbl

[7] Popkov K. A., “On single diagnostic tests for logic networks in the Zhegalkin basis”, Izvestiya Vysshikh Uchebnykh Zavedeniy. Povolzhskiy Region. Fiziko-Matematicheskie Nauki, 2016, no. 3, 3–18 (in Russian)

[8] Popkov K. A., “Lower bounds for lengths of single tests for Boolean circuits”, Discrete Math. Appl., 29:1 (2019), 23–33 | DOI | DOI | MR | Zbl

[9] Romanov D. S., Romanova E. Yu., “A method of synthesis of irredundant logic networks allowing short single diagnostic tests under stuck-at faults at outputs of gates”, Izvestiya Vysshikh Uchebnykh Zavedeniy. Povolzhskiy Region. Fiziko-Matematicheskie Nauki, 2016, no. 2, 87–102 (in Russian)

[10] Popkov K. A., “Short single tests for logic networks under arbitrary stuck-at faults at outputs of gates”, Diskretnaya Matematika, 30:3 (2018), 99–116 (in Russian) | DOI | MR

[11] Kovatsenko S. V., “Synthesis of easily testable logic networks in the Zhegalkin basis for inverse faults”, Vestnik MSU, Ser. 15, 2000, no. 2, 45–47 (in Russian) | Zbl

[12] Romanov D. S., “A method of synthesis of irredundant logic networks in the standard basis allowing single diagnostic tests of the length two”, Izvestiya Vysshikh Uchebnykh Zavedeniy. Povolzhskiy Region. Fiziko-Matematicheskie Nauki, 2016, no. 3, 56–72 (in Russian) | MR | Zbl

[13] Romanov D. S., “A method of synthesis of irredundant logic networks in the Zhegalkin basis allowing single diagnostic tests of the length one”, Izvestiya Vysshikh Uchebnykh Zavedeniy. Povolzhskiy Region. Fiziko-Matematicheskie Nauki, 2015, no. 4, 38–54 (in Russian)

[14] Lyubich I. G., Romanov D. S., “Single fault diagnostic tests for inversion faults of circuit elements over some bases”, Comput. Math. and Modelling, 30:1 (2019), 36–47 | DOI | MR | Zbl

[15] Red'kin N. P., “On schemes permitting short single diagnostic tests”, Discrete Math. Appl., 1:3, 263–270

[16] Popkov K. A., “Synthesis of easily testable logic networks under one-type stuck-at faults at inputs and outputs of gates”, Intellektual'nye Sistemy. Teoriya i Prilozheniya, 23:3 (2018), 131–147 (in Russian)

[17] Popkov K. A., “Synthesis of easily testable logic networks under arbitrary stuck-at faults at inputs and outputs of gates”, Prikladnaya Diskretnaya Matematika, 2019, no. 43, 78–100 (in Russian)

[18] Yablonskiy S. V., Introduction to Discrete Mathematics, Nauka Publ., M., 1986, 384 pp. (in Russian) | MR

[19] Borodina Yu. V., “Circuits admitting single-fault tests of length 1 under constant faults at outputs of elements”, Mosc. Univ. Mat. Bull., 63:5 (2008), 202–204 | DOI | MR | Zbl