Lower bounds for lengths of single tests for Boolean circuits

K. A. Popkov

Diskretnaya Matematika, Tome 29 (2017) no. 2, pp. 53-69

Résumé

We obtain nontrivial lower bounds for lengths of minimal single fault detection and diagnostic tests for Boolean circuits in wide classes of bases in presence of stuck-at faults at outputs of circuit gates.

Détail

Keywords: Boolean circuit, stuck-at fault, single fault detection test, single diagnostic test.

Bibliographie

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

[2] Yablonskii S. V., “Nadëzhnost i kontrol upravlyayuschikh sistem”, Mater. Vsesoyuzn. sem. po diskr. matem. i eë pril., Izd-vo MGU, Moskva, 1986, 7–12

[3] Yablonskii S. V., “Nekotorye voprosy nadëzhnosti i kontrolya upravlyayuschikh sistem”, Matematicheskie voprosy kibernetiki, no. 1, Nauka, Moskva, 1988, 5–25 | MR

[4] Redkin N. P., Nadëzhnost i diagnostika skhem, Izdatelstvo MGU, Moskva, 1992, 192 pp.

[5] Reddy, S. M., “Easily testable realization for logic functions”, IEEE Trans. Comput., 21:1 (1972), 124–141 | MR

[6] Kolyada S. S., Verkhnie otsenki dliny proveryayuschikh testov dlya skhem iz funktsionalnykh elementov, Diss. na soisk. uch. st. k.f.-m.n., Moskva, 2013, 77 pp.

[7] Romanov D. S., “Metod sinteza legkotestiruemykh skhem, dopuskayuschikh edinichnye proveryayuschie testy konstantnoi dliny”, Diskretnaya matematika, 26:2 (2014), 100–130 | DOI | MR | Zbl

[8] Redkin N. P., “O polnykh proveryayuschikh testakh dlya skhem iz funktsionalnykh elementov”, Vestnik Moskovskogo universiteta. Seriya 1. Matematika. Mekhanika, 1986, no. 1, 72–74

[9] Redkin N. P., “O polnykh proveryayuschikh testakh dlya skhem iz funktsionalnykh elementov”, Matematicheskie voprosy kibernetiki, 2, Nauka, Moskva, 1989, 198–222; Romanov D. S.

[10] Discrete Math. Appl., 23:3-4 (2013), 343–362 | DOI | DOI | MR | Zbl

[11] Redkin N. P., “O skhemakh, dopuskayuschikh korotkie testy”, Vestnik Moskovskogo universiteta. Seriya 1. Matematika. Mekhanika, 1988, no. 2, 17–21 | Zbl

[12] Redkin N. P., “O edinichnykh diagnosticheskikh testakh dlya odnotipnykh konstantnykh neispravnostei na vykhodakh funktsionalnykh elementov”, Vestnik Moskovskogo universiteta. Seriya 1. Matematika. Mekhanika, 1992, no. 5, 43–46

[13] Borodina Yu. V., “O sinteze legkotestiruemykh skhem v sluchae odnotipnykh konstantnykh neispravnostei na vykhodakh elementov”, Vestnik Moskovskogo universiteta. Seriya 15. Vychislitelnaya matematika i kibernetika, 2008, no. 1, 40–44 | MR | Zbl

[14] Popkov K. A., “O tochnom znachenii dliny minimalnogo edinichnogo diagnosticheskogo testa dlya odnogo klassa skhem”, Preprinty IPM im. M.V.Keldysha, 2015, no. 74, 21 pp.

[15] Borodina Yu. V., “O skhemakh, dopuskayuschikh edinichnye testy dliny 1 pri konstantnykh neispravnostyakh na vykhodakh elementov”, Vestnik Moskovskogo universiteta. Seriya 1. Matematika. Mekhanika, 2008, no. 5, 49–52 | MR | Zbl

[16] Borodina Yu. V., Borodin P. A., “Sintez legkotestiruemykh skhem v bazise Zhegalkina pri konstantnykh neispravnostyakh tipa 0 na vykhodakh elementov”, Diskretnaya matematika, 22:3 (2010), 127–133 | DOI | MR | Zbl

[17] Popkov K. A., “O edinichnykh diagnosticheskikh testakh dlya skhem iz funktsionalnykh elementov v bazise Zhegalkina”, Preprinty IPM im. M.V.Keldysha, 2016, no. 50, 16 pp.

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

[19] Romanov D. S., “Metod sinteza neizbytochnykh skhem v bazise Zhegalkina, dopuskayuschikh edinichnye diagnosticheskie testy dliny odin”, Izvestiya vysshikh uchebnykh zavedenii. Povolzhskii region. Fiziko-matematicheskie nauki, 2015, no. 4 (36), 38–54