Prikladnaya Diskretnaya Matematika
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Prikl. Diskr. Mat.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Prikladnaya Diskretnaya Matematika, 2019, Number 46, Pages 38–57
DOI: https://doi.org/10.17223/20710410/46/4
(Mi pdm683)
 

This article is cited in 5 scientific papers (total 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
Full-text PDF (754 kB) Citations (5)
References:
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.
Funding agency Grant number
Russian Science Foundation 19-71-30004
Bibliographic databases:
Document Type: Article
UDC: 519.718.7
Language: Russian
Citation: K. A. Popkov, “A method for constructing logic networks allowing short single diagnostic tests”, Prikl. Diskr. Mat., 2019, no. 46, 38–57
Citation in format AMSBIB
\Bibitem{Pop19}
\by K.~A.~Popkov
\paper A method for constructing logic networks allowing~short single diagnostic tests
\jour Prikl. Diskr. Mat.
\yr 2019
\issue 46
\pages 38--57
\mathnet{http://mi.mathnet.ru/pdm683}
\crossref{https://doi.org/10.17223/20710410/46/4}
Linking options:
  • https://www.mathnet.ru/eng/pdm683
  • https://www.mathnet.ru/eng/pdm/y2019/i4/p38
  • This publication is cited in the following 5 articles:
    Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Прикладная дискретная математика
    Statistics & downloads:
    Abstract page:187
    Full-text PDF :91
    References:27
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024