Synthesis of easily testable logic networks under~arbitrary stuck-at faults at~inputs~and~outputs~of~gates

K. A. Popkov

Prikladnaâ diskretnaâ matematika, no. 1 (2019), pp. 78-100.

Résumé

Two binary vectors are called $k$-adjacent if they differ in at most $k$ components, where $k\in\mathbb{N}$. For $\alpha\in\{0,1\}$ and $s\in\mathbb{N}$, let $\alpha^s$ be the Boolean vector $(\alpha,\ldots,\alpha)$ with $s$ coordinates $\alpha$. For each natural $k$, consider the bases $B(k)=\{\varphi(x_1,\ldots,x_{2k+2}),x_1\ldots x_{k+1}\vee\overline x_1\ldots\overline x_{k+1},\overline x,0\}$ and $B'(k)=\{\varphi(x_1,\ldots,x_{2k+2}),\xi(x_1,\ldots,x_{3k+2}),\eta(x_1,\ldots,x_{4k+2}),\overline x,0\}$, where $\varphi(x_1,\ldots,x_{2k+2})$ is an arbitrary non-self-dual Boolean function taking the value $\alpha$ on the vector $\alpha^{2k+2}$ and the value $\overline\alpha$ on all other vectors $k$-adjacent to this vector; $\xi(x_1,\ldots,x_{3k+2})$ is an arbitrary Boolean function taking the value $\alpha$ on the vector $\alpha^{3k+2}$, the value $\overline\alpha$ on all other vectors $k$-adjacent to this vector, and the value $\alpha$ on all vectors $k$-adjacent to the vector $(\alpha^{k+1},\overline\alpha^{2k+1})$; $\eta(x_1,\ldots,x_{4k+2})$ is an arbitrary Boolean function taking the value $1$ on the vector $\alpha^{4k+2}$, the value $0$ on all other vectors $k$-adjacent to this vector, and the value $\alpha$ on all vectors $k$-adjacent to the vector $(\alpha_{2k+1},\overline\alpha^{2k+1})$. Let $D_{k\text{(I)}}(f)$ ($D_{k\text{(IO)}}(f)$, $D'_{k\text{(I)}}(f)$, $D'_{k\text{(IO)}}(f)$) be the least length of a fault detection test (fault detection test, diagnostic test, diagnostic test, respectively) for irredundant logic networks consisting of logic gates in the basis $B(k)$ (basis $B(k)$, basis $B'(k)$, basis $B'(k)$, respectively), implementing given Boolean function $f(x_1,\ldots,x_n)$, and having at most $k$ arbitrary stuck-at faults on inputs of gates (on inputs and/or outputs of gates, on inputs of gates, on inputs and/or outputs of gates, respectively). Let a Boolean function $f(x_1,\ldots,x_n)$ be called palindromic if it takes the same value on any two opposite binary $n$-tuples. The following facts are obtained. The quantity $D_{k\text{(I)}}(f)$ equals $0$ iff $f$ is an identical function (i.e., $f\equiv x_i$ for some $i\in\{1,\ldots,n\}$) and equals $2$ otherwise. The quantity $D_{k\text{(IO)}}(f)$ equals $0$ iff $f$ is an identical function, equals $1$ iff $f\equiv 0$, equals $2$ iff $f$ is not an identical or palindromic function, equals $3$ iff $f$ is a palindromic function and $f\not\equiv 0,1$, and is undefined iff $f\equiv 1$. The quantity $D'_{k\text{(I)}}(f)$ equals $0$ iff $f$ is an identical function and equals $2$ otherwise. The quantity $D'_{1\text{(IO)}}(f)$ equals $0$ iff $f$ is an identical function, equals $1$ iff $f\equiv 0$, equals $2$ iff $f\equiv\overline x_i$ for some $i\in\{1,\ldots,n\}$, equals $3$ iff $f$ is not a self-dual function and $f\not\equiv 0,1$, equals $4$ iff $f$ is a self-dual function and $f\notin\{x_1,\ldots,x_n,\overline x_1,\ldots,\overline x_n\}$, and is undefined iff $f\equiv 1$. For each $k\in\mathbb N$, the equality $D'_{k\text{(IO)}}(f)=4$ holds true under $n\geqslant 3$, and in the case $k\geqslant 2$, the proportion of those Boolean functions $f$ in $n$ variables, for which $D'_{k\text{(IO)}}(f)=4$, tends to $1$ under $n\to\infty$.

Détail

Keywords: logic network, arbitrary stuck-at fault, fault detection test
Mots-clés : 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] Kolyada S. S., Upper bounds on the lengths of fault detection tests for logic networks, Cand. Sci. Dissertation, MSU, M., 2013, 77 pp. (in Russian)

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

[7] Saluja K. K., Reddy S. M., “Fault detecting test sets for Reed-Muller canonic networks”, IEEE Trans. Comput., C-24:10 (1975), 995–998 | DOI | MR

[8] Romanov D. S., Romanova E. Yu., “Method of synthesis of irredundant circuits allowing single fault detection tests of constant length”, Diskretnaya Matematika, 29:4 (2017), 87–105 (in Russian) | DOI

[9] Red'kin N. P., “On fault detection tests for logic networks under one-type stuck-at faults at inputs of gates”, Izvestiya Vuzov, Matematika, 1988, no. 7, 57–64 (in Russian) | MR

[10] Red'kin N. P., “On circuits allowing short single diagnostic tests”, Diskretnaya Matematika, 1:3 (1989), 71–76 (in Russian) | MR

[11] Red'kin N. P., “O proveryayushchikh testakh dlya skhem pri konstantnykh neispravnostyakh na vkhodakh elementov [On fault detection tests for logic networks under stuck-at faults at inputs of gates].”, Vestnik MSU, Ser. 1, 1997, no. 1, 12–18 (in Russian) | MR | Zbl

[12] Popkov K. A., “Synthesis of Easily Testable Logic Networks under One-Type Stuck-at Faults at Inputs and Outputs of Gates”, Preprinty IPM im. M. V. Keldysha, 2018, 087, 18 pp. (in Russian)

[13] Ugol'nikov A. B., Post Classes, Tutorial, MSU, TsPI Publ., M., 2008, 64 pp. (in Russian)