Bounds on Shannon functions of lengths of contact closure tests for contact circuits

K. A. Popkov

Diskretnaya Matematika, Tome 32 (2020) no. 3, pp. 49-67.

Résumé

We consider the problem of synthesis of irredundant two-pole contact circuits which implement $n$-place Boolean functions and allow short single fault detection or diagnostic tests of closures of at most $k$ contacts. We prove that the Shannon function of the length of a fault detection test is equal to $n$ for any $n$ and $k$, and that the Shannon function of the length of a diagnostic test is majorized by $n+k(n-2)$ for $n\geqslant 2$.

Détail

Keywords: contact circuit, contact closure, Boolean function, fault detection test, diagnostic test, Shannon function.

Bibliographie

[1] Lupanov O. B., Asimptoticheskie otsenki slozhnosti upravlyayuschikh sistem, Izd-vo Mosk. un-ta, Moskva, 1984, 138 pp.

[2] Chegis I. A., Yablonskii S. V., “Logicheskie sposoby kontrolya raboty elektricheskikh skhem”, Trudy MIAN, 51 (1958), 270–360 | MR | Zbl

[3] Yablonskii S. V., “Nadezhnost i kontrol upravlyayuschikh sistem”, Materialy Vsesoyuznogo seminara po diskretnoi matematike i ee prilozheniyam (Moskva, 31 yanvarya–2 fevralya 1984 g.), Izd-vo Mosk. un-ta, Moskva, 1986, 7–12

[4] Yablonskii S. V., “Nekotorye voprosy nadezhnosti i kontrolya upravlyayuschikh sistem”, Matematicheskie voprosy kibernetiki. Vyp. 1, Nauka, Moskva, 1988, 5–25

[5] Redkin N. P., Nadezhnost i diagnostika skhem, Izd-vo Mosk. un-ta, Moskva, 1992, 192 pp.

[6] Popkov K. A., “On diagnostic tests of contact break for contact circuits”, Discrete Math. Appl., 30:2 (2020), 103–116 | MR | MR | Zbl

[7] Madatyan Kh. A., “Polnyi test dlya bespovtornykh kontaktnykh skhem”, Problemy kibernetiki, no. 23, Nauka, Moskva, 1970, 103–118 | MR

[8] Redkin N. P., “O polnykh proveryayuschikh testakh dlya kontaktnykh skhem”, Metody diskretnogo analiza v issledovanii ekstremalnykh struktur, no. 39, Izd-vo IM SO AN SSSR, Novosibirsk, 1983, 80–87 | MR

[9] Redkin N. P., “O proveryayuschikh testakh zamykaniya i razmykaniya”, Metody diskretnogo analiza v optimizatsii upravlyayuschikh sistem, no. 40, Izd-vo IM SO AN SSSR, Novosibirsk, 1983, 87–99

[10] Romanov D. S., “O sinteze kontaktnykh skhem, dopuskayuschikh korotkie proveryayuschie testy”, Uchenye zapiski Kazanskogo universiteta. Fiziko-matematicheskie nauki, 156:3 (2014), 110–115

[11] Romanov D. S., Romanova E. Yu., “Single fault detection tests for generalized iterative switching circuits”, Moscow Univ. Comput. Math. Cyber., 2015, no. 39, 144–152 | MR | Zbl

[12] Popkov K. A., “Tests of contact closure for contact circuits”, Discrete Math. Appl., 26:5 (2016), 299–308 | MR | Zbl

[13] Popkov K. A., “On fault detection tests of contact break for contact circuits”, Discrete Math. Appl., 28:6 (2018), 369–383 | MR | MR | Zbl

[14] Popkov K. A., “Korotkie edinichnye proveryayuschie testy dlya kontaktnykh skhem pri obryvakh i zamykaniyakh kontaktov”, Intellektualnye sistemy. Teoriya i prilozheniya, 23:3 (2019), 97–130

[15] Popkov K. A., “Short tests of closures for contact circuits”, Math. Notes, 107:4 (2020), 653–662 | MR | Zbl

[16] Popkov K. A., “O polnykh diagnosticheskikh testakh dlya kontaktnykh skhem pri obryvakh i/ili zamykaniyakh kontaktov”, Izv. vysshikh uchebn. zaved. Povolzhskii region. Fiz.-matem. nauki, 2019, no. 3 (51), 3–24

[17] Yablonskii S. V., Vvedenie v diskretnuyu matematiku, Nauka, Moskva, 1986, 384 pp. | MR

[18] Lozhkin S. A., Lektsii po osnovam kibernetiki (uchebnoe posobie dlya studentov), Izdatelskii otdel f-ta VMiK MGU, Moskva, 2004, 251 pp.