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

Дискрет. матем., 2014, том 26, выпуск 2, страницы 83–99 (Mi dm1282)

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

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

К. А. Попков

МГУ им. М. В. Ломоносова

Аннотация: Рассматриваются задачи проверки исправности и диагностики состояний $N$ функциональных элементов, реализующих в исправном состоянии заданную булеву функцию $f(x_1,\ldots,x_n)$, путём составления из них схем с одним выходом и наблюдения выдаваемых этими схемами значений на любых входных наборах значений переменных. Допускаются произвольные константные неисправности на выходах функциональных элементов; при этом предполагается, что не более $k$ элементов неисправны, где $k$ – заданное натуральное число, не превосходящее $N$. Требуется минимизировать число схем, необходимых для проверки исправности и определения состояний всех функциональных элементов. Доказано, что, если $f\notin\{x_1\&\ldots\&x_n,\:x_1\vee\ldots\vee x_n,\:\overline{x_1}\}$ и выполнено некоторое условие на $k$ и $N$, то для проверки исправности всех элементов достаточно $2k+1$ схем. Если при этом функция $f$ нелинейна, то для определения состояний всех элементов также достаточно $2k+1$ схем.

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

УДК: 519.718.7

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

DOI: 10.4213/dm1282


 Англоязычная версия: Discrete Mathematics and Applications, 2014, 24:4, 213–225

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


© МИАН, 2024