Поттосин Ю.В. Дискретная математика и теория проектирования цифровых устройств и систем
Подождите немного. Документ загружается.
121
g
(x
1
, x
2
, x
3
) = x
1
x
2
x
3
∨
x
1
x
2
x
3
,
ϕ′
(g, x
4
) = g
x
4
∨
g x
4
.
Для функции g и разбиения (Z
1
, Z
2
) карта декомпозиции представлена в
виде табл. 16.8.
Таблица 16.8
Карта декомпозиции для функции g
х
3
х
1
х
2
0 1
0 0 0 0
0 1 1 0
1 0 1 0
1 1 0 0
Окончательно получаем
f(x
1
, x
2
, x
3
, x
4
) =
ϕ
(g
2
(g
1
(x
1
, x
2
), x
3
), x
4
) = g
2
x
4
∨
g
2
x
4
;
g
2
(g
1
, x
3
) = g
1
x
3
;
g
1
(x
1
, x
2
) = x
1
x
2
∨
x
1
x
2
.
Параллельная разделительная декомпозиция по разбиению (Z
1
, Z
2
, … , Z
m
)
приводит функцию f(х) к виду
f(х) =
ϕ
(g
1
(z
1
), g
2
(z
2
), … , g
m
(z
m
)). (16.1)
Эта форма соответствует схеме, приведенной на рис. 16.4.
х z
1
g
1
ϕ
= f
z
2
g
2
…
z
m
g
m
Рис. 16.4. Структура, соответствующая суперпозиции f
(x) =
ϕ
(g
1
, g
2
, … , g
m
)
122
У т в е р ж д е н и е 16.3. Булева функция f
(x) допускает параллельную
разделительную декомпозицию вида (16.1) тогда и только тогда, когда она
допускает двухблочные разделительные декомпозиции вида
f
(x) =
ϕ
1
(g
1
(z
1
), z
2
, … , z
m
);
f
(х) =
ϕ
2
(z
1
, g
2
(z
2
), … , z
m
);
…
f
(x) =
ϕ
т
(z
1
, z
2
, … , g
m
(z
m
)).
Пусть функция f
(x) задана с помощью табл. 16.9. Эта таблица является
картой декомпозиции для разбиения ({x
1
, x
2
, x
3
}, {x
4
, x
5
, x
6
}). Среди ее строк
имеется только два различных значения, следовательно, заданная функция
допускает декомпозицию вида
f
(х) =
ϕ
1
(g
1
(x
1
, x
2
, x
3
), x
4
, x
5
, x
6
),
а если строки заменить одноименными столбцами, то убедимся, что существует
суперпозиция
f
(х) =
ϕ
2
(x
1
, x
2
, x
3
, g
2
(x
4
, x
5
, x
6
)).
Таблица 16.9
Задание функции f
(х)
х
4
х
5
х
6
х
1
х
2
х
3
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1
0 0 0 1 0 1 1 1 0 1 0
0 0 1 1 0 1 1 1 0 1 0
0 1 0 0 1 0 0 0 1 0 1
0 1 1 0 1 0 0 0 1 0 1
1 0 0 0 1 0 0 0 1 0 1
1 0 1 0 1 0 0 0 1 0 1
1 1 0 0 1 0 0 0 1 0 1
1 1 1 1 0 1 1 1 0 1 0
Таким образом, заданная функция f
(х) допускает параллельную
разделительную декомпозицию вида f
(х) =
ϕ
(g
1
, g
2
).
Определим функцию g
1
как
g
1
(x
1
, x
2
, x
3
) =
х
1
х
2
∨ х
1
х
2
х
3
.
Тогда табл. 16.10 будет задавать функцию
ϕ
1
. По этой таблице получим
123
g
2
(x
4
, x
5
, x
6
) =
х
6
∨
х
4
х
5
.
После соответствующего кодирования столбцов значениями переменной g
2
будем иметь
ϕ
1
(g
1
, g
2
) =
g
1
g
2
∨ g
1
g
2
.
Таблица 16.10
Задание функции
ϕ
1
(g
1
,
x
4
,
x
5
,
x
6
)
х
4
х
5
х
6
g
1
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1
0 0 1 0 0 0 1 0 1
1 1 0 1 1 1 0 1 0
16.4. Неразделительная декомпозиция
При неразделительной декомпозиции множества аргументов Z
1
, Z
2
, … , Z
m
могут пересекаться. Рассмотрим двухблочную неразделительную
декомпозицию
f
(x) =
ϕ
(g(z
1
), z
2
),
где компонентами векторов z
1
и z
2
являются переменные из множеств Z
1
и Z
2
соответственно, причем
Z
1
∪ Z
2
= X, Z
1
∩ Z
2
≠ ∅.
Естественно, имеет смысл решать задачу такой декомпозиции только при
|
Z
1
| < |
X
| и |
Z
2
| + 1 < |
X
|.
Особенностью карты декомпозиции для такой задачи является то, что
некоторые ее элементы находятся на пересечении строки и столбца, в кодах
которых одна и та же переменная (принадлежащая как Z
1
, так и Z
2
) имеет
противоположные значения. Значение функции для такого элемента не
определено. Это можно представить как внесение новых аргументов, число
которых равно |
Z
1
∩ Z
2
|. При этом каждый из них связан с каким-либо из
заданных аргументов так, что он не может принимать неодинаковое с ним
значение. Таким образом, данную задачу можно решить как задачу
неразделительной декомпозиции не полностью определенной булевой
функции.
124
У т в е р ж д е н и е 16.4. Булева функция f
(х) допускает двухблочную
неразделительную декомпозицию вида f
(x) =
ϕ
(g(z
1
), z
2
) тогда и только тогда,
когда граф ортогональности строк карты декомпозиции для (Z
1
, Z
2
) является
бихроматическим.
Это справедливо как для полностью, так и для не полностью определенных
функций.
Пусть функция f
(x
1
, x
2
, x
3
, x
4
, x
5
) имеет значение 1 на следующих наборах
значений переменных:
х
1
х
2
х
3
х
4
х
5
0 0 0 0 0
0 0 0 1 0
0 0 1 1 0
0 0 1 1 1
0 1 0 0 0
0 1 0 0 1
0 1 1 0 0
0 1 1 0 1
1 0 0 0 0
1 0 0 1 0
1 0 1 1 0
1 0 1 1 1
1 1 0 0 0
1 1 0 0 1
1 1 1 0 0
.
Положим, что для нее требуется получить суперпозицию
f
(x
1
, x
2
, x
3
, x
4
, x
5
) =
ϕ
(g
(x
1
, x
2
, x
3
), x
2
, x
4
, x
5
).
Карта декомпозиции для такого случая представлена в табл. 16.11.
Таблица 16.11
Карта декомпозиции для f(x
1
, x
2
, x
3
, x
4
, x
5
) =
ϕ
(g(x
1
, x
2
, x
3
), x
2
, x
4
, x
5
)
х
2
х
4
х
5
х
1
х
2
х
3
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1
0 0 0 1 0 1 0 – – – –
0 0 1 0 0 1 1 – – – –
0 1 0 – – – – 1 1 0 0
0 1 1 – – – – 1 1 0 0
1 0 0 1 0 1 0 – – – –
1 0 1 0 0 1 1 – – – –
1 1 0 – – – – 1 1 0 0
1 1 1 – – – – 1 0 0 0
125
Граф ортогональности строк данной карты декомпозиции изображен на
рис. 16.5, где вершины обозначены кодами соответствующих строк карты
декомпозиции, а в скобках показана раскраска вершин графа – цвет «0» и цвет
«1». Считая данные коды наборами значений аргументов х
1
, х
2
, х
3
функции g, а
величины в скобках – ее соответствующими значениями, получим
g(x
1
, x
2
, x
3
) =
x
2
x
3
∨
x
1
x
2
∨
x
2
x
3
.
000 (0) 001 (1) 011 (1) 010 (1)
101 (1) 100 (0) 111 (0) 110 (1)
Рис. 16.5. Граф ортогональности строк карты декомпозиции
По табл. 16.12, задающей функцию
ϕ
, получим ДНФ этой функции:
ϕ
(g, x
2
, x
4
, x
5
) = g
x
2
x
4
∨ g
x
2
x
4
∨
g
x
4
x
5
∨
g
x
2
x
5
.
Многоблочные неразделительные декомпозиции получаются аналогично
двухблочным неразделительным декомпозициям.
Таблица 16.12
Задание функции
ϕ
(g,
x
2
,
x
4
,
x
5
)
х
2
х
4
х
5
g
1
0 0 0 0 0 1 0 1 0 0 1 1 1 0 0 1 0 1 1 1 0 1 1 1
0 1 0 1 0 1 0 0 0
1 0 0 1 1 1 1 0 0
16.5. Декомпозиция систем булевых функций
Рассмотрим следующую задачу. Пусть задана система не полностью
определенных булевых функций f
1
, f
2
, … , f
m
от общего множества аргументов
Х = {x
1
, x
2
, … , x
n
}. Для заданной пары подмножеств (Z
1
, Z
2
) множества Х, такой,
что X = Z
1
∪ Z
2
, требуется найти суперпозиции
f
i
(x) =
ϕ
i
(g
1
(z
1
), g
2
(z
1
), … , g
k
(z
1
), z
2
), i = 1, 2, … , m, (16.2)
где z
1
и z
1
– векторы, компонентами которых служат переменные из множеств
Z
1
и Z
2
, причем
k < |
Z
1
|, k + |
Z
2
| ≤ n
126
и не важно, пересекаются или нет подмножества Z
1
и Z
2
.
В векторной форме данную задачу сформулируем следующим образом:
для системы функций y = f
(x) требуется найти суперпозицию
y =
ϕ
(w, z
2
), w = g
(z
1
),
такую, чтобы число компонент вектора w было меньше числа компонент
вектора z
1
, а сумма чисел компонент векторов w и z
2
была меньше длины
вектора х. Дополнительно можно еще поставить задачу минимизации числа
компонент вектора w.
Эта задача имеет приложение в синтезе логических схем из блоков,
реализующих достаточно сложные системы булевых функций, с ограниченным
числом внешних полюсов.
Для решения рассматриваемой задачи используется карта декомпозиции.
Так же, как и для одной функции, строки ее соответствуют значениям
векторной переменной z
1
, столбцы – значениям векторной переменной z
2
. На
пересечении строки и столбца помещается значение вектора у (компоненты
которого задают значения, которые принимают функции системы на
соответствующих наборах значений аргументов). Ввиду неполной
определенности функций здесь не обязательно должно быть
||
1
2
Z
строки и
||
2
2
Z
столбца.
Каждую строку карты декомпозиции рассматриваем как троичный вектор,
составленный из векторов значений функций.
У т в е р ж д е н и е 16.5. Система не полностью определенных булевых
функций f
1
, f
2
, … , f
m
допускает декомпозицию в форме (16.2) тогда и только
тогда, когда хроматическое число графа ортогональности строк ее карты
декомпозиции для (Z
1
, Z
2
) не превышает 2
k
.
Если удастся раскрасить упомянутый граф в 2
k
цвета, то закодируем строки
карты декомпозиции значениями векторной переменной
w = g
(z
1
) = (g
1
(z
1
), g
2
(z
1
), … , g
k
(z
1
))
так, чтобы строки, соответствующие одноцветным вершинам, были
закодированы одним кодом, а строки, соответствующие вершинам различных
цветов, – различными кодами. Таким образом, значениям векторной
переменной z
1
ставятся в соответствие значения векторной переменной w, т. е.
построена система функций g
1
(z
1
), g
2
(z
1
), … , g
k
(z
1
).
Карту декомпозиции, строкам которой приписаны значения переменной w,
а столбцам – значения векторной переменной z
2
, можно рассматривать как
представление системы функций y =
ϕ
(w, z
2
).
Пусть, например, задана система слабо определенных булевых функций
127
у
1
= f
1
(х), у
2
= f
2
(х), у
3
= f
3
(х),
где х = (x
1
, x
2
, х
3
, х
4
, х
5
, х
6
), и заданы векторные переменные
z
1
= (x
1
, x
2
, х
3
, х
4
), z
2
= {x
5
, x
6
}.
Заданная система представлена в виде пары булевых матриц, одна из
которых содержит наборы значений аргументов (значения вектора х), другая
представляет значения функций на этих наборах (значения вектора у).
Считается, что на всех наборах значений аргументов, которые не присутствуют
в соответствующей матрице, все функции заданной системы не определены.
Матрицы имеют следующий вид:
0
1
0
1
0
1
0
0
1
0
0
0
1
0
1
0
1
1
1
0
0
1
0
0
0
0
1
0
0
0
1
0
1
1
1
0
0
1
0
0
1
0
0
0
1
0
0
1
1
0
0
0
1
0
1
1
0
0
0
1
654321
хххххх
,
10
9
8
7
6
5
4
3
2
1
1
1
0
1
1
0
0
1
0
1
0
0
0
0
1
0
1
0
1
1
0
1
1
0
0
1
1
1
0
0
321
ууу
.
Карта декомпозиции системы булевых функций приведена в табл. 16.13.
Граф ортогональности строк матрицы изображен на рис. 16.7. У вершин графа
показаны наборы значений переменных x
1
, x
2
, x
3
, x
4
, которые приписаны
соответствующим строкам карты декомпозиции.
0 1 1 0 (0 0) 0 1 0 0 (0 0)
1 0 0 0 (0 1)
1 1 1 0 (0 1)
0 0 1 0 (0 0)
1 0 1 0 (1 1)
0 0 0 1 (1 0)
Рис. 16.6. Граф ортогональности строк карты декомпозиции
128
Таблица 16.13
Карта декомпозиции системы слабо определенных булевых функций
у
1
= f
1
(х), у
2
= f
2
(х), у
3
= f
3
(х)
х
5
x
6
x
1
x
2
x
3
x
4
0 0 0 1 1 1 1 0
1 0 0 0 0 1 1 1 0 0 – – – – – –
0 1 0 0 – – – – – – 0 1 0 – – –
0 1 1 0 0 0 1 – – – – – – 1 0 1
0 0 0 1 – – – 1 0 1 – – – 1 1 0
1 1 1 0 – – – – – – – – – 0 1 1
0 0 1 0 – – – 0 0 1 – – – – – –
1 0 1 0 – – – – – – – – – 1 0 0
Граф раскрашивается не менее чем в четыре цвета, поскольку в нем легко
заметен полный четырехвершинный подграф, все вершины которого должны
быть раскрашены в разные цвета. В скобках приведены коды цветов в виде
двухкомпонентных булевых векторов w = (w
1
, w
2
). В то же время четыре цвета
оказываются достаточными – в результате находится схема, показанная на
рис. 16.7
х
1
х
2
w
1
х
3
y
1
х
4
w
2
y
2
х
5
y
3
х
6
Рис. 16.7. Схема, реализующая систему из трех функций от шести переменных
Систему функций w
1
= g
1
(x
1
, x
2
, x
3
, x
4
), w
2
= g
2
(x
1
, x
2
, x
3
, x
4
) представим
следующими матрицами:
0
0
0
1
0
0
0
1
1
1
0
1
0
0
0
0
1
0
1
1
0
1
0
1
0
0
0
1
4321
хххх
,
7
6
5
4
3
2
1
1
0
1
0
0
0
1
1
0
0
1
0
0
0
21
ww
.
129
Табл. 16.14, полученную из табл. 16.13 совмещением неортогональных
одноцветных строк, можно считать заданием системы функций y =
ϕ
(w, z
2
).
Таким образом, заданная система не полностью определенных булевых
функций y = f
(x) разложена на две системы:
w = g
(z
1
) и y =
ϕ
(w, z
2
).
Последнюю представим парой матриц:
0
1
0
1
0
1
0
0
1
0
0
0
1
0
1
0
1
1
1
0
0
0
1
0
1
1
0
0
0
1
0
1
1
0
0
0
1
0
0
0
6521
xxww
,
10
9
8
7
6
5
4
3
2
1
1
1
0
1
1
0
0
1
0
1
0
0
0
0
1
0
1
0
1
1
0
1
1
0
0
1
1
1
0
0
321
yyy
.
Таблица 16.14
Задание системы булевых функций y =
ϕ
(w, z
2
)
x
5
x
6
w
1
w
2
0 0 0 1 1 1 1 0
0 1 0 1 1 1 0 0 – – – 0 1 1
0 0 0 0 1 0 0 1 0 1 0 1 0 1
1 0 – – – 1 0 1 – – – 1 1 0
1 1 – – – – – – – – – 1 0 0
После минимизации получим следующие ДНФ:
w
1
= x
1
x
2
x
3
∨ x
4
;
w
2
= x
1
;
y
1
=
w
2
x
5
x
6
∨ w
1
∨ w
2
x
6
;
y
2
= x
5
x
6
∨w
1
w
2
x
6
∨ w
1
w
2
x
5
;
y
3
=
w
1
x
6
∨
w
2
x
5
.
130
Г л а в а 17
Синтез комбинационных схем методом факторизации
Рассмотрим следующую задачу. Задана система полностью определенных
булевых функций и задан базис – набор логических элементов И, ИЛИ с
ограниченным число входных полюсов. Требуется построить схему с
наименьшим по возможности числом элементов. Система функций
минимизирована и задана в виде системы ДНФ. Имеется в виду матричное
представление системы ДНФ, т. е. задана пара матриц: троичная матрица Х,
представляющая множество элементарных конъюнкций, и булева матрица Y,
представляющая отношение вхождения между элементарными конъюнкциями
и ДНФ.
Суть метода факторизации состоит в вынесении за скобки в ДНФ
некоторых факторов (множителей).
Пусть k – число входных полюсов логического элемента в заданном
базисе. Не нарушая общности, будем считать, что оба элемента И и ИЛИ
заданного базиса имеют одно и то же число входных полюсов. Синтезируемую
схему представим системой уравнений вида h
i
=
p
iii
zzz ooo ...
21
, каждое из
которых представляет функцию, реализуемую элементом из заданного базиса
(И, ИЛИ). Здесь h
i
,
j
i
z (j = 1, 2, … , p) – переменные, соответствующие
полюсам базисных элементов, o – символ операции конъюнкции (∧) или
дизъюнкции (∨).
17.1. Реализация конъюнкций
Для реализации элементарных конъюнкций выполняются следующие
действия.
1. Матрица Х преобразуется в матрицу Х
′
, где каждому столбцу х
i
матрицы
Х соответствует два столбца х
i
и
х
i
, значения которых определяются
следующим образом: значение 0 в столбце х
i
преобразуется в значения 0, 1 в
столбцах х
i
,
х
i
; значение 1 – в значения 1, 0; значение «–» – в значения 0, 0.
2. В матрице Х
′
отыскивается минор, содержащий только единицы и
образованный не более чем k столбцами и как можно большим числом строк.
3. Все единицы матрицы Х
′
, входящие в полученный минор, заменяются
нулями, в матрицу Х
′
добавляется столбец g
j
+ 1
, где j – число столбцов, которое
к данному моменту приобрела матрица Х
′
в результате выполнения
рассматриваемых действий. Этот столбец имеет единицы в строках минора и
нули – в остальных строках. В формируемую систему уравнений вносится
уравнение g
j
+ 1
=
p
iii
zzz ∧∧∧
...
21
, где
j
i
z (j = 1, 2, … , p) – литерал,
соответствующий столбцу, входящему в выделенный минор.