авторефераты диссертаций БЕСПЛАТНАЯ  БИБЛИОТЕКА

АВТОРЕФЕРАТЫ КАНДИДАТСКИХ, ДОКТОРСКИХ ДИССЕРТАЦИЙ

<< ГЛАВНАЯ
АГРОИНЖЕНЕРИЯ
АСТРОНОМИЯ
БЕЗОПАСНОСТЬ
БИОЛОГИЯ
ЗЕМЛЯ
ИНФОРМАТИКА
ИСКУССТВОВЕДЕНИЕ
ИСТОРИЯ
КУЛЬТУРОЛОГИЯ
МАШИНОСТРОЕНИЕ
МЕДИЦИНА
МЕТАЛЛУРГИЯ
МЕХАНИКА
ПЕДАГОГИКА
ПОЛИТИКА
ПРИБОРОСТРОЕНИЕ
ПРОДОВОЛЬСТВИЕ
ПСИХОЛОГИЯ
РАДИОТЕХНИКА
СЕЛЬСКОЕ ХОЗЯЙСТВО
СОЦИОЛОГИЯ
СТРОИТЕЛЬСТВО
ТЕХНИЧЕСКИЕ НАУКИ
ТРАНСПОРТ
ФАРМАЦЕВТИКА
ФИЗИКА
ФИЗИОЛОГИЯ
ФИЛОЛОГИЯ
ФИЛОСОФИЯ
ХИМИЯ
ЭКОНОМИКА
ЭЛЕКТРОТЕХНИКА
ЭНЕРГЕТИКА
ЮРИСПРУДЕНЦИЯ
ЯЗЫКОЗНАНИЕ
РАЗНОЕ
КОНТАКТЫ

Операторные преобразования и минимизация полиномиальных представлений булевых функций

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

Казимиров Алексей Сергеевич Операторные преобразования и минимизация полиномиальных представлений булевых функций 01.01.09 дискретная математика и математическая кибернетика

АВТОРЕФЕРАТ

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

Красноярск 2007

Работа выполнена на кафедре математической информатики Иркутского государственного педагогического университета

Научный консультант:

доктор физико-математических наук, профессор Винокуров Сергей Федорович

Официальные оппоненты:

доктор физико-математических наук, профессор Нужин Яков Нифантьевич;

кандидат физико-математических наук, доцент Кузнецов Александр Алексеевич

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

Институт математики им. Соболева СО РАН

Защита состоится 18 октября 2007 г. в 14 часов на заседании дис сертационного совета К 212.099.06 в Сибирском федеральном уни верситете по адресу: 660074, г. Красноярск, ул. Киренского, 26.

С диссертацией можно ознакомиться в библиотеке Сибирского федерального университета (г. Красноярск, ул. Киренского, 26).

Автореферат разослан 17 сентября 2007 г.

Ученый секретарь диссертационного совета К.В. Сафонов

Общая характеристика работы

Актуальность темы. Булевы функции получили свое название в честь английского математика Джорджа Буля, который в своей монографии сформулировал алгебраическую систему логики. Тем не менее, современное понятие булевой алгебры восходит к работам Джевонса и Пирса второй половины XIX века.

Первоначально булевы функции рассматривались как логические формулы и явились действенным средством решения комбинатор ных логических задач. Поэтому до середины XX века интерес к буле вым функциям носил преимущественно теоретический характер. Од нако в 1938 г. Клод Шеннон показал [10], как релейные схемы могут быть промоделированы с помощью булевых функций. В настоящее время булевы функции применяются при логическом проектирова нии цифровой и микропроцессорной техники, в теории кодирования и криптографии, а также в математическом моделировании.

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

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

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

Построение различных классификаций также интересно в связи с применением к следующим задачам: вычисление возможных харак теристик функций;

выбор функций, обладающих наилучшими для конкретной ситуации параметрами;

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

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

Задача перечисления заключается в определении числа классов эквивалентности без нахождения самих представителей. Впервые за дачу подсчета числа классов эквивалентности булевых функций по ставил Пойа [7], он же вычислил значения при малых n для груп пы перестановок переменных и группы Джевонса. Подход, разрабо танный Пойа, основывался на связи задачи перечисления с теорией представлений групп. В [11] были найдены явные формулы для вы числения числа классов для этих групп в общем случае.

Пойа разработал общий метод нахождения числа классов для случая, когда группа является подгруппой группы подстановок на множестве значений переменных. В дальнейшем теория перечисле ния Пойа была обобщена в работах Де Брёйна [3].

n n Каждая булева функция n переменных реализуется 23 2 раз личными полиномиальными представлениями. Одним из критери ев оценки этих представлений является их сложность. Чем мень ше сложность полинома, тем он предпочтительнее, так как мень шая сложность дает меньшие размеры и большую скорость работы электронных схем, построенных с использованием данного полино ма. Появление интереса непосредственно к полиномиальным пред ставлениям булевых функций, как объектам исследования, связано с практическими приложениями после того, как в конце прошлого века в цифровой технике стали активно использоваться элементы ти па "сложение по модулю 2". Тенденция развития электроники в на правлении увеличения быстродействия, уменьшения энергоемкости и стоимости привела к необходимости повышения эффективности цифровой техники во время проектирования на уровне представ ления схем булевыми функциями.

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

Использование минимальных формул позволяет повысить эффек тивность электронных схем, реализующих данные функции, умень шить их размер и увеличить скорость работы без применения новых технологий. При этом для большинства функций полиномиальные нормальные формы по сравнению с другими нормальными формами дизъюнктивными и конъюнктивными имеют более компактный размер [9] и обладают лучшей тестируемостью [5].



Исследование полиномиальных представлений ведется весьма ин тенсивно. Рассматривается широкий спектр вопросов: от исследо ваний сложности и нахождения минимальных форм до алгоритмов прямой реализации на микросхемах специального типа програм мируемых логических матрицах [8].





В ряде работ [1, 2] был предложен и разработан операторный подход к исследованию булевых функций. Переход к операторным формам позволил упростить работу с полиномиальными формами, а также обобщить и структурировать классы полиномиальных нор мальных форм.

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

Цели работы:

• получить оценки на число классов относительно по оператор ным преобразованиям булевых функций;

• найти инварианты операторных преобразований;

• построить алгоритмы минимизации булевых функций с исполь зованием операторной эквивалентности.

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

• получена замкнутая формула для числа S-классов булевых функ ций и асимптотическая оценка числа SP-классов булевых функ ций;

• найдена полная система инвариантов для функций 5 перемен ных по SP-преобразованиям;

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

Основные результаты диссертации являются новыми.

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

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

Апробация работы. Результаты диссертации докладывались на следующих конференциях: международная конференция "Алгебра, логика и кибернетика"(Иркутск, 2004 г.);

VI международная конфе ренция "Дискретные модели в теории управляющих систем"(Москва, 2004 г.);

V школа-семинар "Распределенные и кластерные вычисле ния"(Красноярск, 2005 г.);

VII международная конференция "Дис кретные модели в теории управляющих систем"(Москва, 2006 г.);

XVI международная школа-семинар "Синтез и сложность управля ющих систем"(Санкт-Петербург, 2006 г.);

российская школа-семинар "Синтаксис и семантика логических систем"(Иркутск, 2006 г.);

V Си бирская научная школа-семинар с международным участием "Ком пьютерная безопасность и криптография"(Томск, 2006 г.);

межвузов ская зональная конференция "Математика и проблемы ее преподава ния в вузе"(Иркутск, 2007 г.);

международный российско-китайский семинар "Алгебра и логика"(Иркутск, 2007 г.);

международная кон ференция "Алгебра и ее приложения"(Красноярск, 2007 г.).

Публикации. По теме диссертации опубликовано 16 научных ра бот [12]–[27], отражающих основное содержание диссертации, в том числе три работы в журналах, рекомендованных ВАК РФ.

Структура и объем работы. Диссертация изложена на 90 стра ницах и состоит из введения, трех глав, заключения и списка литера туры, содержащего 85 наименований, включая работы диссертанта.

Содержание работы Во введении дается обоснование актуальности темы исследова ний. Определяются основные понятия и терминология, принятая при изложении результатов.

Для дальнейшего изложения нам потребуются следующие обо значения и определения.

Будем использовать запись x для обозначения вектора перемен ных (x1,..., xn ), а для обозначения вектора констант 1,..., n.

Степень определим следующим образом:

x, если = 1, x = x, если = 0.

Если в записи функции отсутствуют переменные, то предполага ется, что ее переменными являются x1,..., xn.

Степень функции f обозначим через deg(f ).

Через det(M ) обозначим определитель матрицы M, а ее ранг через rank(M ).

Кронекерово произведение матриц будем обозначать символом.

Введем следующее обозначение для кронекеровой степени матрицы A:

A A... A = A[n].

n Остаточными подфункциями функции f по переменной xi назы ваются функции размерности на единицу меньше, полученные под становкой констант вместо переменной xi.

Нулевая остаточная:

fxi (x1,..., xn1 ) = f (x1,..., xi1, 0, xi,..., xn1 ).

Единичная остаточная:

fxi (x1,..., xn1 ) = f (x1,..., xi1, 1, xi,..., xn1 ).

Производная функции f по переменной xi определяется следую щим образом:

0 fxi (x1,..., xn1 ) = fxi (x1,..., xn1 ) fxi (x1,..., xn1 ).

Полиномиальной нормальной формой (ПНФ) функции f назы вается ее представление в виде суммы по модулю 2:

f (x1,..., xn ) = K1... Ks, (1) в которое в качестве слагаемых входят произведения Ki = z1 ·... · zki, где zj = xt или zj = xt для некоторой переменной xt, причем переменная может входить в произведение не более одного раза. В сумму может входить Ki, не содержащее ни одной переменной. Такое Ki считается равным 1.

Сложность представления (1) функции f (x1,..., xn ) определяет ся как s число слагаемых.

Сложность L(f ) функции f (x1,..., xn ) определяется как слож ность представления этой функции с минимальным числом слагае мых.

Сложность L(n) класса Fn всех булевых функций от n перемен ных определяется так:

L(n) = max L(f ) f Fn Тотальной булевой функцией называется функция, определенная на всех наборах.

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

Рассмотрим класс операторов на множестве булевых функций n переменных, которые удобно представить последовательностями a1... an, где ai {d, e, p}, а число n называется размерностью опе ратора.

Действие оператора a = a1... an на функцию f () определяется x по правилу: a(f ()) = fn (), где f0 () = f () и x x x x fi1 (), x если ai = e;

fi () = fi1 (x1,..., xi1, xi, xi+1,..., xn ), если ai = p;

x (fi1 ())xi, x если ai = d.

Представление функции f в виде s ai (h), f () = x (2) i= в котором a1,..., as операторы размерности n, называется опера торной формой функции f, построенной по функции h.

Пусть S полная группа подстановок на множестве {d, e, p}:

dep dep dep dep dep dep S=,,,,,.

dep dpe ped edp epd pde S-преобразованием операторов размерности n назовем после довательность 1... n, где i S. Преобразование действует на оператор a = a1... an следующим образом: (a) = 1 (a1 )... n (an ).

Действие S-преобразований распространяется на множество функ ций. SP-преобразование определяется как композиция S-преобразо вания и перестановки символов операторов.

Отображение i из множества Fn в некоторое множество X, удо влетворяющее соотношению i((f )) = i(f ) для всех f Fn и g G, называется инвариантом группы G.

Инвариант i группы G называется полным, если из совпадений значений i(f ) и i(f ) следует, что функции f и f являются G-экви валентными.

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

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

Теорема 1. Специальная операторная форма по фиксированной функции h является каноническим представлением.

Во втором параграфе определяются преобразования операторов.

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

Предложение 1. Пусть имеется S-преобразование и две опе раторные формы функции f () x 1 и 2. Тогда две функции g1 = (1 ) и g2 = (2 ), полученные S-преобразованием этих оператор ных форм, равны.

Доказывается, что множества S- и SP-преобразований составля ют группы.

Предложение 3. Группа SPn содержит 6n · n! преобразований.

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

Теорема 2. Для любых двух базисных функций h1 () и h2 () x x число Sh1 -классов совпадает с числом Sh2 -классов.

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

В третьем параграфе исследуются инварианты операторных пре образований.

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

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

Теорема 3. Действие любого S-преобразования = 1... n на функцию f (), где f представляется вектором, представимо в ви x де: (f ) = A() · f, при этом A() матрица размерности 2n 2n, которая получается следующим образом:

1. При n = 1 имеет место соответствие:

10 I = A() =, D = A() =, 01 1 0 E = A() =, P = A() =, 1 1 11 0 M = A(µ) =, N = A() =.

10 1 2. При n 1 матрица A() равна кронекерову произведению () соответствующих матриц:

A() = A(1 )... A(n ).

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

Предложение 5. I[n] единичная матрица размерности 2n 2n и имеют место следующие равенства:

M[n] · N[n] = I[n] ;

M[n] · M[n] = N[n] ;

N[n] · N[n] = M[n].

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

Теорема 4. Число S-классов KS (n) булевых функций n перемен ных выражается формулой n 1 2ni (2i +2(1)i ) 2ni (2i +2(1)i ) 2i Cn (4ni 1) i KS (n) = +2.

6 6n i= В шестом параграфе получена асимптотическая оценка числа SP классов.

Теорема 5. Для Invn числа инвариантных относительно группы SPn функций выполняется неравенство n Invn 6n · n! · 23· Следствие. Для числа SP-классов KSP (n) имеет место следу ющая асимптотическая оценка:

n KSP (n) n · n!

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

Теорема 6. L(7) 28.

Следствие. L(n) 32 2n при n 7.

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

В параграфе 8 приводится алгоритм точной минимизации функ ций шести переменных, основой которого послужил алгоритм из [6].

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

В параграфах 9 и 10 описываются генетические алгоритмы ми нимизации тотальных и частично заданных функций. Построенные алгоритмы реализованы на языке C++ в последовательном и парал лельном вариантах. Тестовые запуски для предположительно самых сложных функций 7 и 8 переменных показали работоспособность алгоритмов.

Библиографический список [1] Избранные вопросы теории булевых функций: Монография / А. С. Балюк, С. Ф. Винокуров, А. И. Гайдуков и др.;

Под ред.

С. Ф. Винокурова, Н. А. Перязева. М.: Физматлит, 2001.

192 с.

[2] Винокуров С.Ф. Полиномиальные операторные разложения и канонические формы булевых функций / С.Ф. Винокуров.

Иркутск: Из-во Иркутского ун-та. 1992. 26 с.

[3] Де Брейн Н.Дж. Теория перечисления Пойа / Н.Дж. Де Брейн // Прикладная комбинаторная математика. Под. ред.

Э. Беккенбаха. М.: Мир, 1968. С. 61–106.

[4] Логачев О.А. Булевы функции в теории кодирования и крип тологии / О.А. Логачев, А.А. Сальников, В.В. Ященко М.:

МЦНМО, 2004. 470 с.

[5] Fujiwara H. Logic Testing and Design for Testability / H. Fujiwara // Computer System Series, MIT Press, 1986.

[6] Gaidukov A. Algorithm to derive minimum ESOPs for 6-variable functions / A. Gaidukov // Proceedings of the 5th International Workshop on Boolean Problems 2002, Freiberg, Germany, Sept. 19– 20, 2002. pp. 141–148.

[7] Plia G. Sur les types des propositions composees / G. Plia // J.

o o Symb. Logic. 1937. 5. pp. 98–103.

[8] Sasao T. On the complexity of mod-2 sum PLA’s / T. Sasao, P. Besslich // IEEE Trans. on Comput. 1990. V. 39, No 2.

P. 262–266.

[9] Sasao T. Representation of Discrete Functions / T. Sasao. Kluwer Academic Publishers, May 1996.

[10] Shannon C. The Symbolic Analysis of Relay and Switching Circuits / C. Shannon. Trans. Am. Inst. Electrical Eng. 38, 1938.

713 p.

[11] Slepian D. On the number of symmetry types of Boolean functions of n variables / D. Slepian // Canad. J. Math. 1953. V. 5.

№ 2. pp. 185–193.

Работы автора по теме диссертации [12] Казимиров А.С. Верхняя оценка сложности булевых функций в классе ПНФ / С.Ф. Винокуров, А.С. Казимиров // Algebra and Model Theory 4. Novisibirsk. Novosibirsk State Technical University, 2003. P. 160–165.

[13] Казимиров А.С. Алгоритм частичной минимизации булевых функций в классе ПНФ / А.С. Казимиров // Алгебра, логика и кибернетика: Материалы Международной конференции. Ир кутск, ГОУ ВПО "Иркутский государственный педагогический университет 2004. С. 151–152.

[14] Казимиров А.С. Некоторые свойства специальной операторной формы булевых функций / С.Ф. Винокуров, А.С. Казимиров // Дискретные модели в теории управляющих систем: Труды VI Международной конференции. М.: Издательский отдел Фа культета ВМиК МГУ, 2004. С. 19–21.

[15] Казимиров А.С. О сложности булевых функций в классе ПНФ / С.Ф. Винокуров, А.С. Казимиров // Вестник Иркутского уни верситета. Специальный выпуск: Материалы ежегодной научно теоретической конференции молодых ученых. Иркутск: Ир кут. ун-т, 2004. С. 78–79.

[16] Казимиров А.С. О числе OP-классов булевых функций / С.Ф. Винокуров, А.С. Казимиров // Проблемы теоретической кибернетики: Тезисы докладов XIV Международной конферен ции. М.: МГУ, 2005. С. 29.

[17] Казимиров А.С. Параллельный генетический алгоритм при ближенной минимизации булевых функций / А.С. Казимиров, Л.В. Рябец // Распределенные и кластерные вычисления: Пя тая школа-семинар в рамках международной конференции "Па раллельные вычислительные технологии"(PaCT–2005). Крас ноярск: Институт вычислительного моделирования СО РАН, 2005. С. 44–48.

[18] Казимиров А.С. Оценка числа классов LP-эквивалентности бу левых функций / А.С. Казимиров // Вестник Бурятского уни верситета: Математика и информатика. Улан-Удэ: Бурятский государственный ун-т, 2005. Серия 13. Выпуск 2. С. 17–22.

[19] Казимиров А.С. Генетические алгоритмы в задачах миними зации булевых функций / А.С. Казимиров // Технологии Microsoft в теории и практике программирования: Тез. докл.

Новосибирск, 2006. С. 182–184.

[20] Казимиров А.С. Исследование полиномиальных представлений одной последовательности булевых функций / А.С. Казими ров // Дискретные модели в теории управляющих систем: VII Международная конференция, Покровское, 4–6 марта 2006 г.:

Труды. М.: МАКС Пресс, 2006. С. 139–141.

[21] Казимиров А.С. Число классов булевых функций, порож денных операторными отображениями / А.С. Казимиров // Материалы XVI Международной школы-семинара "Синтез и сложность управляющих систем- М.: Изд-во механико математического факультета МГУ, 2006. С. 44–48.

[22] Казимиров А.С. О числе SP-классов булевых функций / А.С. Казимиров // Синтаксис и семантика логических систем:

Материалы российской школы-семинара. Иркутск, Издатель ство ГОУ ВПО "Иркутский государственный педагогический университет 2006. С. 45–49.

[23] Казимиров А.С. Параллельные генетические алгоритмы в зада чах минимизации булевых функций / С.Ф. Винокуров,А.С. Ка зимиров // Вестник ТГУ. Приложение. 2006. № 17. С.

226–230.

[24] Казимиров А.С. Генетический алгоритм минимизации частич но заданных булевых функций / А.С. Казимиров // Вестник Бурятского университета: Математика и информатика. Улан Удэ: Изд-во Бурятского госуниверситета, 2006. Серия 13.

Выпуск 3. С. 28–32.

[25] Казимиров А.С. Алгоритм нахождения полиномиальных пред ставлений частично заданных функций большой размерности / А.С. Казимиров // Математика и проблемы ее преподавания в вузе: Труды III межвузовской конференции, посвященной памя ти профессора Б.А. Бельтюкова Иркутск: Изд-во Иркут. гос.

пед. ун-та, 2007. С. 125–126.

[26] Казимиров А.С. Генетический алгоритм нахождения полиноми альных представлений частично заданных булевых функций / А.С. Казимиров // Алгебра и логика: Материалы международ ного российско-китайского семинара. Иркутск: Издательство Иркут. гос. пед. ун-та, 2007. С. 65–67.

[27] Казимиров А.С. Группы операторных преобразований булевых функций / А.С. Казимиров // Международная конференция "Алгебра и ее приложения": Тезисы докладов. Красноярск, 2007. С. 64–65.

Редакционно-издательский отдел государственного образовательного учреждения высшего профессионального образования Иркутского государственного педагогического университета 664000, Иркутск, ул. Н. Набережная, Подписано в печать 14.09. Формат бумаги 6084 1/16. Объем 1,0 п.л.

Тираж 100 экз.

Отпечатано на RISO в ООП факультета МФИ ИГПУ

 

Похожие работы:





 
2013 www.netess.ru - «Бесплатная библиотека авторефератов кандидатских и докторских диссертаций»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.