Эта публикация цитируется в
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