This article is cited in
5 papers
Mathematical Backgrounds of Computer and Control System Reliability
A method for constructing logic networks allowing short single diagnostic tests
K. A. Popkov Keldysh Institute of Applied Mathematics, Moscow, Russia
Abstract:
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\&y,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\&y,\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.
UDC:
519.718.7
DOI:
10.17223/20710410/46/4