Оценки длин проверяющих и диагностических тестов для контактов

Актуальность и цели. Рассматриваются задачи проверки исправности и диагностики состояний N контактов путем составления из них двухполюсных контактных схем и наблюдения выдаваемых этими схемами значений на любых входных наборах значений переменных. Допускаются произвольные константные неисправности контактов; при этом предполагается, что не более k контактов неисправны (k - заданное натуральное число, не превосходящее N). Требуется минимизировать число схем, необходимых для проверки исправности и определения состояний всех контактов. Материалы и методы. Используется метод «забивания» контактных схем такими неисправностями контактов, при которых каждая из схем реализует булеву константу. Результаты. Получены нижние оценки k/[sqrt N)] и k/(N-k) для числа указанных схем. В случаях k=N-1 и k=N найдены точные значения этого числа. Выводы. Для проверки исправности и диагностики состояний контактов невозможно обойтись схемами, число которых меньше некоторых фиксированных чисел, зависящих от N и k.