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

 

1. Обобщенная структура и принцип функционирования синхронных управляющих автоматов

 

Математической моделью дискретного  устройства является абстрактный автомат, определяемый как шестикомпонентный кортеж, или вектор [4 - 11]:

 

S = (Z, A ,W, δ, λ, a₁),                               (5.1)

у которого:

Z={z₁,…z_f…z_F} - множество входных сигналов автомата (входной алфавит);

A={a₁,…a_m…a_M} - множество состояний автомата (алфавит состояний);

W={w₁,…w_g…w_G} – множество выходных сигналов автомата (выходной алфавит);

δ : A х Z  ® A – функция переходов автомата, реализующая отображение D_δ A х Z на A. Другими словами, функция δ некоторым парам состояние - входной сигнал (a_m, z_f) ставит в соответствие состояние автомата a_s = δ (a_m, z_f), a_s A;

λ : A х Z ® W  – функция выходов, реализующая отображение D_l A х Z на W, которая некоторым парам состояние - входной сигнал (a_m, z_f) ставит в соответствие выходной сигнал автомата w_g = λ (a_m, z_f);

a₁ A – начальное состояния автомата.

Под алфавитом здесь  понимается непустое множество попарно  различных символов. Элементы алфавита называются буквами, а конечная упорядоченная последовательность букв - словом в данном алфавите.

Абстрактный автомат имеет один вход и один выход. Автомат работает в дискретном времени, принимающем целые неотрицательные значения  t = 0,1,2,… В каждый момент t дискретного времени автомат находится в некотором состоянии a(t) из множества состояний автомата, причем в начальный момент времени t(0) автомат может находиться в начальном состоянии a(0) = a₁. В момент t, будучи в состоянии a(t), автомат способен воспринять на входе букву входного алфавита  z(t) Z. В соответствии с функцией выходов он выдает  в тот же момент времени  t  букву  выходного алфавита           w(t) = λ (a(t)_, z(t)) и в соответствии с функцией переходов перейдет  в  следующее  состояние     a(t +1) = δ (a(t)_, z(t)),    причем a(t +1) A, а w(t) W. Смысл понятия абстрактного автомата состоит в том, что он реализует некоторое отображение множества слов входного алфавита Z в множество слов выходного алфавита W. Иначе, если на вход автомата, установленного в начальное состояние a₁, подавать буква за буквой некоторую последовательность букв входного алфавита z(0), z(1), z(2), … - входное слово, то на выходе автомата будут последовательно появляться буквы выходного  алфавита w(0), w(1), w(2), … - выходное слово. Каждому входному слову соответствует определенное выходное слово, структура которого определяется функциями переходов и выходов.

Таким образом, на уровне абстрактной теории понятие "работа автомата" понимается как преобразование входных слов в выходные слова. Структурной моделью нулевого уровня абстрактного автомата является модель, представленная на рис. 5.1.

 

 

            

                Z                                           W

 

 

Рис. 1.3  Структурная модель абстрактного автомата

 

Чтобы задать конечный автомат S, необходимо описать все компоненты вектора S = (Z, A ,W, δ, λ, a₁), т.е. входной и выходной алфавиты и алфавит состояний, а также функции переходов и выходов. Среди множества состояний может быть выделено начальное состояния автомата a₁, в котором автомат находится в момент t = 0. 

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

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

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

 

 

 

 

 

 

2.  Последовательность синтеза синхронных управляющих автоматов

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

Для применения общепринятых методов синтеза исходную постановку задачи необходимо формализовать, т.е. привести ее к каноническим формам описания управляющих автоматов. Обычно при проектировании используется методика синтеза микропрограммных управляющих автоматов, основанная на использовании граф-схем алгоритмов (ГСА).

ГСА – это ориентированный связный  граф, включающий вершины четырех  типов: начальную, конечную, операторную  и условную (рис. 5.2). Конечная, операторная  и условная вершины имеют по одному входу, начальная вершина входов не имеет. У начальной и операторной вершин по одному выходу, у условной – два выхода, помеченных символами 1 и 0. Конечная вершина выходов не имеет.

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

1. входы и выходы вершин соединяются друг с другом с помощью дуг, направленных всегда от выхода ко входу;
2. каждый выход соединен только с одним входом;
3. любой вход соединяется, по крайней мере, с одним выходом;
4. любая вершина ГСА лежит, по крайней мере, на одном пути из начальной вершины к конечной;
5. в каждой условной вершине записывается один из элементов множества X={x₁, … , x_L} логических условий (разрешается в различных условных вершинах запись одинаковых элементов множества Х);
6. один из выходов условной вершины, помеченный “0” или “1”, может соединяться с ее входом, что недопустимо для операторной вершины; такие условные вершины будем иногда называть возвратными или ждущими;
7. в каждой операторной вершине записывается оператор (микрокоманда) Y_t – подмножество множества микроопераций Y={y_{1, …,} y_N}; допускается Y_t = 0; разрешается также запись в различных операторных вершинах одинаковых микрокоманд.

 

а), б) - начальная и  конечная вершины; в) - операторная вершина;

г) - условная вершина.

Рис. 1.4 Графическое представление вершин ГСА.

 

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

Условия обязательно  формулируются в виде вопроса, на который возможными ответами являются  ДА или НЕТ.

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

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

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

ГСА относится к начальным  языкам описания алгоритма функционирования управляющего автомата. Характерной  особенностью начальных языков является то, что они не позволяют в явном виде задать функцию переходов. Поэтому для дальнейшего синтеза управляющего автомата необходим переход от начального языка описания работы автомата (т.е. от ГСА) к какому – либо автоматному языку описания, например, к таблицам переходов и выходов.

 

3. Современная элементная база для реализации логических преобразователей и блоков памяти УА

 

Известно два подхода  к реализации логики управляющих  автоматов (УА) - жесткая и гибкая логика управления.

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

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

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

 

1.4 Исходные данные  для курсового проектирования

 

 

Для применения общепринятых методов синтеза исходную постановку задачи необходимо формализовать, т.е. привести ее к каноническим формам описания управляющих автоматов. Обычно при проектировании используется методика синтеза микропрограммных управляющих автоматов, основанная на использовании граф-схем алгоритмов (ГСА).

В задании на курсовой проект нам предлагается ГСА, представленная на рисунке

 

 

 

 

 

 

 

 

 

 

 

 

 

Рисунок 1.5. Граф схема алгоритма управляющего автомата типа Мили.

 

2. АНАЛИЗ ГСА СИНТЕЗИРУЕМОГО УА И ДЕТАЛИЗАЦИЯ ЕГО СТРУКТУРНОЙ СХЕМЫ
1. Анализ и разметка ГСА.

 

Правило разметки ГСА  при реализации автомата по  модели Мили:

-символом начального  состояния а₁ отмечается вход вершины, следующей за начальной, а также вход конечной вершины ГСА;

-входы всех вершин, следующих за операторными, отмечаются  различными символами а₂ …а_i …а_n;

-входы вершин ГСА,  следующих за операторными, должны  быть отмечены только одним  единственным символом а_i.

В результате разметки ГСА по указанным  правилам удается определить множество внутренних состояний УА  А = { а₁, …а_i ,…а_n }, а также мощность этого множества, которая равна IАI = n.

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

Для циклически выполняемых алгоритмов за начальное состояние автомата может быть взято любое его  допустимое состояние, которое выбирают произвольным образом и отмечают символом а₁. Все последующие состояния такого (не инициального) автомата отмечаются символами а₂ …а_i …а_n. В не инициальных автоматах за начальное его состояние может быть взято любое из допустимых состояний автомата. Для установки УА в выбранное начальное состояние необходимо также привести сигналом НУ элементы блока памяти в определенные исходные (начальные) состояния.