Сложность и алгоритмы построения проверяющих тестов и некоторых классов полиномиальных форм булевых функций

• Автор: Рябец, Леонид Владимирович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2007
• Место защиты: Иркутск
• Количество страниц: 102 с.

Глава 1. Сложность некоторых классов полиномиальных форм булевых функций

§ 1. Сложность вложения специальной операторной формы в

класс Кь

§ 2. Сложность булевых функций и кронексровы спектры

Глава 2. Проверяющие тесты для бесповторных булевых функций

§ 3. Алгоритм построения проверяющих тестов

§ 4. Функция Шеннона для проверяющих тестов относительно

бесповторной альтернативы

Глава 3. Алгоритмы построения минимальных представлений булевых функций

§ 5. Алгоритм получения сложности специальной операторной

формы
§ 6. Алгоритм нахождения минимального представления функции в классе кронекеровых форм
§ 7. Алгоритм приближенной минимизации функции в классе
полиномиальных нормальных форм
Заключение
Список литературы

При проектировании современных вычислительных устройств важную роль играет аппарат дискретных функций. Несмотря па то, что скорость работы цифровых устройств постоянно повышается, существует некоторый физический предел этого роста. Проводимые в настоящее время разработки дискретных устройств с большим числом состояний носят пока экспериментальный характер. До сих пор аппарат булевых функций является наиболее адекватным для проектирования цифровой, в том числе микропроцессорной техники. Поэтому результаты исследований в области булевых функций способны еще на этапе проектирования цифровых устройств повысить их надежность и эффективность.
Практически важной характеристикой логических устройств является надежность их функционирования. Необходимость обеспечения этого свойства привела к возникновению и развитию направления под названием надежность и контроль управляющих систем.
Задачу правильности функционирования логических устройств можно рассматривать как на структурном, так и на макроуровне. Решение задачи на макроуровне осуществляется с помощью тестового подхода, предложенного С.В. Яблонским [27]. Его суть заключается в следующем. Пусть имеется некоторое логическое устройство с п входами и 1 выходом, реализующее некоторую булеву функцию /. Если логическое устройство ломается, то начинает функционировать другим образом, реализуя при этом функцию д, называемую функцией неисправности.
Для определения того, какую из функций / или g реализует устройство, можно подавать на вход по очереди все 2” наборов возможных значений переменных и сравнивать значения выдаваемые устройством со значениями функций / или g на этих входных наборах. Очевидно, что в общем случае эта процедура очень громозка и в случае, когда поломки не единичны и приводят к целому классу функций неисправности,

становится еще более сложной.
С.В. Яблонский предложил сравнивать / с функциями неисправностей на подобласти их определения, при этом если / отличается от каждой из функций неисправностей, то подобласть называется тестом. В общем случае тесты позволяют определять исправно ли логическое устройство не только на макроуровне (проверяющие тесты), по и исследовать его структурно, обнаружить в случае поломки логического устройства саму неисправность (диагностические тесты) [21].
Выделяются три основных типа неисправностей логических устройств. Константные неисправности соответствуют фиксации входного сигнала на некотором входе элемента логического устройства, неисправности типа слипания — ошибочной спайке входных каналов, инверсные — случайному подключению ко входу инвертора сигнала. В каждом из случаев изучается поведение соответствующей функции Шеннона и устанавливается ее явный вид.
Исследованию различных характеристик тестов посвящен целый ряд работ, например [18, 23, 24].
Одним из подходов, позволяющих избежать проверки всех наборов функции, является ограничение множества булевых функций, которые могут возникнуть в результате неисправностей логического устройства [49]. В работах [10, 16] получены сложности проверяющих тестов для функций классов Поста. Один из последних обзоров по тестированию содержится в [17].
Интересным классом для исследования сложности тестов является класс бссповторных булевых функций. Схемы, реализующие бесповтор-ную функцию, в случае константных неисправностей и нарушений работы элементов, сохраняют свойство бесповториости. Для бесповторных функций, существенно зависящих от всех своих переменных, в различных базисах получены оценки для функции Шеннона [8, 9]. В данной работе найдено точное значение функции Шеннона для проверяющих
Глава 2. Проверяющие тесты для бесповторных булевых функций
Вторая Глава IIосвящена исследованию верхней оценки функции Шеннона для проверяющих тестов относительно бесповторной альтернативы в базисе {-|, V, &, 0}.
В третьем параграфе рассматривается представление бесповторных функций в виде бинарных деревьев и для такого типа деревьев формулируется алгоритм построения проверяющих тестов относительно бесповторной альтернативы. Алгоритм позволяет получать проверяющие тесты определенной структуры и с заранее известной сложностью.
В четвертом параграфе при доказательстве ряда вспомогательных утверждений исследуется структура и размерность тестов, полученных с помощью сформулированного ранее алгоритма. На основе результатов по структуре полученных тестов приводится точное значение функции Шеннона для проверяющих тестов относительно бесповторной альтернативы в базисе {-|, V, &, 0}.