научная статья по теме ДЕКОМПОЗИЦИЯ СИСТЕМ БУЛЕВЫХ ФУНКЦИЙ, ЗАДАННЫХ ДИАГРАММАМИ ДВОИЧНОГО ВЫБОРА Кибернетика

Текст научной статьи на тему «ДЕКОМПОЗИЦИЯ СИСТЕМ БУЛЕВЫХ ФУНКЦИЙ, ЗАДАННЫХ ДИАГРАММАМИ ДВОИЧНОГО ВЫБОРА»

ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2011, № 4, с. 86-101

= КОМПЬЮТЕРНЫЕ МЕТОДЫ =

УДК 517.98

ДЕКОМПОЗИЦИЯ СИСТЕМ БУЛЕВЫХ ФУНКЦИЙ, ЗАДАННЫХ ДИАГРАММАМИ ДВОИЧНОГО ВЫБОРА © 2011 г. П. Н. Бибило, П. В. Леончик

Белоруссия, Минск, Объединенный ин-т проблем информатики НАНБелоруссии Поступила в редакцию 10.11.09 г., после доработки 05.10.10 г.

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

Введение. Эффективность решения задач синтеза комбинационных логических схем в значительной степени зависит от формы представления булевых функций, которые требуется реализовать логической схемой. В качестве исходных форм описания булевых функций (и их систем) в практике проектирования используются как двухуровневые — системы дизъюнктивных нормальных форм (ДНФ) и таблицы истинности, выраженные троичными и булевыми матрицами, так и многоуровневые — алгебраические скобочные формы и диаграммы двоичного выбора (Binary Decision Diagram — BDD). Существующие методы синтеза схем ориентируются на различные формы исходного представления функций. Наибольшее развитие в настоящее время получили методы, оперирующие с алгебраическими представлениями функций и предназначенные для синтеза схем в заданной библиотеке проектирования заказных схем [1], и декомпозиционные методы, развитые для синтеза сетей программируемых логических матриц (ПЛМ) [2, 3] и структур FPGA (Field-Programmable Gate Arrays) [4]. Структура ПЛМ адекватна структуре реализуемой на ПЛМ системы ДНФ булевых функций, поэтому в литературе большое внимание было уделено решению задач декомпозиции систем ДНФ. Проблемам декомпозиции булевых функций и их систем посвящена работа [5] и монографии [6, 7], которые также содержат обзоры результатов по декомпозиции. При решении задач декомпозиции используются различные формальные модели — булевы и троичные матрицы [2, 3, 8], специальные таблицы [6], аппарат понятий производной, дифференциала и разности булевой функции [1], спектральные представления [9], логические уравнения [7] и др.

Задания булевых функций в виде BDD широко изучались в [10—14]. В отечественной литературе вместо BDD употреблялся термин "бинарные программы" [15]. Применение BDD для декомпозиции булевых функций отражено в [16—20]. В [17, 18] рассматривались простые случаи декомпозиции булевой функции по описанию ее в виде BDD: декомпозиция с фиксированной выходной функцией (двухместными дизъюнкцией, конъюнкцией, суммой по модулю 2) и простая декомпозиция, с одной промежуточной переменной, в работе [19] содержатся результаты обширного вычислительного эксперимента, в [20] BDD использовались для синтеза схем, реализующих сумматоры, а в [16] — при синтезе структур FPGA.

Появление FPGA вызвало большой интерес к BDD и декомпозиции систем булевых функций [21], аппарат BDD был эффективно применен для синтеза структур FPGA в широко известных синтезаторах логических схем, например в LeonardoSpectrum [14]. После создания промышленных синтезаторов логических схем FPGA и заказных сверхбольших интегральных схем (СБИС) интерес к проблемам декомпозиции булевых функций несколько ослабел, но, тем не менее, остался достаточно высоким — появились новые работы [22, 23], в которых изучаются разложения на уровне алгебраических представлений булевых функций, декомпозиция стала применяться для изменения структуры многоуровневых представлений с целью уменьшения задержек логических схем [24], была изучена [25] проблема выбора разбиения множества переменных, для которого возможно функциональное разложение с одной промежуточной переменной. Для решения задач декомпозиции предложено [7, 26] использовать мощные программы (SAT-solvers) решения задачи о выполнимости конъюнктивной нормальной формы (Boolean satisfiability prob-

lem — SAT-problem), хорошо зарекомендовавшие себя при верификации логических схем. Экспериментальные исследования показали [27], что использование эффективных программ технологически независимой оптимизации двухуровневых и многоуровневых представлений систем булевых функций может значительно улучшить результаты (уменьшить сложность схем и увеличить быстродействие) последующего за оптимизацией синтеза в промышленных синтезаторах.

В данной работе исходное представление функций в виде BDD привлекается для решения задачи декомпозиции системы полностью определенных булевых функций c несколькими промежуточными переменными. Особенностью такого метода является то, что один (из двух) блоков разложения остается заданным в виде BDD, а функции другого блока разложения строятся заданными в виде ДНФ. Поэтому схема может быть осуществлена в смешанном базисе — один из блоков легко реализуется на ПЛМ, а другой может быть выполнен в выбранной библиотеке логических элементов. Предлагается алгоритм выбора двухблочного разбиения множества аргументов, по которому проводится декомпозиция, и приводятся результаты экспериментов по реализации функций разложения схемами в библиотеке проектирования заказных СБИС с помощью промышленного синтезатора LeonardoSpectrum.

1. Диаграмма двоичного выбора для одной функции и системы функций. BDD строятся на основе разложения Шеннона. Разложением Шеннона полностью определенной булевой функции f (xb...,xn) по переменной (аргументу) xt называется представление

f (Xi,...,Х„) == Xf (Xi,...,Xj-i,1,Xj+i,...,Xn) v Xif (xi,...,xt-i, 0,xt+i,...,Xn). (1.1)

Функции f(Xi,...,Xi_i,i,Xi+i,...Xn), f(Xi,...,Xi_i,0,xj+1,...xn) в (1.1) — коэффициенты разложения. Они получаются из функции f (x1,..., Xn) подстановкой вместо переменной Xj константы 1 и 0 соответственно. Видно, что если коэффициенты равны, то f (x1, ..., Xn) = f (x1,..., Xj _i, Xj+i, ...Xn). Переменная Xi именуется в этом случае несущественной или фиктивной переменной полностью определенной функции f(x1,..., xn). Каждый из коэффициентов f(x1,..., Xj _1,1, xi+1,...xn), f(x1,...,Xj_1,0,xi+1,...xn) может быть разложен по одной из переменных из множества {x1,...,xi_1,xj+1,...xn}. Этот процесс разложения коэффициентов заканчивается, когда все n переменных будут использованы для разложения. На последнем шаге разложения коэффициенты вырождаются до констант 0, 1.

Под диаграммой двоичного выбора, т.е. под BDD, понимается ориентированный граф, задающий все различные коэффициенты разложений Шеннона булевой функции f (x1,...,xn) по всем ее переменным x1,...,xn при установленном порядке (перестановке) переменных, по которым проводятся разложения. Условимся, что к коэффициенту f (x1,..., xt _1,0, xi+1, ...xn) на BDD будет вести штриховая дуга, а к коэффициенту f (x1,..., xt _1,1, xt+1,...xn) — сплошная. Для упрощения графа BDD вершины-константы 0, 1 обычно дублируются, а ориентированные дуги заменяются неориентированными ребрами. Заметим, что в литературе граф BDD рисуется в сокращенном виде — полученные коэффициенты разложения не отмечаются и лишь предполагается, что все заходящие в одну и ту же вершину переменную ребра соответствуют одному и тому же коэффициенту разложения.

Упорядоченную систему f = (f 1(x), . ., fm(x)) булевых функций для краткости будем называть

также векторной булевой функцией или векторной функцией. Векторная функция f = (f1, f2, f3)

(табл. 1) представляется в виде системы ДНФ, заданной парой матриц Tx, Bf. В каждой из строк

матрицы Tx, располагающейся в левой части таблицы, содержится элементарная конъюнкция

булевых переменных, единичные значения элементов матрицы Bf в правой части таблицы отмечают вхождения данной конъюнкции в ДНФ соответствующей компонентной функции. BDD

для векторной функции f = (f1, f2, f3), m = 3 (табл. 1) приведена на рис. 1. Порядок < x1, x2, x3, x4, x5, x6> переменных, по которым выполнено многократное разложение Шеннона, совпадает с порядком следования переменных в функции. Граф BDD для векторной функции получается из BDD-компонентных функций отождествлением тех вершин, которые соответствуют одинаковым коэффициентам разложения. По диаграмме двоичного выбора легко записывается многоуровневое представление компонентных булевых функций f1. Например, для векторной функ-

Таблица 1

T ±x Bf

x1 x2 x3 X4 x5 x6 f1 f2 f3

1 0 - 1 0 1 0 1 0

1 1 1 - 1 0 0 1 0

0 - 0 - 1 - 0 1 0

1 0 1 - 1 - 0 0 1

1 0 1 1 - 1 0 0 1

1 1 0 1 - 1 0 0 1

0 - - 1 0 1 1 0 0

- 1 0 - 1 - 1 0 1

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

а — , 2 л — 3 4 а — 5 6

/ = х^ v х^ ; / = хдо v х^ ; / = х^ v х^ ;

1 - ! 2 2 3 4 - 1 4 5 3

у = х2s v х2ф ; у = х2ф ; у = х2s v х2ф ; у = х2ф ;

6 — 5 6 2 — 2 1 3 —» 3 4 5 5 2 /1 ->\

у = х2ф v х2ф ; ф = x3s v x3s ; ф = х3к ; ф = x3s ; ф = x3s ; (1.2)

6 — 2 1 » 1 2 -» 3 л 2 4 -» 4

ф = x3s ; s = х4л, ; s = х4л, v х4л, ; s = х4л, ;

л 1 — 1 л 2 — 1 л 3 л 4 2 1 2

л = х5ю ; к = х5ю v х5; к = х5; к = х5ю ; ю = х6; ю = х6.

2. Постановка задачи. Пусть задано разбиение Y/Z множества X = {хь..., хп} переменных векторной булевой функции /(х) = (/ 1(х),...,/т(х)) на два непересекающиеся подмножества Y = {y1,..., yr}, Z = {zb..., zn-r}. Обозначим через y = (y1,..., yr) вектор, полученный упорядочением переменных из подмножества Y, а через z = fo,..., zn-r) — ранжированием переменных из подмножества Z. Пусть диаграмма двоичного выбора векторной функции /(х) построена так, что начальные r переменных последовательности разложения Шеннона являются переменными подмножества Y.

Задача 1. Для компонентных булевых функций /' (х), представленных в виде BDD, и заданного разбиения Y/Z множества переменных X построить функциональные разложения (провести раздельные декомпозиции) вида

fs (х) = fJ(y, z) = gJ(hJ(y), z), (2.1)

где hJ(y) = (hJ(y),...,hJp (y)). Каждой из компонентных функций/' при этом требуется минимизировать

Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.

Показать целиком