ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 23.10.2024
Просмотров: 105
Скачиваний: 0
= 1, . . . , п). Из ф , . . |
. , ф , ф |
с учетом распределения сдвигов |
имеем: |
|
|
Ф*. = Ол'Л'х; |
ф*, = ххх\\ |
|
Ф'ѵ —ö ; |
ф‘ѵ-5= xlxx; |
|
ф у - а = |
І х ѵ л '; |
ф * , к = 0 . |
После этого исходное покрытие (7-7) сокращается следующим об
разом. Пусть ф*, = |
С === 0 |
и пусть cpY (/ — некоторый отмеченный |
куб в покрытии У), |
Если |
хотя бы одна связанная координата в d |
не совпадает с соответствующей связанной координатой в ср, то ср Yq из покрытия Y t удаляется. Например, в покрытии Ух у куба Пхх | 3 первая (связанная) координата не совпадает с первой (связанной) координатой ф*, = Олжс, и потому куб 11а'а'|3 из покрытия должен
быть удален. В остальных кубах покрытия Yt все совпадающие с d связанные координаты заменяются свободными, все прочие коорди наты не меняются. Таким образом, покрытие Уг примет вид:
А'10А' 1
Y 1 ХІ 1 X 5
аОа'А' к.
Аналогом рассмотренного выше перехода от MCA М' к MCA М " являются следующие преобразования. В исходном покрытии индек сом 2 отмечен только куб Y5\xxxx\2. Так как ф*, ==|а1аа|, находим
пересечение хххх П хіхх = аТ.ѵа'.1 Далее покрытие Y &\xxxx\2 заме
няем на У5 1aIa'a'J 2, после чего сразу же fy = хіхх, фКз = хіхх,
Ф* аі.ѵа, и покрытие У, преобразуется рассмотренным только
I а
что способом к виду
А'А'А' 1 5
Уо
хххО к,
а покрытие У51х\хх | 2 вновь заменяется на первоначальное У51хххх | 2 Таким образом, исходное покрытие (7-7) заменяется покрытием ■
|
Оххх |
1 |
|
Юа'х 3 |
|
|
Пхх |
5 |
|
Уі X Юа' |
1 |
|
х П х |
5 |
|
хОхх |
к |
1 Это равносильно |
умножению сс53 = 1 |
на ср^ = х2 при аналитическом |
представлении функций |
перехода. |
|
162
XXX 1 5
XXX 0 к
у 8 хххх к
Y, X 1,хх 5
хОхх к
пхххх 2 .
Поскольку в правом столбце отсутствует цифра 4, покрытие Y4 может быть удалено, так как к оператору У4 нет путей ни из одного оператора (ау4 = 0 для всех j = О, 1, . . . , 5). Полученное в резуль тате покрытие оказывается существенно проще исходного.
7-3. Минимизация операторных вершин в граф-схеме алгоритма
Минимизация операторных вершин в полностью определенной ГСА может быть осуществлена методом, аналогичным предложенному В. М. Глушковым для минимизации микропрограмм [6 ]. Поясним его
на примере ГСА на рис. 7-14, имеющей начальную, конечную, 10 опе раторных и 6 условных вершин. Будем интерпретировать граф-схему как автомат Мура, состояния которого отождествлены с начальной, конечной и операторной вершиной, а функция переходов определена так же, как в § 5-2 при синтезе микропрограммного, автомата Мура по ГСА. В качестве выходного сигнала берется оператор, записанный
163
Таблица 7-16
А в т о м а т М у р а , с о о т в е т с т в у ю щ и й Г С А н а р и с . 7 - 1 4
Исходное состояние |
Состояние |
Входной |
|
и выходной сигнал |
перехода |
сигнал |
|
Я,(>'о) |
ff2 |
1 |
|
Я-лО"і) |
я.ч |
Хі |
|
О.] |
Хі |
||
|
|||
* 3 ( T g) |
|
1 |
я і ( Т з )
°-о(Уг)
а 0( Ѵ й)
<h(Ys)
о 6( Т з )
Я в ( І 'х )
а ю |
Л-., |
Оц |
Х.І |
«о |
Л 2*^х |
Л? |
ЛГо.Ѵ'1 |
Оо |
х гх і |
« 8 |
Л'2-Vi |
« з |
1 |
°1 0 |
Х-1 |
О ц |
|
° І 0 |
A'j |
« и |
|
я 0 |
* 1 |
а$ |
А'і |
aao(T.j) |
а к |
i |
О ц { у ь) |
Ок |
1 |
а к( У к) |
а к |
1 |
Класс
эквивалент ности
А о
А і
2
A 3
Разбиение яп
Исходное
состояние
ивыходной
сигнал
я . О ' о )
а г { У і)
п б ( Г і )
f l .( V 'i )
а з ( ^ 2 )
° о ( Г 2)
я - і ( Г з )
а 7 ( ^ з )
° а ( Г з )
я1 о ( ^ 4 )
Оц ( Г 6)
Класс
перехода
А,
А3
А,
А3
Ао
А3
Аз
Аз
Аі
1А г
A t
Аъ
Аз
Аь
АА
Аъ.
A q
A q
Таблица 7-17
Входной
сигнал
1
*і
■ь
ЛѴѴ'і
.Ѵ2Л.'і
*2 * 1
*2 * 1
* 1
X1
1
1
. x 4
Xi
Xi
Xi
x 4
X4
1
1
A q |
a K( Y K) |
А, |
1 |
в соответствующей данному состоянию вершине, |
причем в начальном |
||||||||||||||
состоянии а1 выдается выходной сигнал |
Y 0, |
а в конечном состоянии |
|||||||||||||
Y |
~ ___Yi |
ак — сигнал |
Ук. Прямая |
таблица переходов мик- |
|||||||||||
0 |
ропрограммного автомата Мура приведена в табл. |
||||||||||||||
Г,----- |
7-161. |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Далее |
производится |
|
минимизация |
автомата |
|||||||||
|
|
Мура путем разбиения множества состояний на |
|||||||||||||
|
|
классы |
0-, |
1-, . . . , |
|
k-, |
/г + |
1-эквивалентных |
|||||||
|
|
состояний до совпадения |
разбиений |
на двух сле |
|||||||||||
|
|
дующих друг за другом шагах так, |
как изложено |
||||||||||||
|
|
в § 5-4. Разбиение на 0-классы: |
|
|
|
|
|||||||||
|
|
|
|
^ ii ^2’ |
Лз> |
/lj, |
Ah, |
А,)}; |
q= |
{ ), |
|||||
|
|
Л 1 |
{Оз 1 |
Об) |
Яо) . ^ |
2 = |
1&3I |
Go}. |
Л з = |
(Cl^, |
ö - , |
Qg ], |
|||
|
|
|
^ |
4 = |
l a lo)> |
^ 5 = | й ц | , |
Л о : = |
| £?K}. |
|
|
|||||
|
|
Рис. 7-15. |
Разбиение |
строящейся |
ГСА с минимальным |
||||||||||
|
|
|
|
|
числом операторных вершин |
|
|
|
|||||||
|
Таблица разбиений я 0 сведена в табл. |
7-17. |
|
|
|
|
|
|
|||||||
|
Из этой |
таблицы |
|
|
|
|
|
|
|
|
|
|
|
|
|
-М |
[В0, Ві, |
В2, В3, В4, |
Bq, ІЗ(з}, Bq-- |
{^l} , Bl -- {^2» Я5, |
Ц9] , |
B2 -- |
{Ö3, |
||||||||
a e)> |
^ 3 = l ö 4> ß 7i ö 8j'> |
^ 4 = |
{а 1 оЬ |
^ 5 = |
{a llj> |
-Sß ==: {а к} » |
= |
3T0 - |
|||||||
Последовательность разбиений завершена. Выбирая из каждого класса по одному состоянию, получим таблицу переходов ми нимального автомата Мура (табл. 7-18), от которой необходимо перейти к граф-схеме, равносильной исходной, но содержащей начальную, конечную и пять операторных вершин.
Для этого аналогично изложенному в § 7-1 делаем разбиение будущей ГСА на подграфы
(рис. 7-15)2.
По числу подграфов получаем четыре под системы формул перехода:
1. |
Yi, |
Yl - Y i \ |
|
|
2. Уг-* |
^ г Ѵ ^ з ; |
(7-8) |
|
|
3. Y s ^ |
XqY 4 |
\J XiY 5', |
|
|
|
Рис. 7-16. ГСА с мини |
|||
4. V4 -+ |
|
Y * - + Y K. |
|
|
|
|
мальным числом опера |
||
1 Так как после минимизации необходимо полу |
торных вершин |
|||
чить ГСА, у которой должны быть начальная и ко нечная вершины, конечная вершина исходной ГСА
выделяется в самостоятельное состояние. Поскольку в ГСА нет пути из конечной
вдругие вершины, то на уровне автомата Мура из состояния ак нет переходов
вдругие состояния, т. е. под действием любого входного сигнала автомат ос
тается в состоянии ак. Этому соответствует последняя строчка в табл. 7-16.
- Можно было бы от табл. 7-18 тривиальным образом перейти к MCA и да лее от MCA к ГСА, но это можно сделать и непосредственно по табл. 7-18.
166
Далее, если мы хотим минимизировать и условные вершины в по лученных подграфах, необходимо воспользоваться методом миними зации из § 7-1 или искать (путем перебора) близкую к минимальной систему скобочных формул перехода. Система (7-8) уже представляет собой систему скобочных формул, притом минимальную — это оче видно из полученных выражений. По системе (7-8) построена мини мальная граф-схема алгоритма на рис. 7-16.
Таблица 7-18
Минимальный автомат Мура
Исходное состояние н пыходноі'1 сигнал
Щ(Го)
а г ( Г і )
a»(Yt)
a i ( Y a )
ЩоОС)
МП )
Як(Гк)
Состояние |
Входной |
перехода |
сигнал |
СІ-2 |
1 |
“ з |
х і |
0 .1 |
* і |
о 2 |
1 |
|
|
й 1 0 |
. х і |
« и |
X . , |
Як |
1 |
|
|
ак |
1 |
ак |
1 |
7-4. Объединение граф-схем алгоритмов
При описании алгоритма работы сложной системы часто представ ляется целесообразным построение нескольких ГСА, каждая из ко торых описывает часть общего поведения системы (частные ГСА). На пример, при проектировании устройства управления арифметического устройства проще отдельно построить граф-схемы алгоритмов выпол нения операций сложения, вычитания, умножения и деления! Оче видно, что в этих ГСА некоторые операторные и условные вершины будут одинаковыми, и если для каждой ГСА синтезировать отдельный автомат управления, то результат синтеза может быть далеко не оп тимальным. В связи с этим возникает задача объединения частных ГСА в единую граф-схему, решение которой позволит минимизиро вать суммарное число операторных и условных вершин. -
167