Файл: Горбатов В.А. Синтез композиции операционного и управляющего автоматов в вычислительной технике учеб. пособие.pdf
ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 05.08.2024
Просмотров: 57
Скачиваний: 0
учитывающей теоретико-структурные свойства булевой функ ции и не требующей перебора всех ТДНФ этой функции.
Рассмотрим более подробно процесс приведения произ вольного мографа к решетчатому виду.
Количество меток каждой вершины щ мографа равно соб ственной частоте соответствующей буквы модели, а количе ство общих меток для пары вершин щ и щ —значению вза имной частоты соответствующих букв.
Следовательно, дугу (t, /) мографа можно характеризовать
тремя |
величинами fi}, fa, /«, где fa —собственная частота |
буквы |
l) 'fjj — собственная частота буквы /; fa — взаимная |
частота букв і и / (і ф /) • Рассматривая процесс образования циклов нечетной дли
ны с циклической перестановкой весов и гомоморфных им подмографов, замечаем, что обобщенные буквы [11] не могут образовать таких графов, но чем больше не выполняется усло вие обобщенных букв, тем больше вероятность вхождения этой пары букв в подмографы типа А или В [11]. Другими сло вами, чем больше сумма собственных частот букв і и jifu + fa ) при данной взаимной частоте fa, тем больше вероятность вхождения этих букв в подмодели вида i|)rQ(2,1) [11]. Чем. меньше взаимная частота букв / (fiS) при данной сумме их собственных частот, тем больше вероятность вхождения букв /, j в подмодели вида cprQ(2,1).
Будем характеризовать каждую дугу (і, /) мографа (слог модели) ф(/) значением производной от модели, вычислен ной на соответствующем слоге
/и — 2/~,•/ + fa
(4-1)
fu
Тогда, чем больше значение производной, тем больше степень неодинакового участия букв в словах; чем* больше неоднородность мографа, тем большая вероятность образова-. ния’ подмоделей вида cprQ (2,1) в этой модели, тем более сложный (в смысле числа элементов) будет соответствовать этой модели синтезируемый функциональный граф. Поэто му максимальный интервал I функции, которому соответст вует полный подграф в мографе, можно оценить как
fit — ii + fit |
(4-2) |
|
tii |
||
|
где r — ранг интервала I.
4* |
51 |
Следовательно, используя критерий решетчатости [11], можно, оценивая каждый максимальный интервал, синтези ровать ТДНФ функции, учитывая при атом теоретико-струк турные свойства этой функции. Другими словами, критерий решетчатости позволил предложить критерий с целью выяс нения, «какой из максимальных интервалов является лиш ний» при синтезе минимальных булевых графов.
Используя оценку (4-2) максимальных интервалов, пред ложим следующий алгоритм синтеза оптимального ТДНФ функции f с учетом ее теоретико-структурных свойств.
Для определения, какая простая импликанта функции яв ляется «лишней», предложим1следующую процедуру:
1. Совершенную ДНФ функции f задаем в виде матрицы инцидентности Q.
2.Выделяем простые импликанты функции f и записы ваем их в список I.
3.Строим ядро функции /. Если оно пусто, то переходим
кпункту б, в противном случае из списка I вычеркиваем элементы ядра и переходим к пункту 4.
4.В матрице Q заменяем конституенты единицы функции покрываемые вычеркнутыми из списка I простыми импли-
кантами, на простые импликанты.
5.Если любая строка матрицы Q представляет собой простую импликанту, то переходим к пункту 8, в противном случае — к пункту б.
6.По матрице Q строим частотную матрицу F (F = Q TXQ).
7.Согласно (4-2) оцениваем каждую простую импликанту
из списка I. Выбираем простую импликанту с минимальной оценкой. Выбранную простую импликанту' вычеркиваем из списка I и переходим к пункту 4.
8. Полученная матрица Q задает минимизированную бу леву функцию с учетом ее теоретико-структурных свойств.
Проиллюстрируем эту процедуру на следующем примере. Минимизировать с учетом теоретико-структурных свойств булеву функцию f(x\, %2, жз, ац), равную 1 на наборах, деся
тичные эквиваленты которых есть 2, 3, 4, 5, 8, 9, 11, 12, 14, 15, и принимающую значение равное 0 на остальных, наборах.
52
Пункт 1. Матрица Q имеет вид
х і |
Хі |
Х2 |
*2 |
х з |
Хз |
Хі |
Х і |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 ' 0 |
1 |
|
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
Пункт 2. Список I простых импликант булевой функции / следующий:
001 - |
100- |
11 -0 |
010- |
-011 |
1-11 |
− 1 0 0 |
1 0 − 1 |
111 - . |
Пункт 3. Функция f имеет ядро, состоящее из обязатель ных простых импликант 010—, 001— и 100 — . После вы черкивания элементов ядра из списка I имеет вид
- 1 0 0 |
11 — 0 |
- 0 1 1 |
1 - 1 1 |
1 0 - 1 |
111 — |
Пункт 4. После соответствующей замены строк матрица Q имеет следующий вид:
Хі |
Х і |
Х2 |
Х2 |
х з |
Хз |
Х і |
Х і |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
О |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
’ l |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
53
Пункт 5. Четвертая по седьмую строки матрицы Q' не яв ляются простыми импликантами, поэтому переходим к пунк ту б.
Пункт 6. Частотная матрица отношений F '{ F '— (Q ')TX Q ') , соответствующая матрице Q', имеет вид
|
х \ |
Х і |
*2 |
Х2 |
*3 |
*3 |
Л/4 |
Х і |
|
|
5 |
0 |
3 |
2 |
3 |
2 |
2 |
2 |
|
|
0 |
2 |
1 |
1 |
1 |
1 |
0 |
0 |
|
|
3 |
1 |
4 |
0 |
2 |
2 |
1 |
2 |
|
|
2 |
1 |
0 |
3 |
2 |
1 |
1 |
0 |
|
|
3 |
1 |
2 |
2 |
4 |
0 |
2 |
1 |
|
|
2 |
1 |
2 |
1 |
0 |
3 |
0 |
1 |
|
|
2 |
0 |
1 |
1 |
2 |
0 |
2 |
0 |
|
|
2 |
0 |
2 |
0 |
1 |
1 |
0 |
2 |
|
Пункт 7. Оцениваем |
каждую |
простую |
іимпликанту из |
||||||
списка I, полученного в пункте 3. |
|
|
|
|
|||||
Согласно (4-2) имеем |
|
|
|
|
|
|
|
||
р ( X — 100) = |
р (х2 X, 7і ) = |
|
( 4 ~ 222 + 3 + |
||||||
+ |
' 4 - 2 - 2 + 2 + |
_ 3 — 2 - 1 -4- 2 ^ ^ |
0 9 1 |
||||||
р ( - |
011) « |
0,91 |
р (1 - 1 1 ) |
~ |
0,58 |
||||
р (10 - |
1) « |
'1,08 |
|||||||
р (11 — 0).~ |
0,58 |
р (111 - ) |
и |
0,67. |
|||||
Выбираем простую импликанту 11 — 0. Переходим к пункту 4.
Пункт 4. В матрице Q' заменяем конституенты единицы функции f, покрываемые 11 — 0, на эту простую импликанту. В результате получаем матрицу
Х і |
Х \ |
Х 2 |
Х 2 |
Х з |
*3 |
Х і |
Х і |
|
|
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
|
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
|
1 |
0 |
0 |
1 |
0 |
1 |
0 |
' 0 |
|
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
|
1 |
0. |
0 |
1 |
1 |
0 |
1 |
0 |
• |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
54
Пункт 5. Матрица Q" содержит конституенты • единицы функции fi, не являющиеся простыми импликантами. Пере ходим к пункту б.
Пункт 6. Частотная |
матрица |
отношений F ", соответст |
|||||
вующая Q", есть |
|
|
|
|
|
|
|
Хі |
Хі |
%2 |
X2 |
*3 |
*3 |
Xi |
Xi |
0 |
0 |
2 |
•2 |
2 |
1 |
2 |
1 |
0 |
2 |
1 |
1 |
1 |
1 |
0 |
0 |
2 |
l^ |
3 |
0 |
1 |
1 |
1 |
1 |
2 |
l' |
0 |
3 |
2 |
1 |
1 |
0 |
2 |
1 |
1 |
2 |
3 |
0 |
2 |
0 |
1 |
1 |
1 |
1 |
0 |
2 |
0 |
0- |
2 |
0 |
1 |
1 |
2 |
0 |
2 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
Пункт 7. Согласно (4-2) оцениваем простые импликанты из списка I, покрывающие оставшиеся конституенты едини
цы функции / |
|
|
|
р (-011) |
-0 ,7 5 |
р (1 - 1 1 ) |
«0,5, |
р ( 1 0 - 1 ) |
«0,91 |
р (111 - ) |
« 1,16. |
Выбираем простую импликанту 1 — 11. Переходим к пунк ту 4.
Пункты 4, 5 и 8. Полученная матрица Q '"
Xl |
Xl |
X2 |
X2 |
Хз |
*3 |
Xi |
Xi |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 " |
1 |
. 0 |
1 |
0 |
задает булеву функцию /, минимизированную с учетом ее теоретико-структурных свойств. Полученная тупиковая ДНФ функции соответствует минимальной решетчатой ДНФ функ ции f, сложность которой равна 10.
55
