Single fault detection tests for logic networks of AND, NOT gates
Prikladnaâ diskretnaâ matematika, no. 4 (2017), pp. 66-88

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

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.
Keywords: logic network, stuck-at fault, single fault detection test.
@article{PDM_2017_4_a4,
     author = {K. A. Popkov},
     title = {Single fault detection tests for logic networks of {AND,} {NOT} gates},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {66--88},
     publisher = {mathdoc},
     number = {4},
     year = {2017},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2017_4_a4/}
}
TY  - JOUR
AU  - K. A. Popkov
TI  - Single fault detection tests for logic networks of AND, NOT gates
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2017
SP  - 66
EP  - 88
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2017_4_a4/
LA  - ru
ID  - PDM_2017_4_a4
ER  - 
%0 Journal Article
%A K. A. Popkov
%T Single fault detection tests for logic networks of AND, NOT gates
%J Prikladnaâ diskretnaâ matematika
%D 2017
%P 66-88
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2017_4_a4/
%G ru
%F PDM_2017_4_a4
K. A. Popkov. Single fault detection tests for logic networks of AND, NOT gates. Prikladnaâ diskretnaâ matematika, no. 4 (2017), pp. 66-88. http://geodesic.mathdoc.fr/item/PDM_2017_4_a4/