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

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

Автоматика и телемеханика, № 7, 2014

( 2014 г. П.Н. БИБИЛО, д-р техн. наук (bibilo@newman.bas-net.by) (Объединенный институт проблем информатики НАН Беларуси, Минск)

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

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

1. Введение

Диаграммы двоичного выбора (Binary Decision Diagram, BDD), называемые также диаграммами двоичных решений, явились конкретной формой задания граф-схем алгоритмов выбора решений [1, 2] применительно к булевым функциям. Представление полностью определенных булевых функций (и систем функций) в виде бинарных программ [3] и BDD - многоуровневых представлениях на базе разложения Шеннона [3-6] - во многих случаях является гораздо более компактным, чем двухуровневые И/ИЛИ представления тех же функций в матричных формах, под которыми понимаются ДНФ (дизъюнктивные нормальные формы) и таблицы истинности. Кроме того, использование специальных структур данных при программной реализации алгоритмов получения и обработки BDD позволяет получать эффективные программы выполнения различных операций над BDD. Аппарат BDD широко используется при решении различных задач [7, 8], возникающих при проектировании цифровых систем.

Декомпозиция (функциональное разделение) булевых функций по входным переменным изучалась давно и использовалась при синтезе комбинационных логических схем с различными целями [9]. Для программируемых логических матриц (ПЛМ) декомпозиция является способом уменьшения числа входных переменных либо площади ПЛМ [10]. Для синтеза структур FPGA (Field-Programmable Gate Array - программируемая пользователем вентильная матрица) декомпозиция [11, 12] стала одним из приемов технологического отображения в сеть настраиваемых элементов LUT (Look-Up Table - таблица, реализующая логическую функцию). При синтезе схем из библиотечных элементов декомпозиция может использоваться либо с целью разбиения функционального описания на меньшие по размерности блоки, для которых возможно использовать более эффективные (и более трудоемкие) оптимизационные процедуры [13], либо с целью увеличения быстродействия схем [14].

В [15] рассматривались простые случаи декомпозиции булевой функции по представлению ее в виде БББ: декомпозиция с фиксированной выходной функцией (двухместными дизъюнкцией, конъюнкцией, суммой по модулю 2) и простая декомпозиция, т.е. декомпозиция с одной промежуточной переменной. Использование БББ-представлений для систем полностью определенных функций позволило более эффективно решать задачу выбора разбиения переменных, по которому проводится декомпозиция [16].

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

2. Частичные булевы функции

Булева функция /, значения 0, 1 которой определены на всех элементах х* € Vх называется полностью определенной, Vх - булево пространство над переменными вектора х = (х1,... , хп). Если же на некоторых элементах Vх значения функции / не определены, то такая функция называется неполностью определенной, или частичной. Частичная булева функция / принимает единичное значение на элементах х* подмножества М^ булева пространства Vх и нулевое значение на элементах подмножества М0. На всех остальных элементах пространства Vх, образующих подмножество М- пространства Vх, значение частичной функции не определено. Неопределенное значение функции обозначается символом "-". Частичные функции /1 и /2 равны, если и только если М^ = М^2, М0 = М02, М-! = М—2. Чаще всего задают частичную булеву функцию / (х) множествами М1 М0. Каждое из множеств Мр М0 можно задать в виде ДНФ ^1, ^о, обладающих свойством ортогональности: = 0. Далее в выражениях знак "&", как правило,

будет опускаться. Частичная функция /1 реализуется частичной функцией /2 (обозначается /1 — /2), если и только если М^ С М^2, М°1 С М02. Для полностью определенных булевых функций отношение реализации является отношением равенства.

Векторной булевой функцией Г(х) будем называть упорядоченную систему булевых функций Г(х) = (/ 1(х),...,/т(х)). Отношение реализации векторных функций сводится к выполнению отношения реализации между компонентными функциями: если каждая компонентная функция /г*, г = 1,..., т, векторной функции Р(х) = (/ 1*(х1,..., хп),..., /т*(х1,..., хп)) реализует

соответствующую компонентную функцию /г векторной функции Г(х) = = (/ 1(х),...,/т(х)), то тогда выполняется отношение реализации между векторными функциями: векторная функция Г * реализует векторную функцию Г, т.е. Г(х) — Г*(х). В этом случае векторная функция Г*(х) называется доопределением векторной функции {(х).

3. Представление системы частичных булевых функций в виде БББ

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

(1) /(х) = Хг/(Х1, . . .,Хг-1,0,Хг+1, . . . ,Ж„) V Xif(x1, ...,Хг-1, 1,Жт, • • • ,Ж„).

Функции в правой части (1) называются коэффициентами разложения. Они получаются из функции /(ж1,...,жп) подстановкой вместо переменной Жг константы 0 и 1 соответственно. Если исходная функция /(х) является частичной, то и коэффициенты разложения являются частичными булевыми функциями. Каждый из коэффициентов /(Ж1, . . . , Жг_1, 0, Жг+1, . . . , Жп), / (ж1, ..., Жг_1,1, Жг+1,..., жп) может быть разложен по одной из переменных из множества {ж1, ..., жг-1, жг+1,..., жп}. Процесс разложения коэффициентов заканчивается, когда все п переменных будут использованы для разложения. В процессе разложения либо на последнем шаге разложения коэффициенты вырождаются до констант 0, 1, "—".

Далее будут рассматриваться БББ для векторной булевой функции Г(х), при этом перестановки переменных, по которым ведутся разложения, одинаковы для всех компонентных функций /г(х), г = 1,..., т. Например, на рис. 1 дана БББ, представляющая систему частичных функций, зависящих от шести переменных. БББ содержит три вида вершин: функциональные вершины, соответствующие различным разлагаемым функциям; вершины-переменные, т.е. вершины, соответствующие переменным разложения; листовые вершины, соответствующие константным (0, 1, —) значениям (функциям-константам). Функцию-константу " —" далее всегда будем обозначать как для такой функции все ее значения не определены. Другими словами - это функция-константа, не имеющая ни одного определенного значения 0, 1. Заметим, что БББ, представляющая систему полностью определенных булевых функций, в качестве листовых вершин имеет только 0, 1. Функциональные вершины, соответствующие исходным компонентным функциям /г(х), будем называть корневыми вершинами БББ. Все листовые вершины будем располагать внизу БББ. Однако многочисленные связи, идущие к листовым вершинам, будут загромождать рисунок, поэтому листовые вершины будем дублировать и располагать на различных уровнях. При этом всегда будем принимать во внимание, что соответствующие функции-константы могут попадать в горизонтальный разрез БББ и быть коэффициентами разложения Шеннона. Горизонтальные разрезы БББ будем проводить после уровня вершин-переменных. Например (рис. 1), на уровне, находящемся после переменной ж3, располагаются коэффициенты (функции) г1, г2, ..., г8, а также и функции-константы г9 = и г10 = 1 (константа 1). Будем считать, что каждому уровню БББ

w

Рис. 1. BDD, представляющая систему частичных функций.

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

Минимизация сложности BDD основана на том, что различные разлагаемые функции могут иметь одинаковые коэффициенты разложения. Рассматриваемые в данной статье диаграммы двоичного выбора для частичных функций соответствуют широко известным [8] упорядоченным приведенным диаграммам двоичного выбора (ROBDD - Reduced Ordered Binary Decision

Diagram) для полностью определенных функций. Под сложностью BDD будем понимать число функциональных вершин BDD. Вершины-переменные и листовые вершины не будем учитывать при оценке сложности BDD и сравнении различных BDD, реализующих одну и ту же систему булевых функций. Например, сложность BDD (рис. 1) равна 30, так как BDD содержит 30 функциональных вершин.

По BDD легко можно построить многоуровневое представление - суперпозицию частичных булевых функций, принимая во внимание то, что листовым вершинам соответствуют функции-константы 0,1, " —". Для BDD (рис. 1) многоуровневое представление имеет вид:

f1 = Xip1 V Xip2] /2 = Xip3 V Xip4]

i _ i i о _ 2 3

p = X'2f V X'2i-P ; p = Х'2й, V X2d ;

p3 = Ж2С4 V Ж205; p4 = x-2a6 V X2a';

а2 2 = Х3Г V xsr ; а Go = Х3Г2 V Ж3Г4; а4 — -5 жз^ V ХзГ ;

а5 — - w 2 = x3ip V Х3Г ; а6 = Ж3Г6 V Х3Г1; а7 — fi 0 = Ж3Г V Х3Г ;

r1 = Ж5<p~ V .T5S1; r2 — -2 ж4^> V x4w2; r3 — Q = X4<p V X4W :

r4 = 45 x4w V x4w ; r5 — X4W6 V x±t

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

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