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

Дискрет. матем., 2018, том 30, выпуск 3, страницы 99–116 (Mi dm1509)

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

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

К. А. Попков

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

Аннотация: Доказаны следующие факты:
1) любую неконстантную булеву функцию можно реализовать неизбыточной схемой из функциональных элементов в базисе $\{x\&y,$ $\overline x,x\oplus y\oplus z\}$, допускающей единичный проверяющий тест длины не более 2 относительно произвольных константных неисправностей на выходах элементов,
2) существует такая булева функция $\psi$ от шести переменных, что любую неконстантную булеву функцию можно реализовать неизбыточной схемой из функциональных элементов в базисе $\{\psi\}$, допускающей единичный диагностический тест длины не более 3 относительно произвольных константных неисправностей на выходах элементов.

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

УДК: 519.718.7

Статья поступила: 08.03.2018

DOI: 10.4213/dm1509


 Англоязычная версия: Discrete Mathematics and Applications, 2019, 29:5, 321–333

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


© МИАН, 2024