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

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

КОЛПАКОВ Антон Валериевич

МЕТОДЫ И АЛГОРИТМЫ ЛИНЕЙНЫХ И АФФИННЫХ ПРЕОБРАЗОВАНИЙ ДЛЯ МОДЕЛИ БИНАРНЫХ ДИАГРАММ РЕШЕНИЙ

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

АВТОРЕФЕРАТ диссертации на соискание ученой степени кандидата технических на™

Казань 2004

Работа выполнена в Казанском государственном университете им.В.И.Ульянова-Ленина

Научный руководитбль доктор технических наук, профессор

Латыпов Рустам Хафизович

Официальные оппоненты доктор технических наук, профессор

Захаров Вячеслав Михайлович кандидат физико-математических наук, доцент Нурмеев Наиль Нуреевич

Ведущая организация Институт проблем информатики при

академии наук РТ

Защита состоится 2004 года часов на заседании

диссертационного совета Д 212.079.01 в Казанском государственном техническом университете им.А.Н.Туполева по адресу: 420111, Казань, К.Маркса 10, зал заседаний ученого совета.

С диссертацией можно ознакомиться в библиотеке Казанского государственного технического университета им. А.Н.Туполева.

Автореферат разослан С? Y. 2004 г.

Ученый секретарь диссертационного совета, доктор физ-мат. наук, профессор г/^^^ П. Г. Данилаев

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ Актуальность проблемы:

Все возрастающая сложность задач, решаемых современной вычислительной техникой, требует поиска новых подходов для ускорения вычислений. Информация становится главным ресурсом научно-технического и социально-экономического развития мирового сообщества, предъявляя все большие требования к вычислительным системам. Обработка информации требует больших вычислительных затрат. Уменьшение размера схем может привести к значительному ускорению процесса вычислений, а также экономии элементов, необходимых для построения схем. Минимизация бинарных диаграмм решений (БДР или Я0В013 в англоязычной литературе), которые легко переносятся в транзисторную логику, на практике означает минимизацию размера схем. БДР являются одной из моделей представления булевых функций в виде направленного нецикличного графа и имеют связь с топологией реальных схем. Бинарные диаграммы решений являются эффективным способом манипуляции большими структурами ' данных с целью их оптимизации, верификации и вычисления различных характеристик.

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

(схема)

Функция/'-К

VI-V

Модель в виде бинарной диаграммы решений_

У

Реализация

Рис. 1. Схема связи функции, модели БДР и реализации

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

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

по сложности возможностям вычислительной техники для их эффективного использования. Поэтому производятся поиски эвристических алгоритмов для сокращения размера бинарных диаграмм решений, которые дают приемлемые по критерию соотношения сложности к эффективности результаты. В связи с этим актуальной задачей является построение таких эвристических алгоритмов. Преобразования над входящими переменными интересны тем, что преобразования в результате производятся не над таблицей функции, а только над входящими переменными. При этом преобразование является линейным и задается матрицей размером пхп, вместо матриц размерности 2"х2", которыми описываются преобразования над таблицей функции, где и- число входящих переменных. Идея линейного преобразования входных переменных в задаче минимизации схем заключается в том, что вычисление исходной выходной функции разбивается на два этапа. Сначала производится линейное преобразование переменных, после чего вместо исходной выходной функции схема вычисляет «измененную» функцию, чтобы получить «правильное»

выходное значение. Таким образом f(xl,...,xtl) = ¿(/(х„...,х„)).

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

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

Бинарные диаграммы решений были использованы разработчиками CAD (САПР СБИС) для построения схем для ПЛИСов (работы "Legl С., Wurth В., Eckl R. A Boolean approach to performance-directed technology mapping for lut-based fpga designs / Design Automation Conference 1996, pp 74-116", "Chang S.C., Marek-Sadovska M. and Hwang T.T. 1996, Technology mapping for tlu fpga's based on binary decision diagrams/ Proc. IEEE Trans. Computer Aided Des. Integrated Circuits & Syst.,1226-1236", "H. Sawada, T. Suyama, A. Nagova. 1995. Logic synthesis for look-up table based fpgas using functional decomposition and support minimization/ In Pore. Int. Conf. Computer Aided Design, pp. 54-59", "Y.Lai, T. Pedram, S. Vrudhula.1993. Bdd based decomposition of logic functions with application to fpga synthesis. In Proc. Design Automation Conf., pp 74-116", "J.-H. Jiang, J.-Y Jout, J.-D. Huang, J.-S. Wei. 1997, A variable portioning algorithm of bdd for fpga technologuy mapping. IEEE. Trans. Fundamentals E80-Ad, 10 (October), 1813-1819") в основном на стадии логической декомпозиции функций.

Декомпозиция функций, основанная на бинарных диаграммах решений, называется BDS, что расшифровывается как BDD-based Decomposition System (C.Yang. 2000. BDD-based logic synthesis system. Ph. D. Thesis, Univ. Of Massachusetts, Amherst). Также показано, что этот подход может эффективно использоваться как для алгебраических, так и для булевых (а также AND-OR и AND-XOR) декомпозиций. При этом используются бинарные диаграммы решений для представления и маципуляций булевыми функциями и выполнения логической декомпозиции.

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

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

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

• Разработка критериев, обеспечивающих сокращение размера бинарных диаграмм решений.

• Разработка алгоритмов на базе полученных критериев.

• Экспериментальная проверка влияния алгоритмов на размер бинарных диаграмм решений.

• Обоснование верхней оценки для сложности алгоритма.

в Исследование возможностей улучшения критериев и алгоритмов для получения лучших результатов. Научная новизна:

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

• Предложен новый подход к сокращению размера бинарных диаграмм решений.

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

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

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

• Создан комплекс программ, реализующий. разработанные критерии и алгоритмы.

« Найдена верхняя оценка для числа шагов алгоритма. Практическая ценность и реализация результатов работы:

В диссертации построены новые алгоритмы для минимизации размера бинарных диаграмм решений (БДР), Показано, что можно уменьшить размер бинарной диаграммы решений путем приведения булевой функции к виду, удовлетворяющему некоторому критерию, используя линейные и аффинные преобразования над входными переменными. В ходе построения результирующего преобразования используются преобразования только над соседними переменными, что уменьшает число шагов алгоритма. Разработанные алгоритмы можно использовать для выделения подклассов базовых функций, с помощью которых можно задать любую другую булеву функцию, зависящую от соответствующего количества входящих переменных. Разработан комплекс программ для реализации алгоритмов, работающий под операционной системой Windows с использованием средства разработки Microsoft Visual С++. Разработанный программный комплекс используется в учебном процессе на факультете ВМК при выполнении курсовых и дипломных работ студентов. Результаты также использованы при моделировании цифровых систем в Институте проблем информатики Академии наук Татарстана и в кампании Сканер. Имеются соответствующие справки о внедрении. Работа поддержана грантом № 05-5.2-234 из средств Фонда НИОКР Татарстана. Апробация:

Основные положения диссертационной работы докладывались и

обсуждались:

1. Fifth International Workshop on Applications if Reed-Muller Expansions in Circuit Design, August 10-11,2001, Misissipi State University.

2. Четвертая международная конференция «Автоматизация проектирования дискретных схем» 14-16 ноября 2001г., Минск.

3. XXVIII International conference (Information Technologies in Science, Education, Telecommunication, Business, autumn session) IT+SE'2001, Yalta, Ukraina, 2001.

4. XIII Международная конференция «Проблемы теоретической кибернетики» Казань, 27-31 мая 2002 г.

5. На семинарах на кафедрах прикладной математики КГУ, теоретической кибернетики КГУ, компьютерных систем и информационной безопасности КГТУ им. Туполева.

Публикации:

По теме диссертации опубликованы 5 работ, из них 4 статьи и 1 тезисы. Список работ приведен в конце автореферата. Структура и объем работы:

Диссертационная работа состоит из введения, четырех глав, заключения и приложения, изложенных на 139 страницах, содержит 26 рисунков, 1 таблицу, 'I список литературы из 102 наименований.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении обосновывается актуальность темы диссертационной работы, дается ее краткая характеристика, формируется цель, определяются задачи и формулировки результатов, выносимые на защиту.

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

Ориентированный граф, не содержащий циклов, называется бинарной диаграммой решений (рис. 2), если

® Есть одна или две оконечные вершины с полустепеныо исхода равной нулю, которые обозначены 0 или 1.

® Есть множество узлов, обозначенных переменными с полустепенью исхода 2. Две исходящие вершины представляются двумя функциями low и high. На рисунках дуги к ним обозначаются пунктиром и сплошной линией соответственно.

• Порядок следования переменных сохраняется при любом из путей от начальной вершины к оконечной (упорядоченность).

® Является сокращенным - то есть однозначным и неизбыточным. При этом под однозначностью понимается, что нет двух различных узлов, обозначенных одной переменной, у которых выходы указывают на одинаковые функции low и high. А под неизбыточностью - нет узлов у которых low функция тождественно равна high. * Для сокращения размера в смысле количества узлов применяются линейные и

аффинные преобразования:

Линейное преобразование L:V-*V переводит вектор X в вектор Y, так

что:

Ух = 2Х*<

Л=2>»Л

Рис. 2. Бинарная диаграмма решений (ВОБ) для функции (х, о х2)л(х3 о *4) и порядка переменных х, < х2 < х3 < хл

Аффинное преобразование Ь: V" V" переводит вектор X в вектор У, так

что:

»

Ух =2>1л+61

1=1

п

Уп = 1Чл+ьп

; а„е{0,1}Л6{0,1}

ГО

Для записи в матричном виде Ь, представляется в виде вектора В= ...

А/

Тогда преобразование записывается в виде У = АХ + В,

при этом матрица А, задающая линейное преобразование, является невырожденной, то есть:

При этом преобразование затрагивает только входящие переменные (рис. 3).

I

X

/:

Г

Рис. 3. Иллюстрация преобразования переменных и изменения функции.

Для получения исходного результата:

-1

Вход

Г

Выход

Рис. 4. Схема получения исходной функции из преобразованной

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

Проблема использования алгоритмов с различными переборами заключается в огромном количестве вариантов преобразований,

л-1

Всего линейных преобразований от п переменных возможно 1~[(2"-2')>

(=0

п-1

а количество аффинных 2" *]~|(2Я-2'). Эти числа очень велики, и поэтому

1т О

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

Рассмотрим разложение Шенона функции по двум переменным:

/ — xlXJ2fx¡=0 ^=0 V V =1>,уВ,

В формуле используются значения четырех подфункций. Число возможных перестановок этих значений: 4!= 24. Рассмотрим число возможных аффинных преобразований над двумя элементами:

2" -1\(2" -2') =4(4-1)(4-2)=24.

1-0

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

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

Для задания преобразований над соседними переменными используются матрицы:

"1 . 01

В,"

1

где А„ находится в строке », ; = {1,1}

В,

Р 0 1

', / = 1,.., п -1, размерность этой матрицы (и +1) х (л +1).

д =

О

, размерность этой матрицы (и + 1)х(м+1). Единица

справа

располагается в строке /. При умножении на эту матрицу происходит отрицание переменной с номером г.

А~ =

V

результирующая матрица для аффинных

ч0 ...... О 1

преобразований, представляет из себя матрицу А линейных преобразований, расширенную справа столбцом, задающим отрицание.

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

Теорема 2.1. Произведением матриц В, можно получить матрицу линейного преобразования А для задания любого невырожденного линейного преобразования.

Теорема 2.2. Произведением матриц В~и £>, можно получить матрицу аффинного преобразования А~.

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

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

В третьей главе Разработаны критерии и алгоритмы минимизации БДР.

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

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

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

Определение Весом ветви м<(/) будем называть количество результирующих единиц в поддереве /.

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

Рассмотрим дерево до второго уровня (рис. 5). Так как зона воздействия только одна, то упорядочиваются 4 поддерева по их весу, для этого переставляются элементы на уровне 2 с помощью преобразований над элементами уровней 0 и 1 (это преобразования над переменными и х2).

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

уровня Ь.

На следующем уровне уже 2 зоны синхронного воздействия при использовании преобразований над переменными предыдущих двух уровней (х2их3). Рассмотрим веса 8-ми исходящих поддеревьев (рис. 6) обозначенные как /' = 0,1,2,3, / = 0,1. Тогда при преобразовании, приводящем к перестановке и>от и и>10, также будут переставлены и 1С,,.Такое свойство будет выполняться для любого уровня, начиная со 2-го, и таких четверок на уровне Ь будет 21.

Рис. 6. Демонстрация идеи метода

Каждому элементу уровня £ бинарного дерева соответствует пара элементов на следующем уровне. То есть, для обеспечения возможности дальнейшей максимизации удельного веса данного уровня, необходимо изменить веса этих пар друг относительно друга на уровне ¿ + 1. Соответственно это перераспределит веса соответствующих им элементов на уровне I. Так как одной четверке уровня Ь соответствует две четверки уровня ¿ + 1 и два из вариантов не имеют принципиального значения, то вариантов изменения разницы весов становится 2: - + - + или - + + - (рис. 6).

Рассмотрим общий случай: Допустим, есть некоторая БДР, построенная для ¿+1 входящих элементов. Рассмотрим уже упомянутые преобразования для переменных х,и Эти преобразования синхронно воздействуют аналогичным образом на оконечные четверки элементов.

Так как одной четверке уровня Ь соответствуют две четверки уровня ¿+1, то для обеспечения возможности увеличения разницы весов левой и правой частей этой четверки необходимо максимально увеличить разницу весов элементов в левых и правых парах. Л это достигается работой с четверками уровня 1 + 1. Рассмотрение большего числа элементов на уровне Ь +1, чем 8, также бессмысленно потому, что для уровня Ь максимизируются ячейки по 4 элемента (т.к. приоритетной является схема - + - + и т.д., а схема -

+ + - необходима в связи с ограниченной зоной действия преобразований -блоками из четырех значений, расположенных в одном поддереве).

Получаем алгоритм (А1):

1) Ь-1, N = 2. Упорядочиваем (переставляем) функции таким образом, чтобы м>(/0) < < №(/г) 5 н(/3).

2) £=£+1, N=2^. Максимизируем' величину

ЛГ/2-1

~ ^(/21) ~ м'(/з/) I, переставляя подмножества

/-0

(Уоо > • ■ • Уо.Л//2-1 )> (Уоо»-"Уо, ЛГ/2-1 )> С/20»* *" У2.Л//2-1С/зО >"• ./з,ЛГ/2-1) • ЕСЛИ

перестановка прошла успешно (максимизируемое значение изменилось), то возвращаемся на уровень назад.

3) Цикл заканчивается, если I равно количеству уровней в дереве, иначе возвращаемся к пункту 2.

Так как приведенный алгоритм является приближенным, то для компенсации случаев его неудачной работы применяется также алгоритм двухуровнего перебора (А2):

Производится перебор с использованием преобразований только над соседними переменными.

1) Ь = 1, N = 2, Минимизируем количество узлов в двоичной диаграмме, переставляя функции /0,/,/г,/3-

2) ¿ = 1 + 1, И = 2Ы, Минимизируем количество узлов в двоичной диаграмме, переставляя подмножества (/оа>"-/о,ы/г-\)> (/оа>'-'/о.м/2-1)' /г,н/г-\)> (/з<х>"'А,ып-1) • Если перестановка прошла успешно (количество узлов уменьшилось), то возвращаемся на уровень назад.

3) Цикл заканчивается, если I равно количеству уровней в дереве, иначе возвращаемся к пункту 2.

В дополнение был опробован алгоритм выявления симметрии (АЗ);

1) ¿ = 1, 5 = 0,N = 2. Выявляем симметрию в е°ли есть пара равных значений, то перестановками приводим к виду: ХХУУ или ХХУг, или YZXX. Если получились 2 пары (случай (ХХУУ)) , то фиксируем первый уровень, установив 5 = 1. Это означает, что первый уровень больше не преобразовывается.

2) Ь = Ь+\,Ы ~2Ы. Аналогично рассматриваем подмножества

С/оо>■ • *Уо^/2-1 (/оо>-"/о,ЛГ/2-1)' С/20»•••/г.ЛГ/2-1)» С/зо»'"/3,^/2-1)' Если есть поэлементно равные подмножества, перестановками подмножеств приходим к виду: ХХУУ или ХХУг, или YZXX. Если получились 2 пары (случай (ХХУУ)), то:

Если 5 £ £ -1, то возвращаемся на уровень назад. Иначе фиксируем первые уровни, установив 5 = 1. Иначе если пришлось переставлять подмножества, то возвращаемся на уровень назад.

3) Цикл заканчивается, если Ь равно количеству уровней в дереве, иначе

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

Я = | количество элементов 1 - количество элементов 0 | Рассмотрим задание функции в виде двоичного набора длины N = 2". Пусть количество единиц в наборе равно и,, а количество нулевых элементов в наборе равно и„, N = и, + и0, тогда Я = |и,-и0| = (Д^-2и0|.

Однородность уровня Ь будет выражена формулой: 2е"'-1

Яд = X I ^л " 2и0, | , где л0, - количество нулей в соответствующей

/»о

подфункции, а = 2"'1*1 - ее размерность. Соответственно, однородность функции выражается формулой:

Яг=2А.

/.-о

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

1) ¿ = 1, N = 2. Упорядочиваем (переставляем) функции /0,/1,/2,/э таким образом, чтобы Ч/0) ^ м<(/;) ^ Ц/г) 2 и'(/3).

2) ¿ = ¿ + 1, N-2И, Максимизируем величину Яд, переставляя подмножества

(/<» > • • • fo.NI2-1 )> (Ло > • • ■ /<>,N/2-1 )> (/20 > • • • /2,N/2-1 ), (/зо."-Лаг/м), Если

перестановка прошла успешно (максимизируемое значение изменилось), то возвращаемся на уровень назад.

3) Цикл заканчивается, если £ равно количеству уровней в дереве, иначе возвращаемся к пункту 2.

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

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

Пусть Я - число успешных преобразований.

Таблица. Результаты тестирования алгоритма по тестам 1Л38упИ1 93. В скобках показаны результаты, полученные с использованием метода однородности, если они отличались. __

Схема Bx од В ы xo Исход ный размер Размер в результате, узлов Размер с учетом изоморфности выходов** Время работы в секундах

д 9 узлов* Исходный размер Размер в результа те

Bw 5 28 253 170(158) 114 82(66) 1.60

С17 5 2 12 11 10 11 0.11

Rd53 5 3 29 15 23 15(14) 0.17

Xor5 5 1 9 1 9 1 0.07

9sym 9 \ 33 38(24) 33 38(24) 0.59

Conl 7 2 18 15(16) 18 15(14) 0.18

Inc 7 9 115 96(100) 85 81(78) 0.72

Sqrt8 8 4 43 45(41) 42 44 0.61

Ex5p 8 63 793 672(639) 356 322(280) 9.80

Misexl 8 7 75 60(58) 47 41(45) 1.04

Apex4 9 19 1610 1563(1585) 1021 1034 13.41

Clip 9 5 280 112(127) 254 97(87) 3.47

Sao2 10 4 182 103(108) 154 91(88) 11.11

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

** - обозначено, что диаграммы с несколькими выходами разделяют изоморфные подграфы (методы при этом работают как и при *).

Доказаны следующие теоремы:

Теорема 4.1. Значение однородности некоторого уровня Ъ не может

измениться при преобразованиях другого уровня.

Теорема4.2. £<;#£(«-1)2"

Число шагов алгоритма однородности, М:

М = где N = 2".

Теоремы 4.1 и 4.2 позволили обосновать конечность числа шагов алгоритма однородности и получить верхнюю оценку числа шагов.

Рис. 7. Результаты, полученные при тестировании алгоритмов.

В таблице приводятся экспериментальные результаты работы алгоритмов по тестам И38упЙ1 93. На рис. 7 приводятся результаты совместного использования алгоритмов, полученные на всех возможных значениях функций, зависящих от 3 и 4 переменных и на случайных функциях, зависящих от 5 переменных и более. Кроме того, в этой главе рассматриваются пути возможных дальнейших исследований и способы улучшения работы алгоритмов.

В приложении приведены исходные тесты разработанного комплекса программных средств.

Основные результаты работы:

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

1 минимизации. Установлено, что существующие методы представления

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

2. Предложена модель сокращения размера БДР с помощью линейных и аффинных преобразований входящих переменных.

3. Предложена модель и исследовано влияние линейных и аффинных преобразований на поддеревья в бинарном дереве и выделены базисные преобразования.

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

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

6. Доказано теорема о том что алгоритм однородности конечен и отрабатывает за число шагов не более чем О(ЛПодЛ'), где N = 2" - размер таблицы истинности функции.

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

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

1. Kolpakov A.V., Latypov R.Kh. Minimization of BDD using linear transformation of variables // Fifth International Workshop on Applications if Reed-Muller Expansions in Circuit Design, August 10-11, 2001, Misissipi State University, P.57-65

2. Колпаков A.B., Латыпов P.X. Бинарные диаграммы и линейные преобразования переменных // Четвертая международная конференция «Автоматизация проектирования дискретных схем» 14-16 ноября 2001г., Минск, т. 2, С. 116-121.

3. Kolpakov A.V., Latypov R.Kh. Fast minimizations algorithms for BDD's // XXVIII International conference (Information Technologies in Science, Education, Telecommunication, Business, autumn session) IT+SE'2001, Yalta, Ukraina, 2001, P.22-24.

4. Колпаков A.B., Латыпов P.X. Минимизация BDD с помощью линейных преобразований переменных // XIII Международная Конференция «Проблемы теоретической кибернетики» Казань, 27-31 мая 2002, C.9I.

5. Колпаков А.В., Латыпов Р.Х. Приближенные алгоритмы минимизации двоичных диаграмм решений на основе линейных преобразований переменных // Автоматика и телемеханика. №6. 2004, С. 112-128.

РНБ Русский фонд

2007-4

14913

Лицензия на полиграфическую деятельность №0128 от 08.06.9Sr. выдана Министерством информации и печати Республики Татарстан Подписано в печать 29.04.2004 г. Форм. бум. 60x84 1/16. Печ. л.1. Тираж 120. Заказ 111.

Минитипография института проблем информатики АН РТ 420012, Казань, ул.Чехова, 36. ^

Введение.

1 Глава 1. Базовые понятия и определения.

1.1 Необходимые определения.

1.2 Линейные и аффинные преобразования.

1.3 Модели компактного представления бинарного дерева - виды диаграмм.

1.4 Бинарные диаграммы решений - формальный подход.

1.5 Бинарные диаграммы решений с разделением общих частей для функций с несколькими выходами.

1.6 Минимизация не полностью заданных функций.

1.7 Выводы.

2 Глава 2. Линейные и аффинные преобразования переменных и обоснование алгоритмов.

2.1 Проблема сокращения размера бинарных диаграмм с помощью линейных и аффинных преобразований.

2.2 Линейные и аффинные преобразования переменных и сокращение размера бинарных диаграмм решений.

2.3 Матричное задание линейных и аффинных преобразований.

2.4 Теорема 2.1.

2.5 Теорема 2.2.

2.6 Анализ влияния линейных и аффинных преобразований над соседними переменными на бинарное дерево.

2.7 Идея алгоритма сокращения размера БДР.

2.8 Выводы.

3 Глава 3. Построение алгоритмов.

3.1 Построение алгоритма.

3.2 Алгоритм упорядочения дерева

3.3 Модифицированный алгоритм (А1).

3.4 Метод двухуровнего перебора (А2).

3.5 Алгоритм выявления симметрии (A3).

3.6 Алгоритм однородности (А4).

3.7 Выводы.

4 Глава 4. Теоремы и экспериментальные оценки эффективности алгоритмов.

4.1 Число шагов алгоритма однородности.

4.2 Пример сокращения БДР функции XOR5 алгоритмом А4.

4.3 Экспериментальная оценка уменьшения бинарных диаграмм.

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

4.5 Функции с несколькими выходами.

4.1 Описание программного комплекса.

4.2 Выводы.

Состояние проблемы:

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

Интерес к диаграммам решений возрос после публикации [1], причем как к оригинальным диаграммам решений для функций-триггеров, где большинство исследователей ссылались на [2] и [3], так и для функций с несколькими выходами на [4]. ДР стали структурой данных, полученной сокращением деревьев решений (бинарных деревьев), с помощью использования общих изоморфных поддеревьев и удаления избыточной информации из деревьев решений для данной функции. Бинарные деревья были впервые представлены в диссертации [5] о некоторых проблемах в теории дискретных множеств, защищенной в 1935 году в Сорбонне. Разложение Шеннона имеет вид: / = vxjx-,, (1 </'<«)•

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

Пунктиром обозначается нулевое значение переменной, а сплошной линией — единичное. На каждом уровне присутствует только одна переменная, по которой и выполняется разложение функции (рисунок 1).

• • ■

Рис. 1. Бинарное дерево

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

Рис. 2. Удаление изоморфности из бинарного дерева.

Если после отождествления изоморфностей сократить узлы, которые указывают на один узел (таким образом, как показано на рисунке 3),

Рис. 3. Сокращение узлов, оба выхода которых указывают на один и тот же узел. в результате получится бинарная диаграмма решений (БДР).

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

Основной недостаток приложений, базирующихся на бинарных диаграммах решений, - это то, что структуры данных являются зависимыми от порядка переменных, а также что для некоторых функций не существует эффективного представления, например для булевских ^ умножений. Для решения проблемы оптимального порядка переменных были написаны специальные алгоритмы, частично сокращающие перебор полного множества вариантов. Для решения проблемы представления умножения и для повышения общей компактности были предложены несколько расширений базовой структуры двоичных диаграмм решений -например диаграммы с подавлением нуля (ZBDD)[89]. При этом продолжается также поиск других путей сокращения размера бинарных диаграмм решений. Линейные преобразования были очень обнадеживающей концепцией, так как непосредственно структуры данных остаются неизменными, а изменяются (перекодируются) только входные переменные, причем для сохранения результирующих значений изменяется и сама функция. Также следует отметить, что даже такая значительно более простая задача, как нахождение оптимального порядка переменных, является NP-полной [12]. В случае с линейными преобразованиями ситуация осложняется тем, что количество вариантов линейных преобразований по сравнению с перестановками входящих переменных существенно больше. В работе «Линейные преобразования и точная минимизация BDD» Wolfgang Gunter и Rolf Drechsler (1998) [7] применили расширение метода перестановок (permutations) линейными преобразованиями и получили более хорошие результаты минимизации бинарных диаграмм решений. Однако, несмотря на высокую эффективность, алгоритм имеет очень большую сложность. Идея заключается в том, чтобы найти такое линейное преобразование, при котором сложность реализации преобразования и видоизмененной функции будет меньше, чем исходной. Тогда для нахождения оптимального линейного преобразования вместо преобразований над таблицей функции, что обычно и делается в спектральных методах, преобразуются только входные переменные.

То есть если рассмотреть исходный вектор переменных X, линейное преобразование Z, то в результате получим схему преобразования, показанную на рисунке 4. s L

X ) Y

Рис. 4. Иллюстрация преобразования переменных и изменения функции.

Таким образом, имеем: АХ = Y, где Y- это преобразованный вектор переменных, а А - матрица, задающая линейное преобразование L. Если исходная функция была /, то формула f\Y) = A(f(X)) будет задавать измененную функцию.

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

Смысл минимизации линейными преобразованиями заключается в поиске наименьшего или приемлемого по размеру (в смысле количества узлов) в бинарной диаграмме решений преобразованной функции по сравнению с исходной БДР. Для получения исходной функции из преобразованной применяется схема, показанная на рисунке 5.

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

Рис. 5. Схема получения исходной функции из преобразованной.

Этот подход к минимизации интересен простой реализацией результатов вычислений: достаточно преобразовать входящие переменные умножением на матрицу размерности пхп и получается значительно упрощенная схема. Но NP-полнота точных алгоритмов и огромное п-1 количество вариантов ]~[(2Л-2') [7] линейных преобразований позволяет 0 осуществлять линейное преобразование для получения минимально возможной функции (точную оптимизацию) только на функциях с очень небольшим количеством переменных. Поэтому в настоящее время производятся поиски различных эвристических алгоритмов, которые давали бы вполне приемлемые результаты, но имели бы значительно меньшие требования как по времени вычислений, так и по другим требуемым ресурсам.

Для преодоления проблем, связанных с большой размерностью БДР при реализации булевских умножений, и для более компактного представления функций были предложены расширения структуры БДР. Этой области посвящено достаточно много современных работ. Расширениями БДР(ЕЮО) являются KDD (Kronecker Decision Diagrams)

6], PKDD (Pseudo-Kronecker Decision Diagrams) [6], ZBDD[89]. Различия заключаются в следующем:

В бинарной диаграмме на каждом узле применяется разложение Шеннона. При этом кроме объединения изоморфных ветвей применяется удаление узла, если его исходящие ветви указывают на один узел. Другие виды диаграмм решений. используют различные комбинации типа разложения и метода сокращения «вырожденных» узлов, как например, ZBDD (Zero suppressed Binary Decision Diagram - Бинарные диаграммы решений с подавлением нуля). В ZBDD - вместо удаления вершины, у которой исходящие ветви указывают на один узел, применяется удаление узлов, если единичный выход указывает на 0. Этот метод в общем случае хуже, чем в бинарной диаграмме решений (BDD), но значительно лучше в некоторых специальных случаях, например при реализации булевских умножений.

Диаграммы решений Кронекера (KDD) являются расширением BDD путем использования разложений positive Davio Expansion и Negative Davio Expansion. В этом случае на каждом уровне применяется либо разложение Шеннона, либо Davio Expansion, либо Negative Davio Expansion.

Псевдо-Кронекеровские диаграммы решений (PKDD) - расширение KDD, но в этом случае на одном уровне можно использовать разложения positive Davio Expansion и Negative Davio Expansion, либо разложение Шеннона.

В работе [6] описываются преимущества PKDD над BDD, но при этом опять возникает проблема построения оптимального PKDD. Процесс построения оптимальной псевдо-кронекеровской диаграммы решений сам по себе является процессом оптимизации и для этого требуются большие вычислительные ресурсы. Поэтому при построении PKDD также применяются эвристические алгоритмы. При этом по проведенным исследованиям на случайных функциях от 15 переменных, размер PKDD составляет около 65% от базовой функции.

В работе [7] описан метод точной минимизации BDD, с использованием линейных преобразований над входящими переменными. Метод является расширением линейными преобразованиями метода перестановок, и имеет сложность N1, где N = 2" - количество значений функции. Значение N1 является слишком большой величиной, и поэтому применение метода возможно только для функций от небольшого количества переменных (не более 6).

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

Актуальность проблемы:

Бинарные диаграммы решений (БДР или ROBDD в англоязычной литературе) являются одной из моделей представления булевых функций в виде направленного нецикличного графа и имеют связь с топологией реальных схем.

На практике бинарные диаграммы решений можно реализовать с помощью элементарных мультиплексоров, то есть БДР напрямую отображается в архитектуру аппаратных средства, например программируемые логические устройства и используется на стадии синтеза таких устройств (рисунок 6).

Функция (схема) /-к

-V

Модель в виде бинарной диаграммы решений л V

Л У

Реализация

Рис. 6. Схема связи функции, модели БДР и реализации

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

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

Необходимость в исследованиях, направленных на поиск алгоритмов для сокращения размера БДР, обусловлена отсутствием приемлемых по сложности точных методов для нахождения минимально возможной диаграммы. Это связано с тем, что точные алгоритмы для нахождения минимальной диаграммы, известные на сегодняшний день, использующие различные фиксированные классы преобразований, очень близки к полному перебору и не удовлетворяют по сложности возможностям вычислительной техники для их эффективного использования. Поэтому производятся поиски эвристических алгоритмов для сокращения размера бинарных диаграмм решений, которые дают приемлемые по критерию соотношения сложности к эффективности результаты. В связи с этим актуальной задачей является построение таких эвристических алгоритмов. Преобразования над входящими переменными интересны тем, что преобразования в результате производятся не над таблицей функции, а только над входящими переменными. При этом преобразование является линейным и задается матрицей размером пхп, вместо матриц размерности 2" х2"5 которыми описываются преобразования над таблицей функции, где п- число входящих переменных. Идея линейного преобразования входных переменных в задаче уменьшения размера схем заключается в том, что вычисление исходной выходной функции разбивается на два этапа. Сначала производится линейное преобразование переменных, после чего вместо исходной выходной функции схема вычисляет «измененную» функцию, чтобы получить «правильное» выходное значение. Таким образом /(*„.,*„) = z(/(x„.,*„)).

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

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

Бинарные диаграммы решений были использованы разработчиками CAD (САПР СБИС) при построении схем для ПЛИСов в основном на стадии логической декомпозиции функций. Сейчас декомпозиция функций, основанная на бинарных диаграммах решений, называется BDS — что расшифровывается как BDD-based Decomposition System [33]. Также показано, что этот подход может эффективно использоваться как для алгебраических, так и для булевых (а также AND-OR и AND-XOR) декомпозиций. При этом используются бинарные диаграммы решений для представления и манипуляций булевыми функциями и выполнения логической декомпозиции.

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

Теперь рассмотрим некоторые статьи, имеющие отношение к преобразованию бинарных диаграмм решений с целью уменьшения их размера. Эта задача является актуальной, так как размер БДР непосредственно влияет на размер схем, например при построении ПЛИС.

В статье [12] «Использование нижних оценок в процессе динамической минимизации бинарных диаграмм» приводится описание метода нижних оценок для упрощения при оптимизации размера бинарных диаграмм путем поиска оптимального преобразования. В статье приводится сложность поиска оптимальной последовательности переменных. Она составляет 0(п2*3"), где п — количество входящих переменных. Применение этого метода в среднем на 50% сокращает время поиска оптимального результата. Но с точки зрения сложности 0(3") является очень большой величиной, также следует учитывать, что в данном виде оптимизации применяются только перестановки переменных, без линейных преобразований. Этот критерий может быть использован только для сокращения перебора. Если рассматривать оптимизацию как приведение функции к определенному виду, данный метод не подходит.

В работе [7] «Линейные преобразования и точная минимизация BDD» представлен алгоритм нахождения оптимального линейного преобразования переменных булевой функции для минимизации соответствующей двоичной диаграммы решений. В результатах показано, что бинарные диаграммы могут быть существенно сокращены при использовании линейных преобразований. Так как перестановка входит в подмножество линейных преобразований, то их применение для минимизации бинарных диаграмм увеличивает возможности. Всего п—\ линейных преобразований J~[(2" -2'), что меньше чем 2й!, но существенно i-0 больше, чем и! (количества перестановок переменных). При этом используется разложение конечного преобразования на более простые, или это можно рассматривать как произведение более простых матриц, каждая из которых соответствует простому преобразованию. Из-за большой сложности вычислений данный алгоритм подходит только для функций, имеющих не более 6 входящих переменных.

В работе [20] "Диаграммы решений в синтезе. Алгоритмы, расширения и приложения" дан обзор различным видам диаграмм решений. Наиболее популярными являются бинарные диаграммы решений. Но они имеют ряд недостатков, один из которых - это экспоненциальный размер относительно некоторых функций, например умножителей. Поэтому для решения данной проблемы применяются некоторые другие виды диаграмм решений. В работе описаны различные типы применяемых разложений и редукций, и в зависимости от этого получается определенный тип диаграммы решений. Кроме этого, описываются различные методы минимизации для диаграмм решений, а также понятие World level DD и смешанных диаграмм решений.

Генетический алгоритм для получения оптимального порядка переменных" [22] - представлен алгоритм нахождения оптимального порядка переменных для минимизации бинарных диаграмм решений. Это альтернатива точному алгоритму нахождения оптимального порядка переменных. При аналогичных результатах с точным алгоритмом на приведенных тестах он позволяет сократить время поиска в среднем на 50%. Но подход к минимизации двоичных диаграмм решений путем поиска оптимального порядка переменных уже достаточно хорошо изучен и из-за меньшего количества вариантов дает менее хорошие результаты, чем использование линейных преобразований.

EXOR преобразования входящих переменных, для разработки эффективных двухуровневых AND/EXOR сумматоров" [40]. В работе показано результатами и доказано, что сумматоры, которые имеют экспоненциальное представление в виде бинарных диаграмм, можно после линейных преобразований представить в виде бинарных диаграмм, сложностью 0(пг).

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

В работе S. Minato [89] представлены бинарные диаграммы решений с подавлением нуля (ZBDD), которые были разработаны как альтернатива классическим двоичным диаграммам решений для случаев, когда бинарные диаграммы оказываются неэффективными. Отличаются от БДР методом применяемой редукции. В бинарных диаграммах узел удаляется, если оба его выхода указывают на одну вершину, а для ZBDD — если единичная ветвь указывает на 0.

Минимизация бинарных диаграмм, используя линейные преобразования, основываясь на эволюционной технике"[18] Алгоритм работает следующим образом:

1. Случайно выбираются две переменные и одна из них заменяется на их сумму по модулю два.

2. Повторение пункта 1 дважды

3. Перестановка двух переменных.

4. Линейный сдвиг

5. Инверсия: в случайно выбранном окне из 8-ми переменных инвертировать порядок переменных в окне.

6. Удаление линейного преобразования переменных

7. Точная минимизация: выбор трех переменных и нахождение оптимального линейного преобразования с использованием точного алгоритма.

Согласно тестам, алгоритм показывает неплохие результаты за приемлемое время. Но остается подход упрощенного перебора.

Представление неполностью заданных функций, используя диаграммы решений Псевдо-Кроннекера» [6]. В этой статье дается определение BDD (бинарных диаграмм решений), KDD и PKDD. В PKDD в узлах применяется одно из 3 разложений (S,pD,nD (Формулы 1.1-1.3)). Всего вариантов для задания PKDD З2""1 и, выбирая для каждого узла одно из разложений, можно упростить PKDD. В статье рассмотрен эвристический алгоритм для минимизации PKDD для неполностью заданных функций. Метод заключается в минимизации функции, последовательно используется сначала неполное задание функции, затем производится минимизация построением KDD, затем PKDD.

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

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

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

• Разработка критериев, обеспечивающих сокращение размера бинарных диаграмм решений.

• Разработка алгоритмов на базе полученных критериев.

• Экспериментальная проверка влияния алгоритмов на размер бинарных диаграмм решений.

• Обоснование верхней оценки для сложности алгоритма.

• Исследование возможностей улучшения критериев и алгоритмов для получения лучших результатов.

Научная новизна:

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

• Предложен новый подход к сокращению размера бинарных диаграмм решений.

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

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

• Создан комплекс программ, реализующий разработанные критерии и алгоритмы.

• Найдена верхняя оценка для числа шагов алгоритма. Практическая ценность и реализация результатов работы:

В диссертации построены новые алгоритмы для сокращения размера бинарных диаграмм решений (БДР). Показано, что можно уменьшить размер бинарной диаграммы решений путем приведения булевой функции к виду, удовлетворяющему некоторому критерию, используя линейные и аффинные преобразования над входными переменными. В ходе построения результирующего преобразования используются преобразования только над соседними переменными, что уменьшает число шагов алгоритма. Разработанные алгоритмы можно использовать для выделения подклассов базовых функций, с помощью которых можно задать любую другую булеву функцию, зависящую от соответствующего количества входящих переменных. Разработан комплекс программ для реализации алгоритмов, работающий под операционной системой Windows с использованием средства разработки Microsoft Visual С++. Разработанный программный комплекс используется в учебном процессе на факультете ВМК КГУ при выполнении курсовых и дипломных работ студентов. Результаты также использованы при моделировании цифровых систем в Институте проблем информатики Академии наук Татарстана и в предприятии Сканер. Имеются соответствующие справки о внедрении. . Работа поддержана грантом № 05-5.2-234 из средств Фонда НИОКР Татарстана. Апробация:

Основные положения диссертационной работы докладывались и обсуждались:

1. Fifth International Workshop on Applications if Reed-Muller Expansions in Circuit Design, August 10-11., Mississippi State University.- 2001.

2. Четвертая международная конференция «Автоматизация проектирования дискретных схем», 14-16 ноября, Минск.- 2001.

3. XXVIII International conference (Information Technologies in Science, Education, Telecommunication, Business, autumn session) IT+SE'2001, Yalta, Ukraina.- 2001.

4. XIII Международная Конференция «Проблемы теоретической кибернетики» Казань, 27-31 мая.- 2002.

5. На семинарах на кафедрах прикладной математики КГУ, теоретической кибернетики КГУ, компьютерных систем и информационной безопасности КГТУ им. Туполева.

Публикации:

По теме диссертации опубликованы 5 работ, из них 4 статьи и 1 тезисы. Работы приведены в списке литературы. Структура и объем работы:

Диссертационная работа состоит из введения, четырех глав, заключения и приложения, изложенных на 139 страницах, содержит 26 рисунков, 1 таблицу, список литературы из 102 наименований. Диссертация состоит из четырех глав.

Основные результаты работы:

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

2. Предложена модель сокращения размера БДР с помощью линейных и аффинных преобразований входящих переменных.

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

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

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

6. Доказана теорема о том что алгоритм однородности конечен и отрабатывает за число шагов не более чем O(NlogN), где N = 2" размер таблицы истинности функции.

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

Заключение

1. Bryant, R.E. Graph-based algorithms for Boolean functions manipulations / R.E. Bryant // 1.EE Trans. Computers. - 1986.-Vol. C-35, No. 8.-P.667-691.

2. Akers, S.B. Binary decision diagrams/ S.B. Akers// IEE Trans. On Computers.- 1978.-Vol. C-27,No. 6. P.509-516.

3. Lee C.Y. Representation of switching circuits by binary decision diagrams / C.Y. Lee // Bell Syst. Tech. J.- 1959.-Vol. 38.- P.985-999.

4. Thayse, A. Optimization of multiple-valued decision diagrams/ A. Thayse, M. Davio, J. -P. Deschamps // Proc. 8th Int. Symp. On Multiple-Valued Logic.- 1978.- P.171-177.

5. Kurepa, Dj.R. Ensemles ordonnes et ramifies/ Dj.R. Kurepa // Paris.- 1935.-P.89-97.

6. Matsuura, M. Representation of incompletely specified switching functions using Pseudo-Kronecker Decision Diagrams/ M. Matsuura, T. Sasao // Fifth International Workshop on Applications of the Reed-Muller Expansion in Circuit Design.- 2001.- P.27-33.

7. Gunter, W. Linear transformations and exact minimization of BDDs/ W.Gunter, R. Drechsler // IEEE Great Lakes Symposium on VLSI, Lafayette.- 1998.- P.325-330.

8. Thierauf, T. The Computational Complexity of Equivalence and Isomorphism Problems / T. Thierauf // (Lecture notes in computer science 1852), Springer.- 2000.

9. Heinrich-Litan, L. Least Upper Bounds for the Size of OBDD using symmetry properties / L. Heinrich-Litan, P. Molitor // IEE Transactions on computers.- 2000.- Vol. 49, №4.

10. Gunter, W. BDD Minimization by Linear Transformation / W. Gunter, R. Drechsler // Advanced Computer Systems, Szczecin, Poland.- 1998.1 l.Schmiedle, F. Dynamic Re-Encoding During MDD Minimization / F.

11. Becker, B. OKFDDs versus OBDDs and OFDDs/ B. Becker, R. Drechsler, M. Theobald // Proc. International Colloquium Automata, Languages and Programming.- 1995.- P.475-486.

12. Drechsler, R. Dynamic Minimization of OKFDs/ R. Drechsler, B. Becker // Proc. International Conferece on Computer Design.- 1995.-Р.602-607.

13. Bryant, R.E. Graph based algorithms for Boolean function manipulations / R.E. Bryant//IEEE Trans. On Сотр.- 1986.-№35(8).-P.677-691.

14. Drechsler, R. Binary Decisions Diagrams Theory and Implementation / R. Drechsler, B. Becker // Kluwer Academic Publishers.- 1998.

15. Gunter, W. BDDs minimization by linear transformations based on evolutionary techniques/ W. Gunter, R. Drechsler // International Workshop on Boolean Problems, Freiberg.- 1998.

16. Yibin, Y. A graph-based synthesis algorithm for AND//XOR networks/ Y. Yibin, R. Kaushik // Design Automation Conf.- 1997.

17. Becker, B. Decision diagrams in synthesis. Algorithms, application and extensions/ B. Becker, R. Drechsler// VLSI Design Conf.- 1997.- P.46-50.

18. Scholl, С. Efficient ROBDD based computation of common decomposition functions of multi-output Boolean functions/ C. Scholl, P. Molitor // IFIP Workshop on Logic and Architecture Synthesis. Grenoble.- 1994.- P.61-70.

19. Drechsler, R. A genetic algorithm for variable ordering of OBDDs/ R. Drechsler, B. Becker, N. Gockel // J.W. Goethe-University, Frankfurt.-1995.- №5.

20. Tsai, C.-C. Boolean functions classifications via fixed polarity Reed-Muller forms/ C.-C. Tsai, M. Marek-Sadowska // IEEE Transaction on Computers.-1997.- Vol. 46,№2.

21. Hansen, J. P. Synthesis by spectral translation using boolean decision diagrams / J. P. Hansen, M. Sekine // In Design Automation Conf. On CAD.- 1996.- P. 248-253.

22. Miller, M. A spectral method for boolean function matching / M. Miller // In European Design & Test Conf.- 1996.- P.602.

23. Ruddel, R. Dynamic variable ordering for ordered binary decision diagrams / R. Ruddel // In Int'l Conf. on CAD.- 1993.- P.42-47.

24. Field-Programmable Gate Arrays / S.D. Brown, RJ. Francis, J. Rose, Z.G. Vranesic// Kluwer Academic Publisher.- 1992.

25. Murgai, R. Logic Synthesis for Field-Programmable Gate Arrays/ R. Murgai, R.K. Brayton, A.L. Sangiovanni-Vincentelli // Kluwer Academic Publisher.-1995.

26. Harrison, M. Counting theorems and their application to classification of switching functions/ M. Harrison // In A. Mukhopadyay, editor, Recent Developments in Switching Theory, Academic Press.- 1971.

27. Jain, J. Sampling schemes for computing OBDD variable orderings / J. Jain, W. Adams, M. Fujita// In International Conference on CAD.- 1991.- P.472-475.

28. Yang, C. BDS: a BDD-based logic optimization system / C. Yang, M. Ciesielski, V. Singhal II In Design Automation Conf.- 2000.- P.92-97.

29. Meinel, C. Linear shifting of decision diagrams/ C. Meinel, A. Somenzi, T. Theobald // In International Conference on Computer Design.- 1997.- P.338-343.

30. Slobodova, A. Sample method for minimization of OBDD / A. Slobodova and C. Meinel // In International Workshop on Logic Synth.- 1998.- P.311-316.

31. Waak, S. On the Descriptive and Algorithmic Power of Parity Ordered Binary Desicions Diagrams/ S. Waak // Symposium on Theoretical Aspects of Computer Science.- 1997.- Vol. 1200 of LNCS.

32. Decision Diagrams and AND/OR Graphs for Design Automation Problems / R. Drechsler, W. Kunz, D. Stoffel, A. Zuzek// 3rd International Workshop on Applications of the Reed-Muller Expansion in Circuit Design.- 1997.- P.3-12.

33. Minimizing ROBDD sizes of incompletely specified Boolean functions by exploiting strong symmetries / C. Scholl, S. Melchior, G. Hotz, P. Molitor // Proceedings of the European Design and Test Conference, Paris, France.-1997.

34. Drechsler, R., EXOR transform of input to design efficient two-level AND/EXOR adders / R. Drechsler, B. Becker // Electronic Letters.- 2000.-Vol. 36, № 3.- P.201-202.

35. Hett, A. Reordering Based Synthesis / A. Hett, R. Drechsler, B. Becker // 3rd International Workshop on Applications of the Reed-Muller Expansion in Circuit Design.-1997,- P. 13-22.

36. Bessilich, P.W. An efficient program for logic synthesis of mod-2 sum expressions / P.W. Bessilich, R.W. Riege // Proc. Euro ASIC'91.- 1991.-P.136-141.

37. Akers, S.B. On a Theory of Boolean functions / S.B. Akers // Proc. Ind. Appl. Math.- 1959.-№7.- P.487-498.

38. Besslich, Ph.W. Efficient computer method for EXOR logic design / Ph.W. Besslich // IEE Proc.-1983.- Vol. 131. Pt.E, № 6.- P.203-206.

39. Clarke, E.M. Hybrid spectral transform diagrams / E.M. Clarke, M. Fujita, W. Heinle // Proc. Int. Conf. on Information, Communications and Signal Processing, (1st ICICS).- 1997.- Vol. 1.- P.251-255.

40. Clarkson ,T.G. Vector algorithm for Reed-Muller expansions / T.G. Clarkson, N. Zhuang // Electronics Letters.- 1994.- Vol. 30, №.7.- P.549-550.

41. Csanky, L. Canonical restricted mixed-polarity exclusive sums of products / L. Csanky, M.A. Perkowski, I. Schaefer // Proc. Int. Symp. on Circuits and Systems, (ISCAS'92).- 1992.-Vol. 1.-P.17-20.

42. Csanky, L. Canonical restricted mixed-polarity exclusive-OR sums of products and the efficient algorithm for their minimization / L. Csanky, M.A. Perkowski, I. Schaefer // IEE Proc. Computers and Digital Techniques.-1993.- Vol. 140, №1.- P.69-77.

43. Davio, M. Taylor expansion of symmetric Boolean functions / M. Davio // Philips Res. Repts.- 1973.- Vol. 28.- P.466-474.

44. Debnath, D. GRMIN: a heuristic simplification algorithm for generalized Reed-Muller expressions / D. Debnath, T. Sasao // Proc. of the Asian and South Pacific Design Automation Conference, (ASP-DAC'95).- 1995.-P.341-347.

45. Debnath, D. Exact minimization of fixed polarity Reed-Muller expressions for incompletely specified functions / D. Debnath, T. Sasao // Proc. of the Asia and South Pacific Design Automation Conference, (ASP-DAC 2000).-2000.- P.247-252.

46. Dill, R.M. Evolutionary minimization of generalized Reed-Muller forms / R.M. Dill, M. Perkowski // Proc. Int. Conf. on Computational Intelligence and Multimedia Applications, H.Servaraj, B.Verma (Eds.), Australia.- 1998.-P.727-733.

47. Drechsler, R. Sympathy: fast exact minimization of fixed polarity Reed-Muller expressions for symmetric functions / R. Drechsler, B. Becker // Proc. European Design and Test Conference, (ED& TC 95).- 1995.- P.91-97.

48. Drechsler, R. Relation between OFDDs and FPRMs / R. Drechsler, B. Becker // Electronics Letters.- 1996.- Vol. 32, №21.- P. 1975-1976.

49. Falkowski, B. Generation of multi-polarity Arithmetic transform from reduced representation of Boolean functions / B. Falkowski, C.H. Chang // Proc. 28th Int. Symp. on Circuits and Systems.- 1995.- P.2168-2171.

50. Falkowski, B.J. Optimization of partially-mixed-polarity Reed-Muller expansions / B.J. Falkowski, C.H. Chang // Proc. Int. Symp. on Circuits and Systems, (ISCAS '99).- 1999.- Vol. 1, P.383-386.

51. Falkowski, B.J. Generalised fc-variable-mixed-polarity Reed-Muller expansions for system of Boolean functions and their minimization / B.J. Falkowski, C.-H. Chang// IEE Proc. Circuits, Devices and Systems.- 2000.-Vol. 147, №4.- P.201-210.

52. Falkowski, B.J. Effective minimization of logic functions in Reed-Muller domain / B.J. Falkowski, G. Holowinski, K. Malecki // Proc. Int. Conf. on Applications of Computer Systems, Poland.- 1997.- P.248-255.

53. Falkowski, B.J. Algorithms for fast Reed-Muller transform / В.J. Falkowski, S. Rahardja // Proc. of IEEE International Symposium on Circuits and Systems, (ISCAS '97).- 1997.- Vol. 4.- P.2669-2672.

54. Gibbs, J.E. Some methods of solution of linear ordinary logical differential equations / J.E. Gibbs, M.J. Millard // NPL DBS Kept.- 1969.- №2.

55. Green, D.H. Families of Reed-Muller canonical forms / D.H. Green // Int. J. Electronics.- 1991.- Vol. 70, №2.- P.259-280.

56. Harking, B. Efficient algorithm for canonical Reed-Muller expansions of Boolean functions / B. Harking // IEE Proc. Computers and Digital Techniques.- 1990.- Vol. 137, №5. p.366-370.

57. Kebschull, U. Efficient graph-based computation and manipulation of functional decision diagrams / U. Kebschull, W. Rosenstiel // Proc. 4th European Conference on Design Automation with the European Event in ASIC Design.- 1993.- P.278-282.

58. Using a genetic algorithm for optimizing fixed polarity Reed-Muller expansions of Boolean functions/J.F. Miller, H. Luchian, P.G. Bradbeer, P.J. Barclay // Int. J. Electronics.- 1994.- Vol. 76, №4. p.601-609.

59. Purwar, S. An efficient method of computing generalized Reed-Muller expansions from binary decision diagram / S. Purwar // IEEE Trans, on Computers.- 1991.- Vol. 40, №11.- P.1298-1301.

60. Song, N. Minimization of Exclusive Sum of Products expressions for multi-output multiple-valued input, incompletely specified functions / N. Song, M. Perkowski // IEEE Trans, on CAD.- 1996.- Vol. 15, №4.- P.385-395.

61. Stankovic, R.S. Functional decision diagrams for multiple-valued functions / R.S. Stankovic // Proc. 25th International Symposium on Multiple-Valued Logic.- 1995.- P.284-289.

62. Stankovic, R.S. Decision diagrams for representation of discrete functions: uniform interpretation and classification / R.S. Stankovic, T. Sasao // Proc. ASP-DAC'98, Yokohama, Japan, February 13-17.- 1998.

63. Thornton, M.A. BDD-based spectral approach for Reed-Muller circuit realization / M.A. Thornton, V.S.S. Nair // IEE Proc. Computers and Digital Techniques.- 1996.- VoL143, №2.- P.145-150.

64. Tsai, C.-C. Efficient minimization algorithms for fixed polarity AND/XOR canonical networks / C.-C. Tsai, M. Marek-Sadowska // Proc. Third Great Lakes Symposium on Design Automation of High Performance VLSI Systems.- 1993.- P.76-79.

65. Tsai, C.-C. Minimization of fixed-polarity AND/XOR canonical networks / C.-C. Tsai, M. Marek-Sadowska // IEE Proc. Computers and Digital Techniques.- 1994.- Vol. 141, №6.- P.369-374.

66. Tsai, C.C. Detecting symmetric variables in Boolean functions using generalized Reed-Muller forms/ C.C. Tsai, M. Marek-Sadowska // Proc. Int. Symp. on Circuits and Systems, (ISCAS'94).- 1994.- Vol. 1.- P.287-290.

67. Tsai, C.C. Generalized Reed-Muller forms as a tool to detect symmetries / C.C. Tsai, M. Marek-Sadowska // IEEE Transactions on Computers.- 1996.-Vol. 45, №1.- P.33-40.

68. Generalized partially-mixed-polarity Reed-Muller expansion and its fast computation / H. Wu, M.A. Perkowski, X. Zeng, N. Zhuang // IEEE Trans, on Computers.- 1996.- Vol. 45, №9.- P. 1084-1088.

69. Xu, L. Multi-level optimisation of fixed polarity Reed-Muller expansions using Reed-Muller binary decision diagrams / L. Xu, L. McKenzie // IEE

70. Colloquium on Synthesis and Optimisation of Logic Systems.- 1994.- P. 3/13/4.

71. Zakrevskij, A.D.Fast algorithm for minimizing Reed-Muller expansions of systems of incompletely specified MVL functions / A.D. Zakrevskij, L.A. Zakrevski // Proc. 27th International Symposium on Multiple-Valued Logic.-1997.- P.61-65.

72. Sasao, T. Optimization of multiple-valued AND-EXOR expressions using multiple-place decision diagrams / T. Sasao // Proc. 22nd IEEE Int. Symp. on Multiple-Valued Logic.- 1992.- P.451-458.

73. Somenzi, F. Binary decision diagrams / F. Somenzi, M. Broy, R.

74. Steinbruggen // Calculational System Design.- 1999.- Vol. 173 of NATO Science Series F: Computer and Systems Sciences. IOS Press.- P.303-366.

75. Sasao, T. On the complexity of MOD-2 sum PLA's / T. Sasao, Ph. W. Besslich // IEEE Trans, on Computers.- 1990.- Vol. 34, №2,- P.262-266.

76. Sasao, T. An exact minimization algorithm for generalized Reed-Muller expressions / T. Sasao, D. Debnath // Proc. Asia-Pacific Conference on Circuits and Systems, APCCAS '94.- 1994.- P.460-465.

77. Sasao, T. Representations of Discrete Functions / T. Sasao, M. Fujita // Kluwer Academic Publishers.- 1996.

78. Minato, S. Zero-Suppressed BDDs for Set Manipulation in Combinatorial Problems / S. Minato // Proc. of the Design Automation Conf.- 1993.- P.272-277.

79. Берж, К. Теория графов и ее применения/ К. Берж.- М.: Иностр. лит., 1962.- 320с.

80. Асанов, М.О. Дискретная математика: Графы матроиды, алгоритмы / М.О. Асанов, В .А. Баранский, В.В. Расин.- Ижевск: НИЦ "РХД", 2001.

81. Евстигнеев, В.А. Применение теории графов в программировании / В.А. Евстигнеев.- М.:Наука, 1985.-352с.

82. Камерон, П. Теория графов, теория кодирования и блок-схемы / П. Камерон, Дж. ван Линт.- М.: Наука, 1980.-144с.

83. Кристофидес, Н. Теория графов. Алгоритмический подход / Н. Кристофидес.-М.: Мир, 1978.-432с.95.3ыков, А.А. Основы теории графов/А.А. Зыков.- М.: Наука, 1987.-384с.

84. Вирт, Н. Алгоритмы и структуры данных/ Н. Вирт.- М.: Мир, 1989.-360с.

85. Янг, М. Дж. Visual С++ / М. Дж. Янг.- К: BHV-Киев, 2000.

86. Колпаков, A.B. Бинарные диаграммы и линейные преобразования переменных / А.В. Колпаков, Р.Х. Латыпов // Четвертая международная конференция «Автоматизация проектирования дискретных схем», 14-16 ноября, Минск.- 2001.- Т. 2.- С. 116-121.

87. Колпаков, A.B. Минимизация BDD с помощью линейных преобразований переменных / А.В. Колпаков, Р.Х. Латыпов // XIII Международная Конференция «Проблемы теоретической кибернетики» Казань, 27-31 мая.- 2002.- С.91.

88. Колпаков, А.В. Приближенные алгоритмы минимизации двоичных диаграмм решений на основе линейных преобразований переменных / А.В. Колпаков, Р.Х. Латыпов // Автоматика и телемеханика.-2004.- №6,-С.112-128.