RUS  ENG
Полная версия
ЖУРНАЛЫ // Прикладная дискретная математика // Архив

ПДМ, 2022, номер 55, страницы 59–76 (Mi pdm760)

Эта публикация цитируется в 1 статье

Математические основы надежности вычислительных и управляющих систем

Короткие единичные проверяющие тесты для схем при произвольных неисправностях функциональных элементов

К. А. Попков

Институт прикладной математики им. М. В. Келдыша РАН, г. Москва, Россия

Аннотация: Доказано, что любую неконстантную булеву функцию от $n$ переменных можно реализовать неизбыточной схемой из функциональных элементов в базисе $\{\&,\oplus,\neg\}$, допускающей при $n\geqslant 3$ единичный проверяющий тест длины не более $6n-10$ относительно произвольных неисправностей элементов.

Ключевые слова: схема из функциональных элементов, булева функция, неисправность, единичный проверяющий тест.

УДК: 519.718.7

DOI: 10.17223/20710410/55/4



Реферативные базы данных:


© МИАН, 2024