Том 21, номер 6, 2014 г., Стр. 73-89
УДК 519.718.7
Попков К. А.
Оценки длин проверяющих и диагностических тестов для функциональных элементов
Аннотация:
Рассматриваются задачи проверки исправности и диагностики состояний N функциональных элементов, в исправном состоянии реализующих заданную булеву функцию f (x1, … , xn), путём составления из них схем с одним выходом и наблюдения выдаваемых этими схемами значений на любых входных наборах значений переменных. Допускаются произвольные константные неисправности на выходах функциональных элементов; при этом предполагается, что не более k элементов неисправны, где k — заданное натуральное число, не превосходящее N. Требуется минимизировать число схем, необходимых для проверки исправности и определения состояний всех элементов. Показано, что для любых f, N и k необходимо не менее k схем. Для функций f специального вида получены необходимые и достаточные условия того, что для проверки исправности и определения состояний всех элементов достаточно k схем.
Ил. 3, библиогр. 2.
Ключевые слова: функциональный элемент, неисправность, схема, проверяющий тест, диагностический тест.
Попков Кирилл Андреевич 1,2
1. Московский гос. университет им. М. В. Ломоносова,
Ленинские горы, 1, 119991 Москва, Россия
е-mail: kirill-formulist@mail.ru
Статья поступила 18 декабря 2013 г.
Исправленный вариант — 2 июля 2014 г.
Литература
[1] Лупанов О. Б. Асимптотические оценки сложности управляющих систем // М.: Изд-во МГУ, 1984. - 139 c.
[2] Редькин Н. П. Надёжность и диагностика схем. - М.: Изд-во МГУ, 1992. - 191 c.
