Абстрактный синтез управляющего автомата

Функция управляющего автомата задаётся кодированной граф-схемой алгоритма (ГСА) микропрограммы. Кодированную ГСА (рисунок 5, б)) получают путём замены в содержательной ГСА (рисунок 5, а) микрооператоров (наборов совместимых микроопераций) на коды микрокоманд, а логических условий на их идентификаторы.

 

 

а) б)

 

 

Рисунок 5 - Фрагмент содержательной (а) и кодированной (б) ГСА

микропрограммы

 

3.1.1 Получение отмеченной ГСА

 

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

Будем полагать, что автомат начинает работу с состояния s₀, в котором он не вырабатывает никаких выходных сигналов и после выполнения микропрограммы снова оказывается в этом же состоянии. Затем автомат переходит в состояния, предписанные законом функционирования, и формирует микрокоманды y, соответствующие текущим значениям сигналов x. Момент окончания выполнения микропрограммы отмечается возвратом автомата в начальное состояние s₀.

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

- символом s₀ отмечаются начальная и конечная вершины ГСА;

- каждая операторная вершина отмечается единственным символом s₁, s₂, s₃, s₄, s₅, ...;

- две различные операторные вершины не могут быть отмечены одинако­выми символами.

На рисунке 6, а) представлена ГСА, отмеченная по приведенному выше правилу. В каждом такте автомат Мура, интерпретирующий данную микропро­грамму, переходит из одного состояния в другое и выдаёт соответствующие выходные управляющие сигналы y_i. Порядок выдачи выходных сигналов y_i оп­ределяется значениями входных сигналов x_i. Так, при наличии входного сиг­нала х₁ = 0 автомат из состояния s₀ перейдет в со­стояние s₁ и выдаст выходной сигнал у₁. В сле­дующем такте работы под воздействием входного сигнала х₂ = 1 автомат из состояния s₁ перейдёт в состояние s₃ с выдачей выходных сигналов у₂ и у₃.

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

- символом s₀ отмечается выход начальной и вход конечной вершины;

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

- входы двух различных вершин не могут быть отмечены одинаковыми символами;

- входы вершины могут отмечаться только одним символом состояния.

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

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

На рисунке 6, б) представлена ГСА, отмеченные по приведённому выше правилу.

 

 

 

а) б)

 

а - для автомата Мура,

б - для автомата Мили.

 

Рисунок 6 – Отмеченные граф-схемы

 

3.1.2 Построение графа-переходов или функционирования автомата

 

Для автома­тов Мура и Мили их внутренние состояния представляются вершинами графа. Внутренние переходы от одного состояния к другому изображаются на­правленными дугами. Для автоматов Мили и Мура значение входного сигнала, вызывающего этот переход из текущего состояния s(t) в последующее s(t+1), приписывается соответствующей дуге. Для автомата Мура значения выход­ных сигналов зависят только от внутреннего состояния и поэто­му приписываются соответствующей вершине. Та­ким образом, на графах отображаются обе характеристические функции конечного автомата. Граф автомата Мура, построенный по ГСА, представлен на рисунке 7, а).

При формировании графа для автомата Мили необходимо учитывать, что значения выход­ных сигналов y(t), определяемые значениями текущего состояния s(t) и входных сигналов х(t), ставятся в соот­ветствие самой дуге. Граф автомата Мили приведен на рисунке 7, б).

 

а) б)

 

а - для автомата Мура,

б - для автомата Мили.

 

Рисунок 7 – Графы функционирования автоматов

 

 

3.1.3 Построение таблицы переходов и выходных функций

 

Для автомата Мура в ячейках таблицы переходов-выходов для каждой пары значений аргументов х(t), s(t) проставляются бу­дущие внутренние состояния s(t+1). Значения выходных сигналов y(t) представляются в отдельном столбце. Пример табличного представления функций автомата Мура приведен на рисунке 8, а).

Для автомата Мили в ячейках таблицы переходов-выходов для каждой пары значений аргументов проставляются бу­дущие внутренние состояния и текущие значения выходных сигналов. Пример табличного представления функций автомата Мили приведен на рисунке 8, б).

 

 

s	x1x2	y Y
s0	s1	s1	s2	s2	-
s1	s5	s3	s5	s3	y1
s2	s5	s3	s5	s3	y2
s3	s4	s4	s4	s4	y2, y3
s4	s0	s0	s0	s0	y4
s5	s5	s3	s3	s5	y3

s	x1x2
s0	s1/y1	s1/y1	s1/y2	s1/y2
s1	s1/y3	s2/y2y3	s1/y3	s2/y2y3
s2	s3/y4	s3/y4	s3/y4	s3/y4
s3	s0/-	s0/-	s0/-	s0/-

 

а) б)

 

а - для автомата Мура,

б - для автомата Мили.

 

Рисунок 8 – Табличное представление функций

1234	Поделиться:

Популярное:

1. Антибиотики, нарушающие синтез микробной стенки
2. Богословский язык как метафизический синтез
3. Вопрос 58. Театральное искусство: художественный синтез.
4. Глава 22. Особенности православно-богословского синтеза культуры
5. Глава 5. Попытка синтеза. Проектирование.
6. ГЛАВА VI. «ТОНКИЙ ЯД». СИНТЕЗ
7. Живопись действия» и «цветовое поле». Абстрактный экспрессионизм и психоаналитические техники.
8. Задача творческого синтеза в культуре
9. Коррекционная работа, направленная на развитие звукового анализа и синтеза у детей с ОНР.
10. На каком этапе энергетического обмена синтезируются 2 молекулы АТФ?
11. Народная культура как синтез язычества и христианства