HomeIssuesShort complete diagnostic tests for circuits with one additional input in the standard basis

Short complete diagnostic tests for circuits with one additional input in the standard basis | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2022. № 56. DOI: 10.17223/20710410/56/6

We prove that each monotone (antimonotone) Boolean function in n variables can be modeled by a logic circuit with one additional input in the basis “conjunction, disjunction, negation” allowing a complete diagnostic test with length no more than n + 2 (no more than n + 1, respectively) relative to constant faults of type 1 at outputs of logic gates.
Download file
Counter downloads: 37
  • Title Short complete diagnostic tests for circuits with one additional input in the standard basis
  • Headline Short complete diagnostic tests for circuits with one additional input in the standard basis
  • Publesher Tomask State UniversityTomsk State University
  • Issue Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics 56
  • Date:
  • DOI 10.17223/20710410/56/6
Keywords
logic circuit, stuck-at fault, complete diagnostic test, Boolean function
Authors
References
Яблонский С. В. Надёжность и контроль управляющих систем // Материалы Всесоюзного семинара по дискретной математике и её приложениям (Москва, 31 января-2 февраля 1984 г.). М.: Изд-во МГУ, 1986. С. 7-12.
Яблонский С. В. Некоторые вопросы надёжности и контроля управляющих систем // Математические вопросы кибернетики. Вып. 1. М.: Наука, 1988. С. 5-25.
Редькин Н. П. Надёжность и диагностика схем. М.: Изд-во МГУ, 1992. 192 с.
Попков К. А. Нижние оценки длин полных диагностических тестов для схем и входов схем // Прикладная дискретная математика. 2016. №4(34). С. 65-73.
Редькин Н. П. К вопросу о длине диагностических тестов для схем // Математические заметки. 2017. Т. 102. Вып. 4. С. 624-627.
Ложкин С. А. Лекции по основам кибернетики (учебное пособие для студентов). М.: Издательский отдел ф-та ВМиК МГУ, 2004. 251 с.
Яблонский С. В. Введение в дискретную математику. М.: Наука, 1986. 384 с.
Попков К. А. О возможностях построения легкотестируемых контактных схем и схем из функциональных элементов: дис.. д-ра физ.-мат. наук. М., 2021. 377 с.
Коршунов А. Д. О числе монотонных булевых функций // Проблемы кибернетики. Вып. 38. М.: Наука, 1981. С. 5-108.
Short complete diagnostic tests for circuits with one additional input in the standard basis | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2022. № 56. DOI: 10.17223/20710410/56/6
Short complete diagnostic tests for circuits with one additional input in the standard basis | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2022. № 56. DOI: 10.17223/20710410/56/6
Download full-text version
Counter downloads: 111