Введение к работе
Актуальность темы. При проектировании современных вычислительных устройств важную роль играет аппарат дискретных функций. Несмотря на то, что скорость работы цифровых устройств постоянно повышается, существует некоторый физический предел этого роста. Проводимые в настоящее время разработки дискретных устройств с большим числом состояний носят пока экспериментальный характер. До сих пор аппарат булевых функций является наиболее адекватным для проектирования цифровой, в том числе микропроцессорной техники. Поэтому результаты исследований в области булевых функций способны еще на этапе проектирования цифровых устройств повысить их надежность и эффективность.
Практически важной характеристикой логических устройств является надежность их функционирования. Необходимость обеспечения этого свойства привела к возникновению и развитию направления под названием надежность и контроль управляющих систем.
Задачу правильности функционирования логических устройств можно рассматривать как на структурном, так и на макроуровне. Решение задачи на макроуровне осуществляется с помощью тестового подхода, предложенного СВ. Яблонским [14]. Его суть заключается в следующем. Пусть имеется некоторое логическое устройство с п входами и 1 выходом, реализующее некоторую булеву функцию /. Если логическое устройство ломается, то начинает функционировать другим образом, реализуя при этом функцию д, называемую функцией неисправности.
Для определения того, какую из функций / и д реализует устройство, можно подавать на вход по очереди все 2 наборов возможных значений переменных и сравнивать значения, выдаваемые устройством со значениями функций / или д на этих входных наборах. Очевидно, что в общем случае эта процедура очень громозка и в случае, когда поломки не единичны и приводят к целому классу функций неисправности, становится еще более сложной.
СВ. Яблонский предложил сравнивать / с функциями неисправностей на подобласти их определения, при этом если / отличается от каждой из функций неисправностей, то подобласть называется тестом. В общем случае тесты позволяют определять, исправно ли логическое устройство не только на макроуровне (проверяющие тесты), но и исследовать его структурно, обнаружить в случае полом-
ки логического устройства саму неисправность (диагностические тесты) [11].
Выделяются три основных типа неисправностей логических устройств. Константные неисправности соответствуют фиксации входного сигнала на некотором входе элемента логического устройства, неисправности типа слипания — ошибочной спайке входных каналов, инверсные — случайному подключению ко входу инвертора сигнала. В каждом из случаев изучается поведение соответствующей функции Шеннона и устанавливается ее явный вид.
Под сложностью теста обычно понимают количество наборов в этом тесте. Одним из подходов, позволяющих избежать проверки всех наборов функции, является ограничение множества булевых функций, которые могут возникнуть в результате неисправностей логического устройства. В [8] получены сложности проверяющих тестов для функций классов Поста. Один из последних обзоров по тестированию содержится в [9].
Интересным классом для исследования сложности тестов является класс бесповторных булевых функций. Схемы, реализующие бесповторную функцию, в случае константных неисправностей и нарушений работы элементов, сохраняют свойство бесповторности. Для бесповторных функций, существенно зависящих от всех своих переменных, А.А. Вороненко получены оценки функции Шеннона для различных базисов [4, 5]. В диссертации найдено точное значение функции Шеннона для проверяющих тестов относительно бесповторной альтернативы — тестов для бесповторных булевых функций, существенно зависящих от всех своих п переменных, на множестве всех бесповторных булевых функций размерности п.
Еще одним актуальным вопросом теории булевых функций является вопрос о сложности представления функций с помощью тех или иных структур.
Одним из основных способов задания булевых функций является формульное или, иначе, термальное представление. Вопрос о принципиальной возможности реализации тех или иных булевых функций формулами с использованием специально выбранных базисных функций был решен Э. Постом [18].
Хорошо исследован вопрос о реализации булевых функций дизъюнктивными и конъюнктивными нормальными формами [12]. Но полученные высокие нижние оценки сложности, совпадающие
с верхними, наложили определенное ограничение на возможность практической реализации таких нормальных форм.
В конце прошлого века в связи с бурным развитием цифровой техники стали активно использоваться элементы типа "сложение по модулю 2" (EXOR). Это дало новый толчок в развитии исследований по полиномиальным представлениям булевых функций. Было замечено, что при использовании полиномиальных нормальных форм часто получаются представления булевых функций меньшей сложности, кроме того, схемы, построенные с использованием элементов EXOR обладают лучшей тестируемостью.
Впервые полиномиальные нормальные формы были рассмотрены И. И. Жегалкиным при исследовании некоторых вопросов математической логики [6]. Затем, в 50-х годах прошлого века, полиномиальные нормальные формы исследовались в связи с их применением в теории кодирования [17, 19]. Однако вопрос сложности представлений булевых функций полиномиальными нормальными формами остается открытым, известные нижняя [16] и верхняя [7] оценки не совпадают.
С целью более детального исследования представлений булевых функций из всего класса полиномиальных нормальных форм выделяют некоторые подклассы, обладающие теми или иными свойствами. Примером такого подкласса может служить класс поляризованных полиномов Жегалкина. Одним из направлений обобщения классов поляризованных полиномов являются полиномы со смешанной полярностью, получившие название кронекеровых форм. Класс кро-некеровых форм определяется кронекеровым произведением трех типов базисов:
Ті = [1,ж], Т2 = [1,х], Т3 = [х,х].
В этом классе, например, третий базис определяет базис для совершенных полиномиальных нормальных форм, первый — для полиномов Жегалкина. Исследованиям кронекеровых форм посвящены работы [2, 15].
В диссертации найден алгоритм нахождения минимальной сложности булевой функции в классе кронекеровых форм.
В 90-х годах был предложен операторный подход к исследованию булевых функций [10]. Использование операторов позволило обобщить полиномиальные нормальные формы на полиномиальные формы по базисным функциям. Введение понятия пучка операторов
позволило описывать произвольные классы полиномиальных форм по базисным функциям [1, 3].
На языке операторов была сформулирована новая каноническая форма булевых функций — специальная операторная форма [23]. Вид специальной операторной формы оказался очень тесным образом связан со свойствами полиномиальных представлений булевых функций. В диссертации решен вопрос о ее связи со сложностью функций в классе ПНФ.
Значительным и мощным аппаратом для работы с булевыми функциями являются спектральные методы. В основе таких методов лежат дискретные преобразования Рида-Маллера. Сами методы нашли широкое применение в логическом синтезе и логическом проектировании (определение эквивалентностей различного типа) [13]. В ряде работ были предложены различные методы нахождения спектров булевых функций: на основе матричных преобразований [13, 20], представлений функций в виде бинарных диаграмм решений [22], с использованием вероятностных методов [21]. В первой главе диссертации с помощью операторного подхода обобщено понятие спектра Рида-Маллера и введено понятие кронекерова спектра булевых функций. Для такого типа спектров предложен метод их нахождения с использованием операторов и получена связь со сложностью булевых функций в классе кронекеровых форм.
Цели работы:
исследовать сложность представления специальной операторной формы булевых функций в различных классах операторных пучков;
найти связь сложности специальной операторной формы со сложностью булевых функций;
перенести операторный подход, развитый для булевых функций, на спектральную теорию, и в рамках этого подхода описать связь двоичного спектра со сложностью булевых функций;
исследовать верхнюю оценку функции Шеннона для проверяющих тестов бесповторных булевых функций, существенно зависящих от всех своих переменных;
исследовать вопросы построения минимальных представлений
булевых функций большой размерности в различных классах
полиномиальных форм.
Основные результаты и научная новизна. Основные научные результаты диссертации следующие:
найдена сложность представления специальной операторной формы булевых функций в классах двупорожденных операторных пучков с фиксированным оператором в начале пучка;
определена связь сложности специальной операторной формы со сложностью булевых функций в классе двупорожденных операторных пучков и классе всех операторных форм;
с использованием операторного подхода введено понятие кро-некерова спектра булевых функций, найдены способы построения таких спектров и определена связь кронекерова спектра со сложностью функций в классе кронекеровых форм;
найдено точное значение функции Шеннона для проверяющих тестов относительно бесповторной альтернативы и алгоритм построения таких тестов;
сформулированы и реализованы алгоритмы построения минимальных представлений булевых функций в классе кронекеровых форм и в классе полиномиальных нормальных форм с использованием свойств специальной операторной формы.
Основные результаты диссертации являются новыми.
Теоретическая и практическая ценность. Полученные результаты имеют теоретическое значение и могут найти применение в исследованиях по теории функциональных систем и по теории сложности булевых функций. Результаты могут быть использованы в логическом проектировании.
Методы исследований. В диссертации используются методы комбинаторики, теории булевых функций и линейной алгебры. В ряде случаев проводились компьютерные вычисления.
Апробация работы. Результаты диссертации были представлены на ежегодной научно-теоретической конференции молодых ученых Иркутского государственного университета (Иркутск, 2003 г., 2004 г.), Международной конференции «Алгебра, логика и кибернетика» (Иркутск, 2004 г.), VI Международной конференции «Дискретные модели в теории управляющих систем» (Москва, 2004 г.), конференции-конкурсе «Технологии Microsoft в теории и практике программирования» (Новосибирск, 2006 г.), V Сибирской научной школе-семинаре с международным участием «Компьютерная безопасность и криптография» (Шушенское, 2006 г.), школе-семинаре «Синтаксис и семантика логических систем» (Иркутск, 2006 г.), Международном российско-китайском семинаре «Алгебра и логика» (Иркутск, 2007 г.), Международной конференции «Алгебра и ее приложения» (Красноярск, 2007 г.), а также докладывались на семинаре кафедры Математической информатики Иркутского государственного педагогического университета «Дискретная математика и математическая информатика» под руководством д.ф.-м.н., профессора НА. Перязева.
Публикации. По теме диссертации опубликовано 13 научных работ, отражающих основное содержание диссертации, в том числе две работы в журналах, рекомендованных ВАК РФ.
Структура и объем работы. Диссертация изложена на 102 страницах и состоит из введения, трех глав, заключения и списка литературы, содержащего 62 наименования, включая работы диссертанта.
