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

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

ИЗВЕСТИЯ РАН. ТЕОРИЯ И СИСТЕМЫ УПРАВЛЕНИЯ, 2013, № 6, с. 68-86

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

УДК 517.98

МИНИМИЗАЦИЯ ДИАГРАММ ДВОИЧНОГО ВЫБОРА ДЛЯ СИСТЕМ НЕ ПОЛНОСТЬЮ ОПРЕДЕЛЕННЫХ БУЛЕВЫХ ФУНКЦИЙ © 2013 г. П. Н. Бибило

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

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

DOI: 10.7868/S0002338813060048

Введение. Синтез комбинационных схем разбивается на два больших этапа: технологически независимую оптимизацию реализуемых систем булевых функций и технологическое отображение — покрытие оптимизированных представлений описаниями логических элементов. Эффективными методами технологически независимой оптимизации являются методы получения многоуровневых представлений систем булевых функций в виде диаграмм двоичного выбора (BDD — Binary Decision Diagram) [1—6], аналогом BDD при схемной реализации булевых функций — схемы в базисе мультиплексоров с одним управляющим входом [7].

BDD (специальные графовые представления) и их многочисленные модификации нашли широкое применение в самых различных областях — такие представления используются при верификации цифровых систем [8], при синтезе логических схем [9], при поиске тестов и т.д. Для систем полностью определенных булевых функций вычислительной основой методов оптимизации BDD являются операции сравнения булевых функций на равенство. Применяются эффективные структуры данных для представления BDD и соответствующие алгоритмы, позволяющие выполнять различные операции на BDD как для булевых (двоичных) функций, так и для k-знач-ных функций.

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

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

1. Интервальная матричная форма задания системы частичных булевых функций. Булево пространство, образованное над вектором x = (xf,...,xn) булевых (0, 1) переменных xt, i = 1,n, обозначим через Vх. Элементами «-мерного булева пространства Vх являются всевозможные наборы значений компонент вектора x = (xf,...,xn). Скалярная булева функция f(x1,...,xn) = f (x), значения 0, 1 которой определены на всех элементах булева пространства Vх, называется полностью определенной. Если же на некоторых элементах булева пространства Vх значения функции f (x) не определены, то такая функция называется не полностью определенной, или частичной. Частичная булева функция f (x) принимает единичное значение на элементах подмножества Mf булева

Таблица 1. Интервальная форма двухкомпонентной векторной функции

№ п.п. Тх Т

х1 х2 х3 х4 х5 х6 р1 Р2

1 1 1 1 0 1 - 1 -

2 - 0 1 0 1 - - 1

3 1 1 1 - 0 - 0 -

4 1 - 0 1 0 0 0 1

5 1 - 1 1 1 1 0 0

6 0 1 - - - - 1 -

7 - 1 1 1 0 0 - 0

8 0 - - - 1 0 1 -

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

Будем задавать частичную булеву функцию /(х) множествами М^, М0. Для частичной булевой

функции каждое из множеств М0, М0 можно представить в виде дизъюнктивных нормальных

форм (ДНФ) Б0, Б0, обладающих свойством ортогональности: Б0&Б0 = 0. Далее в выражениях знак "&", как правило, будет опускаться.

Частичная функция gреализуется частичной функцией к (обозначается g ■< Ь), если М0 с М},

М{0 с М°к. Для полностью определенных булевых функций отношение реализации является отношением равенства.

Частичной векторной булевой функцией f (х) будем называть упорядоченную систему частичных булевых функций Г(х) = (/:(х), ..., /т(х)). Интервальная матричная форма задания такой функции состоит из троичной матрицы Т задания элементарных конъюнкций и троичной матрицы Тр вхождений конъюнкций в ДНФ Б0,, Б0,, представляющих области нулевых и единичных значений

компонентных функций /'(х), / = 1, т. Элементами троичной матрицы являются 0, 1, "—".

Пример интервальной формы задания двухкомпонентной частичной векторной функции ((х) =

1 2

= (/ (х),/ (х)) шести аргументов приведен в табл. 1. ДНФ, задающие области единичных и нуле-

12

вых значений / , / , имеют следующий вид:

Б/1 — X} 1X2 Х3 Х4 Х5 VXl Х2 VXlX5 Хб ;

П° — •

Б/1 — Х1Х2Х3 Х5 V X} Х3Х4 Х5Хб V Х1Х3Х4Х^Х^;

Б/ 2 - Х2Х3 Х4 Х5 VXl Х3 Х4 Х5 Х 6 ;

Л° —

Б/2 — Х1Х3Х4Х5Хб V Х2Х3Х4 Х5Хб .

Неопределенное значение "—" элемента I = 1, т, ] = 1, к, матрицы Т не означает, что функция р принимает неопределенное значение на всех наборах, которые порождает троичный вектор строки I матрицы Тх; например, рассмотрим шестую и седьмую строки данной таблицы. На наборе (0, 1, 1, 1, 0, 0) значение функции р1 не является неопределенным значением "—", а равно

значению 1, так как данный набор входит в интервал (01----), на котором значение функции

р1 равно 1. Если же все строки матрицы Тх являются попарно ортогональными, то в строках матрицы Тр задаются значения 0, 1, "—" компонентных частичных функций р>.

Отношение реализации векторных функций сводится к выполнению отношения реализации между компонентными функциями: если каждая компонентная функция /*(х), I = 1, т, векторной функции 1*(х) = (/*(х), ..., /*т(х)) реализует соответствующую компонентную функцию/' (/' ^ /*)

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

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

/(х) = х/х==о V х/х==1, (2.1)

где коэффициенты при переменной разложения /х==0 = /(хь...,хг-1,0,х1+1,...хп), /х==1 =

= /(х1,..., х1 -1,1, хг+1,...хя).

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

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

Например, на рис. 1 дана БЭЭ, представляющая векторную функцию, заданную в табл. 1. БЭЭ содержит три вида вершин: функциональные вершины, соответствующие разлагаемым функциям; вершины-переменные, т.е. вершины, соответствующие переменным разложения; листовые вершины, соответствующие константным (0, 1, —) значениям (функциям-константам). Функцию-константу "—" далее всегда будем обозначать ф-. Заметим, что БЭЭ, представляющая полностью определенную векторную булеву функцию, в качестве листовых вершин имеет только 0, 1 [10]. Функциональные вершины, соответствующие исходным компонентным функциям

/'будем называть корневыми вершинами БЭЭ. Все листовые вершины должны располагаться внизу на нижнем уровне БЭЭ. Однако многочисленные связи, идущие к листовым вершинам, часто загромождают рисунок, поэтому листовые вершины будем дублировать и располагать на различных уровнях. При этом всегда будет приниматься во внимание, что соответствующие функции-константы могут попадать в горизонтальный разрез БЭЭ и быть коэффициентами разложения Шеннона. Например (рис. 1), на функциональном уровне, находящемся после разложения Шеннона по переменной х3, располагаются коэффициенты (функции) г1, г2, ..., г8, а

также и функции-константы г9 = ф- и г10 = 1 (константа 1). Коэффициенты разложения функции а1 по переменной х3 равны, поэтому из вершины-переменной х3 вниз идет одно ребро, имеющее две пометки 0, 1. Аналогично — из функциональной вершины г1. Такие функциональные вершины, как а1 и г1, следует исключить из БЭЭ, но функцию г1 = а1 = и константу 1 надо учитывать при рассмотрении коэффициентов на соответствующем функциональном уровне, например, после третьего шага разложения.

В принятых в литературе [4—6] графических изображениях БЭЭ отсутствуют функциональные вершины, они подразумеваются. Вместо пометок 0, 1 для ребер, идущих вниз от вершин-переменных, иногда применяют штриховые линии для ребер, помеченных 0, и сплошные линии — для ребер, помеченных 1. Такие сокращенные изображения БЭЭ полезны для перехода от БЭЭ к матричным заданиям функций, когда учитываются только вершины-переменные, а внутренние функциональные вершины не принимаются во внимание.

Функционально эквивалентное БЭЭ матричное представление векторной

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

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