Матричные схемы алгоритмов (МСА)
Синтез микропрограммных
Автоматов.
МПА и их особенности.
МПА - управляющие автоматы, форми- рующие последовательности сигналов, инициирующих выполнение микропрог- рамм в операционных автоматах (объек-
тах управления).
МПА обладает рядом особенностей:
· это инициальные автоматы (имеющие начальное состояние);
· это циклические автоматы (многократно формирующие последовательность управляющих сигналов);
· это структурные автоматы с кодированными (как правило двоично) входным и выход-ным алфавитами, причем с достаточно большим числом входов и выходов.
Для МПА используются свои специфи-
ческие методы анализа и синтеза, так
как большое число выходов и особенно
входов затрудняет применение канони-
ческих методов.
МПА в простейшем случае взаимодей- ствуют с ОА только по выходам.
![]() |
Здесь микропрограммы не имеют раз- ветвлений - они безусловны.
В общем случае МПА работает в контуре, причем не только с ОА, но и с внешней средой, выполняющей роль управления более высокого уровня. Сигналы внешней среды инициируют требуемую работу УА в зависимости от состоя-ний УА и ОА.
Микропрограммы здесь могут быть условными,
зависящими от оповещающих сигналов.
Обычно МПА рассматривается для контура
«УА-ОА» .В этом контуре хотя бы один из автоматов имеет задержку – является авто-
матом Мура или автоматом Мили с задерж-
кой. Микропрограммирование должно учи-тывать взаимодействие УА и ОА.
Рассмотрим варианты такого взаимо-
действия.
1. Пусть УА - автомат с задержкой, а ОА - автомат Мили (по оповещаю-щим сигналам).
\ Y(t+1) = j(Y(t))
Микрокоманда в такте (t+1) зависит от результатов микрокоманды такта t.
2. УА - автомат Мили.
ОА - автомат с задержкой
\ Y(t+1) = j(Y(t)). Микрокоманда в такте (t+1) зависит от результатов микрокоманды такта t.
3. УА и ОА оба с задержкой
![]() |
\ Y(t+2) = j(Y(t))
Микрокоманда в такте (t+2) зависит от результатов микрокоманды такта t.
Чаще всего УА строятся как автоматы с
задержкой , а ОА - как автоматы Мили
(по оповещающим сигналам).
Граф- схемы алгоритмов (ГСА)
См. методичку
Першеев В.Г. «Построение МПА»,
раздел 2
Матричные схемы алгоритмов (МСА)
См. методичку
Першеев В.Г. «Построение МПА», раздел 3
![]() |


|
|
|
|
|
|
|







|
|
|


|
|
|
|
|
МСА по строкам описывается формулами переходов.
Продолжение примера.
Кн®К1
К1®x1K2 Ú 1x2К3 Ú
1
2К4
К2®К3
.
.
.
Формулы переходов МСА обязательно ортогональны (условия переходов к раз-
ным столбцам несовместимы)
Кi® 1Кj Úx2Кp Ú...
Если МСА полностью определена, все ее формулы переходов полны: дизъюнкция
условий по строке (любой) равна 1.
Переходя от ГСА к МСА , мы получаем полностью определенную МСА . Недоопределенной МСА соответствует фраг-
мент ГСА (часть вершин такого фрагмента не будет иметь связей).