Представления объектов проектирования

Данная глава посвящена объектам логического проектирования - логическим схемам и элементам, из которых состоят схемы, - технологическим базисам. Так как после этапа высокоуровневого синтеза логические схемы представляются RTL-описаниями комбинационной логики и элементов памяти, то основными объектами, для которых возможна логическая оптимизация, являются комбинационные части иерархически описанных проектов цифровых схем. Даются способы представления систем булевых функций, являющихся математическими моделями комбинационных частей проектов, изучаются также иерархические описания логических схем на языках SF и VHDL.

Булевы функции и формы их представления

Булевыми называются двоичные (0, 1) функции /(х) = /(xi, Х2,..., х„) двоичных (булевых) переменных xj,X2,...,x„. Пусть Vх - булево пространство, построенное над переменными булева вектора х = (хь Х2,..., х„). Элементами этого пространства являются /7-компонентные наборы (векторы) х нулей и единиц. Булева функция, значения 0, 1 которой определены на всех элементах х е Vх, называется полностью определенной. Множество М элементов х булева пространства, на которых полностью определенная булева функция принимает значение 1, называется характеристическим множеством функции. Если же на некоторых элементах булева пространства Vх значения функции не определены, то такая функция называется не полностью определенной, или частичной. Частичная булева функция принимает единичное значение на элементах х подмножества М булева пространства Vх и нулевое значение на элементах подмножества М^. На всех остальных элементах пространства Vх, образующих подмножество Мпространства Vх, значение частичной функции не определено. Неопределенное значение функции обозначается знаком «-». Будем задавать частичную булеву функцию f(x) множествами Mf, М%. Пример частичной булевой функции, зависящей от переменных X], Х2, хз, хд, дан в табл. 2.1.

Таблица 2.1. Частичная булева функция

Область значений

*1 х2х3х4

f

М

0 0 0 0

1

0 0 0 1

1

10 0 0

1

10 0 1

1

110 1

1

1111

1

Mf

0 0 10

0

110 0

0

10 11

0

0 111

0

Любая полностью определенная булева функция может быть задана в виде ДНФ, т. е. в форме дизъюнкции элементарных конъюнкций. Элементарная конъюнкция — это конъюнкция литералов (булевых переменных xz- либо их инверсий х^. Литерал X/ называется положительным, литерал Xi - отрицательным.

Если в ДНФ каждая элементарная конъюнкция является полной, т. е. содержит литералы всех переменных, то такая ДНФ называется совершенной (СДНФ). Пример ДНФ D полностью определенной булевой функции /(xi, хг, хз, хд, Х5, Хб):

D = X1X4X5X6VX2X3X5 vЛ4Х2Х4Х5Х6. (2.1)

ДНФ D состоит из трех элементарных конъюнкций к, к2, кз, в записи которых знак Л конъюнкции опущен. Представив элементарные конъюнкции, входящие в ДНФ D, троичными векторами - интервалами булева пространства Vх, получим матричное представление ДНФ D:

Х1 х2 х3 х4 х5 х6

  • 1 0 1 кх
  • 1 0 - 1 - к2
  • 1 - 0 1 0 к3

Интервалу соответствует множество наборов, которые получаются из соответствующего троичного вектора всевозможными заменами «-» нулями и единицами [33]. Например, интервалу 0—101 соответствует множество {000101, 001101, 010101, 011101} наборов. Жирным шрифтом выделены компоненты, получаемые заменой значений «-».

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

Матричные формы задания систем функций. Наряду с понятием системы булевых функций будем употреблять также понятие векторной булевой функции f (х), под которой будем понимать упорядоченную систему булевых функций /(x) = (/i(x),.../m(x)). Значениями векторных функций на элементах булева пространства являются m-компонентные булевы векторы /(х ).

Три формы Ф1, Ф2, ФЗ матричного задания векторных функций различаются в зависимости от того, являются функции заданными на интервалах либо на наборах значений множества аргументов. Матричные формы иногда называются двухуровневыми И-ИЛИ формами задания функций.

Форма Ф1 интервального задания векторной полностью определенной функции. Пример векторной функции f (*) = с компонентными функциями

/1(х) - /1(*Ь*2>*3>*4) - Х1Х2Х4 v *1X3*4,

/2(*) = /2(*1>*2,*3>*4) = Х1*зХ4 VX1X3X4

представлен в табл. 2.2.

Таблица 2.2. Матричное задание системы ДНФ полностью определенных функций

тх

в?

X] х2 х, х4

fif2

0 1-1

1 0

1 - 0 -

0 1

1-10

1 1

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

Форма Ф2 задания в виде СДНФ каждой из компонент той же векторной функции /(х) = (/1(х),/2(*)) представлена в табл. 2.3. Форма Ф2 состоит из пары булевых матриц: матрица Вх задает полные элементарные конъюнкции, матрица В?задает их вхождение в СДНФ функций - компонент векторной функции /(х).

Таблица 2.3. Матричное задание системы СДНФ полностью определенных функций

вх

В'

X] х2 X, х4

fifi

0 10 1

1 0

0 111

1 0

10 0 0

0 1

10 0 1

0 1

110 0

0 1

110 1

0 1

10 10

1 1

1110

1 1

Ф о р м а ФЗ задания векторной функции /(*) = (/1(*),/2(*)) в виде таблицы истинности представлена в табл. 2.4. Жирным шрифтом выделены наборы, на которых /(х) = (0,0) = 0.

Таблица 2.4. Таблица истинности системы полностью определенных функций

вх

в>

X] х2 х3 х4

fxfl

0 0 0 0

0 0

0 0 0 1

0 0

0 0 10

0 0

0 0 11

0 0

0 10 0

0 0

0 10 1

1 0

0 110

0 0

0 111

1 0

10 0 0

0 1

10 0 1

0 1

10 10

1 1

10 11

0 0

110 0

0 1

110 1

0 1

1110

1 1

1111

0 0

Задание полностью определенных булевых функций формулами. Кроме матричных форм задания полностью определенных булевых функций, широко распространено их задание формулами [41]. Чаще всего в качестве логических операций используются двухместные логические операции: конъюнкция (Л, &), дизъюнкция (V), дизъюнкция с исключением (Ф), импликация (—>), эквиваленция (~, =) и одноместная операция отрицания (->). В литературе операцию Ф часто называют также «сумма по модулю 2», а операцию отрицания - инверсией. В табл. 2.5 приведены результаты логических операций на наборах значений операндов, участвующих в операции.

Представления функций в виде ДНФ и СДНФ - это частные случаи задания функций формулами, точнее говоТаблица 2.5. Логические операции

X

У

-?х

х&у х/у

хМу

хфу

х^у

х~у

Х

0

0

1

0

0

0

1

1

0

1

1

0

1

1

0

0

1

0

0

0

1

1

1

0

1

1

0

1

1

0

1

1

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

Представление полностью определенной функции формулой можно рассматривать как суперпозицию функций, под которой понимается подстановка функций на места аргументов. Например, формула

f = (x®y)zvyz

может интерпретироваться как многоуровневое представление, т. е. суперпозиция функций g(gi,g2), gi(g3,*), gi(y9z),

f = g(gi,g2>=giv?2;

gi=g3& Z g2=y& z; g3=x®y.

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

Булевы сети. Графической формой скобочного представления служит булева сеть [21]. Булева сеть - это ориентированный ациклический граф. Вершины, обладающие нулевой полустепенью исхода, помечаются как выходы сети; вершины, обладающие нулевой полустепенью захода, -как входы. Каждой вершине графа соответствует некоторая переменная. Вершина i называется входной вершиной для

Булева сеть

Рис. 2.1. Булева сеть

вершины у, если в сети есть дуга, ведущая из i в у. Чтобы построить булеву сеть по выражению, задающему булеву функцию, необходимо для каждого знака логической операции выражения построить вершину сети и поставить ей в соответствие данную операцию и некоторую промежуточную переменную. Далее необходимо добавить входные вершины и правильным образом соединить вершины дугами. На рис. 2.1 представлена булева сеть для булевой функции f = (x®y)zvyz.

Диаграммы двоичного выбора. Еще одной широко распространенной формой многоуровневого представления булевых функций служат BDD (binary decision diagrams - диаграммы двоичного выбора) [96, 102, 103, 111]. В отечественной литературе под этим понимаются бинарные программы [58]. BDD строятся на основе разложения Шеннона.

Разложением Шеннона полностью определенной булевой функции /(xi,...,x„) по переменной xz называется представление /(xi,...,x„) в виде

/(хь...,хй) = xz/(xi,...,xz_i,l,xz+i,...,x„)vXi/(xi,...,xz_i,0,xz+i,...,xn). (2.2)

Функции /(xi,..., Xz-1,1, Xz+1,.. .Xn ), /(Xi,..., XZ_1,0, Xz+1,.. .xn) в (2.2) называются коэффициентами разложения. Они получаются из функции/(xi,...,x„) подстановкой вместо переменной xz константы 1 или 0 соответственно. Видно, что если коэффициенты равны, то /(Х1,...,ХЛ) = /(xi,...,xz_i,xz+i,...x„). Переменная xz называется в этом случае несущественной или фиктивной переменной полностью определенной функции /(xi,...,x„). Для полностью определенной функции можно проверить каждую из переменных на несущественность, а затем удалить сразу все найденные несущественные переменные. Однако для частичной функции это сде лать нельзя - проверку на несущественность требуется проводить не для отдельных переменных, а для подмножества переменных. Определение понятия несущественности подмножества переменных для частичной булевой функции будет дано далее.

Каждый из коэффициентов /(xi,...,xz-i,l,xz+i,...x„) и /(xi,...,xz_i,0,xz+i,...xw) может быть разложен по одной из переменных из множества {xi,...,xz-i,xz+i,...x„}. Процесс разложения коэффициентов заканчивается, когда все п переменных будут использованы для разложения. На последнем шаге разложения коэффициенты вырождаются до констант 0, 1.

Под диаграммой двоичного выбора, т. е. под BDD, понимается граф, задающий разложение Шеннона булевой функции по всем ее переменным xi,...,x„ при заданном

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

Рассмотрим построение BDD на примере ДНФ (2.1). Пусть порядок переменных, по которым проводится разложение Шеннона, совпадает с порядком Х1,Х2,хз,Х4,Х5,Хб следования переменных. Для заданной булевой функции и при заданном порядке переменных разложения соответствующая BDD является единственной. Пусть на графическом изображении BDD штриховая дуга соответствует нулевому значению, нештриховая дуга - единичному значению переменной разложения. BDD для рассматриваемой функции, заданной ДНФ (2.1), изображена на рис. 2.2.

Многоуровневое представление функции, соответствующее BDD (рис. 2.2), дано следующими логическими выражениями:

/ = X15i V Xi^2J *$1 = Х2$5 v *2^3; s2 = ^3 = *3$6 v х3^7>

  • •?4 = Х3510 v -^З^ s5 = X4S9', S6 = X4‘$’1O v •^4*yllj s7 = X4S9',
  • 5g = X4^l2j ^9 = Х551з; 5щ = X5; 5ц = X5513 V X5; S2 = X§S4',
  • 513 = *6i 514 =X6- (2.3)
Диаграмма двоичного выбора (BDD) для одной функции

Рис. 2.2. Диаграмма двоичного выбора (BDD) для одной функции

Рассмотрим более подробно процесс получения этих формул. Коэффициент

/(1,Х2,Хз,Х4,Х5,ЛГб) =Х4Х5Х6 VX2X3X5 = 51

получается в результате подстановки 1 вместо переменной xi В ДНФ (2.1), Коэффициент /(0,Х2,Хз,Х4,Х5,Хб) = 52 — Х2Х3Х5 VX2X4X5X6 получается в результате подстановки 0 вместо переменной xj. Далее аналогично:

/(0,1,*з,*4,*5э*б) =5'3= *4*5*6 v *3*5;

/(1,1,Хз,Х4,%5,Хб) = 54 =*3*5 VX4*5*6?

/(0,0,*з,*4,*5,*б) =55 =*4*5*65 /(1,0,*з,*4,*5,*б) = 0.

Аналогично получаются остальные формулы многоуровневого представления (2.3).

Выражения (2.3) представляют ту же функцию / что и ДНФ, заданная формулой (2.1). В (2.3) каждое из выражений имеет вид (2.2) разложения Шеннона либо вырождается до более простого выражения, если один из коэффициентов равен 0 или 1. Заметим, что если переменная Xj является несущественной, то соответствующая вершина отсутствует в графе, в этом случае переменная Xj отсутствует и в записи многоуровневого представления функции.

Представление в виде BDD системы функций строится путем нахождения одинаковых коэффициентов разложения для компонентных функций системы. Например, для системы функций, заданных в табл. 2.6, соответствующая BDD показана на рис. 2.3.

Таблица 2.6. Система ДНФ булевых функций

т*

В'

Х1 Х2Х3Х4Х5Х6

f,f2

101-1-

0 1

1011-1

0 1

1101-1

0 1

0--101

1 0

-10-1-

11

Многоуровневое представление, соответствующее BDD (рис. 2.3), состоит из совокупности булевых формул

/i =*ivi v*iv2; fi =*iV5 v*iv6; vi =*251 у*2ф2;

|/2=*2фз; Ж5=*2фз; Фб =*2ф5 VX2(p6; ф2 = *352 V ХЗД;

Фз =хзХз; ф5 =*з52; фб =*з52; 51 =*4X1; 52 =*4X3 vx4X2;

54 = *4X45X1 =*5<»i; Х2 = *5<»1 VX5; Хз =*5;а>1 = *б. (2.4)

Диаграмма двоичного выбора для системы функций

Рис. 2.3. Диаграмма двоичного выбора для системы функций

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

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

 
Посмотреть оригинал
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >