Short Complete Diagnostic Tests for Circuits Implementing Linear Boolean Functions

K. A. Popkov

Matematičeskie zametki, Tome 113 (2023) no. 1, pp. 75-89.

Résumé

We prove that each of the Boolean functions $x_1\oplus\dots\oplus x_n$, $x_1\oplus\dots\oplus x_n\oplus 1$ can be implemented by a logic circuit in each of the bases $\{x\oplus y,1\}$, $\{x\\overline y,x\vee y,\overline x\}$, $\{x\,x\vee y,\overline x\}$, allowing a complete diagnostic test of length not exceeding $\lceil\log_2(n+1)\rceil$ (for the first two bases) or not exceeding $n$ (for the third basis) relative to one-type stuck-at faults at outputs of gates. We also establish that each of the functions $x_1\oplus\dots\oplus x_n$, $x_1\oplus\dots\oplus x_n\oplus 1$ can be implemented by a logic circuit in the basis $\{x\oplus y,1\}$ allowing a complete diagnostic test of length not exceeding $\lceil\log_2(n+1)\rceil+1$ relative to arbitrary stuck-at faults at outputs of gates.

Détail

Keywords: logic circuit, complete diagnostic test, stuck-at fault, linear Boolean function.

Bibliographie

[1] S. V. Yablonskii, “Nadezhnost i kontrol upravlyayuschikh sistem”, Materialy Vsesoyuznogo seminara po diskretnoi matematike i ee prilozheniyam, Izd-vo Mosk. un-ta, M., 1986, 7–12

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

[3] N. P. Redkin, Nadezhnost i diagnostika skhem, Izd-vo Mosk. un-ta, M., 1992

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

[5] K. A. Popkov, “Nizhnie otsenki dlin polnykh diagnosticheskikh testov dlya skhem i vkhodov skhem”, PDM, 2016, no. 4(34), 65–73 | DOI

[6] H. Fujiwara, “On closedness and test complexity of logic circuits”, IEEE Trans. Comput., 30:8 (1981), 556–562 | DOI | MR

[7] D. S. Romanov, E. Yu. Romanova, “Korotkii diagnosticheskii test dlya odnogo klassa skhem”, XXI vek: itogi proshlogo i probl. nastoyaschego plyus. Ser.: Tekhnicheskie nauki. Inform., vychisl. tekhnika i upravl., 2017, no. 04 (38), 91–93

[8] K. A. Popkov, “Polnye diagnosticheskie testy dliny $2$ dlya skhem pri inversnykh neispravnostyakh funktsionalnykh elementov”, Kompleksnyi analiz, matematicheskaya fizika i prilozheniya, Sbornik statei, Trudy MIAN, 301, MAIK «Nauka/Interperiodika», M., 2018, 219–224 | DOI | MR

[9] G. V. Antyufeev, D. S. Romanov, “Ob otsenkakh funktsii Shennona dliny diagnosticheskogo testa pri lokalnykh konstantnykh neispravnostyakh na vkhodakh skhem”, Voprosy radioelektroniki. Ser. EVT, 2016, no. 2, 49–51

[10] K. A. Popkov, “Korotkie polnye diagnosticheskie testy dlya skhem s odnim dopolnitelnym vkhodom v standartnom bazise”, PDM, 2022, no. 56, 104–112 | DOI

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

[12] V. G. Khakhulin, “O proveryayuschikh testakh dlya schetchika chetnosti”, Diskret. matem., 7:4 (1995), 51–59 | MR | Zbl

[13] S. R. Bedzhanova, “Legkotestiruemye skhemy dlya lineinykh funktsii”, Vestn. Mosk. un-ta. Ser. 1. Matem., mekh., 2011, no. 4, 57–59 | MR | Zbl

[14] Kh. A. Madatyan, “Polnyi test dlya bespovtornykh kontaktnykh skhem”, Probl. kibern., 23, Nauka, M., 1970, 103–118 | MR

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

[16] K. A. Popkov, “Korotkie testy zamykaniya dlya kontaktnykh skhem”, Matem. zametki, 107:4 (2020), 591–603 | DOI | MR

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