Построение тестов и оценка их параметров для некоторых классов контактных схем

• Автор: Романов, Дмитрий Сергеевич
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2000
• Место защиты: Москва
• Количество страниц: 114 с.

СОДЕРЖАНИЕ
Глава 1. Введение
§ 1. Общая характеристика работы
§ 2. Основные определения и обозначения
§ 3. Формулировки основных результатов диссертации
Глава 2. Метод мультиразбиений и оценки длины минимальных
единичных диагностических тестов для периодических КБКС
§ 4. Диагностические множества цепей и мультиразбиения, их связь
с тестами. Нижние оценки длин тестов
§ 5. Рекурсивное построение слаборазличимых мультиразбиений и верхние оценки длины единичных диагностических тестов для одного
класса периодических КБКС
Глава 3. Построение близких к оптимальным единичных диагностических тестов для некоторых классов КБКС
§ 6. Тесты для одного класса периодических КБКС из “сдвиговых”
блоков и для счетчиков по модулю сИ
§ 7. Построение асимптотически минимальных единичных тестов для “прямоугольных” схем и построение тестов размыкания для
“треугольных” схем
Глава 4. О метрических свойствах одного класса тестов для схем
счетчиков четности
§ 8. О числе тупиковых проверяющих замыкания тестов заданной
длины
§ 9. Предельное распределение длины тестов
Приложение А. Некоторые вспомогательные утверждения
Приложение Б. Некоторые специальные мультиразбиения
Литература
Глава 1. Введение
§ 1. Общая характеристика работы
Теория надежности и контроля управляющих систем является важным разделом теории управляющих систем (УС). В рамках теории надежности и контроля предполагается, что на УС, характеризующуюся схемной частью и функционированием [15], воздействует источник неисправностей, способный каким-то образом повреждать ее схемную часть (при этом функционирование УС может нарушаться). Анализ УС, находящихся под действием источников неисправностей, привел к формированию трех основных направлений теории надежности и контроля: синтеза надежных схем из ненадежных элементов, синтеза самокорректирующихся схем, теории контроля работы УС.
Математической базой теории контроля работы УС является тестовый подход, сформировавшийся в середине 50-х годов в работах
С. В. Яблонского и И. А. Чегис [46] и [42]. Смысл тестового подхода состоит в следующем. Пусть все схемы, порождаемые источником неисправностей по исходной схеме, известны. Тогда можно разбить функционирования этих схем (включая и функционирование исходной схемы) на классы эквивалентности и сформулировать на языке этих классов эквивалентности цель контроля. Наиболее распространенными целями контроля являются обнаружение неисправностей (определение того, совпадает ли функционирование схемы с правильным) и диагностика неисправностей (определение класса эквивалентности, к которому относится функционирование данной возможно, неисправной —- схемы). Достижение цели контроля обычно осуществляется путем подачи на входы схемы наборов входных значений и анализа значений, полученных на выходах схемы (реже в схемах допускаются внутренние контрольные точки). Множество входных наборов, которое достигает цели контроля, называется тестом. Тесты, контролирующие неисправности, называются проверяющими, тесты, диагностирующие неисправности —- диагностическими. Если источник неисправностей способен повредить в схеме не более одного элемента, о соответствующих тестах говорят, что они единичные. Если же источник неисправностей способен повреждать в схеме любые элементы, тесты для него называются полными. По тому, зависит ли вид подаваемых на входы схемы наборов от полученных на предыдущих шагах выходных значений, или нет, тесты делятся на условные и безусловные. Число наборов теста называется длиной теста. Важными являются понятия

минимального теста (теста минимальной длины) и тупикового (неизбыточного) теста.
Построение и анализ тупиковых и минимальных тестов представляет значительный интерес. С. В. Яблонским и И. А. Чегис в [46], [42] был предложен первый алгоритм построения всех тупиковых тестов по так называемой таблице неисправностей (таблице, в которой заданы столбцами своих значений все попарно неэквивалентные функционирования исходной и неисправных схем), однако высокая трудоемкость этого алгоритма не позволила использовать его для исследования тупиковых и минимальных тестов уже при сравнительно небольших размерах таблиц неисправностей. Этот факт стимулировал создание конкретных алгоритмов построения тестов, получение оценок длин тестов и исследование метрических характеристик множеств тестов для различных классов управляющих систем. В настоящее время теория контроля представляет собой развитую научную область, объединяющую работы многих российских и зарубежных авторов, среди которых
A. Е. Андреев, А. Д. Коршунов, X. А. Мадатян, М. Ю. Мошков,
B. Н. Носков, Г. Р. Погосян, Н. П. Редькин, В. А. Слепян, Н. А. Соловьев, В. И. Шевченко, С. В. Яблонский, D. В. Armstrong, В. D. Eidred, E. F. Moore, J. P. Roth и другие. Из литературы по теории контроля хотелось бы упомянуть монографии Н. А. Соловьева [38], H. II. Редьки-на [24], М. Ю. Мошкова [19], П. П. Пархоменко и Е. С. Согомоняна [23], а также обзор С. В. Яблонского [45].
В настоящей диссертации исследуются вопросы построения и изучения тестов для некоторых классов контактных схем (КС). Типичными для КС неисправностями являются размыкание и замыкание контакта. Отметим два направления в исследованиях тестов для КС:
1) изучение функций Шеннона, характеризующих длину минимального теста для наиболее легкотестируемой контактной схемы, реализующей “самую труднотестируемую” функцию п переменных, при различных источниках неисправностей,
2) изучение тестов для конкретных классов КС.
В первом направлении были получены, например, следующие интересные результаты. Установлено точное значение функции Шеннона для случая полного диагностического теста [18] для функций алгебры логики от п булевых переменных — ее величина оказалась равной 2™, то есть минимальный тест должен в общем случае содержать все наборы. В [25] доказано, что полный проверяющий тест не обязан содержать все наборы: и что соответствующая функция Шеннона не

боразличимости мультиразбиения.
Лемма доказана.
Лемма 4.7. Пусть Бп — (2д)-полюспая п-блочная (не обязательно периодическая) КБКС над базисом . Тогда для схемы Бп существует диагностическое множество цепей мощности, не превосходящей величины 6(] к2та[+2).
Доказательство. Оценка леммы получается при применении одного из классических приемов построения тестов — дихотомии, то есть деления пополам. Пусть 2г"~1 < п 2т, и> Е Но- Построим диагностическое множество цепей Г)2», для схемы Буш, полученной из Бп пристыковкой к ней 2“ — п каких-то блоков из базиса 'Н'1. Включим в £>2<" по 6 цепей, соответствующих каждому из гг+2 =] ’2 п[+2 наборов
тплт, ([о]2в"1[1]2’"*), ([[ог-г[1]П2)
([01]2" ). Теперь диагностическое множество цепей О,, для 5„(Щ) получается из Бу,- отбрасыванием участков всех цепей, лежащих в последних 2Ш — п блоках схемы Б?». Лемма доказана.
Лемма 4.8. Пусть Бп — (2с?)-полюсная п-блочная (не обязательно периодическая) КБКС над базисом /Н(1. Тогда для схемы Бп существует абсолютно диагностическое множество цепей мощности, не превосходящей величины 6(2] к2 п[+2).
Доказательство этой леммы отличается от доказательства предыдущей тем, что в строящееся диагностическое множество цепей Буи, для схемы 52ш наряду с цепями, соответствующими наборам ([0Г1[1Г1), ([[0Г~2[1]П2), , ([[0]2Н1ГТ), ([01]2*"*), вклю-
чаются и цепи, соответствующие противоположным наборам.
Лемма 4.9. Пусть Бп (2 д)-полюсная г-достижимая
п-блочная (не обязательно периодическая) КБКС над базисом Н11, и п Зг. Пусть Б — диагностическое множество цепей Бп, а Бп — двухполюсная КБКС, полученная из Бп усечением. Тогда для Бп существует диагностическое множество цепей Г) такое, что
Б Б + 26] log2 г[+ Юд, а если Бп — Бп(Н) — счетчик по модулю 6, то Б Б + 12с?.
Доказательство. Схема Бп естественным образом разбивается на три подсхемы: Бп = Б1 Б2Б3. КС Б1 состоит из всех усеченных блоков в левой части Бп, КС Б2 состоит из всех блоков Бп, которые сохранились целиком при усечении, КС Б3, состоит из всех усеченных блоков в правой части Бп.