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

ПДМ, 2021, номер 51, страницы 85–100 (Mi pdm732)

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

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

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

К. А. Попков

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

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

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

УДК: 519.718.7

DOI: 10.17223/20710410/51/4



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


© МИАН, 2024