Файл: Баранов, С. И. Синтез микропрограммных автоматов.pdf

Пусть имеются ГСА Г х, . . . , Гч, . . . , r Q, в каждой из которых операторы не повторяются, но среди различных граф-схем могут встречаться одинаковые операторы. Требуется построить объединен­ ную ГСА, которая равносильна каждой из ГСА Гч при тех условиях, когда должна выполняться эта ГСА r q (q = 1, . . . , Q).

Параллельно будем рассматривать пример объединения трех графсхем Г х, Г.,, Г3, изображенных на рис. 7-17. Решение задачи объеди­ нения разбивается на ряд этапов.

4. Строится объединенная MCA М, строки и столбцы которой от­ мечены всеми операторами, входящими в объединение множеств опера-

168

169

Объединенная MCA АТ, построенная по MCA М г, М 2, M s, приве­ дена в табл. 7-22.

Поскольку конъюнкция Pq (q = 1...........Q) равна единице все время, пока MCA М «работает» как MCA M q, ни один оператор не ме­ няет значений переменных p lt . . . , pN (относительно этих перемен­ ных имеем пустое распределение сдвигов), в связи с чем MCA М можно упростить. Так, переход к оператору У5 (столбец У5 в табл. 7-22) про­

исходит всегда при р, = р, = 0 (<р^_ = PjP2), поэтому в строке У5

можно переменные р г и р 2 заменить на р х = р 2 = 0. Точно так же

Для перехода от MCA AT к объединенной ГСА Г необходимо раз­ бить MCA М' на подматрицы и воспользоваться методом построения минимальной ГСА, изложенным в § 7-1, или попытаться найти (путем перебора) близкую к минимальной систему скобочных формул пере­ хода для каждой из подматриц. В обоих случаях следует учесть не­ определенности двух типов, которые возникают при объединении ча­ стных ГСА:

1 Среди строк, как и выше, пет оператора Ук, а среди столбцов—опера­ тора Y n.

170

1. Если число Q объединяемых ГСА меньше 2 Ы , т. е. не все наборы значений переменных р 4, . . . , pN используются для кодирования MCA М г, . . . . M Q, все формулы перехода (или отмеченные покрытия формул перехода) не определены на тех наборах значений переменных

набор р ±, р а = (10), т. е. все формулы перехода не определены на кубе

тие Yj) не определена на тех наборах значений переменных, которые

щих и входящих операторных вершин в одну вершину придем к объе­ диненной ГСА Г, изображенной на рис. 7-18. Эта ГСА построена с по­ мощью программ для ЦВМ М-220, реализующих алгоритмы из § 7-1. К тому же результату можно было бы прийти, если выписать из под­ матриц формулы перехода, доопределить их на неиспользуемых на­ борах значений переменных, после чего проминимизировать и при­ вести к системе скобочных формул. К сожалению, алгоритма подобных преобразований формул перехода, гарантирующего получение реше­ ния, близкого к минимальному, нет. Особые трудности возникают в не­ полностью определенных формулах перехода, и требуется значитель­ ный опыт и многократные попытки для получения хорошего решения. Например, чтобы прийти к той же граф-схеме, которая была получена с помощью методов § 7-1, необходимо доопределить формулы перехода с помощью выражений, заключенных в квадратные скобки, и преобра­ зовать их в систему скобочных формул следующим образом:

у 0 -> (РіРз*і V РіРз*7*Л/ РіРз*і V [Pi/WCi]) Yi V

V (№*1*3 V PlPA*3*e V PlP2*7*l*5 V РіРзхіхъV

V \РіРзхіхзх 7 V РіРгх іхзх вх ~У) E4V ІРіРзх іхзхе V [РіР-гх іхзхвх ~}) У 5 V

V (РіРв*7*1*6 V ~PlPlXlXb) Y 7 V (PlP3*7 V [РіРз*7І) ^S =

= Pi (x7Y 8 V x~(-И (Рг (хъУ 7 V хьУ -i) V Рг (хз (хс,Уa V *6_Ел) V хзУ 4)) V

V хіУ і)) V pi (xi (Рг (хьУ 7 V *пЕ4) V J2 (хз (хбУ 5 V y ^ j )

173