Микропрограммные автоматы (стр. 2 из 4)
Рисунок 2-Графы схемы алгоритмов
ГСА составляют так, чтобы обеспечить выполнение необходимых операций и проверку логических условий в соответствии со словесным описанием алгоритма.
На основании перечня микроопераций и реализующих их функциональных узлов составляется структурная схема ОА. Здесь широкими стрелками показаны шины, по которым передается информация, а тонкими – сигналы у, управляющие работой отдельных узлов или передачей информации по шинам.
ГСА должна удовлетворять следующим условиям:
1. Входы и выходы вершин соединяются друг с другом с помощью направленных всегда от выхода к входу.
2. Каждый выход соединен только с одним входом.
3. Любой вход соединяется, по крайней мере, с одним выходом.
4. Любая вершина ГСА лежит, по крайней мере, на одном пути из вершины «Начало» в вершину «Конец».
5. Один из выходов условной вершины может соединяться с ее входом, что недопустимо для операторной вершины. Такие условные вершины иногда называются возвратными.
6. В каждой условной вершине записывается логическое условие из множества логических условий. Разрешается в различных условных вершинах записывать одинаковые логические условия.
7. В каждой операторной вершине записывается оператор, представляющий собой выходной сигнал или совокупность выходных сигналов управляющего автомата. Разрешается в различных операторных вершинах записывать одинаковые операторы.
5. Содержательные граф-схемы алгоритмов
Обычно при проектировании различных устройств предварительно составляется так называемая содержательная ГСА, в которой внутри условных и операторных вершин записаны логические условия и микрооперации в содержательных терминах.
В качестве примера построим содержательную ГСА устройства, вычисляющего функцию знака числа:
Соответствующая содержательная ГСА представлена на рис. 3.
Рисунок 3. Содержательная ГСА функции определения знака числа
6. Синтез управляющего автомата по граф-схеме алгоритма
Конечный управляющий автомат, реализующий микропрограмму работы дискретного устройства, принято называть микропрограммным автоматом. Как уже отмечалось, микропрограмма отображается с помощью ГСА. Рассмотрим последовательность этапов синтеза управляющего автомата по его ГСА.
1. Запись словесного алгоритма функционирования операционного автомата (выполняемых операций) с учетом структуры операционного автомата.
2. Построение содержательной ГСА функционирования операционного автомата.
3. Построение отмеченной ГСА с учетом типа автомата.
4. Построение графа переходов автомата или таблицы переходов.
5. Проведение структурного синтеза автомата по его графу переходов известными методами, например, с помощью канонического метода структурного синтеза.
Построение отмеченной ГСА производится по содержательной ГСА. Для автоматов Мили и Мура процедура разметки имеет различия.
6.1 Построение отмеченной ГСА автомата Мили
Если необходимо построить микропрограммный автомат Мили, то содержательная ГСА управляющего автомата размечается в соответствии со следующими правилами:
1) символом состояния a1 отметить вход вершины, следующей за вершиной «Начало», а также вход вершины «Конец»;
2) входы всех вершин, следующих за операторными, должны быть отмечены символами а с последовательными индексами;
3) если выход вершины отмечается, то только одним символом;
4) входы различных вершин, за исключением вершины «Конец», отмечаются различными символами;
5) содержательные термины микроопераций и логических условий. заменяются их условными обозначениями: в каждой операторной вершине последовательно проставляются символы выходных сигналов, если в различных операторных вершинах записаны одинаковые микрооперации, то разрешается их отмечать одинаковыми символами выходных сигналов; если в различных условных вершинах записаны одинаковые логические условия, то разрешается их отмечать одинаковыми символами входных сигналов.
6.2 Построение отмеченной ГСА автомата Мура
Если необходимо построить микропрограммный автомат Мура, то содержательная ГСА управляющего автомата размечается в соответствии со следующими правилами:
1) символом a1 отмечаются вершины «Начало» и «Конец»;
2) различные операторные вершины отмечаются различными символами;
3) все операторные вершины должны быть отмечены.
4) содержательные термины микроопераций и логических условий. заменяются их условными обозначениями.
Содержательная ГСА (рис. 3.) после разметки по приведенному алгоритму представлена на рис. 5.
После получения отмеченной ГСА строится граф переходов автомата. Он имеет столько различных вершин, сколько различных букв аi с индексами имеется в отмеченной ГСА. Каждая вершина графа переходов автомата отмечается буквой а с соответствующим индексом.
Между двумя вершинами графа имеется дуга, если на отмеченной ГСА между вершинами с метками ai и ak, имеется путь. Над дугой ставится входной сигнал, равный конъюнкции логических условий соответствующего пути в отмеченной ГСА. При этом выполнению логического условия соответствует переменная без отрицания, а невыполнению логического условия – переменная с отрицанием на соответствующей дуге графа переходов автомата.
Если в отмеченной ГСА между упомянутыми вершинами с метками ai и аk имеется несколько путей, то в графе переходов автомата на дуге, связывающей аi и аk через символ дизъюнкции перечисляются все конъюнкции, соответствующие имеющимся путям.
Если строится граф переходов автомата Мура, то символы микроопераций (выходные сигналы управляющего автомата) записываются около соответствующих его вершин. Для автомата Мили символы микроопераций записываются на соответствующих дугах при конъюнкциях логических условий, описывающих путь через операторную вершину с рассматриваемой микрооперацией.
Если в отмеченной ГСА имеется безусловный переход между операторными вершинами, т.е. путь, не проходящий ни через какие условные вершины, то на графе переходов автомата ему соответствует дуга, которой приписывается входной сигнал «1», показывающий, что данный переход в автомате осуществляется при поступлении очередного синхросигнала.
В дальнейшем синтез проводится с помощью описанного ранее метода структурного синтеза. Подчеркнем, что входными сигналами синтезируемого структурного автомата являются конъюнкции булевых переменных (или дизъюнкции конъюнкций), каждая из которых отображает путь через соответствующие условные вершины отмеченной ГСА, а выходными сигналами – микрооперации, обозначающие либо вершины, либо дуги графа переходов автомата, в зависимости от его типа. Используя канонический метод структурного синтеза, можно построить функциональную схему автомата.
7. Построение УА с программируемой логикой на основе ПЗУ
В отличие от УА с жесткой логикой, закон функционирования которого обеспечивается определенным образом соединенными логическими элементами, в автоматах, построенных на основе ПЗУ, заданная микропрограмма реализуется в явной форме и хранится в памяти в виде последовательности управляющих слов. Управляющее слово определяет порядок работы устройства в течение одного такта и называется микрокомандой (МК). Она содержит информацию о микрооперациях, которые должны выполняться в данном такте, и (или) об адресе следующей микрокоманды.
Формат МК в общем случае может иметь операционно-адресную структуру.
| Операционная | Адресная |
Микрокоманда может содержать следующие части:
| У1 m | X1 L | A1 P | P1 k |
– операционную часть Y, состоящую из одного или нескольких полей, в каждом записывается номер выходного сигнала yj, вырабатываемого в данном такте;
– адресную часть, состоящую из поля X, в которое записывается номер логического условия Xi (обычно единственного), проверяемого в данном такте;
Рисунок 6.Обобщенная структурная схема управляющего автомата, построенного на основе ПЗУ
– а также из поля A, в которое записывается информация об адресе следующей МК;
– служебную часть Р, содержащую вспомогательную управляющую информацию.
Обобщенная структурная схема УА, выполненного на основе ПЗУ, дана на рис. 6.
Перед началом работы на УА подается сигнал СБРОС, устанавливающий все триггеры автомата и регистра микрокоманд (РМК) в нулевое состояние. Этим обеспечивается занесение содержимого нулевой ячейки ПЗУ в РМК при поступлении первого тактового импульса после подачи стартового сигнала В.
С помощью дешифратора ДШУ вырабатывается соответствующий выходной сигнал yj, а с помощью ДШХ определяется номер логического условия Xi, проверяемого в данном такте. В зависимости от значения Xi, прошедшего через схему выбора ЛУ, и информации, поступающей из адресного поля А, устройство формирования адреса следующей МК (УФ АМК) вырабатывает адрес ячейки ПЗУ, содержимое которой будет переписано в РМК в следующем такте. На УФ АМК может также поступать внешний управляющий сигнал V, обеспечивающий, например, выбор определенного алгоритма из тех, чьи микропрограммы хранятся в ПЗУ автомата.