Верхние оценки длины проверяющих текстов для схем из функциональных элементов

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

Содержание
Введение

Глава 1. Схемы в базисах из элементов, имеющих не более двух входов

§1. Основные определения и формулировка результата

§2. Неизбыточные схемы, допускающие единичные проверяющие

тесты длины п +

§3. Неизбыточные схемы, допускающие единичные проверяющие

тесты длины п +

§4. Неизбыточные схемы, допускающие единичные проверяющие

тесты длины п +

§5. Константные неисправности на входах функциональных элементов
Глава 2. Схемы в произвольных функционально полных конечных базисах
§1. Вспомогательные определения и формулировка результата
§2. Единичные проверяющие тесты для схем в базисах {х&у, х},
{х V у. х} с особенностью поломки инвертора
§3. Единичные проверяющие тесты для схем в базисе {<5, х, особенностью поломки инвертора
§4. Единичные проверяющие тесты для схем в базисе {х © у, х ~
У,Ч>7І
§5. Доказательство основной теоремы
Глава 3. Фиксированное число неисправностей в базисе Же-галкина

Введение
Данная работа является исследованием в области математической теории контроля исправности и диагностики неисправностей управляющих систем.
К числу основных модельных объектов математической теории синтеза, сложности, надежности и диагностики управляющих систем относятся схемы из ненадежных элементов, реализующие булевы функции. Для обеспечения надежного функционирования схем необходимо решать задачу контроля исправности ее элементов. Для решения этой задачи С.В.Яблонским и И.А.Чегис [1, 2] были предложены логические способы контроля исправности и диагностики неисправностей управляющих систем, суть которых состоит в том, что на входы схем подаются некоторые специальным образом подобранные “проверяющие” наборы значений переменных и на основе наблюдаемых выходных значений схемы делается заключение об ее исправности и характере неисправностей (при их наличии).
Пусть /(х) — произвольная булева функция, зависящая от переменных XI, £2, • ■ ■ 1 хп, а 5 — схема из функциональных элементов в некотором базисе В, реализующая функцию /(х). На схему воздействует некоторый источник неисправностей, под влиянием которого схема вместо функции /(х) может выдавать какие-то функции неисправностей д(х),д2(х),..., дк(х) [3]. Всякое множество Т = {а, од,..., ф } входных наборов схемы 5 называется проверяющим тестом для этой схемы, если для любой функции неисправности дг(х), не равной тождественно /(х), в Т найдется хотя бы один набор ф такой, что /(сг) ф дДсг). Если для любой пары функций неисправностей дг(х) и д0{х) в проверяющем тесте Т найдется хотя бы один набор сг такой, что дг(а) ф д3{&), то такой тест Т называется диагностическим тестом схемы 5; он позволяет не только обнаружить

неисправность схемы 5, но и в случае ее неисправности определить, какая именно функция неисправности реализуется на ее выходе. Число I — количество наборов в Т называется длиной теста.
Различают полные тесты, когда в схеме допускается произвольное количество неисправных элементов, и единичные тесты, когда в неисправное состояние может перейти ровно один элемент схемы. В случае единичных тестов принято рассматривать лишь неизбыточные схемы, т.е. такие схемы, в которых при переходе в любое неисправное состояние любого элемента схема реализует нетривиальную [3], то есть отличную от /(х) функцию неисправности д(х).
В качестве тривиального теста всегда можно взять тест, содержащий все 2П наборов значений переменных булевой функции от п переменных. Соответственно возникает вопрос, возможно ли в том или ином случае найти более короткие тесты. Так возникает задача построения минимальных тестов, т.е. тестов, содержащих минимальное число наборов.
Пусть 0(Т) — длина теста Т. Введем обозначения: О(Б) = штР(Т), где минимум берется по всем проверяющим (или диагностическим) тестам Т для схемы из функциональных элементов 5; Ив{/) = пппТ)(5), где минимум берется по всем схемам 5 в данном базисе В, реализующим функцию /; Дв(те) = тах Ов(/), где максимум берется по всем функциям от п переменных. Функция Ов{п) называется функцией Шеннона длины проверяющего (диагностического) теста для базиса В. Она показывает, в частности, что для любой булевой функции от п переменных существует схема и тест, длина которого не превосходит /?д(п). Аналогично определяется функция Шеннона длины проверяющего (диагностического) теста для контактных схем.
К основным задачам теории диагностики схем относится поиск верхних и нижних оценок функций Шеннона для единичных или полных проверяю-

лином Жегалкина, в котором К - конъюнкция минимальной длины(если таких конъюнкций несколько, выбираем из них любую). Без ограничения общности можем перенумеровать переменные так, чтобы получить К = Х&,... &,хт. Так же заметим, что /(ад,..., хп) можно представить в виде Р = К 0 К2 ф Къ 0 ... ® Ад ® с 0 Ь(тос1 2) 0
Функцию /(ж) реализуем схемой 5*, представленной на рисунке 13.

Под блоком В понимается подсхема, изображённая на рисунке 14; очевидно, при подаче на входы этого блока переменных х и у в исправном состоянии на выходе будет реализована функция х!ку.
Под блоком понимается подсхема, изображённая на рисунке 15; очевидно, при подаче на входы этого блока переменных х и у в исправном состоянии на выходе будет реализована функция х&гу.
Под блоком й понимается подсхема, изображённая на рисунке 16. При подаче на входы этого блока переменных х и у в исправном состоянии на