Введение к работе
Актуальность темы
Данная работа является исследованием в области математической теории контроля исправности и диагностики неисправностей управляющих систем, одного из разделов дискретной математики и математической кибернетики.
Сложность управляющих систем и большие требования к надежности их функционирования потребовали изобретения новых, достаточно эффективных и легко поддающихся автоматизации способов контроля исправности и диагностики неисправностей таких систем. Весьма удачными, получившими широкое признание и всестороннее теоретическое исследование оказались предложенные в работах СВ. Яблонского и И.А. Чегис1,2 логические способы контроля исправности и диагностики неисправностей управляющих систем. Содержательная суть этих способов заключается в следующем.
Управляющая система, скажем контактная схема или схема из функциональных элементов, рассматривается как некоторое устройство ("черный ящик") с п входами, на которые подаются переменные Xi,...,x„, и выходом, на котором реализуется функция f(x), х = (хи ...,„). На схему воздействует некоторый источник неисправностей, под влиянием которого схема вместо "правильной" функции /() может выдавать какие-то отличные от f(x) функции неисправностей 9i(x), ..., дк(х). Характер воздействия источника неисправностей на схему предполагается известным, а потому набор возможных функций неисправностей #1,...,( заранее известен. В ходе эксперимента на входы схемы можно последовательно . подавать наборы сгі,...,<Г| значений переменных и наблюдать значения 7Гі, ...,7Г/ на выходе схемы. Если в результате эксперимента можно ответить на вопрос, реализует ли схема заданную функцию / или же она реализует одну из функций неисправностей, то множество Т = {сгі,...,сг/} является проверяющим тестом; если результат эксперимента позволяет ответить на вопрос, какую именно функцию из множества {f,gi, ...,<7fc} реализует схема, то Т является диагностическим тестом. Различают полные тесты, когда допускается любое подмножество неисправных элементов в схеме,
1Яблонский СВ., Чегис И.А. О тестах для электрических схем // УМН — 1955. - ТЛО, вып. 4(66). - С. 182-184.
2Чегис И.А., Яблонский СВ. Логические способы контроля работы электрических схем // Труды МИАН. — 1958. — Т.51. — С. 270-360.
и единичные тесты, когда в неисправное состояние может перейти лишь один элемент. Число наборов в тесте Т определяет его длину.
При таком способе контроля исправности и диагностики неисправностей схем весьма актуальными и важными становятся задачи: а) поиск минимальных, т.е. имеющих наименьшую .-возможную длину тестов для заданных схем; б) построение схем, допускающих короткие тесты; в) оценка длины минимальных тестов для заданных схем (в первой задаче) или для заданных функций (во второй задаче). Работы1'2 стали истоком и начальной базой для последующего создания и развития соответствующей математической теории.
Первоначально существенное внимание уделялось контактным схемам; в качестве неисправностей рассматривались обычно обрывы и замыкания контактов. Уже в работе2 представлен ряд результатов, касающихся построения легкотестируемых контактных схем как для произвольных булевых функций, так и для некоторых конкретных булевых функций и операторов. Здесь, а в дальнейшем в работах В.В. Глаголева3, СМ. Вартаняна4,' Д.С. Романова5 и других авторов исследовались возможности построения легкотестируемых схем, имеющих блочную структуру. Схемы с блочной структурой можно строить для булевых функций, допускающих простую декомпозицию (скажем, для линейных и для симметрических булевых функций), а также для достаточно простых булевых операторов (например, сравнения булевых наборов, арифметического сложения двоичных чисел). Типичные полученные при этом верхние оценки длины проверяющих и единичных диагностических тестов носят константный и логарифмический по п характер (п — число переменных у реализуемых функций и операторов).
Заслуживающим внимания классом контактных схем,.-допускающих короткие тесты, оказался класс бесповторных контактных схем, в которых присутствует ровно по одному контакту каждой переменной. Тесты для таких схем изучали И.В. Коган6,
3Глаголев В.В. Построение тестов для блочных схем // ДАН СССР, — 1962. - Т. 144. - №6. - С. 1237 - 1240.
Вартанян СМ. Единичные диагностические тесты для последовательных блочных схем. — Дисс. на соиск. уч. ст. к.ф.-м.н. — М., 1987. — 114с.
Романов Д.С. Построение тестов и оценка их параметров для некоторых классов контактных схем. —Дисс. на соиск. уч. ст. к.ф.-м.н. — М., 2000. — 114с. 6Коган И.В. О тестах для бесповторных контактных схем // Проблемы кибернетики. — Вып. 12. — М.: Наука, 1964. — С. 39—44.
В.В. Ваксов7, Х.А. Мадатян8. Они установили, что если булева функция от п переменных допускает бесповторную реализацию, то для нее можно строить контактные схемы, допускающие полные проверяющие тесты и единичные диагностические тесты линейной по п длины. Вместе с тем Х.А. Мадатян8 установил, что любая контактная схема для линейной булевой функции от п переменных допускает лишь тривиальный полный диагностический тест,-содержащий все 2" входных наборов значений переменных, а Н.П. Редькин9 показал, что любую булеву функцию от п переменных можно реализовать контактной схемой, допускающей полный проверяющий тест, длина которого не превосходит Щ 2п. В случаях, когда в качестве неисправностей допускаются только обрывы (или только замыкания) контактов Н.П. Редькин10 показал, что любую булеву функцию от п переменных можно реализовать контактной схемой, допускающей полный проверяющий тест, экспоненциальной, но существенно меньшей чем 2" длины.
В целом же теория тестирования контактных схем содержит достаточно много сильных, в ряде случаев окончательных результатов, связанных с синтезом легкотестируемых схем и оценкой длины тестов для индивидуальных булевых функций и операторов, а также для функций из отдельных весьма "жидких" классов (например, симметрических булевых функций). Другой раздел, в котором рассматриваются произвольные или, как говорят еще "почти все" булевы функции, содержит, наоборот, совсем немного существенных результатов.
В теории тестирования схем из функциональных элементов имеет место "уклон" в противоположную сторону: здесь много сильных результатов, относящихся к синтезу легкотестируемых схем для произвольных булевых функций и малоизученными остаются проблемы построения легкотестируемых схем и оценки длины тестов для индивидуальных булевых функций и операторов.
Понятия проверяющего и диагностического тестов для СХЄМ'
Ваксов В.В. О тестах для бесповоротных контактных схем // Автоматика и телемеханика. — 1965. — Т. 26, №3. — С. 521-524.
8Мадатян Х.А. Полный Тест для бесповоротных контактных схем // Проблемы кибернетики. — Вып. 23. — М.: Наука, 1970. — С. 103-118.
9Редькин Н.П. О полных проверяющих тестах для контактных схем // Методы дискретного анализа в исследовании экстремальных структур. — Вып. 39. - Новосибирск: Изд-во ИМ СО АН СССР, 1983. — С. 80-87.
10Редышн Н.П. О проверяющих тестах замыкания и размыкания // Методы дискретного анализа в оптимизации управляющих систем. — Вып. 40. — Новосибирск: Изд-во ИМ СО АН СССР, 1983. - С. 87-99.
из функциональных элементов вводятся точно так же, как и для контактных схем. В качестве неисправностей чаще всего рассматриваются константные и инверсные неисправности на выходах элементов, на входах элементов и на входах схем.
В работе S.M. Reddy11 было показано, что в случае произвольных константных неисправностей на выходах элементов любую булеву функцию f(xi,...,xn) можно реализовать схемой в базисе Жегалкина, допускающей единичный проверяющий тест длины п + 3. В работах Н.П. Редькина12'13'14 установлено: а) в случае' произвольных константных неисправностей на выходах элементов любую булеву функцию от п переменных можно реализовать схемой (в любом конечном функционально полном базисе), допускающей полный проверяющий тест, длина которого по порядку не превосходит 2/2; б) в случае однотипных константных неисправностей на выходах элементов любую булеву функцию от п переменных можно реализовать схемой в классическом базисе {хку, хМу, х}, допускающей единичный диагностический тест, длина которого не превосходит 2п+1, в) в случае однотипных константных неисправностей на выходах элементов для любой булевой функции f(xi,...,xn) можно построить неизбыточную схему15 в бесконечном базисе {xiSzx2,xikx2^x3,...; x^V x2,Xi V х2 V х3, .-.;}, допускающую . единичный диагностический тест, длина которого по порядку не превосходит log п.
Наиболее близкие к окончательным, а в ряде случаев и окончательные результаты установлены для однотипных неисправностей на выходах элементов. Для базиса Жегалкина СВ. Коваценко16 установил, что в случае инверсных неисправностей на выходах элементов любую булеву функцию можно реализовать
uReddy S.M. Easily testable realization for logic functions//IEEE Trans. Comput. - 1972. - v.21. - N 1. - P. 124-141.
12Редышн Н.П. О полных проверяющих тестах для схем из функциональных элементов. (1992) , 198-222.
13Редышн Н.П. О единичных диагностических тестах для однотипных константных неисправностей на выходах функциональных элементов // Вестник Московского университета. Серия 1, Математика. Механика. — 1992. — N 5. — С. 43-46.
14Редькин Н.П. О синтезе легкотестируемых схем в одном бесконечном базисе // Вестник Московского университета. Серия 1, Математика. Механика. — 2007, №3. С. 29-33.
15Редькин Н.П. Надежность и диагностика схем. М. : Изд-во МГУ. 1992.
16Коваценко СВ. Синтез легкотестируемых схем в базисе Жегалкина для инверсных неисправностей // Вестник московского университета. Серия 15. Вычислительная математика и кибернетика. — 2000. — № 2. — С. 45-47.
неизбыточной схемой, допускающей единичный проверяющий тест длины 1. Н.П. Редькин17 для произвольного функционально полного конечного базиса и инверсных неисправностей на выходах элементов показал, что любую булеву функцию можно реализовать неизбыточной схемой, допускающей единичный проверяющий тест длины 3. Ю.В Бородина18 для однотипных константных неисправностей на выходах элементов и классического базиса установила, что любую булеву функцию можно реализовать схемой, допускающей полный проверяющий тест длины 2, и для некоторых функций этот результат неулучшаем. Для однотипных константных: неисправностей типа 1 на выходах элементов и базиса Жегалкина она же установила19, что любую булеву функцию можно реализовать схемой, допускающей тест длины 1; аналогичный результат, но в случае неисправностей противоположного типа установлен в работе20 Ю.В. Бородиной и П.А. Бородина.
Что касается направления, связанного с исследованием тестирования схем для индивидуальных булевых функций, то оно вплоть до настоящего времени является малоизученным. Приведем некоторые результаты, касающиеся тестирования схем для отдельных индивидуальных булевых функций. В работах В.Н. Носкова21'22 получены линейные по п нижние оценки длины полных проверяющих тестов для схем, реализующих функцию выбора от п переменных, и единичных диагностических тестов для схем/ реализующих функцию xik...kxn Vx~i&t...&xn, в случае константных
17Редькин Н.П. Единичные проверяющие тесты для схем при инверсных неисправностях элементов. Математические вопросы кибернетики (2003), 217-230.
18Бородина Ю.В. О синтезе легкотестируемых схем в случае однотипных константных неисправностей на выходах элементов // Вестник Московского университета. Серия 15. Вычислительная математика и кибернетика. — 2008.
- № 1. - С. 40-44.
19Бородипа Ю.В. О схемах, допускающих единичные тесты длины 1 при константных неисправностях на выходах элементов // Вестник Москва ун-та. Серия 1. Математика. Механика. — 2008, №5. — С. 49-52.
20Бородина Ю.В., Бородин П.А. Синтез легкотестируемых схем в базисе Жегалкина при константных неисправностях типа "0"на выходах элементов // Дискретная математика. — 2010. — Т. 22, вып. 3. — С. 127-133.
21Носков В.Н. О сложности тестов, контролирующих работу входов логических схем // Дискретный анализ. Новосибирск: ИМ СО АН СССР, — 1975. — Т. 26.
- С. 23-51.
22Носков В.Н. О длинах единичных диагностических тестов, контролирующих работу входов логических схем // Методы дискретного анализа в синтезе управляющих систем. — сборник трудов Института математики СО АН СССР.
- 1978. - вып. 32. - С. 40-51.
неисправностей на входах схем; эти оценки использовались для обоснования нижних оценок соответствующих функций Шеннона. В работе Н.П. Редькина23 исследовалась зависимость длины проверяющих тестов от вида неисправностей, в качестве которых рассматривались константные неисправности на выходах элементов и константные неисправности на входах элементов; при этом устанавливались соответственно константные верхние оценки длины проверяющих тестов для дизъюнкций и конъюнкций п переменных и линейные по п нижние оценки длины тестов для тех же функций. В.Г. Хахулин24 рассматривал схемы из функциональных элементов для линейной булевой функции 1п = і! 8 ... ф г„ при наличии произвольных константных неисправностей на входах элементов; им ' установлено, что полный проверяющий тест для таких схем имеет длину не менее п + 1 и что существует схема, реализующая 1п и допускающая полный проверяющий тест длины п + 2.
Именно к последнему направлению относится диссертация, в которой исследуются вопросы, связанные с построением легкотестируемых схем из функциональных элементов и оценкой длины тестов для наиболее известных и часто встречающихся в теоретических и в прикладных исследованиях конкретных булевых функций — дизъюнкций и конъюнкций. В качестве неисправностей здесь предполагаются инверсные неисправности на входах и на выходах элементов, а также на входах схем.
Цель работы
Основной целью работы является синтез легкотестируемых схем из функциональных элементов в различных базисах для элементарных дизъюнкций и конъюнкций, а также для линейных функций. В качестве неисправностей рассматриваются: а) инверсные неисправности на входах схем; б) инверсные неисправности на входах элементов схем; в) инверсные неисправности на выходах элементов схем. Одновременно с синтезом легкотестируемых схем целью работы является также получение верхних и нижних оценок длины тестов для рассматриваемых неисправностей.
Научная новизна работы
23Редькин Н.П. О зависимости длины проверяющих тестов от вида,-неисправностей // Методы дискретного анализа в теории кодов и схем. — Сборник трудов Института математики СО АН СССР. — 1987. — Вып. 46. — С. 65-71.
24Хахулин В.Г. О проверяющих тестах для счетчика четности // Дискретная математика. — 1995. — Т.7, вып. 4. — С. 51-59.
Все результаты работы являются новыми. В диссертации . получены следующие основные результаты.
1. Найдены значения длин минимальных тестов для схем
из функциональных элементов, реализующих элементарные
дизъюнкции в случае инверсных неисправностей на входах схем.
В данном случае были рассмотрены единичные проверяющие,
единичные диагностические, полные проверяющие и полные
диагностические тесты.
2. Найдена наименьшая возможная длина полного
диагностического теста для схем в базисах {V} и {V,-},
реализующих дизъюнкцию Xi V ... V хп и обобщенную дизъюнкцию
xi V ... V Хк V Xk+i V ... V хп, 1 ^ к ^ п, соответственно, в случае
инверсных неисправностей на входах элементов схем.
-
Получена верхняя оценка длины минимального единичного диагностического теста для схем, реализующих линейные функции в классическом базисе {&, V,"}, в случае инверсных неисправностей на выходах элементов.
-
Получены верхние оценки длин минимальных единичного диагностического и полного проверяющего тестов для схем, реализующих элементарные дизъюнкции, в случае инверсных неисправностей на выходах элементов. Установлено также, что полученная оценка длины минимального единичного диагностического теста в общем случае не улучшаема.
Методы исследования
В диссертации используются методы дискретной математики и математической кибернетики, теории диагностики управляющих систем, математической теории управляющих систем.
Теоретическая и практическая ценность
Работа имеет теоретический характер. Результаты диссертации могут найти применение в теории диагностики управляющих систем. Представленные в диссертации методы синтеза могут быть использованы при практическом синтезе легкотестируемых схем.
Апробация работы
Результаты диссертации докладывались на семинаре "Диагностика управляющих систем" под руководством профессора' Н.П. Редькина (МГУ, 2007-2011гг.), на семинаре "Математические вопросы кибернетики" под руководством профессора О.М.
Касим-Заде (МГУ, 2011г.), на XV Международной конференции "Проблемы теоретической кибернетики"(Казань, 2008г.), на VI-II Международной конференции "Дискретные модели в теории- управляющих систем" (Москва, 2009г.), на Международной научной конференции студентов, аспирантов и молодых ученых "Ломоносов-2010" и "Ломоносов-2011"(МГУ, 2010-2011гг.), на научной конференции "Ломоносовские чтения" (МГУ, 2008-2010гг.), на X Международном семинаре "Дискретная математика и ее приложения" (Москва, 2010), на XVI Международной конференции "Проблемы теоретической кибернетики"(Нижний Новгород, 2011г.).
Публикации
Результаты диссертации опубликованы в 8 работах автора, список которых приведен в конце автореферата [1—8].
Структура и объем работы
Диссертация состоит из введения, трех глав и списка литературы из 43 наименований. Общий объем диссертации 96 страниц, в работе содержится 5 таблиц и 45 рисунков.
