 |
Исходные данные для курсового проектирования
|
|
|
|
Последовательность синтеза синхронных УА
Задача разработки (синтеза) управляющего автомата может быть поставлена перед разработчиком в различных вариантах. Это может быть словесное описание функционирования устройства, различного рода таблицы, временные диаграммы, циклограммы, ориентированные графы и т.п., определяющие последовательность и условия выполнения тех или иных операций по реализации алгоритма функционирования устройства.
Для применения общепринятых методов синтеза исходную постановку задачи необходимо формализовать, т.е. привести ее к каноническим формам описания управляющих автоматов. Обычно при проектировании используется методика синтеза микропрограммных управляющих автоматов, основанная на использовании граф-схем алгоритмов (ГСА).
ГСА – это ориентированный связный граф, включающий вершины четырех типов: начальную, конечную, операторную и условную. Конечная, операторная и условная вершины имеют по одному входу, начальная вершина входов не имеет. У начальной и операторной вершин по одному выходу, у условной – два выхода, помеченных символами 1 и 0. Конечная вершина выходов не имеет.
ГСА удовлетворяет следующим условиям:
- входы и выходы вершин соединяются друг с другом с помощью дуг, направленных всегда от выхода к входу;
- каждый выход соединен только с одним входом;
- любой вход соединяется, по крайней мере, с одним выходом;
- любая вершина ГСА лежит, по крайней мере, на одном пути из начальной вершины к конечной;
- в каждой условной вершине записывается один из элементов множества X = {x1, …, x L } логических условий (разрешается в различных условных вершинах запись одинаковых элементов множества Х);
|
|
|
- один из выходов условной вершины, помеченный “0” или “1”, может соединяться с ее входом, что недопустимо для операторной вершины; такие условные вершины будем иногда называть возвратными или ждущими;
- в каждой операторной вершине записывается оператор (микрокоманда) Yt – подмножество множества микроопераций Y={y1, …, y N }; допускается Yt = 0; разрешается также запись в различных операторных вершинах одинаковых микрокоманд.
| а) б) в) г) |
| а, б – начальная и конечная вершины; в – операторная вершина; г – условная вершина. |
| Рисунок 4 - Графическое представление вершин ГСА. |
На первом этапе формализации алгоритм функционирования УА разбивается на ряд шагов, выполняемых последовательно во времени. В процессе такого разбиения выделяются все операции (действия) по выполнению алгоритма, а также условия выполнения этих операций на каждом конкретном шаге.
Условия обязательно формулируются в виде вопроса, на который возможными ответами являются ДА или НЕТ.
Выполняемые операции каждого шага заносятся в операторные вершины ГСА, а условия перехода от одного оператора к другому - в условные вершины.
При составлении содержательной ГСА производится ее уточнение. Для каждой элементарной операции в объекте управления выделяется исполнительный механизм (операционный автомат), аппаратно ее реализующей. Если такого соответствия достигнуть не удалось, операции подлежат разбиению на более мелкие операции с соответствующей корректировкой ГСА.
Кроме того, проверяется возможность одновременного совмещения нескольких операций на некоторых шагах алгоритма, а также объединение нескольких мелких операций в более крупную при наличии соответствующего исполнительного механизма в объекте управления.
ГСА относится к начальным языкам описания алгоритма функционирования управляющего автомата. Характерной особенностью начальных языков является то, что они не позволяют в явном виде задать функцию переходов. Поэтому для дальнейшего синтеза управляющего автомата необходим переход от начального языка описания работы автомата (т.е. от ГСА) к какому – либо автоматному языку описания, например, к таблицам переходов и выходов.
|
|
|
Современная элементная база для реализации логических преобразователей и блоков памяти УА
Известно два подхода к реализации логики управляющих автоматов (УА) - жесткая и гибкая логика управления.
Жесткая логика (схемная реализация логики управления) предусматривает реализацию множества состояний автомата блоком памяти (БП) на запоминающих элементах (элементы задержки, триггеры, регистры), а функции выходов и переходов формируются комбинационной схемой (логическим преобразователем).
Алгоритм функционирования УА в этом случае полностью определяется схемой соединения его элементов.
Достоинством УА с жесткой логикой управления является максимально высокое быстродействие, определяемое используемой элементной базой. К недостаткам следует отнести большую трудоемкость проектирования, возрастание сложности структуры УА при усложнении алгоритма и отсутствие универсальности.
Последнее свойство определяет, что УА проектируется под конкретную задачу и при малейшем изменении алгоритма работы устройство должно быть спроектировано заново. Ввиду этого подобная реализация УА получила также название специализированных УА.
Гибкая логика управления (программная реализация логики управления) предусматривает для реализации отдельных функций наличие хранимых программ, составленных из команд, каждая из которых, в свою очередь, включает одну или несколько элементарных операций.
Принцип программного управления, используемый повторно для реализации отдельных сложных операций как последовательности элементарных микроопераций, получил название принципа микропрограммного управления.
За счет увеличения затрат времени в таких УА достигается определенная универсальность, т.к. изменение алгоритма функционирования осуществляется частичной или полной заменой программы (или микрокоманд) без изменения структуры автомата.
|
|
|
В свою очередь, использование стандартной структуры значительно ускоряет и облегчает процесс проектирования УА, причем усложнение алгоритма увеличивает лишь объем программы, практически не влияя на объем оборудования УА.
Исходные данные для курсового проектирования
Для применения общепринятых методов синтеза исходную постановку задачи необходимо формализовать, т.е. привести ее к каноническим формам описания управляющих автоматов. Обычно при проектировании используется методика синтеза микропрограммных управляющих автоматов, основанная на использовании граф-схем алгоритмов (ГСА).
В задании на курсовой проект была предложена ГСА, представленная на рисунке 5.
Рисунок 5 - Граф схема алгоритма управляющего автомата типа Мура
На основе полученного ГСА построим граф автомата, который необходим для дальнейшего синтеза автомата. Каждый выходной сигнал соответствует некоторой микрооперации:
Y1 = {y3,y5,y7};
Y2 = {y2,y4 };
Y3 = {y2,y4,y7};
Y4 = {y6,y7};
Y5 = {y1,y2,y4,y5};
Y6 = {y1,y6};
Y7 = {y1,y2,y3,y5,y6};
Y8 = {y2,y3,y4,y5,y7};
Y9 = {y1,y2};
ГСА относится к начальным языкам описания алгоритма функционирования управляющего автомата. Характерной особенностью начальных языков является то, что они не позволяют в явном виде задать функцию переходов. Поэтому для дальнейшего синтеза управляющего автомата необходим переход от начального языка описания работы автомата (т.е. от ГСА) к какому–либо автоматному языку описания, например, к таблицам переходов и выходов. Для построения таблиц переходов и выходов необходимо произвести разметку ГСА.
2 Разработка граф-схемы алгоритма синтезируемого управляющим автоматом и детализация его структурной
Разработка и разметка ГСА
Правила разметки ГСА при реализации автомата по модели Мура:
- символом начального состояния а1 отмечаются начальная и конечная операторные вершины;
- все операторные вершины отмечаются различными символами а2…аi …аn;
- каждая операторная вершина ГСА должна быть отмечена только одним индивидуальным символом аi.
|
|
|
В результате разметки ГСА по указанным правилам удается определить множество внутренних состояний УА А = {а1, … аi, … аn}, а также мощность этого множества, которая равна |А| = n.
Указанные правила разметки сформулированы для однократно выполняемых алгоритмов, при этом конечное состояние УА отождествляется с начальным состоянием. Правильная работа такого автомата гарантируется только в том случае, если до подачи синхронизирующих сигналов элементы блока памяти будут приведены в определенные исходные (начальные) состояния специальным сигналом начальной установки (НУ). Такая разновидность управляющих автоматов называется инициальными автоматами.
Для циклически выполняемых алгоритмов за начальное состояние автомата может быть взято любое его допустимое состояние, которое выбирают произвольным образом и отмечают символом а1. Все последующие состояния такого (не инициального) автомата отмечаются символами а2…аi …аn. В не инициальных автоматах за начальное его состояние может быть взято любое из допустимых состояний автомата. Для установки УА в выбранное начальное состояние необходимо также привести сигналом НУ элементы блока памяти в определенные исходные (начальные) состояния.
Рисунок 6 - Размеченная ГСА управляющего автомата типа Мура
В результате разметки ГСА по указанным правилам удается определить множество внутренних состояний УА (формула 2.1), определяющих мощность этого множества
А = { а1, …аi,…аn } (2)
Так, для данной ГСА мощность равна |А| = 9.
После разметки ГСА выполняется описание УА с помощью расширенных таблиц переходов и выходов.
В процессе проектирования используют два типа таблиц – прямые и обратные. Оба типа таблиц содержат одинаковые переменные:
аm – состояние УА, из которого осуществляется переход за один такт автоматного времени;
аs – состояние УА, в которое осуществляется переход за один такт автоматного времени;
X (аm, аs) – логическое условие перехода из аm в аs;
Y (аm, аs) – микрокоманда (подмножество микроопераций), выполняемая на переходе из аm в аs (для автомата типа Мили);
Y (аm) – микрокоманда (подмножество микроопераций), выполняемая автоматом в состоянии аm (для автомата типа Мура).
Каждая строка таблицы соответствует одному из путей перехода из одного состояния в другое, имеющемуся в ГСА.. Прямой таблицей переходов и выходов называют таблицу, в которой последовательно перечисляются все переходы сначала из первого состояния во все допустимые, потом из второго и т.д. до последнего состояния.
В обратных таблицах указываются все допустимые переходы из каких – либо состояний сначала в первое, потом во второе и т.д. до последнего состояния. Рассмотрению подлежат все пути переходов от отметок а i к а j. Для автоматов допустимыми являются пути вида:
|
|
|
| ai X(аi, aj) Yk aj ai Yk aj ai X(ai, aj) aj |
| (3) (4) (5) |
Для пути перехода вида (2.2) считают, что X(ai, aj) = 1, т.е. реализуется безусловный переход. На переходе вида (2.3) выходной сигнал полагается равным Yo (пустой оператор).
Поскольку в автоматах Мура выходной сигнал определяется текущим состоянием автомата, то рассмотрению подлежат переходы вида:
| ai X(аi,) aj) aj |
| (6) |
выполняемые под действием входных сигналов X(ai,aj), а также переходы, являющиеся частным случаем (6.4), при входном сигнале равном 1, переходы вида:
| аi, aj |
| (6.5) |
| (7) |
В соотношениях (3)…(7) i = {1, 2…n} и j = {1, 2…n}.
Структурный синтез управляющего автомата с жесткой логикой включает в себя следующие этапы:
- выбор типа элементов памяти;
- кодирование состояний автомата, входных и выходных сигналов в структурном алфавите;
- детализация блока памяти;
- составление расширенной структурной таблицы переходов и выходов;
- канонический синтез логического преобразователя;
- минимизация функций выходов и возбуждения блока памяти.
Структура прямой таблицы переходов и выходов для автомата Мура представлена таблицей 1.
Таблица 1
| аm, Y (аm) | аs | X (аm,аs) |
| а1 Y1 | a2 | 
|
| a4 | 
| |
| а2 Y2 | a3 | 
|
| a2 | 
| |
| а3 Y3 | a8 | 
|
| a3 | 
| |
| а4 Y4 | а5 | 
|
| a4 | 
| |
| а5 Y5 | a6 | |
| а6 Y6 | a8 | 
|
| a7 | 
| |
| а7 Y7 | а7 | *
|
| a8 |
| |
| а8 Y8 | a9 | |
| а9 Y4 | а1 | *
|
| a9 | *
| |
| a5 |
|
|
|
|
