Синтез легкотестируемых схем при константных неисправностях на выходах элементов тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М В ЛОМОНОСОВА

МЕХАНИКО-МАТЕМАТИЧЕСКИЙ ФАКУЛЬТЕТ

На правах рукописи УДК 519 718 7

Бородина Юлия Владиславовна

СИНТЕЗ ЛЕГКОТЕСТИРУЕМЫХ СХЕМ ПРИ КОНСТАНТНЫХ НЕИСПРАВНОСТЯХ НА ВЫХОДАХ ЭЛЕМЕНТОВ

Специальность 01 01 09 — Дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата физико-математических наук

□ОЗ168906

Москва 2008

003168906

Работа выполнена на кафедре дискретной математики механико-математического факультета Московского государственного университета имени М.В. Ломоносова

Научный руководитель- доктор физико-математических наук,

профессор Николай Петрович Редькин

Официальные оппоненты доктор физико-математических наук,

профессор Михаил Юрьевич Мошков кандидат физико-математических наук, доцент Дмитрий Сергеевич Романов

Ведущая организация

Институт математики им С Л Соболева СО РАН

Защита диссертации состоится 23 мая 2008 г в 16 часов 40 минут на заседании диссертационного совета Д 501 001 84 при МГУ по адресу 119991, Российская Федерация, Москва, ГСП-1, Ленинские горы, Московский государственный университет имени М В Ломоносова, механико-математический факультет, аудитория 14-08

С диссертацией можно ознакомиться в библиотеке механико-математического факультета МГУ имени М В Ломоносова (Главное здание, 14-й этаж).

Автореферат разослан 23 апреля 2008 года

Ученый секретарь диссертационого совета

Д 501 001 84 при МГУ, доктор физ -матем наук, профессор

А О Иванов

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы

Данная работа является исследованием в области математической теории контроля исправности и диагностики неисправностей управляющих систем

Пусть 5 — некоторая схема из функциональных элементов с одним выходом, реализующая булеву функцию /(х), х = хг, , х„)

Элементы схемы 5 могут приходить в неисправное состояние, в результате чего схема может реализовывать функцию, отличную от функции /

Для обеспечения надежного функционирования схемы 5 необходимо решать задачу контроля исправности ее элементов Для решения этой задачи С В Яблонским1 предложены (в случае контроля исправности элементов общих управляющих систем) логические методы контроля, суть которых состоит в том, что на входы схемы 5 подаются некоторые специальным образом подобранные "проверяющие" наборы значений переменных х^жг,.. ,х„ и на основе выходных значений схемы делается заключение об ее исправности и характере неисправностей (при их наличии)

Функция, реализуемая на выходе схемы при наличии в схеме неисправных элементов, называется функцией неисправности Всякое множество Т входных наборов схемы 5 называется полным проверяющим тестом для этой схемы, если для любой функции неисправности д(х), не равной тождественно /(х), в Т найдется хотя бы один набор а такой, что /(¿г) ф д{а)2 Число наборов, составляющих тест, называется длиной теста В качестве тривиального теста всегда можно взять тест, содержащий все 2" наборов значений переменных булевой функции от п переменных

Но прежде всего интересна задача построения минимальных тестов, те тестов, содержащих минимальное число наборов. В простейшем случае решение задачи сводится к перебору, что затруднительно при росте п Кроме того, длина минимального теста может существенно зависеть и от вида схемы, реализующей заданную функцию.

Пусть £>(Т) — длина теста Т, £>(5) = тш.О(Т), где минимум берется по всем полным проверяющим тестам Т для схемы 5, £>(/, В) = тш£)(5), где минимум берется по всем схемам 5 в данном базисе В,

1Чегис И А , Яблонский С В Логические способы контроля работы электрических схем // Труды МИАН — 1958 — Т 51 — С 270-360

2Яблонский С В Некоторые вопросы надежности и контроля управляющих систем // Математические вопросы кибернетики — 1988 — № 1 — С 5-25

реализующим функцию /,

2?(п,£) = тах !>(/,£),

где максимум берется по всем булевым функциям /от п переменных Функция В) называется функцией Шеннона длины полного проверяющего теста для базиса В

Кроме проверяющих тестов, рассматриваются еще так называемые диагностические тесты Множество Т входных наборов схемы Б называется полным диагностическим тестом для этой схемы, если Т является полным проверяющим тестом для 5 и для любых двух различных функций неисправности д\{х) и <72(ж) в Т найдется набор а такой, что ^(¿г) -ф д2(5") Для длин полных диагностических тестов также определяется функция Шеннона 1)(п, В) в заданном базисе В В настоящее время задачи логического контроля исправности схем из функциональных элементов часто формулируются так оценить сверху и снизу (в идеале — найти точные значения) величин £>(/, В) и Ю(п,В) для различных базисов В Представляют интерес также оценки "промежуточных" величин В) = тах{£>(/, В) / € К}, где К — некоторый выделенный класс булевых функций от п переменных.

Для упрощения решения этих задач существуют следующие пути ограничение типов возможных неисправностей и их количества, выбор схем определенного типа, выбор класса К булевых функций, синтез легкотестируемых схем

В настоящее время выделяются три основных типа неисправностей константные, однотипные константные и инверсные Неисправности каждого из указанных типов могут предполагаться либо на входах, либо на выходах элементов схемы Константная неисправность типа а (где а равно 0 или 1) на входе (выходе) элемента означает, что на этот вход подается константа а (соответственно, значение на выходе этого элемента всегда равно а) В общем случае значение а может быть своим у каждого неисправного элемента. В случае однотипных константных неисправностей значение а предполагается одним и тем же у всех неисправных элементов Инверсная неисправность на входе элемента означает, что подаваемое на этот неисправный вход значение противоположно значению, подаваемому на исправный вход, инверсная неисправность на выходе означает, что значение на выходе неисправного элемента противоположно значению на выходе исправного элемента

Число неисправных элементов в схеме может предполагаться или любым, или не превосходящим N В последнем случае обычно полагают N = 1, говоря о единичных неисправностях данного типа и,

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

При синтезе легкотестируемых схем главной целью является построение схемы (со сколь угодно большой сложностью, без каких-либо ограничений на порядок ветвления выходов и т д ) с минимально возможной длиной проверяющего теста

Основоположник математической теории тестов С В Яблонский и ряд его учеников и последователей в основном разрабатывали логические методы контроля контактных схем В дальнейшем существенное внимание стало уделяться схемам из функциональных элементов, однако соответствующая теория для схем из функциональных элементов все еще далека от завершенности Ряд важных результатов в оценивании длин тестов для схем из функциональных элементов при различных типах неисправностей получен в работах S Reddy, В Н Носкова, Н П Редышна, С В Коваценко, В Г Хахулина

Для единичных константных неисправностей на выходах элементов S Reddy3 доказал, что для базиса Жегалкина Вх = {&, ф, 1}. при любом натуральном п функция Шеннона D(n,Bi) длины единичного проверяющего теста в случае константных неисправностей на выходах элементов удовлетворяет неравенству D(n, В\) < п + 3

В третьей главе настоящей работы оценка Reddy уточнена в случае единичных однотипных константных неисправностей на выходах элементов

Для произвольного полного конечного базиса В в случае константных неисправностей на выходах элементов Н П. Редькин4'5 получил оценку D(n, В) ^ 2(2^/^ + + п) функции Шеннона длины полного проверяющего теста Им же получены6 асимптотические оценки функции Шеннона длины полного проверяющего теста в случае константных неисправностей на входах элементов схем в стандартном базисе В0 = {&, V,"}. В Г.Хахулин7 оценивал длины пол-

3Reddy S М Easily testable realization for logic functions // IEEE Trans Comput - 1972 - v 21 - N1 - P 124-141

4Редькин НПО полных проверяющих тестах для схем из функциональных элементов // Вестник Московского университета Серия 1 Математика Меха-

ника - 1986 - N 1 - С 72-74

6Редькин НПО полных проверяющих тестах для схем из функциональных элементов // Математические вопросы кибернетики. — Вып 2 — 1989 — С 198-222

6Редькии НПО проверяющих тестах для схем при константных неисправностях на входах элементов // Вестник Московского университета Серия 1 Математика Механика — 1997 — Л"'1 — С 12-18

7Хахулин В Г О проверяющих тестах для счетчика четности // Дискретная математика — 1995 — Т7, вып 4 — С 51-59

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

В случае однотипных константных неисправностей верхние оценки функций Шеннона найдены Н П Редькиньш8: при любом натуральном п функция Шеннона £>(п, В0) длины полного проверяющего теста в случае однотипных константных неисправностей на выходах элементов удовлетворяет неравенству £>(п, Во) < п

В первой главе настоящей работы эта оценка Н.П Редькина уточнена, и найдено точное значение П(п,Во) — 2, п — 2,3,

Кроме того, для стандартного базиса Во Н П Редькиным получены оценки длин тестов в случае же однотипных константных неисправностей на входах элементов9, а также длин единичных диагностических тестов в случае однотипных константных неисправностей на входах или на выходах элементов10,11.

Для инверсных неисправностей на выходах элементов оценки функций Шеннона длин различных тестов получены Н.П Редькиным12'13 и С В Коваценко14

В серии работ В.Н Носкова15 предложены несколько иные методы логического контроля схем из функциональных элементов (и более общих логических устройств)

Цель работы

8Редькин НПО схемах, допускающих короткие тесты // Вестник Московского университета Серия 1 Математика Механика — 1988 — N 2 — С 17-21

9Редышн НПО проверяющих тестах для схем при однотипных константных неисправностях на входах элементов // Известия вузов Математика — 1988 ~ №7 - С 57-64

10Редькин НПО схемах, допускающих короткие единичные диагностические тесты // Дискретная математика — 1989 — Т1, вып 3 — С 71-76

11Редькин НПО единичных диагностических тестах для однотипных константных неисправностей на выходах функциональных элементов // Вестник Московского университета Серия 1 Математика Механика — 1992 — N 5 — С 43-46

12Редькин НПО единичных проверяющих тестах схем при инверсных неисправностях элементов // XII Международная конференция по проблемам теоретической кибернетики (Нижний Новгород, 1999) Тезисы докладов — М Изд-во механико-математического факультета МГУ, 1999 — С 196

13Редькин Н П Единичные проверяющие тесты для схем при инверсных неисправностях элементов // Математические вопросы кибернетики — 2003 — Вып 12 - С. 217-230

14 Коваценко С В Синтез легкотестируемых схем в базисе Жегалкина для инверсных неисправностей // Вестник Московского университета Серия 15 Вычислительная математика и кибернетика — 2000 — Л"*2 — С 45-47

15см , напр Носков В Н Метод синтеза удобных для контроля комбинационных схем // Дискретная математика — 1993 — Т 5, вып 4 — С 3-23

Целью настоящей работы является синтез легкотестируемых схем из функциональных элементов в различных базисах при однотипных константных неисправностях на выходах элементов и получение оценок длины тестов для рассматриваемых схем.

Научная новизна работы

Все результаты работы являются новыми В диссертации получены следующие основные результаты

1 Конструктивно установлено точное значение функции Шеннона длины полного проверяющего теста для схем из функциональных элементов в базисе {&, V, "} в случае однотипных константных неисправностей на выходах элементов

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

3 Для базиса Жегалкина в случае неисправностей типа "1" конструктивно найдено точное значение функции Шеннона длины единичного проверяющего теста

4 Для базиса Жегалкина в случае неисправностей типа "О" разработан способ реализации произвольных булевых функций схемами, допускающими единичные проверяющие тесты длины 2

Методы исследования

В диссертации используются методы дискретной математики и математической кибернетики, теории управляющих систем, математической теории диагностики управляющих систем

Теоретическая и практическая ценность

Работа носит теоретический характер Результаты диссертации могут найти применение в теории диагностики управляющих систем Представленные в диссертации методы синтеза могут быть использованы при практическом синтезе легкотестируемых схем

Апробация работы

Результаты диссертации докладывались на семинаре "Диагностика управляющих систем" под руководством профессора Н П Редькина

(2004-2008 гг), на семинаре "Синтез и сложность управляющих систем" под руководством академика РАН О Б Лупанова (апрель 2006г), профессора О М Касим-Заде (февраль-март 2008г), на семинаре "Математические вопросы кибернетики" под руководством профессора

0 М Касим-Заде (ноябрь 2007г, апрель 2008г), на VIII Международном семинаре "Дискретная математика и ее приложения" (Москва, февраль 2004г), на IX Международном семинаре "Дискретная математика и ее приложения", посвященном 75-летию со дня рождения академика О.Б Лупанова (Москва, июнь 2007г.), на Российской конференции "Математика в современном мире", посвященной 50-летию Института математики им С Л. Соболева СО РАН (Новосибирск, сентябрь 2007г), на XXVIII Конференции молодых ученых механико-математического факультета МГУ (апрель 2006г), на научной конференции "Ломоносовские чтения" (апрель 2006г, апрель 2007г, апрель 2008г)

Публикации

Результаты диссертации опубликованы в 5 работах автора, список которых приведен в конце автореферата [1-5]

Структура и объем работы

Диссертация состоит из введения, трех глав и списка литературы из 35 наименований Общий объем диссертации — 74 страницы, в работе содержится 8 рисунков

СОДЕРЖАНИЕ ДИССЕРТАЦИИ

Во введении содержится обзор результатов, связанных с темой диссертации, приводится постановка задачи, дается краткое изложение основных результатов диссертации

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

В § 1 главы I выделяются классы булевых функций, которые реализуются схемами, допускающими полный проверяющий тест длины

1 при неисправностях типа "1" на выходах элементов

Теорема 1.1. Пусть для функции f от п переменных найдутся такой нулевой набор а = (oj, . .,сгп) с максимальным числом единиц и такая тупиковая дизъюнктивная нормальная форма F, что если для какого-то j € {1, , п} значение а3 = 0, то соответству-

ющая переменная х3 входит в Р без отрицания Тогда функцию / можно реализовать схемой из функциональных элементов, допускающей полный проверяющий тест длины 1

Назовем функцию /(¿г), где х = (хг, х2, ■ , хп), монотонной (антимонотонной) по переменной а;,, если для любых двух соседних по г-ой переменной наборов а = (ах, ,ог,_1,01ог,+1, , аг„) и а' = («1, , 1, а,+ъ , ап) выполняется неравенство /(а) ^ /(а') (соответственно, /(а) > /(а7))

Теорема 1.2. Любую булеву функцию, монотонную или антимонотонную по каждой переменной, можно реализовать схемой из функциональных элементов, допускающей полный проверяющий тест длины 1

Следствие 1.1 Любую монотонную булеву функцию, отличную от константы, можно реализовать схемой из функциональных элементов в базисе {&, V}, допускающей полный проверяющий тест длины 1

Теорема 1.3. Любую булеву функцию, отличную от константы и монотонную или антимонотонную по каждой переменной, кроме одной, можно реализовать схемой из функциональных элементов, допускающей полный проверяющий тест длины 1.

В § 2 главы I установлено точное значение функции Шеннона длины полного проверяющего теста для схем из функциональных элементов в указанном базисе в случае константных неисправностей типа "1" на выходах элементов

Теорема 1.4. Любую булеву функцию от п переменных можно реализовать схемой, допускающей полный проверяющий тест, длина которого не превосходит 2

Этот результат уточняет сформулированную выше теорему Н П Редькина

Теорема 1.5. Для любого п > 2 выполняется равенство

{&, V, -}) = 2

Верхняя оценка для этой теоремы следует из теоремы 1 4, требуемая нижняя оценка £>(«, {&, V,"}) ^ 2 достигается для функции Ж1&Х2 V Х\&Ж2

В § 3 главы I аналогичные теоремам 1 1-1 5 результаты устанавливаются для случая константных неисправностей типа "О" на выходах элементов

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

В § 1 главы II для систем из произвольных булевых функций доказала

Теорема 2.1. Любую систему 3-п>гп из т. булевых функций, отличных от констант, можно реализовать схемой из функциональных элементов, допускающей полный проверяющий тест длины не более 1 + 9, где д < т — число функций из 3-п,т, сохраняющих единицу (т.е равных 1 на наборе (1, , 1))

Значение 1+д в этой Оценке длины теста в общем случае нельзя заменить ни на какое число, меньшее д

Следствие 2.1. Любую систему Тп>т из т монотонных булевых функций, отличных от констант, можно реализовать схемой из функциональных элементов, допускающей полный проверяющий тест длины 2

Следствие 2.2. Пусть Тп,т — система из т булевых функций, отличных от констант, каждая из которых монотонна по каждой из I переменных х\, х^, ■ ,Х1 и антимонотонна по каждой из к переменных х 1+1, , Тогда систему Тп;т можно реализовать схемой из функциональных элементов, допускающей полный проверяющий тест, длина которого не превосходит 1 + 2"~к~1

В § 2 главы II системы монотонных булевых функций реализуются легкотестируемыми схемами в монотонном базисе {&, V}

Теорема 2.2. Любую систему Тп,т из т монотонных булевых функций, отличных от констант, можно реализовать схемой из функциональных элементов в базисе {&, V}, допускающей полный проверяющий тест длины, не превосходящей тт{т, п}.

В § 3 главы II рассматриваются системы булевых функций из некоторых специальных классов Для таких систем предложен метод синтеза схем с определенными ограничениями на количество и расположение инверторов, допускающих полный проверяющий тест, длина которого не превосходит тт{т, 1} (теоремы 2 3 и 2 4)

В ряде случаев этот метод позволяет уточнить оценку длины теста в следствии 2 2

В главе III доказываются теоремы о реализации произвольных булевых функций схемами из функциональных элементов в базисе Жегалкина {&:, ©, 1}, допускающими единичные проверяющие тесты длины 1 или 2 в случае однотипных константных неисправностей на выходах элементов Во всех этих теоремах явно указывается способ построения схемы, а тест зависит от рассматриваемой функции

В случае неисправностей типа "1" справедлива

Теорема 3.1. Любую булеву функцию можно реализовать неизбыточной схемой из функциональных элементов в базисе {&, О), 1, 0}, допускающей единичный проверяющий тест длины 1

В случае неисправностей типа "0" справедлива

Теорема 3.2. Любую булеву функцию можно реализовать неизбыточной схемой из функциональных элементов в базисе {&, ©, 1,0}, допускающей единичный проверяющий тест., длина которого не превосходит 2

Эти результаты уточняют приведенную выше теорему Э КесЫу в случае однотипных константных неисправностей

Автор глубоко благодарен своему научному руководителю доктору физико-математических наук, профессору Николаю Петровичу Редькину за постановку задач, ценные идеи и постоянное внимание к работе, профессору Л А. Шоломову за ценные замечания, а также всем сотрудникам кафедры дискретной математики механико-математического факультета МГУ им М В Ломоносова и отдела теоретической кибернетики Института прикладной математики им М В Келдыша РАН за поддержку и доброжелательное отношение

ПУБЛИКАЦИИ АВТОРА ПО ТЕМЕ ДИССЕРТАЦИИ

1 Бородина Ю В Синтез легкотестируемых схем в базисе {&, V, "} при однотипных константных неисправностях на выходах элементов // Дискретная математика — 2005 — Т 17, вып 1 — С 129-140.

2 Бородина Ю В Синтез легкотестируемых схем в базисе {&, V,"} для систем функций из некоторых классов // Вестник Московского университета Серия 1 Математика Механика — 2007 — №4 — С. 68-72

3 Бородина Ю В О синтезе легкотестируемых схем в случае однотипных константных неисправностей на выходах элементов // Вестник Московского университета Серия 15 Вычислительная математика и кибернетика — 2008 — №1 — С 40-44

4 Бородина Ю В. Синтез легкотестируемых схем в базисе {&, V,"}

при однотипных константных неисправностях на выходах элементов // Материалы VIII Международного семинара "Дискретная математика и ее приложения "(Москва, 2004г) — М • Изд-во механико-математического факультета МГУ, 2004г — С 5&-58

5 Бородина Ю В О синтезе легкотестируемых схем в случае однотипных константных неисправностей на выходах элементов //Материалы IX Международного семинара "Дискретная математика и ее приложения", посвященного 75-летию со дня рождения академика О.Б Лупанова (Москва, 2007г) — М Изд-во механико-математического факультета МГУ, 2007г— С 64-65

Издательство ЦПИ при механико-математическом факультете МГУ им М В Ломоносова

Подписано в печать

Формат 60x90 1/16 Уел печ л 0,75 Тираж -/ОО экз Заказ

Отпечатано с оригинал-макета на типографском оборудовании механико-математического факультета

Введение.

Глава I. Схемы, допускающие минимальные полные проверяющие тесты.

§ 1. Схемы, допускающие полные проверяющие тесты единичной длины в случае неисправностей типа "1".

§ 2. Схемы, допускающие минимальные полные проверяющие тесты в случае неисправностей типа "1".

§ 3. Неисправности типа "0".

Глава II. Синтез легкотестируемых схем для систем булевых функций.

§ 1. Реализация систем булевых функций в базисе {&, V,.

§ 2. Реализация систем монотонных функций в базисе {&, V}.

§ 3. Некоторые другие классы булевых функций.

Глава III. Синтез легкотестируемых схем в базисе

Жегалкина в случае единичных неисправностей.

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

Пусть S — некоторая схема из функциональных элементов [4], [29] с одним выходом, реализующая булеву функцию /(ж), х = (rci, ., хп)

Элементы схемы S могут приходить в неисправное состояние, в результате чего схема может реализовывать функцию, отличную от функции /.

Для обеспечения надежного функционирования схемы S необходимо решать задачу контроля исправности ее элементов. Для решения этой задачи С.В. Яблонским [25] предложены (в случае контроля исправности элементов общих управляющих систем) логические методы контроля, суть которых состоит в том, что на входы схемы S подаются некоторые специальным образом подобранные "проверяющие" наборы значений переменных xi, х^,., хп и на основе выходных значений схемы делается заключение об ее исправности и характере неисправностей (при их наличии).

Функция, реализуемая на выходе схемы при наличии в схеме неисправных элементов, называется функцией неисправности. Всякое множество Т входных наборов схемы S называется полным проверяющим тестом для этой схемы, если для любой функции неисправности д(х), не равной тождественно /(ж), в Т найдется хотя бы один набор а такой, что /(а) ф д(а) [28],[19]. Число наборов, составляющих тест, называется длиной теста. В качестве тривиального теста всегда можно взять тест, содержащий все 2П наборов значений переменных булевой функции от п переменных.

Но прежде всего интересна задача построения минимальных тестов, т.е. тестов, содержащих минимальное число наборов. В простейшем случае решение задачи сводится к перебору, что затруднительно при росте п. Кроме того, длина минимального теста может существенно зависеть и от вида схемы, реализующей заданную функцию.

Введем обозначения [28], [19]: D(T) — длина теста Т; D(S) — minD(T), где минимум берется по всем полным проверяющим тестам Т для схемы 5; D(f:B) = min D(S), где минимум берется по всем схемам S в данном базисе В, реализующим функцию /;

D(n,B) = maxD(f, В), где максимум берется по всем булевым функциям / от п переменных. Функция D(n, В) называется функцией Шеннона длины полного проверяющего теста для базиса В.

Кроме проверяющих тестов, рассматриваются еще так называемые диагностические тесты. Множество Т входных наборов схемы S называется полным диагностическим тестом для этой схемы, если Т является полным проверяющим тестом для S и для любых двух различных функций неисправности gi(x) и в Т найдется набор а такой, что g\(cr) ф #2(0") [28],[19]. Для длин полных диагностических тестов также определяется функция Шеннона D(n, В) в заданном базисе В.

В настоящее время задачи логического контроля исправности схем из функциональных элементов часто формулируются так: оценить сверху и снизу (в идеале — найти точные значения) величин D(f, В) и D(n, В) для различных базисов В. Представляют интерес также оценки "промежуточных" величин D(K,B) = max{D(/, В) : f Е К}, где К — некоторый выделенный класс булевых функций от п переменных. Для упрощения решения этих задач существуют следующие пути:

- ограничение типов возможных неисправностей и их количества [1],

И, [П], [12];

- выбор схем определенного типа [9], [10];

- выбор класса К булевых функций;

- синтез легкотестируемых схем [14], [18].

В настоящее время выделяются три основных типа неисправностей: константные, однотипные константные и инверсные. Неисправности каждого из указанных типов могут предполагаться либо на входах, либо на выходах элементов схемы. Константная неисправность типа а (где а равно 0 или 1) на входе (выходе) элемента означает, что на этот вход подается константа а (соответственно, значение на выходе этого элемента всегда равно ск). В общем случае значение а может быть своим у каждого неисправного элемента. В случае однотипных константных неисправностей значение а предполагается одним и тем же у всех неисправных элементов. Инверсная неисправность на входе элемента означает, что подаваемое на этот неисправный вход значение противоположно значению, подаваемому па исправный вход; инверсная неисправность на выходе означает, что значение на выходе неисправного элемента противоположно значению на выходе исправного элемента.

Число неисправных элементов в схеме может предполагаться или любым, или не превосходящим N. В последнем случае обычно полагают N = 1, говоря о единичных неисправностях данного типа и, соответственно, о длине единичного проверяющего теста или длине единичного диагностического теста.

Везде ниже употребляется одно и то же обозначение D(n, В) для функций Шеннона длин тестов при различных неисправностях, но всякий раз поясняется, какие неисправности (константные, константные данного типа, инверсные, на входах или на выходах) и какие тесты (полные или единичные, проверяющие или диагностические) имеются в виду.

Что касается выбора схем определенного типа, то при исследовании схем в выбранном базисе В можно ограничиваться схемами с заданным порядком ветвления выходов элементов, неизбыточными схемами1 , схемами с условиями на расположение элементов, схемами заданной сложности и т.п.

При синтезе легкотестируемых схем главной целью является построение схемы (со сколь угодно большой сложностью, без каких-либо ограничений на порядок ветвления выходов и т.д.) с минимально возможной длиной проверяющего теста.

Основоположник математической теории тестов С.В. Яблонский и ряд его учеников и последователей в основном разрабатывали логические методы контроля контактных схем (см. [25], [27], обзорную работу [28]). В дальнейшем существенное внимание стало уделяться схемам из функциональных элементов, однако соответствующая теория для схем из функциональных элементов все еще далека от завершенности.

1т.е. схемами, "каждая из которых реализует отличную от константы функцию и при переходе любого одного элемента в неисправное состояние реализует функцию неисправности, отличную от исходной функции (реализуемой схемой при исправных состояниях всех ее элементов) "[19, с. 111]

Ряд важных результатов в оценивании длин тестов для схем из функциональных элементов при различных типах неисправностей получен в работах S. Reddy, В.Н. Носкова, Н.П. Редькина, С.В. Коваценко, В.Г. Хахулина.

Для единичных константных неисправностей на выходах элементов интересный результат был получен S. Reddy для базиса Жегалкина В1 = {&,©,1}.

Теорема А [30] (1972). При любом натуральном п функция Шеннона D(n,Bi) длины единичного проверяющего теста в случае константных неисправностей на выходах элементов удовлетворяет неравенству n,£i) ^п + 3.

Эта оценка остается верной и в случае, когда единичные константные неисправности допускаются не только на выходах, но и на входах элементов (именно, конструкция схемы Reddy и его тест пригодны и для этого более общего типа неисправностей [19, с. 116]).

В третьей главе настоящей работы оценка Reddy уточнена в случае единичных однотипных константных неисправностей на выходах элементов.

Для произвольного полного конечного базиса В в случае константных неисправностей на выходах элементов Н.П. Редькин [13] (1986), [16] (1989) получил оценку

D{n: В) ^ 2(2^/2] + Я*™ + п) функции Шеннона длины полного проверяющего теста.

В случае же константных неисправностей на входах элементов схем в стандартном базисе В0 = {&, V, "} функция Шеннона длины полного проверяющего теста была асимптотически оценена также Н.П. Редькиным [21] (1997):

П(п,В0) < —= .

V log2 п

Правая часть последней оценки неслучайно намного больше правой части предыдущей оценки. Как показал Н.П. Редькин [17] (1987), для конкретных последовательностей булевых функций при переходе от константных неисправностей на выходах элементов к константным неисправностям на входах элементов может оказаться необходимым существенное увеличение длины проверяющих тестов. Именно, для любого полного конечного базиса существует такая последовательность булевых функций fi(xi), /2(гсь ж2),., /п(жь . ., жп),., что

Янх(/п, В) > nD вых где Z)bx(/> В) и .Овыx(f,B) обозначают минимально возможную длину полного проверяющего теста при реализации функции / схемами в базисе В в случае константных неисправностей соответственно на входах и на выходах элементов.

Из оценок длин тестов для конкретных функций отметим результат В.Г. Хахулина [24] (1995). Пусть В — произвольный базис, в котором можно реализовать все функции счетчика четности = хг ф Ф • • • е хп при п > 1. Тогда для минимально возможных длин полных проверяющих тестов в случае константных неисправностей на входах элементов имеют место неравенства п + 1^£>вх(/®,Б) sen+ 2, п = 2,3,. .

В случае однотипных константных неисправностей верхние оценки функций Шеннона найдены Н.П. Редькиным. Они существенно меньше соответствующих оценок для случая константных неисправностей.

Теорема В [14] (1988). При любом натуральном п функция Шеннона D(n, Bq) длины полного проверяющего теста в случае однотипных константных неисправностей на выходах элементов удовлетворяет неравенству

D(n: В0) ^ п.

В первой главе настоящей работы эта оценка Н.П. Редькина уточнена, и найдено точное значение D{n, В0) = 2, п = 2, 3,.

В случае же однотипных константных неисправностей на входах элементов схем в базисе Bq функция Шеннона длины полного проверяющего теста удовлетворяет следующей асимптотической оценке [15] (1988):

Для длин единичных диагностических тестов также имеются принадлежащие Н.П.Редькину [18] (1989), [20] (1992) оценки функций Шеннона

Bx(n,50)<2M+2 + 2W2[+l; £>вых(п, Во) < 2п + 1, где DBX(n,Bo) и DBblx(n,Bo) обозначают функции Шеннона длины единичного диагностического теста для схем в стандартном базисе Bq в случае однотипных константных неисправностей соответственно на входах и на выходах элементов.

Для инверсных неисправностей на выходах элементов оценки функций Шеннона длин различных тестов получены Н.П. Редькиным и

С.В. Коваценко. Для краткости приведем эти оценки в бесформульном виде.

С.В. Коваценко [3] (2000) доказал, что в случае базиса Жегалкина Bi и инверсных неисправностей на выходах элементов любую булеву функцию, существенно зависящую от п переменных, п ^ 1, можно реализовать а) схемой, допускающей единичный проверяющий тест длины 1; б) схемой, допускающей единичный диагностический тест длины, не превосходящей п + 1; в) схемой, допускающей полный диагностический тест длины, не превосходящей 2п~2.

В случае стандартного базиса Bq и инверсных неисправностей на выходах элементов Н.П. Редькин [22] (1999) доказал, что любую булеву функцию можно реализовать неизбыточной схемой, допускающей единичный проверяющий тест длины 2.

Этот результат, а также результат а) С.В. Коваценко, оказались уточнениями следующего результата Н.П. Редькина [23] (2003): Для любого базиса В при любом натуральном п функция Шеннона D(n, В) длины единичного проверяющего теста в случае инверсных неисправностей на выходах элементов удовлетворяет неравенству

D(n,B) ^ 3.

В серии работ В.Н.Носкова [5 - 10] предложены несколько иные методы логического контроля схем из функциональных элементов (и более общих логических устройств). В частности, в работе [10] для булевых функций f(xi, #2, • • •, хп) от п переменных предложен метод синтеза легкотестируемых схем определенного класса в произвольном полном базисе. Каждая из этих схем имеет блочную структуру (число и вид блоков определяются параметрами данного класса схем), а также п + 3 входа х\. £2,.,жп+з и два выхода. На одном из этих выходов при условии xn+i = хп+2 = xn+z = 0 реализуется функция /, а другой выход предназначен для наблюдения за поведением схемы при ее тестировании. В качестве допустимых неисправностей предполагается весьма широкий класс неисправностей, который, в частности, включает в себя константные неисправности на входах и выходах элементов. Число этих неисправностей ограничено в том смысле, что эти неисправности не нарушают блочную структуру схемы и при этом не более т блоков становятся неисправными. Для таких схем и неисправностей В.Н. Носков получает оценку функции Шеннона длины полного проверяющего теста, которая зависит от п, т и других параметров схемы. Здесь эта оценка не приводится ввиду громоздкости необходимых предварительных определений. Трудно также вывести какие-то следствия из этой оценки, например, для константных неисправностей (сам В.Н. Носков такого рода следствия не приводит).

Структура диссертации. Диссертация состоит из введения, трех глав и списка литературы из 35 наименований. Общий объем диссертации — 74 страницы, в работе содержится 8 рисунков. В каждой главе принята сквозная нумерация теорем, лемм и рисунков.

1. Горяшко А.П. Синтез диагностируемых схем вычислительных устройств. — М.: Наука, 1987.

2. Карибский В.В., Пархоменко П.П., Согомонян Е.С., Халчев В.Ф. Основы технической диагностики. — М.: Энергия, 1976.

3. Коваценко С.В. Синтез легкотестируемых схем в базисе Жегал-кина для инверсных неисправностей // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. 2000.- №2. - С.45-47.

4. Лупанов О.Б. Асимптотические оценки сложности управляющих систем. — М.: Издательство Московского университета, 1984.

5. Носков В.Н. Диагностические тесты для входов логических устройств // Дискретный анализ. — Новосибирск: ИМ СО АН СССР, — 1974. Т.26. - С.72-83.

6. Носков В.Н. О сложности тестов, контролирующих работу входов логических схем // Дискретный анализ.— Новосибирск: ИМ СО АН СССР, 1975. - Т.26. - С.23-51.

7. Носков В.Н. О сложности тестов, контролирующих работу входов логических схем // Математические заметки. — 1975. — Т. 18, №1. С.137-150.

8. Носков В.Н. О длинах единичных диагностических тестов, контролирующих работу входов логических схем // Методы дискретного анализа в синтезе управляющих систем. — Сборник трудов Института математики СО АН СССР. — 1978. — Вып. 32. С. 40-51.

9. Носков В.Н. Метод синтеза контролепригодных схем из функциональных элементов // Методы дискретного анализа в изучении булевых функций и графов. — Сборник трудов Института математики СО АН СССР. 1989. - Вып. 48. - С. 52-69.

10. Носков В.Н. Метод синтеза удобных для контроля комбинационных схем // Дискретная математика. — 1993. — Т.5, вып. 4. — С. 3-23.

11. Пархоменко П.П. Диагноз технического состояния дискретных устройств методом выделения подозреваемых неисправностей. Комбинационные устройства. Устойчивые неисправности // Автоматика и телемеханика. — 1971. — №6. — С.26-137.

12. Пархоменко П.П., Согомонян Е.С. Основы технической диагностики. — М.: Энергоиздат, 1981.

13. Редькин Н.П. О полных проверяющих тестах для схем из функциональных элементов // Вестник Московского университета. Серия 1. Математика. Механика. — 1986. — N 1. — С. 72-74.

14. Редькин Н.П. О схемах, допускающих короткие тесты // Вестник Московского университета. Серия 1. Математика. Механика. — 1988. N 2. - С. 17-21.

15. Редькин Н.П. О проверяющих тестах для схем при однотипных константных неисправностях на входах элементов // Известия вузов. Математика. — 1988. — №7. — С. 57-64.

16. Редькин Н.П. О полных проверяющих тестах для схем из функциональных элементов // Математические вопросы кибернетики. Вып.2. — 1989. - С. 198-222.

17. Редькин Н.П. О зависимости длины проверяющих тестов от вида неисправностей // Методы дискретного анализа в теории кодов и схем. — Сборник трудов Института математики СО АН СССР.- 1987. Вып. 46. - С. 65-71

18. Редькин Н.П.О схемах, допускающих короткие единичные диагностические тесты // Дискретная математика. — 1989. — Т.1, вып. 3. С. 71-76.

19. Редькин Н.П. Надежность и диагностика схем. — М.: Издательство Московского университета, 1992.

20. Редькин Н.П. О единичных диагностических тестах для однотипных константных неисправностей на выходах функциональных элементов // Вестник Московского университета. Серия 1. Математика. Механика. — 1992. — N 5. — С. 43-46.

21. Редькин Н.П. О проверяющих тестах для схем при константных неисправностях на входах элементов // Вестник Московского университета. Серия 1. Математика. Механика. — 1997. — №1.- С. 12-18.

22. Редькин Н.П. Единичные проверяющие тесты для схем при инверсных неисправностях элементов // Математические вопросы кибернетики. 2003.— Вып. 12. — С. 217-230.

23. Хахулин В.Г. О проверяющих тестах для счетчика четности // Дискретная математика. — 1995. — Т.7, вып. 4. — С. 51-59.

24. Чегис И.А., Яблонский С.В. Логические способы контроля работы электрических схем // Труды МИАН. — 1958. — Т.51,— С.270-360.

25. Яблонский С.В., Чегис И.А. О тестах для электрических схем // УМН 1955. - Т. 10, вып. 4(66). - С.182-184.

26. Яблонский С.В. Надежность и контроль управляющих систем // Материалы Всесоюзного семинара по дискретной математике и ее приложениям. М.: МГУ. — 1986. — С.7-12.

27. Яблонский С.В. Некоторые вопросы надежности и контроля управляющих систем // Математические вопросы кибернетики. — 1988. № 1. - С.5-25.

28. Яблонский С.В. Введение в дискретную математику. — М.: Высшая школа. — 2002.

29. Reddy S.M. Easily testable realization for logic functions // IEEE Trans. Comput. 1972. - v.21. - N1. - P. 124-141.

30. Бородина Ю.В. Синтез легкотестируемых схем в базисе {&, V, "} при однотипных константных неисправностях на выходах элементов // Дискретная математика. — 2005. — Т.17, вып. 1. — С. 129-140.

31. Бородина Ю.В. Синтез легкотестируемых схем в базисе {&, V, "} для систем функций из некоторых классов // Вестник Московского университета. Серия 1. Математика. Механика. — 2007. — Ш. — С. 68-72.

32. Бородина Ю.В. О синтезе легкотестируемых схем в случае однотипных константных неисправностей на выходах элементов // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. — 2008.— №1. — С.40-44.