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

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

005537030

АКИНИН Андрей Александрович

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

Специальность: 05.13.18 - Математическое моделирование,

численные методы и комплексы программ

АВТОРЕФЕРАТ

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

7 НОЯ 2013

Воронеж - 2013

005537030

Работа выполнена в ФГБОУ ВПО «Воронежский государственный технический университет»

Научный руководитель

Подвальный Семен Леонидович,

доктор технических наук, профессор, ФГБОУ ВПО «Воронежский государственный технический университет», заведующий кафедрой автоматизированных и вычислительных систем

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

Зольников Владимир Константинович,

доктор технических наук, профессор, ФГБОУ ВПО «Воронежская государственная лесотехническая академия», заведующий кафедрой вычислительной техники и информационных систем;

Болкунов Александр Анатольевич,

кандидат технических наук, доцент, «Центр системных исследований и разработок» — ОАО «Научно-технический центр радиоэлектронной борьбы» (г. Воронеж), директор.

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

ФГБОУ ВПО «Воронежский государственный университет»

Защита состоится «28» ноября 2013 г. в II00 в конференц-зале на заседании диссертационного совета Д 212.037.01 ФГБОУ ВПО «Воронежский государственный технический университет» по адресу: 394026, г. Воронеж, Московский просп., 14.

С диссертацией можно ознакомиться в научно-технической библиотеке ФГБОУ ВПО «Воронежский государственный технический университет».

Автореферат разослан «28» октября 2013 г.

Ученый секретарь л

диссертационного совета Л*/* //^Барабанов Владимир Федорович

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

Актуальность темы. Представление булевых функций (БФ) в полиномиальных нормальных формах с фиксированной полярностью в последние двадцать лет получает всё более широкое распространение, так как имеют самые разнообразные приложения: функциональная декомпозиция БФ, сжатие данных, корректирующие коды, спектральный анализ, проектирование устройств волновых вычислений, многоверсионное проектирование и т.п. Особенно широко полиномиальные формы БФ применяются для проектирования комбинационных автоматов, приспособленных к тестопригодному проектированию (Design For Testability или DFT) и встроенному самотестированию (Built - In -Self- Test или BIST). Уникальное свойство тестопригодности полиномиальных логических преобразователей (ПЛП) заключается в том, что для их структурного тестирования используются тестовые векторы с унифицированной битовой структурой, не зависящей от реализуемой логической функции. При этом для обнаружения любой одиночной константной неисправности достаточное и необходимое количество тестовых векторов не превосходит величины 2п, где п - количество аргументов булевой функции (БФ). Данное обстоятельство при широком практическом использовании ПЛП существенно упрощает решение задач синтеза и оценки качества контрольных и диагностических тестов для цифровой техники.

Большой вклад в теоретические и практические разработки по формированию и использованию полиномиальных нормальных форм БФ внесли И.И. Жегалкин, L.S. Reed, D.E. Muller, S.M. Reddy, A.E.A. Almaini, D.H. Green, T. Sa-sao, B.J. Falkowski, M.J. Davio, M. Perkowski, G. Papakonstantinou, H.A. Перязев, В.П. Супрун, А.Д. Закревский, Н.Р. Торопов, В.Д. Малюгин, B.C. Выхованец и многие другие.

Анализ доступных работ, касающихся вопросов преобразования БФ к полиномиальной форме, показывает, что такое преобразование относится к NP-трудным задачам, и в этой связи для п более 5...6 преобразование возможно только с использованием специализированных объектно—ориентированных программных комплексов, которые в настоящее время отсутствуют у отечественных инженеров - схемотехников. Следует также отметить, что из-за обилия различных алгоритмов полиномиального преобразования БФ и отсутствия единого подхода к оценке их вычислительной сложности не представляется возможным объективно ранжировать известные алгоритмы как по вычислительной, так и по объемной сложности, что существенно затрудняет объективный выбор наиболее эффективных алгоритмов как по вычислительной, так и по объёмной их сложности. В то же время каждый из известных формальных методов преобразования ДНФ к полиномиальной форме ориентирован либо на бинарные преобразования, либо на векторные преобразования исходных данных, объем которых не менее 2" бит. Однако характерной особенностью цифровой вычислительной техники является ограниченная разрядность. Если учитывать данную особенность, то можно предположить, что для полиномиального преобразования БФ вычислительными средствами наиболее адекватны алго-

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

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

Тематика диссертационной работы соответствует одному из научных направлений ФГБОУ ВПО «Воронежский государственный технический университет» «Вычислительные комплексы и проблемно-ориентированные системы управления».

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

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

- разработка альтернативных дискретных алгоритмов преобразования БФ к полиному Жегалкина (положительно поляризованный полином Рида-Маллера);

- разработка альтернативных дискретных алгоритмов преобразования БФ к минимизированным поляризованным полиномам Рида - Маллера;

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

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

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

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

- альтернативные алгоритмы преобразования БФ к полиному Жегалкина, которые базируются на различных аналитических методах преобразования

(метод неопределенных коэффициентов; метод частных полиномиальных форм; метод на основе булева дифференциального исчисления; метод фрактального преобразования вектора значений БФ) и которые впервые с единых позиций ранжированы по вычислительной и объемной сложности;

- алгоритм бинарно-векторного полиномиального преобразования БФ к полиному Жегалкина, базирующийся на комбинации аналога метода на основе булева дифференциального исчисления и метода фрактального преобразования вектора значений БФ, отличающийся от известных минимальной вычислительной сложностью при реализации на ЭВМ с ограниченной разрядностью;

- алгоритм решения комбинаторной задачи формирования всех возможных N - разрядных двоичных кодовых комбинаций, в которых произвольные К - разрядов (К < имеют фиксированные значения, отличающийся от известных переборных алгоритмов целенаправленным последовательным формированием всех возможных N - разрядных комбинаций и обеспечивающий существенное уменьшение вычислительной сложности алгоритмов полиномиального преобразования БФ;

- алгоритм векторно — бинарного последовательного преобразования исходного полинома Жегалкина ко всем возможным поляризованным полиномам Рида-Малера, базирующийся на операции «смена ¡-полярности», которая частично выполняется над векторами из машинных слов, а частично - над машинными словами как битовыми объектами, отличающийся от известных минимальной вычислительной сложностью при реализации на ЭВМ с ограниченной разрядностью.

Результаты соответствуют следующим пунктам паспорта специальности:

- п. 2 «Развитие качественных и приближенных аналитических методов исследования математических моделей»;

- п. 3 «Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий»;

- п. 4 «Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента».

Практическая значимость работы. Разработан проблемно-ориентированный программный комплекс, обеспечивающий автоматическое преобразование БФ во все возможные полиномиальные формы Рида-Маллера, поиск минимальной полиномиальной формы и вывод её структурной формулы.

Полиномиальное преобразование БФ, зависящих от 15 или 16 переменных, осуществляется на ПЭВМ клона 1ВМ РС с тактовой частотой процессора 1,5...2 ГГц и объемом оперативной памяти 1 Гб за время, не превышающее 1 часа и 5 часов, соответственно.

Реализация и внедрение результатов работы. Результаты, полученные в диссертации, используются в Научно-исследовательском институте электронной техники (г. Воронеж), в ходе выполнения хоздоговорных НИР и в учебном процессе ФГБОУ ВПО «Воронежский государственный технический университет».

Апробация работы. Основные положения диссертационной работы докладывались на XVI Международной открытой научной конференции "Современные проблемы информатизации" (Воронеж, 2011), V Международной научно-практической конференции «Интеллектуальный потенциал молодых ученых России и зарубежья» (Москва, 2012), V Всероссийской научно-технической конференции МЭС-2012 "Проблемы разработки перспективных микро- и нано-электронных систем" (Москва, 2012) и в Международной молодежной научной школе «Теория и численные методы решения обратных и некорректных задач» (Воронеж, 2012).

Публикации. Основные результаты диссертации опубликованы в 15 научных работах, в том числе 6 - в изданиях, рекомендованных ВАК РФ. В работах, опубликованных в соавторстве и приведенных в конце автореферата, лично соискателем предложены: в [7] основные принципы программной реализации алгоритма восстановления совершенной дизъюнктивныой нормальной формы; в [2] - подходы к программной реализации алгоритма преобразования дизъюнктивных нормальных форм БФ в полином Жегалкина; в [1, 3] - алгоритмизация аналитических методов полиномиального преобразования БФ; в [5] - алгоритм бинарно-векторного разложения БФ и его обоснование; в [6] - формализация алгоритмов и расчетных соотношений; в [8] - анализ подходов к преобразованию булевых функций; [11,12]- разработка программных модулей; в [14] - разработка программного аналога асинхронного двоичного счетчика и экспериментальная диагностика изобретения; в [15] - оптимизация структуры логического преобразователя.

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения, списка литературы из 95 наименований. Основная часть работы изложена на 135 страницах, содержит 17 рисунков, 27 таблиц, приложения.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

В первой главе анализируются структурные и математические модели тестопригодных полиномиальных логических преобразователей, для практической реализации которых требуется представление исходных БФ в полиномиальных нормальных формах (ПНФ) - в виде полинома Жегалкина и в виде поляризованных полиномов Рида-Малера.

Проанализированы аналитические методы полиномиального преобразования БФ, из которых для дальнейших исследований выбраны: метод неопределенных коэффициентов; метод частных полиномиальных нормальных форм (ЧПНФ); метод на основе булева дифференциального исчисления; метод фрактального преобразования вектора значений БФ. Предложен оригинальный теоретический подход к оценке вычислительной сложности альтернативных алгоритмов преобразования булевых функций к полиному Жегалкина.

4

Суть данного подхода проиллюстрируем на примере преобразования БФ Р(хи,х2,х3) = (Ги,Г1,..Г7)к полиному Жегалкина С^х^х^^^^^на основе следующей системы уравнений, вытекающих из метода неопределенных коэффициентов, который, по сути, является дискретной моделью преобразования: ёо = & = ез^ОФ^Ф^ФГЗ; §4 = ^©^);

= ^ ©^©^ = g7=fo©flфf2©fз © f4©f5фf6©f7.

В табл. 1 рассматриваемая система уравнений представлена в графическом (табличном) виде, причем в каждом столбце таблицы перечислены значения БФ, сумма по модулю 2 которых определяет искомый коэффициент полинома Жегалкина. Анализ табл. 1 показывает, что для преобразования БФ в полиномиальную форму необходимо определить 2" коэффициентов .

Для определения каждого из этих коэффициентов максимально потребуется 2" коэффициентов Таким образом, наихудший из алгоритмов преобразования может обладать вычислительной сложностью 2".2П шагов алгоритма. В то же время, как следует из табл. 1, вычислительную сложность алгоритмов полиномиального преобразования можно уменьшить путём целеустремленного обхода только значащих клеток таблицы, то есть только тех, которые содержат значения булевой функции. Возможно также уменьшение вычислительной сложности алгоритмов за счет использования уже найденных выходных данных. Вместе с тем ясно, что с увеличением п экспоненциально увеличивается объем исходной таблицы. Преодоление данного негативного явления требует нахождения способов некоторой согласованной нумерации исходных и выходных данных, которая позволит последовательно вычислять номера всех требующихся для вычисления коэффициента gi (или наоборот). Таким образом, для теоретической оценки вычислительной сложности алгоритмов преобразования булевых функций к полиномиальным формам и ранжирования альтернативных алгоритмов по вычислительной сложности предложен подход, аналоги которого не представлены в доступной научно-технической литературе, базирующийся на геометрической (табличной) модели аналитического метода неопределенных коэффициентов, что позволяет находить соотношение для вычисления количества целенаправленных обходов значащих клеток таблицы, достаточных для определения логических значений всех коэффициентов полиномиальной формы.

Во второй главе разработаны семь альтернативных дискретных алгоритмов А1 - А7 полиномиального преобразования п-аргументных БФ к полиномам Жегалкина и получены оценки их вычислительной и объёмной сложности. Данные алгоритмы в диссертации представлены на языке логических схем (ЯЛС), который допускают эквивалентные преобразования алгоритмов и компактное их представление.

Таблица 1

Во Ш ё2 8з &4 85 Вб «7

(о А) <ь Го <ь 6

К и ^

(2 Г2 {2 {2

Гз Ь

и и {4

Ь

Гб

ь

Алгоритмы А1, А2, АЗ разработаны на основе метода неопределенных коэффициентов, обобщенная дискретная модель которого может быть представлена следующим соотношением, где К^ -элементарные конъюнкции максимального ранга:

р(х".....= Г,К(=§0®£8,.х,© (1)

1 = 1 1<1<^П

Анализ табл. 1 позволяет выявить следующую алгоритмическую закономерность: в определении значения компоненты % с определенным номером ¡, представленным двоичным кодом т^), участвуют только те компоненты £ номера которых .¡, представленные двоичными кодами б(^), содержат те же нулевые значения, что и двоичный код т^). Данная алгоритмическая закономерность формализована алгоритмом А1. Вычислительная сложность алгоритма А1 определяется величиной Б(А 1) = 22" '1 + 2"~'.

Вычислительная сложность алгоритма А2 уменьшена за счет найденного логико-арифметического преобразования кода индекса позволяющего непосредственно вычислять двоичный код номера следующего компонента вектора Б, участвующего в определении компонента Ц;. Таким образом, данное логико-арифметическое преобразование эквивалентно решению комбинаторной задачи последовательного формирования всех возможных N - разрядных двоичных кодовых комбинаций, в которых произвольные К - разрядов (К < N1) имеют фиксированные значения, что эквивалентно работе асинхронного двоичного счетчика с фиксированными разрядами, на который получен патент на изобретение. Вычислительная сложность алгоритма А2 имеет следующую оценку 8(А2) = 3".

Вычислительная сложность алгоритма АЗ уменьшена с помощью использования промежуточных результатов преобразования и логико-арифметических операций, аналогичных работе асинхронного счетчика с фиксированными значениями некоторых разрядов. Вычислительная сложность алгоритма АЗ оценивается величиной 8(АЗ) = 2x3""' +2" 1.

Алгоритм А4 реализован на основе метода частных полиномиальных нормальных форм (ЧПНФ), существо которого заключается в последовательном преобразовании каждого минтерма М, в ЧПНФ и на их основе - формирование окончательной ПНФ функции. Аналитически данное дискретное преобразование можно выразить следующим соотношением:

Р(х0,х|,...,хп|)=у2=л0"1 т. =маемье...емк =р(ма)эр(мь)®...ер(мк),(2)

где Р(Ма),Р(Мь),..,Р(Мк) - частные полиномиальные нормальные формы (ЧПНФ) минтермов булевой функции (эквивалентно формированию табл. I по строкам, причем все 1] заменяются на 1).

Достоинством метода ЧПНФ является то, что для преобразования может использоваться инверсная БФ с последующим инвертированием всех элементов вектора полинома. Отсюда следует, что максимальное количество ЧПНФ не

будет превосходить величины Я=2""', где п-количество аргументов БФ. Вычислительная сложность алгоритма А4 имеет оценку 8(А4)= 3" / 2.

В основу алгоритма А5 положен метод конечных разностей, который является аналогом дифференцирования БФ, то есть разложением булевой функции Р(х) в ряд Тейлора в точке с, определяемой любой элементарной конъюнкцией максимального ранга. При этом полиномиальную форму булевой функции находят в соответствии со следующим соотношением, использующим операции логического умножения (а) и суммы по модулю 2 (е ):

ар| ЭБI

Р(х>=Р(с)©(х|Фс,)— ©...©(х,,©^)— ©...Ф(х,Фс|)(х)Фс,)л дк, I йхк I

©......в(Ч-1Фск.1)(хк®ц.)л-:^-| ©... (3)

Ф^Фс,)...^©^)-^-.

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

8о=Го; ё, =д,' ; ..... В|=А/ ; •••• ё2», =А2°~\ (4)

где Л,' - первые разности ¡-го порядка.

Установлено, что алгоритм А5 тождественен известному алгоритму под названием «Треугольник Паскаля». Новым является установление того факта, что и алгоритм А5, и алгоритм «Треугольник Паскаля» за одну реализацию алгоритма формируют две противоположно поляризованные полиномиальные формы исходной БФ.

Алгоритм А6 полиномиального разложения БФ реализует известный метод разложения БФ функции, учитывающий фрактальность преобразований упорядоченных компонент вектора её значений. В зарубежной литературе такой же метод называют «позитивное разложение Давио». Геометрическая интерпретация данного метода для функции трех аргументов представлена табл. 2, построенной на основе табл. 1, учитывая свойство коммутативности логической функции сумма по модулю 2.

На основании данных табл. 2 становится объяснимым предлагаемое название данного метода как «метод фрактальных преобразований», если учесть тот факт, что разложение булевой функции последовательно производится на основе самоподобных треугольных структур с катетами 2*2; 4*4; ...2""' * 2""'. Вычислительная сложность алгоритма А6 оценивается как 5(А6) = п*2п"' .

На основе комбинации аналога метода на основе булева дифференциального исчисления и метода фрактального преобразования БФ, разработан алго-

Таблица 2

Во 81 82 83 84 85 86 87

Л Ъ и и {?

То Ь и и

и и и

Го и

л {2 п

С2

А) и

Го

ритм А7 бинарно-векторного полиномиального преобразования БФ к полиному Жегалкина, отличающийся от известных минимальной вычислительной сложностью при реализации на ЭВМ с ограниченной разрядностью т. Вычислительная сложность алгоритма А7 уменьшается с увеличением разрядности ин-

2"

струментальной ЭВМ и имеет оценку Б(А7)= (т-1)—^^п-^т^1"44"*"" при

т

т<2".

На рис. 1 представлен алгоритм А7 бинарно-векторного разложения булевой функции.

По окончанию алгоритма из подвекторов А0, Аь ..., Ак, ..., А^ формируется вектор в, содержащий коэффициенты полинома Жегалкина в (Хо, х ь •■•,Хп.|)=(£о,§1,§2, ... Ёт-1,Ет ••• &П-0 ■

Исходя из полученных в работе оценок 5(А1), ..., 8(А7) впервые с единых позиций ранжированы по вычислительной и объемной сложности алгоритмы А1-А7 преобразования БФ к полиному Жегалкина и показано, что алгоритм А7 бинарно-векторного полиномиального преобразования БФ, базирующийся на комбинации аналога метода на основе булева дифференциального исчисления и метода фрактального преобразования вектора значений БФ, отличается от известных минимальной вычислительной сложностью при реализации на ЭВМ с ограниченной разрядностью.

В третьей главе разработаны альтернативные дискретные алгоритмы преобразования БФ к минимизированным поляризованным полиномам Рида -Маллера, которые в общем виде могут быть представлены следующим образом:

С(х0,...,х1| |;Р(р0,...рп г))= х ...х =а0Ф где х| - аргументы логической

N ' '* '' функции; р(р0,...,р|1_|)- вектор

©1а,-х.е X а -х(-х Ф...Фа -х -...-х поляризации; а, е {0,1} (5)

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

Преобразование БФ к поляризованному полиному возможно по двум схемам:

БЫ: поляризация БФ—»преобразование к поляризованному полиному (О );

БЬ2: преобразование к полиному Жегалкина (Сж) —> преобразование к поляризованному полиному (Ср).

Если использовать схему 8Ы, то для получения поляризованного полинома в' может быть применен любой из разработанных в главе 2 алгоритмов А1...А7 и дополнительный алгоритм для предварительной поляризации БФ.

Если БФ задана двоичными значениями минтермов (М;) и задан двоичный вектор поляризации (Р), то двоичное значение поляризованного минтерма находится как М,р= М, © I1. С учетом данного обстоятельства на основе ранее разработанного алгоритма А4 и с минимальными его доработками разработан алгоритм А8, обеспечивающий преобразование БФ к поляризованному полиному С1. На рис. 3 представлена схема алгоритма А8 преобразования БФ к поляризованному

полиному на основе метода ЧПНФ. Рис- 2- Обобщенный

алгоритм

Нет

Вектора поляризации исчерпаны?^

Да

Вывод полинома с минимальным числом конъюнкций

В алгоритме А8 по сравнению с алгоритмом А4 введены всего две дополнительных операции: в п. 3 - ввод вектора поляризации Р(р0,...рп-|); в п. 7 -модификация ]:= с31 © Р номера (кода) .¡-го минтерма в соответствии с заданным вектором поляризации. Вычислительная сложность алгоритма А8 будет иметь практически такую же оценку, как и для алгоритма А4, то есть 8(А8) я 3"/2.

Если БФ исходно задана упорядоченным вектором своих значений ^ (хо'х:> •••'х„.1) = (^о ' >•■■■» ^ >—), то для её поляризации следует переупорядочить значения следующим образом: Р (хо> х:< •■•' Хп-| ) = (^офр> ••"»

С

14

1 Нет

3

Рис. 3. Схема алгоритма А8 преобразования БФ к поляризованному полиному на основе ЧПНФ

Для поляризации вектора значений БФ потребуется простейший алгоритм А9, однако его вычислительная сложность составит $(А9)=2". После поляризации вектора значений БФ целесообразно использовать для дальнейшего преобразования алгоритмы А6 или А7, обладающие наименьшей вычислительной сложностью. По схеме 8Ы разработаны алгоритмы А10, А12, А13 преобразования БФ к минимизированным поляризованным полиномам.

Преобразование БФ к поляризованному полиному возможно и по схеме 8Ь2, используя для этого известную векторную операцию «смена ¡-полярности». Суть данной операции хорошо иллюстрируется графической моделью, представленной на рис. 4.

еъ к р—-

V J --

Рис. 4. Графическая интерпретация операции «смена i-полярности»

Операция «смена i-полярности» имеет такое же графическое представление, как и известное «негативное разложение Давно», которое можно рассматривать как бинарную операцию «смена i-полярности». По схеме Sh2 разработаны и оптимизированы алгоритмы формирования минимизированных поляризованных полиномов А14, А15, А16.

Алгоритмы А14 и Al5 разработаны на основе последовательной поляризации исходного полинома Жегалкина с помощью операции «смена i-полярности». Особенностью данной операции является невозможность одновременной поляризации предшествующего полинома по нескольким переменным. По этой причине последовательная поляризация возможна только при упорядоченной смене двоичных векторов поляризации, которые должны формироваться в виде последовательности кодов Грея.

Разработанный дискретный алгоритм А16 векторно-бинарного последовательного формирования поляризованных полиномов RM, базируется на векторной и бинарной операции «смена i-полярности» и ориентирован на реализацию средствами вычислительной техники с ограниченной разрядностью. При этом векторная операция «смена i-полярности» реализуется над битами слов ограниченной разрядности, а бинарная операция «смена i-полярности» - над словами. Следовательно, алгоритм векторно - бинарного последовательного преобразования исходного полинома Жегалкина ко всем возможным поляризованным полиномам Рида-Малера, базирующийся на операции «смена i-полярности», которая частично выполняется над векторами из машинных слов, а частично - над машинными словами, как битовыми объектами, отличается от

известных минимальной вычислительной сложностью при реализации на ЭВМ с ограниченной разрядностью.

В табл. 3 представлены сводные данные по разработанным дискретным алгоритмам А10, А12, А13, А14...А16, характеризующие их индивидуальную вычислительную и объемную сложности.

Таблица 3

А| Исходные данные Вычислительная и объемная сложность

Р м С* Ы(А,)

А10 + +

А12 + — — =((2" + п2"-' + 2"))х2" 3*2"

А13 + ^и =((2" +(/я-1)—+ (и-1(^2 т)2"~Ыо8'"" + 2"))х2" т 3*2"

А14 — + 5ц = 5д„ + ((2" + 2"~2 )(2" -1) 3*2"

А15 + в,, =(/я-1)— + (и-1о82от)2'м-|08=" +(2" +2"-'))х(2" -1) т 3*2"

А16 + ( 3 г Ц=) ^ 8 £ + (1 - к)(2" - 1Ь""|_,ое'" + (2" -1) х 2" т V / |1, при 1 < ^,(т/2) [О, при1 > 1о£,(ш/2) 3*2"

В табл. 3 обозначено: п - количество входных переменных (аргументов) булевой функции Р; 5(А;) - вычислительная сложность алгоритма А;; Ы(А|) - объемная сложность (слов или бит) для алгоритма А;; Б - вектор упорядоченных значений исходной булевой функции; М - набор значений минтермов исходной булевой функции; в* -вектор упорядоченных значений коэффициентов полинома Жегалкина; т - разрядность ЭВМ.

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

На основе цели и результатов диссертационного исследования сформулированы основные требования к проблемно-ориентированному программному комплексу и предложена его функциональная схема, представленная на рис. 5.

Разработанный программный комплекс базируется на алгоритме А4 (алгоритм формирования полинома Жегалкина на основе метода частных полиномиальных форм) и алгоритме А10 (алгоритм минимизации полиномиальной

формы путём предварительной поляризации минтермов БФ). Выбор данных алгоритмов обусловлен тем, что проведение теоретических исследований и разработка необходимых программных модулей велась параллельно во времени. Найденные перспективные алгоритмы А7 и А16 будут использованы в дальнейших разработках при модернизации программного комплекса.

Рис. 5. Функциональная схема проблемно-ориентированного программного

комплекса

По представленной на рис. 5 схеме в среде С++Вш1с1ег разработаны и комплексированы программные модули для автоматического формирования ПНФ БФ. Главное окно программного комплекса представлено на рис. 6. Программный комплекс обеспечивает автоматическое формирование минимизированной структурной формулы поляризованного полинома не только на основе СДНФ или таблицы истинности БФ, но и на основе ДНФ с их предварительным восстановлением до совершенных форм при минимальных требованиях к ресурсу инструментальной ЭВМ.

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

переменных. Для экспериментов были выбраны БФ, количество минтермов которых равно количеству макстермов. Эксперименты проводились на ПЭВМ клона IBM PC с процессором AMD Athlon(tm)XP 1800+, тактовая частота 1,54 ГГц. Объем оперативной памяти 768 Мб. Хронометраж осуществлялся секундомером. В табл. 4 знаком обозначены прогнозные значения параметров, определенные экстраполяцией графической зависимости функции Tog t, представленной на рис. 7. Прогнозные значения времени минимизации находятся путём определения на графике соответствующей величины Log t с последующим её антилогарифмированием.

Ввод функции__

|5~ | сероед«^. j

виэд&лышй мжтро!*- весомой t

4x1 д2лЗ.»«.*5>-~х2-~х5 - »1 H2*x3~x5 * ~кЗ—¡Л—¡6 - ~*1 » ~х1 —хЗ * ~х2—х4"~х5 - ~х2 • "х5

I» ДНЧ> j Просмотр в СДНФ | Просмотр «к^киии в ПНФ [

ж СДНФ I Вектор ко

Рис. 6. Главное окно проблемно-ориентированного программного комплекса

Таблица 4

параметры n

10* И 12 13 14 15' 16* 17* 18 19 20*

t 1.0 сек 3.67 сек 19.0 сек 108,3 сек 640 сек 47 мин 4.5 час 22 часа 5 сут 24 сут 4 мес

Logt 0.03 0.56 1.27 2.03 2.81 3.45 4.2 4.9 5.6 6.3 7.0

Рис. 7. График зависимости времени минимизации поляризованных полиномов Рида-Малера от количества п аргументов БФ

Для подтверждения корректности аналитических оценок и эффективности предложенных в работе алгоритмов была разработана специальная программа "Статистическая оценка быстродействия программ полиномиального преобразования булевых функций". Данная программа предназначена для сравнения быстродействия программных модулей Р1-Р7, реализующих альтернативные алгоритмы AI-A7 соответственно.

Натурные эксперименты производились на ПЭВМ клона IBM PC с процессором AMD Athlon(tm)XP 1800+, тактовая частота 1,54 ГГц. Объем оперативной памяти 768 Мб.

На рис. 8 представлены графики расчетной вычислительной сложности алгоритмов А1-А7, а на рис. 9 - графики временной сложности программных модулей Р1-Р7 при осуществлении преобразования случайно генерируемой БФ в полином Жегалкина соответствующими алгоритмами А1-А7.

log S(P¡ )

Рис. 8. Графики вычислительной Рис. 9. Графики временной сложности сложности алгоритмов А1-А7 программных модулей Р1-Р7

Анализ и сопоставление графиков на рис. 8 и 9 позволяет сделать следующие выводы.

Предложенный в данной работе теоретический подход к оценке вычислительной сложности альтернативных алгоритмов преобразования булевых функций к полиному Жегалкина, корректен и пригоден для практического использования, так как ранжирование по временной сложности разработанных программных модулей Р1-Р7 соответствует ранжированию по вычислительной сложности алгоритмов А1-А7.

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

Предложенный в данной работе алгоритм бинарно-векторного полиномиального преобразования БФ к полиному Жегалкина по вычислительной сложности предельно близок к минимальной вычислительной сложности полиномиального преобразования БФ одной инструментальной ЭВМ, которая равна 2" (график которой выделен на рис. 7 тонкой линией).

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

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

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

3. Разработан алгоритм бинарно-векторного полиномиального преобразования БФ к полиному Жегалкина, базирующийся на комбинации аналога метода на основе булева дифференциального исчисления и метода фрактального преобразования вектора значений БФ, отличающийся от известных минимальной вычислительной сложностью при реализации на ЭВМ с ограниченной разрядностью.

4. Обобщен алгоритм решения комбинаторной задачи формирования всех возможных N - разрядных двоичных кодовых комбинаций, в которых произвольные К - разрядов (К < Ы) имеют фиксированные значения, отличающийся от известных переборных алгоритмов целенаправленным последовательным формированием всех возможных N - разрядных комбинаций и обеспечивающий существенное уменьшение вычислительной сложности алгоритмов полиномиального преобразования БФ.

5. Разработан алгоритм векторно - бинарного последовательного преобразования исходного полинома Жегалкина ко всем возможным поляризованным полиномам Рида-Малера, базирующийся на операции «смена ¡-полярности», которая частично выполняется над векторами из машинных слов, а частично -над машинными словами как битовыми объектами, отличающийся от известных минимальной вычислительной сложностью при реализации на ЭВМ с ограниченной разрядностью.

6. Разработан проблемно-ориентированный программный комплекс, обеспечивающий автоматическое преобразование БФ во все возможные полиномиальные формы Рида-Маллера, поиск минимальной полиномиальной формы и вывод её структурной формулы. Полиномиальное преобразование БФ, зависящих от 15 или 16 переменных, осуществляется на ПЭВМ клона IBM PC с тактовой частотой процессора 1,5...2 ГГц и объемом оперативной памяти 1 Гб за время, не превышающее 1 часа и 5 часов, соответственно.

Основные результаты диссертации опубликованы в следующих работах:

Публикации в изданиях, рекомендованных ВАК РФ

1. Акинин, А. А. Автоматизация полиномиального разложения булевых функций на основе метода неопределенных коэффициентов [Текст] / А. А. Акинин, Ю. С. Акинина, С. Л. Подвальный, С. В. Тюрин // Системы управления и информационные технологии. - 2011. - № 2 (44). - С. 4-8.

2. Акинин, А. А. Программный модуль преобразования дизъюнктивных нормальных форм булевой функции в полином Жегалкина [Текст]/ А. А. Акинин, С. Л. Подвальный // Вестник Воронежского государственного университета.-2011. - Т. 7. - №4. - С. 183-186.

3. Акинин, А. А. Автоматизация полиномиального разложения булевых функций на основе метода конечных разностей [Текст] / А. А. Акинин, Ю. С. Акинина, С. В. Тюрин // Системы управления и информационные технологии. -2011. - №4.- С. 69-73.

4. Акинин, А. А. Алгоритм фрактального полиномиального разложения булевых функций [Текст] / А. А. Акинин // Вестник Воронежского государственного технического университета.-2011.-Т. 7.-№11. 1,- С. 85-88

5. Акинин, А. А. Метод бинарно-векторного полиномиального разложения булевых функций [Текст]/ А. А. Акинин., Ю. С. Акинина, С. В. Тюрин // V Всероссийская научно-техническая конференция «Проблемы разработки перспективных микро- и наноэлектронных систем 2012» : сборник трудов. Москва, ИППМ РАН, -2012.-С. 55-60.

6. Акинин, А. А. Сравнительная оценка вычислительных алгоритмов полиномиального преобразования булевых функций [Текст]/ А. А. Акинин, С. Л. Подвальный // Вестник Воронежского государственного университета. - 2013. -Т. 9,-№1,-С. 31-35.

Статьи и материалы конференций

7. Акинин, А. А. О программной реализации алгоритма восстановления совершенной дизъюнктивной нормальной формы [Текст]/ А. А. Акинин, Ю. С. Акинина // Информационные технологии моделирования и управления. - 2010, - №6(65). - С.726-731.

8. Акинин, А. А. Общие подходы к преобразованию булевых функций в поляризованные полиномы Рида-Маллера [Текст] / А. А. Акинин, Ю. С. Акинина, С. Л. Подвальный // Новые технологии в научных исследованиях, проек-

17

тировании, управлении, производстве: труды Всероссийской конференции. Воронеж, ВГТУ, -2013 г. - С. 48 - 49.

9. Акинин, А. А. Оптимизация алгоритма полиномиального преобразования булевых функций [Текст]/ А. А. Акинин // Современные проблемы информатизации в анализе и синтезе программных и телекоммуникационных систем: сборник трудов. Воронеж.-2012.-Вып. 17. -С. 256-257.

10. Акинин, А. А. Автоматизация полиномиального разложения булевых функций методом фрактальных преобразований [Текст] / А. А. Акинин // V Международная научно-практическая конференция «Интеллектуальный потенциал молодых ученых России и зарубежья» (10.05.2012): материалы. М. : Издательство «Спутник+». - 2012. С. 9 - 18.

11. Акинин, А. А. Программа "Статистическая оценка быстродействия программ полиномиального преобразования булевых функций " / А. А. Акинин, Ю. С. Акинина, С. В. Тюрин // Свидетельство о государственной регистрации программы для ЭВМ № 2012614544 от 21 мая 2012г.

12. Акинин, А. А. Программа "Преобразователь булевых функций" / А. А. Акинин, Ю. С, Акинина, С. В. Тюрин // Свидетельство о государственной регистрации программы для ЭВМ № 2012614544 от 21 мая 2012 г.

13. Акинин, А. А. Вычислительная сложность оптимизированных алгоритмов полиномиального преобразования булевых функций [Текст] / А. А. Акинин // Международная молодежная научная школа «Теория и численные методы решения обратных и некорректных задач»: материалы. Воронеж: ИПЦ «Научная книга», - 2012. - С. 58-62.

14. Акинин, А. А. Пат. 2452084 Российская Федерация, МПК7 - H ОЗК 023/40. Асинхронный двоичный счётчик [Текст] / Акинин A.A., Тюрин C.B.; заявитель и патентообладатель Воронеж, гос. техн. университет. - № 2009148255; заявл. 24.12.2009; опубл. 27.05.2012; Бюл. № 15.

15. Акинин, А. А. Способ тестопригодной реализации логических преобразователей / А. А. Акинин, Ю. С. Акинина, С. Л. Подвальный, С. В. Тюрин // Заявка на изобретение RUS 2011123026/08 от 07.06.2011; опубл. 20.12.2012, Бюл. № 35. Решение о выдаче патента от 24.04.2013.

Подписано в печать 24.10.2013 Формат 60x84/16. Бумага для множительных аппаратов. Усл. печ. л. 1,0. Тираж 80 экз. Заказ № ¿(¡в

ФГБОУ ВПО «Воронежский государственный технический университет» 394026 Воронеж, Московский просп., 14

Воронежский государственный технический университет

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

04201364809

АКИНИН Андрей Александрович

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

Специальности: 05.13.18- Математическое моделирование,

численные методы и комплексы программ

ДИССЕРТАЦИЯ на соискание ученой степени кандидата технических наук

Научный руководитель д-р техн. наук, проф. Подвальный С.Л.

Воронеж -2013

СОДЕРЖАНИЕ

ВВЕДЕНИЕ................................................................................... 5

1 РАЗРАБОТКА МЕТОДИКИ СРАВНИТЕЛЬНОЙ ОЦЕНКИ ЭФФЕКТИВНОСТИ ДИСКРЕТНЫХ АЛГОРИТМОВ ПОЛИНОМИАЛЬНОГО ПРЕОБРАЗОВАНИЯ БУЛЕВЫХ ФУНКЦИЙ.....

1.1 Структурные и математические модели тестопригодных

14

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

1.2 Особенности аналитических методов полиномиального

23

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

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

Цель работы и задачи исследования........................................... 35

2 РАЗРАБОТКА АЛЬТЕРНАТИВНЫХ ДИСКРЕТНЫХ АЛГОРИТМОВ ^ ПРЕОБРАЗОВАНИЯ БУЛЕВЫХ ФУНКЦИЙ К ПОЛИНОМУ ЖЕГАЛКИНА..............................................................................

2.1 Алгоритмы преобразо вания нл основе метода неопределенных

37

коэффициентов.............................................................................

2.2 Алгоритм п эеобразования на основе частных полиномиальных нормальных форм.........................................................................

2.3. Алгоритм преобразования на основе метода конечных разностей .. 52

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

2.5 Алгоритм бинарно-векторного разложения булевых функций...... 64

Выводы

69

3 РАЗРАБОТКА АЛЬТЕРНАТИВНЫХ ДИСКРЕТНЫХ АЛГОРИТМОВ ПРЕОБРАЗОВАНИЯ БУЛЕВЫХ ФУНКЦИЙ К 72 МИНИМИЗИРОВАННЫМ ПОЛЯРИЗОВАННЫМ ПОЛИНОМАМ РИДА-МАЛЛЕРА..................................................................................

3.1 Общие подходы к преобразованию булевых функций в

72

поляризованные полиномы Рида-Маллера..........................................

3.2 Алгоритмы преобразования к поляризованным полиномам на

76

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

3.3 Алгоритмы преобразования к поляризованным полиномам на

80

основе поляризации полинома Жегалкина...........................................

Выводы............................................................................... 91

4 РАЗРАБОТКА И ВЕРИФИКАЦИЯ ПРОБЛЕМНО-ОРИЕНТИРОВАННОГО ПРОГРАММОЮ КОМПЛЕКСА

93

МИНИМИЗАЦИИ БУЛЕВЫХ ФУНКЦИЙ В КЛАССЕ ПОЛИНОМИАЛЬНЫХ НОРМАЛЬНЫХ ФОРМ С ФИКСИРОВАННОЙ ПОЛЯРНОСТЬЮ................................................................................................

4.1 Разработка структуры и интерфейса программного комплекса....... 93

4.2 Разработка программного модуля восстановления дизъюнктивной нормальной формы булевой функции до совершенной формы..................

4.3 Разработка программного модуля минимизации поляризованных полиномов Рида-Маллера......................................... 106

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

Выводы..............................................................................................................................................................120

ЗАКЛЮЧЕНИЕ......................................................................................................................................................122

УСЛОВНЫЕ ОБОЗНАЧЕНИЯ................................................................................................................124

СПИСОК ЛИТЕРАТУРЫ............................................................................................................................125

ПРИЛОЖЕНИЯ......................................................................................................................................................136

ВВЕДЕНИЕ

Актуальности темы. Представление булевых функций (БФ) в полиномиальных нормальных формах с фиксированной полярностью в последние двадцать лет получает всё более широкое распространение, так как имеет самые разнообразные приложения: спектральная обработка сигналов [1,2]; по-мехозащищенная передача информации [3]; моделирование обратимых логических структур [4,5] и квантовых процессоров [6]; реверсивная логика [7] многоальтернативное и многоверсионное проектирование [8,9]; декомпозиция булевых функций [10]; тестопригодная реализация логических преобразователей на матричных структурах [11-16] и т.п.

Весьма перспективно применение полиномиальных формы БФ для проектирования комбинационных автоматов, приспособленных к тестопри-годному проектированию (Design For Testability или DFT) и встроенному самотестированию (Built - In - Self - Test или BIST). Широкое практическое использование методов DFT и BIST как на уровне электронной компонентной базы, так и на уровне радиоэлектронных средств и систем позволяет сократить сроки разработки систем, затраты на их верификацию в процессе производства и проверку работоспособности в процессе эксплуатации [1722]. Уникальное свойство тестопригодности полиномиальных логических преобразователей (ГШП), заключается в том, что для их структурного тестирования используются тестовые векторы с унифицированной битовой структурой, не зависящей от реализуемой логической функции. При этом для обнаружения любой одиночной константной неисправности достаточное и необходимое количество тестовых векторов не превосходит величины 2п, где п - количество аргументов булевой функции (БФ). Данное обстоятельство при широком практическом использовании ПЛП существенно упрощает решение задач синтеза и оценки качества контрольных и диагностических тестов для цифровой техники. Отличительным свойством полиномиальных логических преобразователей является так же и в то, что представление булевой функции в виде полинома Жегалкина может быть короче её представ-

ления в виде минимальной дизъюнктивной нормальной формы [23], а среди поляризованных полиномов Рида-Маллера могут быть найдены формы в 1.5 раза короче, чем полином Жегалкина [24].

Полиномиальные логические преобразователи могут быть эффективно реализованы как б специализированных больших интегральных схемах (ASIC - Application Specific Integrated Circuit), так и в программируемых логических интегральных схемах типов CPLD и FPGA.

Большой вклад в теоретические и практические разработки по формированию и использованию полиномиальных нормальных форм БФ внесли Жегалкин И.И., Reed L.S., Muller D.E., Reddy S.M., A.E.A. Almaini, D.H. Green, T. Sasao, B.J. Falkowski, M.J. Davio, M. Perkowski, G. Papakonstantinou, H.A. Перязев, В.П. Супрун, А.Д. Закревский, Н.Р. Торопов, В.Д. Малюгин, B.C. Выхованец и многие другие.

Теоретический интерес к полиномиальным формам булевых функций (БФ) обусловлен тем, что нахождение полиномиальной формы БФ относят к NP-трудным задачам [25], в связи с чем асимптотические вычислительная (О) и объемная (V) сложности алгоритмов полиномиального преобразования БФ имеют оценку порядка 0(2П) и V(2n), где п - количество аргументов преобразуемой БФ. Асимптотические оценки вычислительной и объемной сложности характеризуют весь класс [26] алгоритмов полиномиального преобразования БФ, подчеркивая то, что любой алгоритм из данного класса не может быть реализован быстрее, чем за 2" шагов алгоритма, при этом потребуется более чем 2" бит (слов) памяти. Таким образом, теоретический интерес состоит в отыскании наилучших алгоритмов полиномиального преобразования БФ, ориентированных на практическую реализацию средствами вычислительной техники (программными или аппаратурными). Так как преобразования БФ к полиномиальной форме относится к NP-трудным задачам, то преобразование БФ, зависящих более чем от 5...6 аргументов, возможно только с использованием специализированных объектно-ориентированных

программных комплексов, которые в настоящее время отсутствуют у отечественных инженеров - схемотехников.

Анализ даже ограниченного количества доступных работ (печатных и из Интернет-ресурсов) [27-58] показывает, что существует множество алгоритмов полиномиального преобразования БФ, которые разрабатывались и оптимизировались в течение довольно длительного промежутка времени (около тридцати лет). Зачастую, проводилось сравнение не вычислительной сложности алгоритмов, а временной сложности программ, реализующих альтернативные алгоритмы. В свою очередь время выполнения любой программы зависит и от языка программирования, и от быстродействия средств вычислительной техники, которое за тридцатилетний промежуток времени существенно изменилось. Поэтому в настоящее время не представляется возможным объективно ранжировать известные алгоритмы как по вычислительной, так и по объемной сложности, что существенно затрудняет объективный выбор наиболее эффективных. В то же время, проведенный анализ показывает, что каждый из известных формальных методов преобразования ДНФ к полиномиальной форме ориентирован либо на бинарные преобразования, либо на векторные преобразования исходных данных, объем которых не менее 2" бит. Однако характерной особенностью цифровой вычислительной техники является ограниченная разрядность. Если учитывать данную особенность, то естественно предположить, что для полиномиального преобразования БФ вычислительными средствами наиболее адекватны алгоритмы и программы, рациональным образом сочетающие векторные преобразования над данными, объем которых равен разрядности вычислительных средств, и бинарные преобразования над неделимыми машинными словами.

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

Тематика диссертационной работы соответствует одному из научных направлений Воронежского государственного технического университета «Вычислительные комплексы и проблемно-ориентированные системы управления».

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

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

- разработка альтернативных дискретных алгоритмов преобразования БФ к полиному Жегалкина (положительно поляризованный полином Рида-Маллера);

- разработка альтернативных дискретных алгоритмов преобразования БФ к минимизированным поляризованным полиномам Рида - Маллера;

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

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

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

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

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

- альтернативные алгоритмы преобразования БФ к полиному Жегал-кина, которые базируются на различных аналитических методах преобразования (метод неопределенных коэффициентов; метод частных полиномиальных форм; метод на основе булева дифференциального исчисления; метод фрактального преобразования вектора значений БФ) и которые впервые с единых позиций ранжированы по вычислительной и объемной сложности;

- алгоритм бинарно-векторного полиномиального преобразования БФ к полиному Жегалкина, базирующийся на комбинации аналога метода на основе булева дифференциального исчисления и метода фрактального преобразования вектора значений БФ, отличающийся от известных минимальной вычислительной сложностью при реализации на ЭВМ с ограниченной разрядностью;

- алгоритм решения комбинаторной задачи формирования всех возможных N - разрядных двоичных кодовых комбинаций, в которых произвольные К - разрядов (К < 14) имеют фиксированные значения, отличающийся от известных переборных алгоритмов целенаправленным последовательным формированием всех возможных N - разрядных комбинаций и обеспечивающий существенное уменьшение вычислительной сложности алгоритмов полиномиального преобразования БФ;

- алгоритм векторно - бинарного последовательного преобразования исходного полинома Жегалкина ко всем возможным поляризованным полиномам Рида-Малера, базирующийся на операции «смена ¡-полярности», которая частично выполняется над векторами из машинных слов, а частично -над машинными словами, как битовыми объектами, отличающийся от из-

вестных минимальной вычислительной сложностью при реализации на ЭВМ с ограниченной разрядностью.

Результаты соответствуют следующим пунктам паспорта специальности:

- п. 2 «Развитие качественных и приближенных аналитических методов исследования математических моделей»;

- п. 3 «Разработка, обоснование и тестирование эффективных вычислительных методов с применением современных компьютерных технологий».

- п. 4 «Реализация эффективных численных методов и алгоритмов в виде комплексов проблемно-ориентированных программ для проведения вычислительного эксперимента».

Практическая значимость работы. Разработан проблемно-ориентированный программный комплекс, обеспечивающий автоматическое преобразование Б<1 во все возможные полиномиальные формы Рида-Маллера, поиск минимальной полиномиальной формы и вывод её структурной формулы.

Полиномиальное преобразование БФ, зависящих от 15 или 16 переменных, осуществляется на ПЭВМ клона 1ВМ РС с тактовой частотой процессора 1,5...2 ГГц и объемом оперативной памяти 1 Гб за время, не превышающее 1 часа и 5 часов, соответственно.

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

Апробация работы. Основные положения диссертационной работы докладывались на Шестнадцатой Международной открытой научной конференции "Современные проблемы информатизации" (Воронеж, 2011 г.) , V Международной научно-практической конференции «Интеллектуальный по-

тенциал молодых ученых России и зарубежья» (Москва, изд-во «Спутник+», 2012 г.), V Всероссийской научно-технической конференции МЭС-2012 "Проблемы разработки перспективных микро- и наноэлектронных систем" (Москва, ИППМ РАН, 2012) и в Международной молодежной научной школе «Теория и численные методы решения обратных и некорректных задач» (Воронеж, ВИВТ, 2012 г.).

Публикации. Основные результаты диссертации опубликованы в 15 печатных работах, в том числе 6 - в изданиях, рекомендованных ВАК РФ. В работах, опубликованных в соавторстве, лично соискателем предложены: в [7] основные принципы программной реализации алгоритма восстановления совершенной дизъюнктивныой нормальной формы; в [2] - подходы к программной реализации алгоритма преобразования дизъюнктивных нормальных форм БФ в полином Жегалкина; в [1,3]- алгоритмизация аналитических методов полиномиального преобразования БФ; в [5] - алгоритм бинарно-векторного разложения БФ и его обоснование; в [6] - формализация алгоритмов и расчетных соотношений; в [8] - анализ подходов к преобразованию булевых функций; [11, 12] - разработка программных модулей; в [14] -разработка программного аналога асинхронного двоичного счетчика и экспериментальная диагностика изобретения; в [15] - оптимизация структуры логического преобразователя.

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

Содержание работы.

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