A method for constructing logic networks allowing~short single diagnostic tests
Prikladnaâ diskretnaâ matematika, no. 4 (2019), pp. 38-57

Voir la notice de l'article provenant de la source Math-Net.Ru

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.
Keywords: logic network, Boolean function, stuck-at fault, inverse fault, single fault detection test, single diagnostic test.
@article{PDM_2019_4_a3,
     author = {K. A. Popkov},
     title = {A method for constructing logic networks allowing~short single diagnostic tests},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {38--57},
     publisher = {mathdoc},
     number = {4},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2019_4_a3/}
}
TY  - JOUR
AU  - K. A. Popkov
TI  - A method for constructing logic networks allowing~short single diagnostic tests
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2019
SP  - 38
EP  - 57
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2019_4_a3/
LA  - ru
ID  - PDM_2019_4_a3
ER  - 
%0 Journal Article
%A K. A. Popkov
%T A method for constructing logic networks allowing~short single diagnostic tests
%J Prikladnaâ diskretnaâ matematika
%D 2019
%P 38-57
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2019_4_a3/
%G ru
%F PDM_2019_4_a3
K. A. Popkov. A method for constructing logic networks allowing~short single diagnostic tests. Prikladnaâ diskretnaâ matematika, no. 4 (2019), pp. 38-57. http://geodesic.mathdoc.fr/item/PDM_2019_4_a3/