Об оценках функций Шеннона длин тестов при некоторых неисправностях входов схем

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

Содержание
Введение
1 Тестирование булевых функций относительно линейных слипаний
переменных
1.1 Основные определения и обозначения
1.2 Проверяющий тест относительно множественных линейных слипаний переменных
1.3 Диагностические тесты относительно линейных слипаний переменных
1.4 Локальные Ажратные слипания переменных
2 Тестирование булевых функций относительно монотонных симметрических слипаний переменных
2.1 Основные определения и обозначения
2.2 Проверяющий тест относительно множественных монотонных симметрических слипаний переменных
2.3 Диагностический тест относительно монотонных симметрических слипаний переменных
2.4 Диагностический тест относительно дизъюнктивных слипаний переменных
3 Тестирование булевых функций относительно вытеснения переменных

3.1 Основные определения и обозначения
3.2 Проверяющий тест
3.3 Диагностический тест
Заключение
Литература

Введение
Данная работа является исследованием в области теории надежности и контроля управляющих систем. В качестве управляющих систем рассматриваются схемы, реализующие булевы функции. Схемы могут переходить в неисправные состояния. Возникает задача обнаружения и диагностики неисправностей. Данная задача впервые была поставлена в работах И. А. Чегис и С. В. Яблонского [43,44] Ими были предложены логические методы контроля управляющих систем. На входы схемы подаются специальным образом подобранные значения входных переменных Х,..., х„, от которых зависит реализуемая булева функция. По получившимся выходным значениям схемы можно судить об исправности схемы или характере неисправности в случае наличия таковой.
Математически предложенный способ контроля формализуется следующим образом. Пусть /(жт,..., хп) — булева функция, а Е/ — схема, ее реализующая. Пусть на схему воздействует источник неисправностей Б, под действием которого Е/ может перейти в неисправное состояние и реализовать одну из попарно неравных булевых функций /1(^1, ...,хп), /2(^1, хп),..., /т(хь ..., хп). Функции ...,хп),/т(х 1,...,.т„) называются функциями неисправности.
Множество наборов Т = {од,.... называется проверяющим тестом для схемы Е/ относительно источника неисправностей В, если для любой функции неисправности /фху, ...,хп), не равной исходной, в множестве Т найдется набор, на котором функции /{х, ...,х„) и /Джх,..., хп) принимают разные значения. Если же в Т для любых двух неравных функций из множества

вим для каждой пары три набора так, чтобы получалась проверяющая пятерка.

Отсюда следует, что |5*(/)| < 15 •
Теперь пусть /(ху,..., х„) существенно зависит от всех своих переменных. Заметим, что в этом случае г/у = ^ + к — 1. Действительно, пусть среди переменных хц,..., Х{^к-1 ис все переменные принадлежат одному множеству линейности (определено в разделе 1.2). Тогда существует переменная # < А: — 1, для которой есть проверяющая пара с переменной х,+к-1- Выберем к максимально возможным. Все переменные х..., х^+к-1 принадлежат одному множеству линейности. Тогда = ij + С суу = ф + к — 1. Тогда неравенства из предыдущего абзаца преобразуются в: ij > р/, + 1, р/ > г/,_у, г/у = ?/ + к — 1. Получаем:
сц = 1} + к — 1 > р/_у + к > Отсюда следует, что при указанных

условиях на пик число проверяющих нар асимптотически не более 2 • —. Тогда

строим по ним ДД/), Зк(/) < 10 ■

Лемма 9. Пусть д(х,..., хт) — некоторая линейная функция т переменных,
А = {аь...,от} — множество булевых наборов. Тогда существует отличная от д линейная функция /г(.гу,..., хт), равная функции д на всех наборах множества А.
Доказательство. Пусть набор а,; = (а у,..., а‘т), д{а,) = а;. Запишем систему линейных уравнений относительно возможных коэффициентов линейной функции сь...,ет+1:
Са[ ф ... @ стагт © с„,+1 = ау,
суОу Ф ... © с„,ат © ст+ — а,т.
Система совместна в силу существования функции д(ху, ...,хт). Но посколь
ку число неизвестных меньше числа уравнений, получаем, что существует как