Тесты схем для некоторых классов булевых функций тема автореферата и диссертации по математике, 01.01.09 ВАК РФ

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

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

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

доктор физико-математических наук, профессор Лев Абрамович Шоломов кандидат физико-математических наук, профессор Владимир Алексеевич Стеценко

Казанский (Приволжский) федеральный университет '

Защита диссертации состоится /у- февраля 2012 г. в 16 часов 45 минут на заседании диссертационного совета Д.501.001.84 при МГУ по адресу: Российская Федерация, 119991, Москва, ГСП-1, Ленинские горы, д.1, Московский государственный университет имени М.В. Ломоносова, Механико-математический факультет, аудитория 14-08.

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

Автореферат разослан// января 2011 года.

Ученый секретарь диссертационого совета Д 501.001.84 при МГУ, доктор физико-математических наук, профессор

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

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

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

f(x), х = (2:1. хп). На схему воздействует некоторый источник неисправностей, под влиянием которого схема вместо "правильной" функции f(x) может выдавать какие-то отличные от f(x) функции неисправностей gi(x), . gk(i). Характер воздействия источника неисправностей на схему предполагается известным, а потому набор возможных функций неисправностей gi. gk заранее известен. В ходе эксперимента на входы схемы можно последовательно .• подавать наборы cri. cr| значений переменных и наблюдать значения 7Ti, . 7Г/ на выходе схемы. Если в результате эксперимента можно ответить на вопрос, реализует ли схема заданную функцию / или же она реализует одну из функций неисправностей, то множество Т = является проверяющим тестом; если результат эксперимента позволяет ответить на вопрос, какую именно функцию из множества реализует схема, то Т является диагностическим тестом. Различают полные тесты, когда допускается любое подмножество неисправных элементов в схеме,

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

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

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

При таком способе контроля исправности и диагностики

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

возможную длину тестов для заданных схем; б) построение схем, допускающих короткие тесты; в) оценка длины минимальных тестов для заданных схем (в первой задаче) или для заданных функций (во второй задаче). Работы1’2 стали истоком и начальной базой для последующего создания и развития соответствующей математической теории. .

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

обрывы и замыкания контактов. Уже в работе2 представлен

ряд результатов, касающихся построения легкотестируемых контактных схем как для произвольных булевых функций, так и для некоторых конкретных булевых функций и операторов. Здесь, а в дальнейшем в работах В.В. Глаголева3, С.М. Вартаняна4,' Д.С. Романова5 и других авторов исследовались возможности построения легкотестируемых схем, имеющих блочную структуру. Схемы с блочной структурой можно строить для булевых функций, допускающих простую декомпозицию (скажем, для линейных и для симметрических булевых функций), а также для достаточно простых булевых операторов (например, сравнения булевых наборов, арифметического сложения двоичных чисел). Типичные полученные при этом верхние оценки длины проверяющих и единичных диагностических тестов носят константный и логарифмический по п характер (п — число переменных у реализуемых функций и операторов).

Заслуживающим внимания классом контактных схем, допускающих короткие тесты, оказался класс бесповторных контактных схем, в которых присутствует ровно по одному контакту каждой переменной. Тесты для таких схем изучали И.В. Коган6,

3Глаголев В.В. Построение тестов для блочных схем // ДАН СССР, — 1962.

- Т. 144. - №6. - С. 1237 - 1240.

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

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

6Коган И.В. О тестах для бесповторных контактных схем // Проблемы кибернетики. — Вып. 12. — М.: Наука, 1964. — С. 39—44.

В.В. Ваксов7, Х.А. Мадатян8. Они установили, что если булева функция от п переменных допускает бесповторную реализацию, то для нее можно строить контактные схемы, допускающие полные проверяющие тесты и единичные диагностические тесты линейной по п длины. Вместе с тем Х.А. Мадатян8 установил, что любая контактная схема для линейной булевой функции от тг переменных допускает лишь тривиальный полный диагностический тест,' содержащий все 2" входных наборов значений переменных, а Н.П. Редькин9 показал, что любую булеву функцию от п переменных можно реализовать контактной схемой, допускающей полный проверяющий тест, длина которого не превосходит Ц 2П. В случаях, когда в качестве неисправностей допускаются только обрывы (или только замыкания) контактов Н.П. Редькин10 показал, что любую булеву функцию от п переменных можно реализовать контактной схемой, допускающей полный проверяющий тест, экспоненциальной, но существенно меньшей чем 2" длины.

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

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

Понятия проверяющего и диагностического тестов для схем<

7Ваксов В.В. О тестах для бесповоротных контактных схем // Автоматика и телемеханика. — 1965. — Т. 26, №3. — С. 521-524.

8Мадатян Х.А. Полный Тест для бесповоротных контактных схем // Проблемы кибернетики. — Вып. 23. — М.: Наука, 1970. — С. 103-118.

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

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

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

В работе S.М. Reddy11 было показано, что в случае произвольных константных неисправностей на выходах элементов любую булеву функцию f(xi. xn) можно реализовать схемой в базисе Жегалкина, допускающей единичный проверяющий тест длины п + 3. В работах Н.П. Редькина12’13,14 установлено: а) в случае' произвольных константных неисправностей на выходах элементов любую булеву функцию от п переменных можно реализовать схемой (в любом конечном функционально полном базисе), допускающей полный проверяющий тест, длина которого по порядку не превосходит 2"/2; б) в случае однотипных константных неисправностей на выходах элементов любую булеву функцию от п переменных можно реализовать схемой в классическом базисе , допускающей единичный диагностический тест, длина которого не превосходит 2n+l, в) в случае однотипных константных неисправностей на выходах элементов для любой булевой функции f(x 1. Ж„) можно построить неизбыточную схему15 в бесконечном базисе