12.4. МИКРОПРОГРАММНЫЕ АВТОМАТЫ

Основные понятия

При описании функционирования различных средств вычислительной техники достаточно часто используется их представление в вида совокупности управляющего и операционною автоматов (рис. 12.30).

Рис. 12.30

Так, в ЭВМ к операционному автомату следует отнести блоки памяти, регистры, сумматоры, каналы передачи информации, шифраторы и т. д., т. е. все устройства, которые выполняют некоторые операции, а к управляющему автомату — ту часть ЭВМ, которая координирует действия перечисленных устройств, определяя последовательность переработки в них информации. Задачей управляющего автомата является, таким образом, выработка распределенной во времени последовательности выходных (управляющих) сигналов, под воздействием которых в операционном автомате осуществляется некоторая операция.

Элементарный неделимый акт обработки информации в операционном автомате, происходящий в течение одного момента автоматного времени (одного такта работы автомата) называется микрооперацией. Примерами микроопераций могут служить «Сдвиг информации», «4-1», «Инверсирование переменной» и т. д.

Если в операционном автомате одновременно реализуется несколько микроопераций, то такое множество микроопераций называется микрокомандой Не исключен случай, когда множество микроопераций, образующих микрокоманду, пусто Реализация такой микрокоманды в операционном автомате равносильна отсутствию выполнения каких-либо элементарных операций. В случае синхронных дискретных устройств пустая микрокоманда интерпретируется как пропуск такта, когда никакие сигналы от управляющего автомата на операционный автомат не поступают

Микрооперации возбуждаются выходными сигналами управляющего автомата, а их последовательность во времени определяется функциями перехода управляющего автомата.

Совокупность микрокоманд и функций перехода образует микропрограмму Таким образом, для описания микропрограммы необходимо задать множество микрокоманд и функций перехода, определяющих порядок их выполнения. Для описания микропрограмм удобно использовать язык граф-схем алгоритмов

Граф-схемы алгоритмов

ГСА называют ориентированный связный граф, содержащий одну начальную вершину (Начало), одну конечную вершину (Конец) и произвольное конечное множество условных и операторных вершин. Любая вершина ГСА, кроме вершины «Начало», имеет по одному входу. Вершина «Начало» входов не имеет. Вершина «Начало» и любая операторная вершина имеют по одному выходу. Вершина «Конец» выходов не имеет. Любая условная вершина имеет два выхода, помечаемых символами «Да» и «Нет» Вместо этих символов могут быть использованы цифры и «0» соответственно.

Изображение вершин «Начало», «Конец», операторной вершины и условной вершины ГСА представлено на рис. 12.31.

Рис. 12.31

Рис. 12.32

ГСА должен удовлетворять следующим условиям:

1. Входы и выходи вершин соединяются друг с другом о помощью дур, направленных всегда от выхода ко входу.

2. Каждый выход соединен только с одним входом.

3. Любой вход соединяется, по крайней мере, с одним выходом.

4. Любая вершина ГСА лежит, по крайней мере, на одном пути из вершины «Начало» в вершину «Конец».

5. Один из выходов условной вершины может соединяться с ее входом что недопустимо для операторной вершины. Такие условные вершины иногда называются возвратными.

6 В каждой условной вершине записывается логическое условие из множества логических условий. Разрешается в различных условных вершинах записывать одинаковые логические условия.

7. В каждой операторной вершине записывается оператор, представляющий собой выходной сигнал или совокупность выходных сигналов управляющего автомата. Разрешается в различных операторных вершинах записывать одинаковые операторы.

Пример ГСА, содержащей 3 операторные и 2 условные вершины» приведен на рис. 12.32.

Содержательные граф-схемы алгоритмов

Обычно при проектировании различных устройств предварительно составляется так называемая содержательная ГСА, в которой внутри условных и операторных вершин записаны логические условия и микрооперации в содержательных терминах.

В качестве примера построим содержательную ГСА управляющего автомата по размену металлических денег. При этом будем считать, что можно разменивать монеты достоинством в 10, 15, 20 и 50 коп., и каждая монета разменивается на соответствующее число монет достоинством в 5 коп. каждая. Будем полагать, что в качестве операционных автоматов используютсяз

блок анализа стоимости размениваемых монет блок выдачи монет; блок анализа наличия монет; счетчик монет.

Тогда содержательная ГСА управляющего автомата может быть представлена на рис. 12.33.

Следует отметить, что это не единственно возможный вариант содержательной ГСА и что ее вид изменяется в зависимости от выбора количества и типов операционных автоматов.

ГСА и содержательные ГСА отображают микропрограммы работы дискретных устройств.

Логические схемы алгоритмов

В ряде случаев вместо ГСА используются логические схемы алгоритмов , представляющие алгоритм функционирования цифрового автомата в виде конечной строки. Эта строка содержит символы операторов, символы логических условий, а также верхние и нижние стрелки, которым приписаны натуральные числа (например, должны удовлетворять следующим условиям:

в строке может быть записан только один начальный оператор один конечный оператор

перед оператором и после оператора стрелок не должно быть;

вслед за каждым логическим условием всегда стоит верхняя стрелка;

не должно существовать двух нижних стрелок с одинаковыми цифрами;

для каждой верхней стрелки должна быть одна нижняя стрелка.

Рис. 12.33 (см. скан)

Рис. 12.84

для каждой нижней стрелки должна быть хотя бы одна верхняя стрелка

В ЛСА, как и в ГСА, операторы обозначают буквами с индексом, а логические условия — буквами х с индексом.

Рассмотрим ЛСА конкретного цифрового автомата: Эта ЛСА имеет начальный оператор конечный оператор четыре оператора три логических условия Эквивалентная ГСА представлена рис. 12.34. Алгоритмперехода от ЛСА к ГСА очевиден. Соответствующая ГСА имеет начальную и одну конечную вершины, а число ее операторных вершин равно числу операторов в Выход начальной вершины ГСА соединяется дугой со входом вершины, соответствующей в ЛСА ближайшему справа от оператору или логическому условию. Аналогичным образом в ГСА проводятся дуги из операторных вершин. Единичный выход условной вершины соединяется со входом вершины, расположенной в ЛСА справа от Если после логического условия в ЛСА стоит верхняя стрелка то нулевой выход условной вершины соединяется со входом вершины, соответствующей в ЛСА оператору или логическому условию, перед которым стоит стрелка Для реализации безусловного перехода достаточно вместо условия использовать константу читаются слева направо и используются в тех случаях, когда нужна компактная вапись алгоритма (например, при машинной обработке). Следует отметить, что возможен переход от ГСА к ЛСА, однако он более сложен и используется редко.

Синтез управляющего автомата по граф-схеме алгоритма

Конечный управляющий автомат, реализующий микропрограмму работы дискретного устройства, принято называть микропрограммным автоматом. Как уже отмечалось, микропрограмма отображается с помощью ГСА. Рассмотрим последовательность этапов синтеза управляющего автомата по его ГСА.

1. Построение содержательной ГСА;

2. Построение отмеченной ГСА;

3. Построение графа переходов автомата;

4. Проведение структурного синтеза автомата по его графу переходов известными методами, например, с помощью канонического метода структурного синтеза.

Построение отмеченной ГСА производится по содержательной ГСА. Для автоматов Мили и Мура процедура разметки имеет различия.

Если необходимо построить микропрограммный автомат Мили, то содержательная ГСА управляющего автомата размечается в соответствии со следующими правилами:

1) символом состояния отметить вход вершины, следующей за вершиной «Начало», а также вход вершины «Конец»;

2) входы всех вершин, следующих за операторными, должны быть отмечены символами с индексами;

3) если выход вершины отмечается, то только одним символом;

4) входы различных вершин, за исключением вершины «Конец», отмечаются различными символами;

5) содержательные термины микроопераций и логических условий, заменяются их условными обозначениями.

Содержательная ГСА (рис. 12.33) после разметки по приведенному алгоритму представлена на рис. 12.35.

Если необходимо построить микропрограммный автомат Мура, то содержательная ГСА управляющего автомата размечается в соответствии со следующими правилами:

1) символом отмечаются вершины «Начало» и «Конец»;

2) различные операторные вершины отмечаются различными символами;

3) все операторные вершины должны быть отмечены.

Содержательная ГСА (рис. 12.33) после разметки по приведенному алгоритму представлена на рис. 12.36.

После получения отмеченной ГСА строится граф переходов автомата. Он имеет столько различных вершин, сколько различных букв индексами имеется отмеченной ГСА. Каждая вершина графа переходов автомата отмечается буквой с соответствующим индексом. Между двумя вершинами и графа имеется дуга, если на отмеченной ГСА между вершинами с метками имеется путь. Над дугой ставится входной сигнал, равный конъюнкции логических условий соответствующего

Рис. 12.35 (см. скан)

пути в отмеченной ГСА. При этом выполнению логического условия соответствует переменная без отрицания, а невыполнению логического условия — переменная с отрицанием на соответствующей дуге графа переходов автомата. Если в отмеченной ГСА между упомянутыми вершинами с метками имеется несколько путей, то в графе переходов автомата на дуге, связывающей через символ дизъюнкции перечисляются все конъюнкции, соответствующие имеющимся путям. Если строится граф переходов автомата Мура, то символы микроопераций (выходные сигналы управляющего автомата) записываются около соответствующих его вершин. Для автомата Мили символы микроопераций записываются на соответствующих дугах при конъюнкциях логических условий, описывающих путь через операторную вершину с рассматриваемой микрооперацией. Если в отмеченной ГСА имеется безусловный переход между операторными вершинами, т. е. путь, не проходящий ни через какие условные вершины, то на графе переходов автомата ему соответствует дуга, которой приписывается входной сигнал показывающий, что данный переход в автомате осуществляется при поступлении очередного синхросигнала. Графы переходов автоматов Мили и Мура для отмеченных ГСА (рис. 12.35; 12.36) приведены на рис, 12.37; 12.38 соответственно. В дальнейшем синтез проводится о помощью описанного ранее метода структурного синтеза. Подчеркнем, что входными сигналами синтезируемого структурного автомата являются конъюнкции булевых переменных (или дизъюнкции конъюнкций), каждая из которых отображает путь через соответствующие условные вершины отмеченной ГСА, а выходными сигналами — микрооперации, обозначающие либо вершины, либо дуги графа переходов автомата, в зависимости от его типа.

Используя канонический метод структурного синтеза, построим функциональную схему автомата

Рис. 12.36 (см. скан)

Рис. 12.37

Рис. 12.38

Мили, граф которого представлен на рис. 12.41. Таблица переходов — выходов автомата, соответствующая графу (рис. 12.41), представлена в табл. 12.33. Кодирование входных сигналов может быть осуществлено, например, в соответствии с табл. 12.34; 12.36; 12.36.

Отметим, что каждому логическому условию ГСА можно поставить в соответствие физическую одноразрядную шину, предполагая, что логическое условие есть выходной сигнал определенного операционного автомата. Тогда наличие единицы, например на шине будет

Таблица 12.33

Таблица 12.34

Таблица 12.35

Таблица 12.36

Таблица 12.37

Таблица 12.38

означать, что монета поступила в блок анализа наличия монет, и последний информирует об этом управляющий автомат. Таким образом, двоичный вектор будет представлять совокупный входной сигнал управляющего автомата, а сигналы могут быть получены с помощью специальной комбинационной схемы формирования входных сигналов. На практике при синтезе управляющего автомата по ГСА этап кодирования входных сигналов (табл. 12.34) можно опустить и строить комбинационные схемы возбуждения и выходов автомата, используя только схему формирования его входных сигналов. Нетрудно заметить, что табл. 12.34 лишь сокращает (путем кодирования) число физических шин для передачи информации от операционных автоматов к управляющему при введении дополнительной комбинационной схемы. Для выходных сигналов автомата чаще удобней использовать также отдельные физические шины (для каждого выходного сигнала свою физическую шину). Такая организация выходных каналов автомата целесообразна, если операционные автоматы, которыми управляет синтезируемый автомат, физически разнесены. Кодирование выходных сигналов в соответствии с табл. 12.36 требует их дешифрации в блоке операционных автоматов. Реализуем каждый выходной сигнал автомата отдельной физической шиной.

Таблица переходов — выходов управляющего автомата представлена в табл. 12.37. Выберем в качестве элементов памяти автомата Т-триггеры, Тогда таблица функций возбуждения синтезируемого автомата будет иметь вид (табл. 12.38), а функции возбуждения и и», ваписанные по этой таблице в СДНФ, представлены

Функции выходов могут быть получены по табл. 12.37 и аналитически выражаются соотношениями»

Для реализации функций возбуждения и выходов автомата можно использовать дешифраторы состояний. В этом случае перечисленные функции удобно записывать в СДНФ.

В заключение следует сказать, что микропрограмма, отражающая алгоритм функционирования автомата, может быть записана в запоминающее устройство (ЗУ), чаще всего в ПЗУ. При этом вступает в силу общий принцип программного управления, хотя определенные особенности адресации и кодирования микрокоманд имеют место. Поясним это более конкретно.

Как отмечалось ранее, порядок выполнения микрокоманд определяется теми или иными логическими условиями, поступающими извне, в частности от операционного автомата. Для того чтобы реализовать процедуру выбора адреса следующей микрокоманды (в зависимости от значений переменных, отражающих условия), к ПЗУ добавляется относительно несложная схема, суть работы которой вытекает из следующего

В общем случае логических условий может быть несколько, причем в двоичной записи микрокоманды обычно отмечаются единицами лишь те из них, которые подлежат анализу при переходе к следующей операции. Если передача управления не зависит от логических условий, переход является безусловным. Таким образом, микрокоманда включает в себя информацию о выполняемых микрооперациях и анализируемых логических условиях. Если в каждой микрокоманде указывается еще и адрес следующей микрокоманды, то такой апоеоб адресации называется принудительным. Пример структуры микрокоманды для последнего случая приведен на рис. 12.39.

В ПЗУ такая микрокоманда эапивывается в виде двоичного вектора, где — двоичные адреса, разрядность которых определяется емкостью ПЗУ. После выполнения каждой микрокоманды управление передается микрокоманде адресом либо в зависимости от значения анализируемой переменной

Другая организация адресации предусматривает естественный способ смены адресов микрокоманд (о помощью счетчика), и лишь при выполнении анализируемого логического условия управление передается микрокоманде в адресом, который содержится в коде микрокоманды. Понятно, что в этом случае длина микрокоманды уменьшается, так как содержит код только одного адреса.

Рис. 13.39

Автоматы, реализованные таким образом, иногда называют автоматами программируемой логикой в отличие от автоматов, схемы которых строятся на основе дискретных элементов — автоматов с жесткой логикой.

Можно заметить, что в первом случае структура управляющего автомата включает в себя ЗУ и схему выбора адреса следующей команды (иногда еще схему формирования выходных сигналов микроопераций); во втором — схему из дискретных компонентов, состоящую из элементов памяти и комбинационных элементов.

Оба способа реализации к настоящему времени получили дальнейшее развитие на основе программируемых БИС, микропроцессоров и однородных сред.