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

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

на правах рукописи

005536865

Коляда Сергей Сергеевич

ВЕРХНИЕ ОЦЕНКИ ДЛИНЫ ПРОВЕРЯЮЩИХ ТЕСТОВ ДЛЯ СХЕМ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ

01.01.09 — дискретная математика и математическая кибернетика

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

31 ОКТ 2013

МОСКВА 2013

005536865

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

Научный руководитель: Официальные оппоненты:

доктор физико-математических наук, профессор Редькин Николай Петрович Шевченко Валерий Николаевич,

доктор физико-математических наук, профессор (ФГБОУ ВПО "Нижегородский государственный университет им. Н.И. Лобачевского", заведующий кафедрой математической логики и высшей алгебры) Романов Дмитрий Сергеевич, кандидат физико-математических наук, доцент (ФГБОУ ВПО "Московский государственный университет им. М.В.Ломоносова", Факультет вычислительной математики и кибернетики, кафедра математической кибернетики)

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

ФГАОУ ВПО "Казанский (Приволжский) федеральный университет" Защита диссертации состоится 22 ноября 2013 г. в 1645 на заседании диссертационного совета Д.501.001.84 при ФГБОУ ВПО "Московский государственный университет им. М. В. Ломоносова" по адресу: 119991, ГСП-1, Москва, Ленинские горы, МГУ, Механико-математический факультет, аудитория 14-08.

С диссертацией можно ознакомиться в Фундаментальной библиотеке ФГБОУ ВПО "Московский государственный университет им. М. В. Ломоносова" (Москва, Ломоносовский проспект, дом 27, сектор А, 8 этаж). Автореферат разослан 22 октября 2013 г.

Ученый секретарь ^

диссертационного совета

Д.501.001.84 при ФГБОУ ВПО МГУ д 0. Иванов

доктор физико-математических наук, профессор

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

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

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

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

Пусть /(¿с) произвольная булева функция, зависящая от переменных х\, Ж2, • • •, хп, а 5 — схема из функциональных элементов в некотором базисе В, реализующая функцию /(¿). На схему воздействует некоторый источник неисправностей, под влиянием которого схема вместо функции /(£) может выдавать какие-то функции неисправностей д1(х),д2(х),..., дк{х). Всякое множество Т = {<71, а2, ■ ■ ■, а/} входных наборов схемы 5 называется проверяющим тестом для этой схемы, если для любой функции неисправности д^х), не равной тождественно /(¿с), в Т найдется хотя бы один набор сг, такой, что /(¿г) ф £¿(<5"). Если для любой пары функций неисправностей д^х) и д]{х) в проверяющем тесте Т найдется хотя бы один набор а такой, что д^а) ф <?;(сг), то такой тест Т называется диагностическим тестом схемы 5; он позволяет не только обнаружить

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

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

неисправность схемы S, но и в случае ее неисправности определить, какая именно функция неисправности реализуется на ее выходе. Число I — количество наборов в Т называется длиной теста.

Различают полные тесты, когда в схеме допускается произвольное количество неисправных элементов, и единичные тесты, когда в неисправное состояние может перейти ровно один элемент схемы. В случае единичных тестов принято рассматривать лишь неизбыточные схемы, т.е. такие схемы, в которых при переходе в любое неисправное состояние любого элемента схема реализует нетривиальную, то есть отличную от f(x) функцию неисправности д(х).

В качестве тривиального теста всегда можно взять тест, содержащий все 2П наборов значений переменных булевой функции от п переменных-Соответственно возникает вопрос, возможно ли в том или ином случае найти более короткие тесты. Так возникает задача построения минимальных тестов, т.е. тестов, содержащих минимальное число наборов.

Пусть D(T).....длина теста Т. Введем обозначения: D(S) — minD(T),

где минимум берется по всем проверяющим (или диагностическим) тестам Т для схемы из функциональных элементов S; £>в(/) — minD(S), где минимум берется по всем схемам S в данном базисе В, реализующим функцию /; £>д(п) = тах£)д(/), где максимум берется по всем функциям от п переменных. Функция Dß{n) называется функцией Шеннона длины проверяющего (диагностического) теста для базиса В. Она показывает, в частности, что для любой булевой функции от п переменных существует схема и тест, длина которого не превосходит 1?в(п). Аналогично определяется функция Шеннона длины проверяющего (диагностического) теста для контактных схем.

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

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

тов. Для схем из функциональных элементов основными являются следующие типы неисправностей: константные, однотипные константные и инверсные неисправности. Эти неисправности делятся на неисправности на входах и неисправности на выходах элементов схемы. Константная неисправность на выходе функционального элемента означает, что элемент при переходе в неисправное состояние вне зависимости от того, что подаётся на его входы, выдаёт некоторую булеву константу <5, где <5 е {0,1}; константная неисправность на г-ом входе функционального элемента означает, что элемент при переходе в неисправное состояние вне зависимости от того, что подаётся на его входы, функционирует так, как будто на г-й вход подана некоторая булева константа <5, где 5 6 {0,1}. В общем случае значение 5 может быть своим у каждого неисправного элемента и у каждого входа элемента. В случае однотипных константных неисправностей значение 6 предполагается одним и тем же у всех неисправных элементов. Инверсная неисправность на выходе означает, что значение на выходе неисправного элемента противоположно значению на выходе исправного элемента; инверсная неисправность на входе элемента означает, что подаваемое на этот неисправный вход значение противоположно значению, подаваемому на исправный вход. Неисправность на входе схемы означает, что схема функционирует так, как будто на один из ее входов вместо переменной подается некоторая булева константа д. Очевидно, что при такой неисправности, функция, реализуемая на выходе неисправной схемы, не зависит от самой схемы, а зависит лишь от функции, реализуемой исправной схемой. Поэтому тесты для данного типа неисправностей называют ещё тестами для функций. Все недостающие определения можно найти в работе Н.П.Редькина3'.

Первые существенные результаты из области математической теории диагностики схем принадлежат С.В.Яблонскому и ряду его учеников и последователей. Уже в работе С.В.Яблонского2' установлена возможность построения легкотестируемых контактных схем как для произвольных булевых функций, так и для некоторых конкретных булевых функций и опе-

3'Редькин Н.П. Надёжность II диагностика схем. М.: Изд-во МГУ. 1992.

раторов. В работах В.В.Глаголева4\ С.М.Вартаняна5', Д.С.Романова6} получены константные и логарифмические верхние оценки длины проверяющих и единичных диагностических тестов для контактных схем с блочной структурой. Х.А.Мадатян7' установил, что для любой контактной схемы, реализующей линейную булеву функцию от п переменных, минимальный полный диагностический тест совпадает с тривиальным и содержит все 2П входных наборов значений переменных. Для длины полного проверяющего теста для контактных схем Н.П.Редькин8' получил верхнюю оценку ||2П, т.е. установил, что тривиальный тест не является минимальным полным проверяющим тестом. Ещё более сильную верхнюю оценку длины полного проверяющего теста Н.П.Редькин9' установил для контактных схем, в которых допускаются неисправности одного конкретного типа — либо только обрывы контактов, либо только замыкания контактов.

Теория диагностики неисправности схем из функциональных элементов начала развиваться немного позже, но тоже содержит ряд сильных результатов, устанавливающих хорошие, а в некоторых случаях и точные, оценки длины проверяющих и диагностических тестов. Приведем некоторые из них.

Для произвольных константных неисправностей на выходах элементов S.M.Reddy10' получил линейную по числу переменных у реализуемой функции верхнюю оценку длины единичного проверяющего теста для схем в базисе Жегалкина. То есть доказал, что любую булеву функцию от п переменных можно реализовать неизбыточной схемой, допускающей единичный проверяющий тест, длина которого не превосходит п + 3.

4)Глаголев В. В. Построение тестов для блочных схем // ДАН СССР. 1962. Т.144. №6. С. 1237-1240.

5'Вартанян С. М. Единичные диагностические тесты для последовательных блочных схем. Дисс. на соиск. уч. ст. к.ф.-м.н. М. 1987. 114 с.

б'Ромапов Д. С. Построение тестов и оценка их параметров для некоторых классов контактных схем. Дисс. на соиск. уч. ст. к.ф.-м.н. M. 2000. 114 с.

7>Мадатян X. А. Полный тест для бесповортных контактных схем// Проблемы кибернетики. Вып.23. М.: Наука. 1970. С. 103 118.

8'Редькин Н.П. О полных проверяющих тестах для контактных схем// Методы дискретного анализа в исследовании экстремальных стуктур. Вып. 39. Новосибирск: Изд-во ИМ СО АН СССР. 1983. С. 80-87.

"'Редькин Н.П. О проверяющих тестах замыкания и размыкания// Методы дискретного анализа в исследовании экстремальных стуктур. Вып. 40. Новосибирск: Изд-во ИМ СО АН СССР. 1983. С. 87 99.

I0)Reddy S.M. Easily testable realization for logic functions// IEEE IVans. Comput. 1972, №1. p. 124-141.

Н.П.Редькини) получил верхнюю оценку длины полного проверяющего теста для схем в произвольном функционально полном конечном базисе В в случае произвольных константных неисправностей на выходах элементов DB{n) < 2(2lf] + 2Ж + п). Н.П.Редькин12'13^14' установил, что в классическом базисе Bq = {хк.у,х V у,х} в случае однотипных константных неисправностей на выходах функциональных элементов любую булеву функцию от п переменных можно реализовать схемой, допускающей единичный диагностический тест, длина которого по порядку не превосходит %/2™. Им же получена линейная верхняя оценка длины единичного диагностического теста для схем в классическом базисе Bq = {xfoy,x V у,х} в случае однотипных константных неисправностей на выходах функциональных элементов, Дв0(п) < 2п + 1. Он же получил линейную верхнюю оценку функции Шеннона длины полного проверяющего теста в классическом базисе, в случае однотипных константных неисправностей на выходах элементов.

Позже Н.П.Редькиным, С.В.Коваценко, Ю.В.Бородиной, П.А.Бородиным и Д.С.Романовым были получены константные верхние, а в некоторых случаях и точные оценки функций Шеннона длин проверяющих тестов при различных типах неисправностей. С.В.Коваценко15^ установил, что в базисе Жегалкина функция Шеннона длины единичного проверяющего теста относительно инверсных неисправностей на выходах функциональных элементов равна 1. Н.П.Редькин16) установил, что в случае произвольного функционально полного конечного базиса и инверсных неисправностей на выходах функциональных элементов любую булеву

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

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

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

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

15'Коваценко C.B. Синтез легкотестируемых схем в базисе Жегалкина для инверсных неисправностей/,/ Вестник Московского Университета сер. 1. Математика. Механика. Вып. 2. 2000. С. 45 47.

16'Редькин Н.П. Единичные проверяющие тесты для схем при инверсных неисправностях элементов. Математические попросы кибернетики (2003). С. 217-230.

функцию можно реализовать неизбыточной схемой, допускающей единичный проверяющий тест длины 3. Ю.В.Бородина17)18' установила, что в классическом базисе функция Шеннона длины полного проверяющего теста относительно однотипных константных неисправностей на выходах функциональных элементов равна 2. Так же Ю.В.Бородиной19'20' установлено, что функция Шеннона длины единичного проверяющего теста относительно константных неисправностей типа 1 на выходах функциональных элементов в базисе Жегалкина равна 1. Аналогичный результат, но уже для неисправностей типа 0 на выходах функциональных элементов был получен совместно Ю.В.Бородиной и П.А.Бородиным21'. Д.С.Романов22'23' установил, что в базисе {хку,х®у, 1 ,x(yVz)Vx(y ~ z)} любую булеву функцию можно реализовать неизбыточной схемой, допускающей при произвольных константных неисправностях на выходах функциональных элементов единичный проверяющий тест длины 4. В работе Д.С.Романова24' заявлено, что аналогичный результат может быть распространен на случай произвольного базиса, однако, доказательство данного факта не представлено. В работе Д.С.Романова22' также заявлено

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

18'Бородина Ю.В. Синтез легкотестируемых схем при константных неисправностях на выходах элементов. Дисс. на соиск. уч. ст. к.ф.-м.н. М. 2008. 74 с.

19'Бородина Ю.В. О схемах, допускающих единичные тесты длины 1 при константных неисправностях на выходах элементов// Вестник Московского Университета сер. 1. Математика. Механика. 2008. №5. С. 49-52.

20'Бородина Ю.В. Синтез легкотестируемых схем при константных неисправностях на выходах элементов. Дисс. на соиск. уч. ст. к.ф.-м.н. М. 2008. 74 с.

21'Бородина Ю.В., Бородин П.А. Синтез легкотестируемых схем в базисе Жегалкина при константных неисправностях типа "О" па выходах элементов// Дискретная математика. 2010. Т.22. №3. С. 127-133.

Романов Д.С. О синтезе схем, допускающих проверяющие тесты константной длины// Материалы XVI Международной конференции "Проблемы теоретической кибернетики". - Нижний Новгород.: Изд-во Нижегородского госунипсрситста. 2011. С. 400 403.

23'Романов Д.С. Метод синтеза легкотестируемых схем в одном базисе, допускающих единичные проверяющие тесты константной длины// Вестник Московского университета сер. 1. Математика, механика. 2012. №2. С. 24 20.

"'Романов Д.С. Об оценках функции Шеннона длины единичного проверяющего теста относительно произвольных константных неисправностей на выходах элементов.// Материалы XI Международного семинара Дискретная математика и ее приложепия, посвященного 80-летию со дня рождения академика О. Б. Лупанова (Москва, МГУ, 18-23 июня 2012 г.), М.: Изд-во мех.-мат. ф-та МГУ, 2012. С. 100-163.

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

В своих работах Д.С.Романов, Е.В.Морозов и И.А.Кузнецов25)26) получают нетривиальные оценки функций Шеннона длины проверяющих-и диагностических тестов для неисправностей типа "слипания" переменных (некоторый аналог неисправностей на входах схем).

Ещё одним направлением теории синтеза легкотеетируемых схем является поиск минимальных тестов для схем, реализующих индивидуальные булевы функции или некоторые классы булевых функций. В работе В.Г.Хахулина27' установлены линейные верхняя и нижняя оценки длины полного проверяющего теста для схем, реализующих функцию 1п = % 1®.. .Фжп, при наличии произвольных константных неисправностей, на выходах элементов. С.Р.Беджанова28'29'30'31' в своих работах устанавливает различные верхние и нижние оценки длин единичных и полных проверяющих и диагностических тестов для схем, реализующих дизъюнкцию п переменных х\ V ... V хп, при различных видах неисправностей функциональных элементов. В.Б.Кудрявцев, Э.Э.Гасанов, О.А.Долотова, Г.Р.Погосян32' исследуют вопросы длины тестов для схем, реализующих

25'Морозов Е.В., Романов Д.С. О проверяющих тестах относительно множественных линейных слипаний переменных.// Материалы XI Международного семинара Дискретная математика и ее приложения, посвященного 80-летию со дня рождения академика О. Б. Лупанова (Москва, МГУ, 18-23 июня 2012 г.), М.: Изд-во ыех.-мвт. ф-та МГУ. 2012. С. 144-147.

2|!'Кузнецов H.A., Романов Д.С. О полных проверяющих тестах относительно локальных слипаний переменных в булевых функциях.// Ученые записки Казанского университета. Серия Физико-математические науки. 2009. Т.151. книга 2. С. 90-97.

27)Хахулин В.Г. Опроверяющих тестах для счетчика четности.//' Дискретная математика. 1995. T.7. №4. С. 51- 59.

28>Беджанова С.Р. Тесты схем для некоторых классов булевых функций. Дисс. на соиск. уч. ст. к.ф.-м.н. М. 2011. 96 с.

29'Бедаканова С.Р. О минимальных тестах для схем, реализующих дизъюнкцию.// Дискретн. анализ и исслед. опер. 2008. Т.15. №2. С. 3—11.

30'Беджанова С.Р. Схемы для дизъюнкции, допускающие короткие единичные диагностические тесты.// Дискретная математика. 2010. Т.22. №4. С. 43—54.

31'Беджанова С.Р. Диагностика инверсных неисправностей на входах элементов схемы для дизъюнкции.// Вестник Московского университета сер. 15. Вычислительная математика и кибернетика. 2011. №3. С. 44-46.

32'Кудрявцев В.Б., Гасанов Э.Э., Долотова O.A., Погосян Г.Р. Теория тестирования логических устройств.// М.: Физматлит. 2006.

булевы функции из классов Поста и функции ¿-значной логики. Цель работы

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

Основные методы исследования.

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

Научная новизна.

Результаты диссертации являются новыми и состоят в следующем:

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

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

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

Апробация результатов.

Результаты диссертации докладывались на семинарах „Надежность управляющих систем" и „Диагностика управляющих систем" под руководством профессора Н.П. Редькина (МГУ, 2009-2013гг, неоднократно), на VIII Международной конференции „Дискретные модели в теории управляющих систем" (Москва, 6-9 апреля 2009г.), на XVI Международной конференции „Проблемы теоретической кибернетики" (Нижний Новгород, 20-25

июня 2011г.), на Международной научной конференции студентов, аспирантов и молодых ученых „Ломоносов-2011" (МГУ, 11-15 апреля 2011г.) и „Ломоносов-2012" (МГУ, 9-13 апреля 2012г.), на научных конференциях „Ломоносовские чтения" (МГУ, Москва, 2009г., 16-24 апреля), „Ломоносовские чтения" (МГУ, Москва, 2012г., 16-24 апреля), „Ломоносовские чтения" (МГУ, Москва, 2013г., 15-26 апреля).

Публикации.

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

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

Диссертация состоит из введения, трех глав, разбитых на параграфы, и списка литературы из 37 наименований, включая 6 работ автора. Общий объем диссертации 77 страниц, в работе содержится 24 рисунка. В каждой главе принята сквозная нумерация теорем, лемм и рисунков.

КРАТКОЕ СОДЕРЖАНИЕ РАБОТЫ

Во введении к диссертации обсуждается история вопроса, приводятся основные определения.

В главе 1 рассматривается задача построения легкотестируемых схем из функциональных элементов в базисах из элементов, имеющих не более двух входов. Допускаются единичные произвольные константные неисправности на выходах элементов, когда в неисправное состояние может перейти ровно один элемент схемы, который вне зависимости от того, что подаётся на его входы, выдаёт некоторую булеву константу 5, где 6 £ {0,1}.

В §1 главы 1 даются основные определения и формулируется следующая теорема:

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

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

Лемма 1. Пусть даны два базиса В[ и В'2) относительно которых известно, что каждая функция из базиса В[ реализуется неизбыточной схемой из функциональных элементов в базисе В'2 такой, что все возможные функции неисправности этой схемы это константы 0 и 1. И для булевой функции /(х\,... ,хп) существует неизбыточная схема Б в базисе В[, допускающая единичный проверяющий тест длины I. Тогда существует неизбыточная схема Б' в базисе В'2, реализующая /{х\,..., хп), допускающая единичный проверяющий тест длины I.

В §2 главы 1 теорема 1 доказывается для базисов {х&,у, ж}, {х&су, хф у, 1},{а;&у, хфуф 1, 0}, {я&у, х © у, х ® у ®1},{х&у}. Для данных базисов получена верхняя оценка длины единичного проверяющего теста п + 1.

В §3 главы 1 теорема 1 доказывается для базисов {х&у, х}, {ж&г/, 1}. Для этих базисов получена верхняя оценка длины единичного проверяющего теста п + 2.

В §4 главы 1 теорема 1 доказывается для базисов {хку, х ® у ф 1}, {х8гу, хУу}. Здесь получена верхняя оценка длины единичного проверяющего теста п + 3.

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

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

В §1 главы 2 даются дополнительные определения и формулируется следующая теорема:

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

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

Данная теорема является основным результатом диссертации и по сути является обобщением результата, полученного З.М.Ыесйу10' для базиса Жегалкина, на случай произвольного функционально полного конечного базиса.

Булеву функцию щ(х, у, г) = ху ф хг ф уг © 71а; ф 72у Ф 7з^ Ф 74! где 7ь ... ,74 € {0,1}, а 7 = (71,72,73174)» будем называть особенной.

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

Для доказательства теоремы 2 используется следующая лемма, доказанная в работе Н.П.Редькина11'.

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

Далее в главе 2 доказаны несколько вспомогательных лемм, используемых для доказательства теоремы 2.

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

Рассмотрен следующий базис В\ = {ж&у, ж*} (В2 = {XVу, ж*}). Через х* здесь и далее в работе будем обозначать обычное отрицание такое, что элемент, реализующий его, имеет два вида поломок: единичная константная неисправность инвертора и неисправность всех инверторов схемы (у всех одинаковая - либо какая-то константа, либо тождественная функция). В базисе В1 (¿2) конъюнктор (дизъюнктор) при переходе в неисправное состояние выдаёт некоторую булеву константу 6, где 5 & {0,1}, а инвертор при переходе в неисправное состояние выдаёт либо тождественную функцию, либо некоторую булеву константу. Для схем над таким базисом назовём единичной неисправностью либо поломку ровно одного конъюнктора (дизъюнктора), либо константную неисправность ровно одного инвертора

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

Лемма 3. Для любой булевой функции /(хъ... ,х„), где п > 3, существует неизбыточная схема в базисе В\, реализующая данную функцию и допускающая единичный проверяющий тест, длина которого не превосходит п + 1.

Базисы В\ и В2 двойственны, а значит справедлива следующая лемма. Лемма 4. Для любой булевой функции где п > 3, суще-

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

В §3 главы 2 получена верхняя оценка длины единичного проверяющего теста для схем в базисе {5, х, щ} с особенностью поломки инвертора.

Рассмотрен следующий базис = х*, (р.у}, то есть базис состоящий из какой-то константы(0 или 1), отрицания, и особенной функции. Для схем над таким базисом назовём единичной неисправностью либо поломку ровно одного элемента реализующего константу, либо константную неисправность ровно одного инвертора схемы, либо неисправность, при которой все инверторы схемы сломались и реализуют тождественные функции своих входов, либо неисправность, при которой все инверторы схемы сломались и выдают одну и ту же константу, либо константную неисправность ровно одного элемента Е^.

Лемма 5. Для любой булевой функции /(жъ ..., хп), где п> 3, существует неизбыточная схема в базисе Вз, реализующая данную функцию и допускающая единичный проверяющий тест, длина которого не превосходит п + 3.

В §4 главы 2 получена верхняя оценка длины единичного проверяющего теста для схем в базисе {х © у, х ~ у,

Лемма 6. Для'любой булевой функции /(жх,.. .,х„), где п > 3, существует неизбыточная схема в базисе В4, реализующая данную функцию и допускающая единичный проверяющий тест, длина которого не пре-

восходит п + 3.

В §5 главы 2 приводится некоторая классификация произвольных функционально полных конечных базисов, которая позволяет доказать теорему 2 с помощью теоремы 1 и лемм 1-6.

В главе 3 рассматривается задача построения легкотестируемых схем из функциональных элементов в базисе Жегалкина {хку,х@у, 0,1}. Допускаются произвольные константные неисправности на выходах элементов. Сделано предположение, что в неисправное состояние могут перейти не более чем к элементов.

Пусть 5 — схема, реализующая в исправном состоянии булеву функцию /(£), х = .. .,хп). Схему 5 будем считать к-неизбыточной, если при переходе в неисправное состояние любых не более чем к элементов эта схема реализует нетривиальную, то есть отличную от /(£) функцию неисправности д(х).

Доказана следующая теорема.

Теорема 4. Для для любой функции /(жь... ,хп) существует к-неизбыточная схема в базисе Жегалкина, реализующая данную функцию и допускающая полный проверяющий тест,, длина которого не превосходит £Й2*]+1с; + з.

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

Лемма 7. Пусть функция ¡(х1,...,хп) ф 0 представима в виде /(геь ...,хп) = Кх ® ... ф КА, где й < 2Г+1, К{ = хфхф... &х^ или К1 = 1. Тогда существует набор а = (а 1,..., сг„) такой, что \ д |> п — г и т = 1, где\д 1= £?=!*<•

Теорема 4 является обобщением результата, полученного З.М.Кес1с1уш) для базиса Жегалкина, на случай произвольного фиксированного числа неисправностей.

Автор выражает глубокую благодарность своему научному руководителю доктору физико-математических наук, профессору Николаю Петровичу Редькину за постановку задачи и постоянное внимание к работе. Автор также приносит глубокую благодарность всем сотрудникам кафедры дискретной математики за поддержку и внимание.

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

[1] Коляда С.С. О единичных проверяющих тестах для константных неисправностей на выходах функциональных элементов.// Вестник Московского университета сер. 1. Математика, механика. 2011. №6. С. 47-49.

[2] Коляда С.С. Единичные проверяющие тесты для схем из функциональных элементов в базисах из элементов, имеющих не более двух входов// Дискрета, анализ и исслед. опер. 2013. Т.20. № 2. С. 58-74.

[3] Коляда С.С. Единичные проверяющие тесты для схем из функциональных элементов// Вестник Московского университета сер. 1. Математика, механика. 2013. №4. С. 32-34.

[4] Коляда С.С. О единичных проверяющих тестах для схем из функциональных элементов. - М., 2013. - 24 с. - Деп. в ВИНИТИ 27.03.2013, № 87-В2013

[5] Коляда С.С. О проверяющих тестах для схем из функциональных элементов в базисе Жегалкина. Сборник материалов восьмой международной конференции "Дискретные модели в теории управляющих систем", изд-во факультета ВМК МГУ Москва. 2009. С. 142-145.

[6] Коляда С.С. О единичных проверяющих тестах для схем из функциональных элементов// Материалы XVI Международной конференции "Проблемы теоретической кибернетики". - Нижний Новгород.: Изд-во Нижегородского госуниверситета. 2011. С. 209-211.

Отпечатано в отделе оперативной печати Геологического ф-та МГУ Тираж экз. Заказ Ка

]\^сковски^государственный университет имени М. В. Ломоносова

Механико-математический факультет

На правах рукописи УДК 519.71

04201451677

(4ШХК

Коляда Сергей Сергеевич

ВЕРХНИЕ ОЦЕНКИ ДЛИНЫ ПРОВЕРЯЮЩИХ ТЕСТОВ ДЛЯ СХЕМ ИЗ ФУНКЦИОНАЛЬНЫХ ЭЛЕМЕНТОВ

01.01.09 - дискретная математика и математическая кибернетика

ДИССЕРТАЦИЯ на соискание ученой степени кандидата физико-математических наук

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

Москва - 2013

Содержание

Введение 3

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

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

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

тесты длины п + 1........................ 18

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

тесты длины п + 2........................ 23

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

тесты длины п + 3........................ 27

§5. Константные неисправности на входах функциональных элементов ............................... 41

Глава 2. Схемы в произвольных функционально полных конечных базисах 46

§1. Вспомогательные определения и формулировка результата . . 46 §2. Единичные проверяющие тесты для схем в базисах {х&у, х},

{х V у, ж} с особенностью поломки инвертора........ 48

§3. Единичные проверяющие тесты для схем в базисе {5, х, с

особенностью поломки инвертора................ 55

§4. Единичные проверяющие тесты для схем в базисе {х фу, х ~

У>фу} ............................... 56

§5. Доказательство основной теоремы................ 61

Глава 3. Фиксированное число неисправностей в базисе Же-галкина 68

Введение

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

К числу основных модельных объектов математической теории синтеза, сложности, надежности и диагностики управляющих систем относятся схемы из ненадежных элементов, реализующие булевы функции. Для обеспечения надежного функционирования схем необходимо решать задачу контроля исправности ее элементов. Для решения этой задачи С.В.Яблонским и И.А.Чегис [1, 2] были предложены логические способы контроля исправности и диагностики неисправностей управляющих систем, суть которых состоит в том, что на входы схем подаются некоторые специальным образом подобранные "проверяющие" наборы значений переменных и на основе наблюдаемых выходных значений схемы делается заключение об ее исправности и характере неисправностей (при их наличии).

Пусть /(х) — произвольная булева функция, зависящая от переменных х\, £2, • • ■ 5 хп, а 5 — схема из функциональных элементов в некотором базисе В, реализующая функцию /(ж). На схему воздействует некоторый источник неисправностей, под влиянием которого схема вместо функции /(¿) может выдавать какие-то функции неисправностей ^(х), ^(а^),... , дк{х) [3]. Всякое множество Т = {<71, <72,..., 07} входных наборов схемы 5 называется проверяющим тестом для этой схемы, если для любой функции неисправности дг{х), не равной тождественно /(х). в Т найдется хотя бы один набор <7, такой, что /(¿г) ^ дг{&)- Если для любой пары функций неисправностей дг(х) и д3{х) в проверяющем тесте Т найдется хотя бы один набор <7 такой, что дг(а) ф 9з{<*), то такой тест Т называется диагностическим тестом схемы 5; он позволяет не только обнаружить

неисправность схемы S, но и в случае ее неисправности определить, какая именно функция неисправности реализуется на ее выходе. Число I — количество наборов в Т называется длиной теста.

Различают полные тесты, когда в схеме допускается произвольное количество неисправных элементов, и единичные тесты, когда в неисправное состояние может перейти ровно один элемент схемы. В случае единичных тестов принято рассматривать лишь неизбыточные схемы, т.е. такие схемы, в которых при переходе в любое неисправное состояние любого элемента схема реализует нетривиальную [3], то есть отличную от f(x) функцию неисправности д(х).

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

Пусть D(T) — длина теста Т. Введем обозначения: D(S) = minD(T), где минимум берется по всем проверяющим (или диагностическим) тестам Т для схемы из функциональных элементов S; Ds{f) — minD(S'), где минимум берется по всем схемам S в данном базисе В, реализующим функцию /; Ов{п) = max/}#(/), где максимум берется по всем функциям от п переменных. Функция Дв(п) называется функцией Шеннона длины проверяющего (диагностического) теста для базиса В. Она показывает, в частности, что для любой булевой функции от п переменных существует схема и тест, длина которого не превосходит Дв(тг). Аналогично определяется функция Шеннона длины проверяющего (диагностического) теста для контактных схем.

К основным задачам теории диагностики схем относится поиск верхних и нижних оценок функций Шеннона для единичных или полных проверяю-

щих (или диагностических) тестов для схем из функциональных элементов и контактных схем.

Чтобы конкретизировать задачу, обычно рассматривают дополнительные ограничения на тип неисправности [3]. Для контактных схем в качестве неисправностей чаще всего рассматриваются обрывы и замыкания контактов. Для схем из функциональных элементов основными являются следующие типы неисправностей: константные, однотипные константные и инверсные неисправности. Эти неисправности делятся на неисправности на входах и неисправности на выходах элементов схемы. Константная неисправность на выходе функционального элемента означает, что элемент при переходе в неисправное состояние вне зависимости от того, что подаётся на его входы, выдаёт некоторую булеву константу ¿, где 5 Е {0,1}; константная неисправность на г-ом входе функционального элемента означает, что элемент при переходе в неисправное состояние вне зависимости от того, что подаётся на его входы, функционирует так, как будто на г-й вход подана некоторая булева константа (5, где 6 £ {0,1}. В общем случае значение 6 может быть своим у каждого неисправного элемента и у каждого входа элемента. В случае однотипных константных неисправностей значение 5 предполагается одним и тем же у всех неисправных элементов. Инверсная неисправность на выходе означает, что значение на выходе неисправного элемента противоположно значению на выходе исправного элемента; инверсная неисправность на входе элемента означает, что подаваемое на этот неисправный вход значение противоположно значению, подаваемому на исправный вход. Неисправность на входе схемы означает, что схема функционирует так, как будто на один из ее входов вместо переменной подается некоторая булева константа 5. Очевидно, что при такой неисправности, функция, реализуемая на выходе неисправной схемы, не зависит от самой схемы, а зависит лишь от функции, реализуемой исправ-

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

Первые существенные результаты из области математической теории диагностики схем принадлежат С.В.Яблонскому и ряду его учеников и последователей. Уже в работе [2] установлена возможность построения легкотестируемых контактных схем как для произвольных булевых функций, так и для некоторых конкретных булевых функций и операторов. В работах В.В.Глаголева [4], С.М.Вартаняна [5], Д.С.Романова [6] получены константные и логарифмические верхние оценки длины проверяющих и единичных диагностических тестов для контактных схем с блочной структурой. Х.А.Мадатян в [7] установил, что для любой контактной схемы, реализующей линейную булеву функцию от п переменных, минимальный полный диагностический тест совпадает с тривиальным и содержит все 2П входных наборов значений переменных. Для длины полного проверяющего теста для контактных схем Н.П.Редькин в [8] получил верхнюю оценку ||2П, т.е. установил, что тривиальный тест не является минимальным полным проверяющим тестом. Ещё более сильную верхнюю оценку длины полного проверяющего теста Н.П.Редькин установил в [9] для контактных схем, в которых допускаются неисправности одного конкретного типа — либо только обрывы контактов, либо только замыкания контактов.

Теория диагностики неисправности схем из функциональных элементов начала развиваться немного позже, но тоже содержит ряд сильных результатов, устанавливающих хорошие, а в некоторых случаях и точные, оценки длины проверяющих и диагностических тестов. Приведем некоторые из них.

Для произвольных константных неисправностей на выходах элементов 8.М.11ес1с1у в [10] получил линейную по числу переменных у реализуемой функции верхнюю оценку длины единичного проверяющего теста для схем

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

В работе [11] Н.П.Редькин получил верхнюю оценку длины полного проверяющего теста для схем в произвольном функционально полном конечном базисе В в случае произвольных константных неисправностей на выходах элементов — -Ов(п) ^ 2(2^1 + + п). В работе [12] им же было показано, что в классическом базисе Во — {хЬу, х V у, х} в случае однотипных константных неисправностей на выходах функциональных элементов любую булеву функцию от п переменных можно реализовать схемой, допускающей единичный диагностический тест, длина которого по порядку не превосходит у/2^. Им же в [13] получена линейная верхняя оценка длины единичного диагностического теста для схем в классическом базисе Во = {х&у,х V у,х} в случае однотипных константных неисправностей на выходах функциональных элементов, /)д0(гг) ^ 2п + 1. В [14] Н.П.Редькин получил линейную верхнюю оценку функции Шеннона длины полного проверяющего теста в классическом базисе, в случае однотипных константных неисправностей на выходах элементов.

Позже Н.П.Редькиным, С.В.Коваценко, Ю.В.Бородиной, П.А.Бородиным и Д.С.Романовым были получены константные верхние, а в некоторых случаях и точные оценки функций Шеннона длин проверяющих тестов при различных типах неисправностей. С.В.Коваценко в [15] установил, что в базисе Жегалкина функция Шеннона длины единичного проверяющего теста относительно инверсных неисправностей на выходах функциональных элементов равна 1. Н.П.Редькин в [16] установил, что в случае произвольного функционально полного конечного базиса и инверсных неисправностей на выходах функциональных элементов любую булеву функцию можно реализовать неизбыточной схемой, допускающей единичный проверяю-

щий тест длины 3. Ю.В.Бородина в [17, 19] установила, что в классическом базисе функция Шеннона длины полного проверяющего теста относительно однотипных константных неисправностей на выходах функциональных элементов равна 2. Ею же доказано в [18, 19], что функция Шеннона длины единичного проверяющего теста относительно константных неисправностей типа 1 на выходах функциональных элементов в базисе Жегалкина равна 1. Аналогичный результат, но уже для неисправностей типа 0 на выходах функциональных элементов был получен совместно Ю.В.Бородиной и П.А.Бородиным в [20]. Д.С.Романов в [21, 22] установил, что в базисе {х&у,х(&у, 1,х(уУ г) Vх(у ~ г)} любую булеву функцию можно реализовать неизбыточной схемой, допускающей при произвольных константных неисправностях на выходах функциональных элементов единичный проверяющий тест длины 4. В [23] заявлено, что аналогичный результат может быть распространен на случай произвольного базиса, однако, доказательство данного факта не представлено. В [21] также заявлено о существовании базисов, в которых для любой булевой функции можно построить схему, допускающую полный проверяющий тест из четырех наборов в случае произвольных константных неисправностей на выходах элементов.

В работах [24, 25] Д.С.Романов, Е.В.Морозов и И.А.Кузнецов получают нетривиальные оценки функций Шеннона длины проверяющих и диагностических тестов для неисправностей типа "слипания" переменных (некоторый аналог неисправностей на входах схем).

Ещё одним направлением теории синтеза легкотестируемых схем является поиск минимальных тестов для схем, реализующих индивидуальные булевы функции или некоторые классы булевых функций. В работе [26] В.Г.Хахулин установил линейные верхнюю и нижнюю оценки длины полного проверяющего теста для схем, реализующих функцию 1п = х\ ф ... ф хп, при наличии произвольных константных неисправностей на

выходах элементов. В работах [27]-[30] С.Р.Беджанова устанавливает различные верхние и нижние оценки длин единичных и полных проверяющих и диагностических тестов для схем, реализующих дизъюнкцию п переменных х\ V ... V хп, при различных видах неисправностей функциональных элементов. В [31] исследуются вопросы длины тестов для схем, реализующих булевы функции из классов Поста и функции /с-значной логики.

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

Перейдем к обзору результатов по главам.

В главе 1 рассматривается задача построения легкотестируемых схем из функциональных элементов в базисах из элементов, имеющих не более двух входов. Допускаются единичные произвольные константные неисправности на выходах элементов, когда в неисправное состояние может перейти ровно один элемент схемы, который вне зависимости от того, что подаётся на его входы, выдаёт некоторую булеву константу 5, где 6 Е {0,1}.

В §1 главы 1 даются основные определения и формулируется следующая теорема:

Теорема 1. Для любой булевой функции /(х1,...,хп), для любого базисах из элементов, имеющих не более двух входов, существует неизбыточная схема, реализующая данную функцию и допускающая единичный проверяющий тест, длина которого не превосходит п + 3.

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

Лемма 1. Пусть даны два базиса В[ и В'2, относительно которых

известно, что каждая функция из базиса В[ реализуется неизбыточной схемой из функциональных элементов в базисе В'2 такой, что все возможные функции неисправности этой схемы это константы 0 и 1. И для булевой функции /(х\,..., хп) существует неизбыточная схема Б в базисе В[, допускающая единичный проверяющий тест длины I. Тогда существует неизбыточная схема в' в базисе В'2, реализующая /(х\,..., хп), допускающая единичный проверяющий тест длины I.

В §2 главы 1 теорема 1 доказывается для базисов {ж&у, х}, {х&у, а; 0 у, 1 },{х&у, ж фу 0 1, 0}, {х&у, х®у, х 0 у 0 1}, {х&у}. Для данных базисов получена верхняя оценка длины единичного проверяющего теста 71+1.

В §3 главы 1 теорема 1 доказывается для базисов {ж&у, х}, {х&у, 1}. Для этих базисов получена верхняя оценка длины единичного проверяющего теста п + 2.

В §4 главы 1 теорема 1 доказывается для базисов (ж&л/, х 0 у 0 1}, {ж&у, х V у}. Здесь получена верхняя оценка длины единичного проверяющего теста п + 3.

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

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

В §1 главы 2 даются дополнительные определения и формулируется следующая теорема:

Теорема 3. Для любой булевой функции /(хь ... ,хп), где п ^ 3; для любого функционально полного конечного базиса существует неизбыточ-

и

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

Данная теорема является основным результатом диссертации и по сути является обобщением результата, полученного 8.М.11ес1с1у в [10] для базиса Жегалкина, на случай произвольного функционально полного конечного базиса.

Булеву функцию щ(х, у, г) = ху 0 хг 0 уг 0 71 ж 0 72у 0 7з-г 0 74, где 71,..., 74 Е {0,1}, а 7 = (71,72,73,74), будем называть особенной.

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

Для доказательства теоремы 3 используется следующая лемма, доказанная в [11].

Лемма 2. Максимальное расширение произвольного полного конечного базиса содерж