Implementation of Linear Boolean Functions by Self-Correcting Circuits of Unreliable Logic Gates

K. A. Popkov

Matematičeskie zametki, Tome 115 (2024) no. 1, pp. 91-107.

Résumé

We prove that if a Boolean function essentially depends on at least two variables, then it cannot be implemented by a circuit that consists of unreliable gates with at most two inputs each and is self-correcting with respect to at least some faults of an arbitrary number of gates. In view of the previous results, it suffices to establish this fact for linear functions.

Détail

Keywords: logic circuit, self-correction, unreliable gate, linear Boolean function.

Bibliographie

[1] N. P. Redkin, Nadezhnost i diagnostika skhem, Izd-vo MGU, M., 1992

[2] G. I. Kirienko, “O samokorrektiruyuschikhsya skhemakh iz funktsionalnykh elementov”, Probl. kibernetiki, 12 (1964), 29–37 | MR

[3] G. I. Kirienko, “Sintez samokorrektiruyuschikhsya skhem iz funktsionalnykh elementov dlya sluchaya rastuschego chisla oshibok v skheme”, Diskret. analiz, 16 (1970), 38–43 | MR

[4] D. Ulig, “O sinteze samokorrektiruyuschikhsya skhem iz funktsionalnykh elementov s malym chislom nadezhnykh zlementov”, Matem. zametki, 15:6 (1974), 937–944 | MR | Zbl

[5] N. I. Turdaliev, “O samokorrektirovanii skhem dlya nekotorykh posledovatelnostei bulevykh funktsii”, Diskret. matem., 1:3 (1989), 77–86 | MR | Zbl

[6] N. I. Turdaliev, “O samokorrektiruyuschikhsya skhemakh iz funktsionalnykh elementov dlya lineinoi funktsii”, Diskret. matem., 2:2 (1990), 150–154 | MR | Zbl

[7] N. P. Redkin, “Ob asimptoticheski minimalnykh samokorrektiruyuschikhsya skhemakh dlya odnoi posledovatelnosti bulevykh funktsii”, Vestn. Mosk. un-ta. Ser. 1. Matem. Mekh., 1996, no. 3, 3–9 | MR

[8] N. P. Redkin, “Asimptoticheski minimalnye samokorrektiruyuschiesya skhemy dlya odnoi posledovatelnosti bulevykh funktsii”, Diskretn. analiz i issled. oper., 3:2 (1996), 62–79 | MR | Zbl

[9] A. V. Chashkin, “Samokorrektiruyuschiesya skhemy dlya funktsii polinomialnogo vesa”, Vestn. Mosk. un-ta. Ser. 1. Matem. Mekh., 1997, no. 5, 64–66 | MR

[10] V. M. Krasnov, “O slozhnosti samokorrektiruyuschikhsya skhem dlya odnoi posledovatelnosti bulevykh funktsii”, Vestn. Mosk. un-ta. Ser. 1. Matem., mekh., 2009, no. 5, 55–57 | MR | Zbl

[11] K. A. Popkov, “On self-correcting logic circuits of unreliable gates”, Lobachevskii J. Math., 42:11 (2021), 2637–2644 | DOI | MR

[12] K. A. Popkov, “O samokorrektiruyuschikhsya skhemakh iz nenadezhnykh funktsionalnykh elementov, imeyuschikh ne bolee dvukh vkhodov”, Matem. zametki, 111:1 (2022), 145–148 | DOI | MR

[13] N. P. Redkin, “K voprosu o dline diagnosticheskikh testov dlya skhem”, Matem. zametki, 102:4 (2017), 624–627 | DOI | MR

[14] Y. Liu, Design for Test Methods to Reduce Test Set Size, PhD (Doctor of Philosophy) thesis, Univ. of Iowa, Iowa City, 2018

[15] A. I. Timoshkin, “Testable logical circuit of a binary array multiplier in nonstandard basis”, Austrian Journ. of Techn. and Natural Sci., 2018, no. 11–12, 46–49

[16] D. S. Romanov, Ob otsenkakh dlin minimalnykh testov dlya logicheskikh skhem, Dis. $\dots$ dokt. fiz.-matem. nauk, M., 2019

[17] Yu. V. Borodina, “Legkotestiruemye skhemy v bazise Zhegalkina pri konstantnykh neispravnostyakh tipa “1” na vykhodakh elementov”, Diskret. matem., 31:2 (2019), 14–19 | DOI | MR

[18] G. G. Temerbekova, D. S. Romanov, “O edinichnykh proveryayuschikh testakh otnositelno zamen elementov na invertory”, Uchen. zap. Kazan. un-ta. Ser. Fiz.-matem. nauki, 162, no. 3, Izd-vo Kazanskogo un-ta, Kazan, 2020, 359–366 | DOI | MR

[19] K. A. Popkov, O vozmozhnostyakh postroeniya legkotestiruemykh kontaktnykh skhem i skhem iz funktsionalnykh elementov, Dis. $\dots$ dokt. fiz.-matem. nauk, M., 2021

[20] I. G. Lyubich, D. S. Romanov, “O edinichnykh diagnosticheskikh testakh otnositelno inversnykh neispravnostei elementov v skhemakh nad proizvolnymi bazisami”, Diskret. matem., 33:1 (2021), 20–30 | DOI | MR

[21] Yu. V. Borodina, “Nekotorye klassy legkotestiruemykh skhem v bazise Zhegalkina”, Diskret. matem., 33:4 (2021), 3–10 | DOI

[22] K. A. Popkov, “Korotkie edinichnye proveryayuschie testy dlya skhem pri proizvolnykh neispravnostyakh funktsionalnykh elementov”, PDM, 2022, no. 55, 59–76 | DOI | MR

[23] K. A. Popkov, “Korotkie polnye diagnosticheskie testy dlya skhem s dvumya dopolnitelnymi vkhodami v odnom bazise”, Diskret. matem., 34:2 (2022), 67–82 | DOI

[24] K. A. Popkov, “Korotkie polnye diagnosticheskie testy dlya skhem, realizuyuschikh lineinye bulevy funktsii”, Matem. zametki, 113:1 (2023), 75–89 | DOI | MR

[25] S. V. Yablonskii, Vvedenie v diskretnuyu matematiku, Nauka, M., 1986 | MR

[26] N. P. Redkin, Diskretnaya matematika, Fizmatlit, M., 2009