Синтез легкотестируемых схем при константных неисправностях на выходах элементов

• Автор: Бородина, Юлия Владиславовна
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2008
• Место защиты: Москва
• Количество страниц: 74 с. : ил.

Глава I. Схемы, допускающие минимальные полные
проверяющие тесты
§ 1. Схемы, допускающие полные проверяющие тесты
единичной длины в случае неисправностей типа "1"
§ 2. Схемы, допускающие минимальные полные
проверяющие тесты в случае неисправностей типа "1"
§ 3. Неисправности типа "0"
Глава II. Синтез легкотестируемых схем для систем булевых
функций
§ 1. Реализация систем булевых функций в базисе {&, V,
§ 2. Реализация систем монотонных функций в базисе {&, V}
§ 3. Некоторые другие классы булевых функций
Глава III. Синтез легкотестируемых схем в базисе
Жегалкина в случае единичных неисправностей
Список литературы

Диссертация посвящена синтезу легкотестируемых схем из функциональных элементов в различных базисах для булевых функций в случае однотипных константных неисправностей на выходах элементов. В ней найдена минимальная длина проверяющего теста при реализации произвольной булевой функции в базисе {&, V, "}, для этого же базиса предложены конструктивные методы синтеза легкотестируемых схем для систем булевых функций, а также найдены способы реализации произвольных булевых функций схемами в базисе Жегал-кина, допускающими короткие единичные проверяющие тесты.

Пусть S — некоторая схема из функциональных элементов [4], [29] с одним выходом, реализующая булеву функцию /(ж), х — (х, х2) ..., хп)
Элементы схемы S могут приходить в неисправное состояние, в результате чего схема может реализовывать функцию, отличную от функции /.
Для обеспечения надежного функционирования схемы S необходимо решать задачу контроля исправности ее элементов. Для решения этой задачи С.В. Яблонским [25] предложены (в случае контроля исправности элементов общих управляющих систем) логические методы контроля, суть которых состоит в том, что на входы схемы S подаются некоторые специальным образом подобранные "проверяющие" наборы значений переменных х1}Х2 хп и на основе выходных значений схемы делается заключение об ее исправности и характере неисправностей (при их наличии).
Функция, реализуемая на выходе схемы при наличии в схеме неисправных элементов, называется функцией неисправности. Всякое множество Т входных наборов схемы S называется полным проверяющим

тестом для этой схемы, если для любой функции неисправности д(х), не равной тождественно /(.%'), в Т найдется хотя бы один набор а такой, нто /(а) ф д(а) [28],[19]. Число наборов, составляющих тест, называется длиной теста. В качестве тривиального теста всегда можно взять тест, содержащий все 2" наборов значений переменных булевой функции от п переменных.
Но прежде всего интересна задача построения минимальных тестов, т.е. тестов, содержащих минимальное число наборов. В простейшем случае решение задачи сводится к перебору, что затруднительно при росте п. Кроме того, длина минимального теста может существенно зависеть и от вида схемы, реализующей заданную функцию.
Введем обозначения [28], [19]: D{T) —длина теста Т; D(S) = minD(T), где минимум берется по всем полным проверяющим тестам Т для схемы S', D(f,B) = rninD(S), где минимум берется по всем схемам S в данном базисе В, реализующим функцию /;
D(n, В) = таxD(/, В),
где максимум берется по всем булевым функциям f от п переменных. Функция D(n, В) называется функцией Шеннона длины полного проверяющего теста для базиса В.
Кроме проверяющих тестов, рассматриваются еще так называемые диагностические тесты. Множество Т входных наборов схемы S называется полным диагностическим тестом для этой схемы, если Т является полным проверяющим тестом для S и для любых двух различных функций неисправности дфх) и (х) в Т найдется набор а такой, что дфа) ф <72[28],[19]. Для длин полных диагностических тестов также определяется функция Шеннона D(n, В) в заданном базисе В.

Схема Sf служит для контроля исправности элементов из подсхем S4 и Sf. В Sf содержится столько конъюнкторов, сколько инверторов и конъюнкторов — в схемах S4 я Sf, и каждый конъюнктор Е из Sf однозначно соответствует некоторому элементу Е' одной из схем S4 или Sf. Если Е' — инвертор из S4, то один вход Е соединяется с выходом Е', а второй вход Е — с тем входом схемы S4, с которым соединен вход инвертора Е'. Предположим теперь, что Е' — конъюнктор из Sf, т.е. элемент некоторой цепи Z из конъюнкторов. В этом случае один вход конъюнктора Е соединяем с выходом Е', а на второй вход подаем значение той переменной, отрицание которой подается на левый вход верхнего элемента соответствующей цепи Z. Если все элементы