Single fault detection tests for logic networks of AND, NOT gates

K. A. Popkov

Prikladnaâ diskretnaâ matematika, no. 4 (2017), pp. 66-88.

Résumé

Let $D_1(f)$ ($D_0(f)$) be the least length of a fault detection test for irredundant logic networks consisting of logic gates in the basis $\{\,\neg\}$, implementing a given Boolean function $f(x_1,\ldots,x_n)$, and having at most one stuck-at-1 (stuck-at-0 respectively) fault on outputs of the logic gates. Let $f_1=x_i$; $f_2=0, \overline{x_i}$, or $x_{i_1}^{\sigma_1}\ x_{i_2}\dots\ x_{i_k}$; $f_3=\overline{x_{i_1}}\\overline{x_{i_2}}\ x_{i_3}\\dots\ x_{i_k}$ or $\underbrace{(\dots((}_{k-1}x_{i_1}^{\sigma_1}\ x_{i_2})^{\sigma_2}\ x_{i_3})^{\sigma_3}\\dots\ x_{i_k})^{\sigma_k}$; $f_4=x_{i_1}^{\sigma_1}\\dots\ x_{i_k}^{\sigma_k}$; $f_5=\underbrace{(\dots((}_{k-1}x_{i_1}^{\sigma_1}\ x_{i_2}^{\sigma_2})^{\delta_1}\ x_{i_3}^{\sigma_3})^{\delta_2}\\dots\ x_{i_k}^{\sigma_k})^{\delta_{k-1}}$, where $2\leqslant k\leqslant n$ for $f_2$, $f_3$, and $f_5$; $1\leqslant k\leqslant n$ for $f_4$; $\sigma_1,\dots,\sigma_k,\delta_1,\dots,\delta_{k-1}\in\{0,1\}$; $i,i_1,\dots,i_k\in\{1,\dots,n\}$; indices $i_1,\dots,i_k$ are pairwise different; for $f_3$, at least one of numbers $\sigma_2,\dots,\sigma_k$ equals $0$ and if $k=2$, then assume $x_{i_3}\\dots\{i_k}\equiv1$; for $f_5$, at least one of numbers $\delta_1,\dots,\delta_{k-1}$ equals $0$. It is proved that, for each Boolean function $f(x_1,\dots,x_n)\not\equiv1$, $$ D_1(f)=\begin{cases} 0,\text{iff the function $f$ is representable in the form of $f_1$,}\\ 1,\text{iff the function $f$ is representable in the form of $f_2$,}\\ 2,\text{iff the function $f$ is representable in the form of $f_3$,}\\ 3\text{otherwise.} \end{cases} $$ If $f\equiv1$ then the value $D_1(f)$ is undefined. Also, it is proved that, for each Boolean function $f(x_1,\dots,x_n)$ which is different from constants, $$ D_0(f)=\begin{cases} 0,\text{iff the function $f$ is representable in the form of $f_1$,}\\ 1,\text{iff the function $f$ is representable in the form of $f_4$ but not of $f_1$,}\\ 2,\text{iff the function $f$ is representable in the form of $f_5$,}\\ 3\text{otherwise}. \end{cases} $$ If $f\equiv1$ or $f\equiv0$ then the value $D_0(f)$ is undefined.

Détail

Keywords: logic network, stuck-at fault, single fault detection 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., Moscow, 1986, 7–12 (In Russian) | MR

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

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

[5] Reddy S. M., “Easily testable realization for logic functions”, IEEE Trans. Comput., C-21:11 (1972), 1183–1188 | DOI | MR

[6] Kolyada S. S., Upper bounds on the lengths of fault detection tests for logic networks, Cand. Sci. Dissertation, MSU, Moscow, 2013, 77 pp. (in Russian)

[7] Romanov D. S., “Method of synthesis of easily testable circuits admitting single fault detection tests of constant length”, Discrete Math. Appl., 24:4 (2014), 227–251 | DOI | DOI | MR | Zbl

[8] Red'kin N. P., “On complete fault detection tests for logic networks”, Vestnik MSU Ser. 1, 1986, no. 1, 72–74 (in Russian) | Zbl

[9] Red'kin N. P., “On complete fault detection tests for logic networks”, Matematicheskie Voprosy Kibernetiki, 2, Nauka Publ., Moscow, 1989, 198–222 (in Russian) | MR

[10] Romanov D. S., “On the synthesis of circuits admitting complete fault detection test sets of constant length under arbitrary constant faults at the outputs of the gates”, Discrete Math. Appl., 23:3–4 (2013), 343–362 | DOI | MR | Zbl

[11] Red'kin N. P., “On circuits admitting short tests”, Vestnik MSU Ser. 1, 1988, no. 2, 17–21 (in Russian) | Zbl

[12] 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) | Zbl

[13] Borodina Yu. V., “Synthesis of easily-tested circuits in the case of single-type constant malfunctions at the element outputs.”, Mosc. Univ. Comput. Math. Cybern., 32:1 (2008), 42–46 | DOI | MR | Zbl

[14] Popkov K. A., On an exact length value of a minimal single diagnostic test for a particular class of circuits, Preprint No 74, IPM im. M. V. Keldysha, 2015, 21 pp. (in Russian)

[15] Borodina Yu. V., “Lower estimate of the length of the complete test in the basis $\{x|y\}$”, Mosc. Univ. Math. Bull., 70:4 (2015), 185–186 | DOI | MR | Zbl

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

[17] Borodina Yu. V., Borodin P. A., “Synthesis of easily testable circuits over the Zhegalkin basis in the case of constant faults of type 0 at outputs of elements”, Discrete. Math. Appl., 20:4 (2010), 441–449 | DOI | DOI | MR | Zbl

[18] 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)

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