|
This article is cited in 4 scientific papers (total in 4 papers)
Mathematical Backgrounds of Computer and Control System Reliability
Single fault detection tests for logic networks of AND, NOT gates
K. A. Popkov Keldysh Institute of Applied Mathematics, Moscow, Russia
Abstract:
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\&x_{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.
Citation:
K. A. Popkov, “Single fault detection tests for logic networks of AND, NOT gates”, Prikl. Diskr. Mat., 2017, no. 38, 66–88
Linking options:
https://www.mathnet.ru/eng/pdm602 https://www.mathnet.ru/eng/pdm/y2017/i4/p66
|
Statistics & downloads: |
Abstract page: | 170 | Full-text PDF : | 95 | References: | 42 |
|