Geodesic
On logic networks allowing short single fault detection tests under arbitrary faults of gates
Prikladnaâ diskretnaâ matematika, no. 1 (2021), pp. 85-100.

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

It is proved that one can implement any non-constant Boolean function in $n$ variables by an irredundant logic network in the basis $\{\,\oplus,\neg\}$, containing not more than one dummy input variable and allowing a single fault detection test with length not more than $2n+3$ regarding arbitrary faults of logic gates.
Keywords: logic network, Boolean function, fault, single fault detection test. 
@article{PDM_2021_1_a4,
     author = {K. A. Popkov},
     title = {On logic networks allowing short single fault detection tests under arbitrary faults of gates},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {85--100},
     publisher = {mathdoc},
     number = {1},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2021_1_a4/}
}
TY  - JOUR
AU  - K. A. Popkov
TI  - On logic networks allowing short single fault detection tests under arbitrary faults of gates
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2021
SP  - 85
EP  - 100
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2021_1_a4/
LA  - ru
ID  - PDM_2021_1_a4
ER  - 
%0 Journal Article
%A K. A. Popkov
%T On logic networks allowing short single fault detection tests under arbitrary faults of gates
%J Prikladnaâ diskretnaâ matematika
%D 2021
%P 85-100
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2021_1_a4/
%G ru
%F PDM_2021_1_a4
K. A. Popkov. On logic networks allowing short single fault detection tests under arbitrary faults of gates. Prikladnaâ diskretnaâ matematika, no. 1 (2021), pp. 85-100. http://geodesic.mathdoc.fr/item/PDM_2021_1_a4/

[1] I. A. Chegis, S. V. Yablonskiy, “Logical methods of control of work of electric circuits”, Trudy Mat. Inst. Steklov, 51, 1958, 270–360 (in Russian) | MR | Zbl

[2] S. V. Yablonskiy, “Reliability and verification of control systems”, Materialy Vsesoyuznogo seminara po diskretnoy matematike i ee prilozheniyam (Moscow, 31 Jan.–2 Feb. 1984), MSU Publ., M., 1986, 7–12 (in Russian)

[3] S. V. Yablonskiy, “Some questions of reliability and verification of control systems”, Matematicheskie Voprosy Kibernetiki, 1, Nauka, M., 1988, 5–25 (in Russian)

[4] N. P. Red'kin, Circuits Reliability and Diagnostics, MSU, M., 1992, 192 pp. (in Russian)

[5] Yu. V. Borodina, “Circuits admitting single-fault tests of length 1 under constant faults at outputs of elements”, Mosc. Univ. Math. Bull., 63:5 (2008), 202–204 | DOI | MR | Zbl

[6] K. A. Popkov, “Lower bounds for lengths of single tests for Boolean circuits”, Discrete Math. Appl., 29:1 (2019), 23–33 | DOI | MR | Zbl

[7] K. A. Popkov, “Single fault detection tests for logic networks in the basis “conjunction-negation””, Prikladnaya Diskretnaya Matematika, 2017, no. 38, 66–88 (in Russian) | Zbl

[8] S. M. Reddy, “Easily testable realizations for logic functions”, IEEE Trans. Comput., C-21:11 (1972), 1183–1188 | DOI | MR

[9] S. S. Kolyada, “Single fault detection tests for circuits of functional elements”, Mosc. Univ. Math. Bull., 68:4 (2013), 192–193 | DOI | MR | Zbl

[10] S. S. Kolyada, Upper bounds on length of fault detection tests for logic networks, Cand. Diss., M., 2013, 77 pp. (in Russian)

[11] D. S. Romanov, “Method of synthesis of easily testable circuits admitting single fault detection tests of constant length”, Discrete Math. Appl., 24:4 (2014), 227–251 | DOI | MR | Zbl

[12] D. S. Romanov, “On tests for logic networks under faults at outputs of gates”, Materialy XVIII Mezhdunarodnoy konferentsii «Problemy teoreticheskoy kibernetiki» (Penza, 19–23 June 2017), MAKS Press, M., 2017, 213–216 (in Russian)

[13] K. A. Popkov, “Short single tests for circuits with arbitrary stuck-at faults at outputs of gates”, Discrete Math. Appl., 29:5 (2019), 321–333 | DOI | MR | MR | Zbl

[14] S. V. Kovatsenko, “Synthesis of easily testable logic networks in the Zhegalkin basis for inverse faults”, Vestnik MSU, Ser. 15, 2000, no. 2, 45–47 (in Russian) | Zbl

[15] Red'kin N. P., “On single fault detection tests of logic networks under inverse faults of gates”, XII Mezhdunarodnaya konferentsiya po problemam teoreticheskoy kibernetiki, Tezisy dokladov (Nizhny Novgorod, 1999), Mech.-Math. Faculty of MSU Publ., M., 1999, 196 (in Russian)

[16] N. P. Red'kin, “Single fault detection tests for logic networks under inverse faults of gates”, Matematicheskie Voprosy Kibernetiki, 12, Fizmatlit, M., 2003, 217–230 (in Russian)

[17] K. A. Popkov, “Synthesis of easily testable logic networks under one-type stuck-at faults at inputs and outputs of gates”, Intellektual'nye Sistemy. Teoriya i Prilozheniya, 23:3 (2018), 131–147 (in Russian)

[18] D. S. Romanov, E. Yu. Romanova, “Short tests for circuits in the Zhegalkin basis”, Intellektual'nye Sistemy. Teoriya i Prilozheniya, 20:3 (2016), 73–78 (in Russian) | MR

[19] D. S. Romanov, E. Yu. Romanova, “A method of synthesis of irredundant circuits admitting single fault detection tests of constant length”, Discrete Math. Appl., 29:1 (2019), 35–48 | DOI | MR | Zbl

[20] K. A. Popkov, “Synthesis of easily testable logic networks under arbitrary stuck-at faults at inputs and outputs of gates”, Prikladnaya Diskretnaya Matematika, 2019, no. 43, 78–100 (in Russian) | Zbl

[21] K. A. Popkov, “A method of constructing of easily diagnosable logic networks regarding single faults”, Prikladnaya Diskretnaya Matematika, 2019, no. 46, 38–57 (in Russian) | Zbl

[22] K. A. Popkov, “Short complete fault detection tests for logic networks with fan-in two”, Journ. Appl. Industr. Math., 13:1 (2019), 118–131 | DOI | MR | Zbl

[23] S. V. Yablonskiy, Introduction to Discrete Mathematics, Nauka, M., 1986, 384 pp. (in Russian) | MR