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

4. Построение диаграммы переходов автомата по блок-схеме алгоритма функционирования устройства

Введение

Описание функционирования автомата, обычно, начинается с описания реализуемого им алгоритма в виде блок-схемы. Язык блок-схем очень удобен для задания функционала устройства, и поэтому имеет широкое распространение. Однако, для того, чтобы реализовать устройство в виде микросхемы, требуется выполнить несколько последовательных шагов, которые в конечном итоге приводят к описанию устройства на VHDL. И первый из этих шагов – это построение диаграммы переходов конечного автомата. Этот шаг в настоящее время выполняется вручную и поэтому чреват ошибками. Кроме того, ручной режим не позволяет преобразовывать блок-схемы с большим числом операторов т. к. в этом случае достоверность результата существенно падает. Поэтому актуальной выглядит задача автоматизации преобразования блок-схемы в диаграмму переходов, что вполне реально, т. к. это преобразование осуществляется по формальным правилам с соблюдением формальных критериев.

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

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

4.1. Построение диаграммы переходов автомата

Построение диаграммы переходов для автомата Мили начинается с установления связи между определенными точками блок-схемы и состояниями автомата. Напомним, что автомат Мили вначале выдает выход­ную букву, а затем изменяет свое состояние. Автомат задается таблицей переходов, содержащей целочисленные множества Q - состояний, |Q| = q, X - входов, |X| = n, и Y– выходов, |Y| = m. Таблица переходов задает две функции d: Q´X ® Q и l: Q´X ® Y, определяющие соответственно следующее состояние автомата и выход в зависимости от его текущего состояния и входа. Обычно автомат обозначается так: A = (Q, q0, X, Y, d, l), где q0 Î Q – начальное состояние, в котором автомат находится в нулевой момент времени. Однако, для наших целей, в частности – для осуществления суперпозиции автоматов, нам потребуется выделить в множестве состояний два подмножества: Qstart Í Q – начальных состояний и Qstop Í Q - т. н. stop-состояний. Множества начальных и stop-состояний не пересекаются. Особенность начальных состояний состоит в том, что мы не можем в процессе работы автомата вернуться в любое из этих состояний, они служат только для начала работы автомата. Подразумевается, что в нулевой момент времени автомат может находиться в любом (но только одном) начальном состоянии Множество stop-состояний характеризуется тем, что, попадая в любое из них, автомат останавливается. Множество Q \ (Qstart È Qstop) состоит из внутренних состояний. Во время работы автомат несколько раз может попасть только во внутренние состояния.

Будем полагать, что блок-схема содержит следующие вершины

1)  Начальные операторы (Рис. 4.1.1а). Каждый начальный оператор помечен уникальной т. н. начальной меткой. Такие операторы нам нужны только для того, чтобы различать начальные состояния алгоритма. Выполнение алгоритма может начинаться в любом из начальных операторов. Начальные операторы определяют начальные состояния автомата, он начинает работу в одном из начальных состояний.

2)  Заключительные операторы (Рис. 4.1.1б). Аналогично каждый конечный оператор помечен уникальной конечной меткой. Такие операторы нужны для выделения остановок алгоритма. После того, как алгоритм оказывается в заключительном состоянии, он останавливается. Заключительные операторы определяют т. н. stop-состояния автомата. После того, как автомат оказывается в одном из stop-состояний, он останавливается.

3)  Логические tоператоры (Рис. 4.1.1в). Каждый логический оператор помечен булевской переменной, и имеет в точности две выходные дуги, одна из которых отмечена знаком +. По этой дуге вычисление продолжается в случае, когда переменная принимает значение true. По другой дуге вычисление продолжается, если переменная принимает значение false. Пусть все метки логических вершин образуют множество X = {x1, x2, …, xn}. При построении автомата по блок-схеме этими переменными будут метиться дуги диаграммы переходов. Переходы автомата также определяются значениями этих переменных.

4)  Вычислительные операторы (Рис. 4.1.1г). Каждый вычислительный оператор помечен набором т. н. выходов. Все выходы блок-схемы образуют множество Y = {y1, y2, …, ym}. При построении автомата по блок-схеме этими переменными будут метиться дуги диаграммы переходов. Таким образом, можно полагать, что в блок схеме отсутствуют два подряд расположенных вычислительных оператора, т. к. если такая ситуация встречается, то несколько подряд расположенных вычислительных операторов можно объединить в один.

Рис. 4.1.1а Рис. 4.1.1б Рис. 4.1.1в Рис. 4.1.1г

Все операторы блок-схемы определенным образом соединены дугами, которые определяют порядок вычисления. Начальные операторы не имеют входящих дуг, заключительные – выходящих. В блок-схеме может быть несколько начальных и заключительных операторов. В последующем этим операторам будут соответствовать начальные и stop-состояния конечного автомата. Этим наш подход отличается от стандартного представления блок-схем, в которых обычно имеются по одному начальному и одному заключительному оператору. Логический оператор имеет в точности две выходящие дуги, одна определяет вычисление при истинности этого оператора, другая – при ложности. Вычислительный оператор имеет в точности одну выходную дугу. Более подробное описание блок-схем полагаем излишним, т. к. оно стандартно и его можно найти в любом учебнике по информатике.

Переход от блок-схемы к диаграмме автомата Мили осуществляется в два этапа.

На первом этапе путем разметки блок-схемы определяется число состояний автомата.

Правила разметки:

1.  Выделяем все начальные операторы блок-схемы и вход оператора, следующего за начальным оператором, помечаем уникальным начальным состоянием автомата. Для простоты полагаем, что дуги из начальных операторов ведут в разные операторы блок-схемы. Поэтому число начальные состояний автомата равно числу начальных операторов блок-схемы.

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

3.  Выделяем все еще не помеченные входы логических операторов и метим их новыми т. н. внутренними состояниями автомата – каждая дуга помечается уникальным внутренним состоянием. Множества внутренних, начальных и stop-состояний попарно не пересекаются.

4.  Если в результате разметки оказалось, что в один и тот же логический оператор блок-схемы входит несколько размеченных дуг, то им присваивается одно и то же состояние. Таким образом, общее множество состояний автомата определяется множествами начальных, внутренних и stop-состояний.

На втором этапе осуществляется переход от размеченной блок-схемы к диаграмме переходов автомата.

Диаграмма переходов задается множеством вершин, каждая из которой помечена уникальным состоянием автомата из выделенных на первом шаге анализа блок-схемы. Состояния автомата следующим образом соединяются нагруженными дугами. Если на блок-схеме имеется путь между двумя размеченными дугами, которые помечены состояниями qi и qj, (qi – начальная дуга, а qj – заключительная) не проходящий через другую размеченную дугу, то в диаграмме переходов имеется дуга qiqj,.

Возможно существование путей четырёх видов:

1.  Путь проходит через логический оператор (с меткой x), его выходную дугу, помеченную знаком +, и последовательность вычислительных операторов (с метками yj1, yj2, …, yjh). В этом случае в диаграмме имеется дуга, как на рис. 4.1.2а. В терминах автомата эта дуга обозначает, что если в момент времени t автомат находится в состоянии qi, и на его вход поступает значение x, то автомат выдает значения yj1È yj2 È …È yjh и в момент времени t + 1 оказывается в состоянии qj. Напомним, что в нашем случае один вычислительный оператор может быть помечен несколькими символами множества Y. Поэтому все элементы yj1, yj2, …, yjh представляют собой множества.

2.  Путь проходит через логический оператор (с меткой x), его выходную дугу, не помеченную знаком +, и вычислительный оператор (с меткой yj1, yj2, …, yjh). В этом случае в диаграмме имеется дуга, как на рис. 4.1.2б. В терминах автомата эта дуга обозначает, что если в момент времени t автомат находится в состоянии qi, и на его вход поступает значение `x, то автомат выдает значения yj1È yj2 È …È yjh и в момент времени t+1 оказывается в состоянии qj.

3.  Путь содержит единственный логический оператор (с меткой x), его выходную дугу, помеченную знаком +, и заканчивается дугой, также ведущей в логический оператор. В этом случае в диаграмме имеется дуга, как на рис. 4.1.2в. В терминах автомата эта дуга обозначает, что если в момент времени t автомат находится в состоянии qi, и на его вход поступает значение x, то автомат не выдает никакого значения, и в момент времени t+1 оказывается в состоянии qj. если состояния qi и qj, совпадают, то в диаграмме появляется петля.

4.  Путь содержит единственный логический оператор (с меткой x), его выходную дугу, не помеченную знаком +, и заканчивается дугой, также ведущей в логический оператор. В этом случае в диаграмме имеется дуга, как на рис. 2в. В терминах автомата эта дуга обозначает, что если в момент времени t автомат находится в состоянии qi, и на его вход поступает значение x, то автомат не выдает никакого значения, и в момент времени t+1 оказывается в состоянии qj. если состояния qi и qj, совпадают, то в диаграмме появляется петля.

Пример 4.1.1. Синтез простого автомата

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

Представим алгоритм решения задачи в виде блок-схемы на рис. 4.1.3а.

Рис. 4.1.3а. Блок схема простого алгоритма

Для построения автомата переходим к блок-схеме, в котором все логические вершины помечены буквами входного алфавита, а вычислительные – буквами выходного алфавита. Это делается по вполне понятной причине: автомат представляет собой управляющую систему, а вычисление конкретных значений – это задача функционального блока. Блок схема, в которой вершины помечены буквами входного и выходного алфавита, изображена на рис. 4.1.3б.

Рис. 4.1.3б. Блок схема алгоритма, подготовленная к синтезу автомата

На первом этапе выполним разметку по сформулированным выше правилам. Разметка приведена на рис.4.1.3б. Метки, обозначенные крестиками, соответствуют трем состояниям диаграммы. Поэтому диаграмма, в которой после выполнения алгоритма автомат переходит в начальное состояние, изображена на рис. 4.1.3в.

Переход от отмеченных блок-схем к графу автомата осуществляется в следующем порядке.

Вершинами графа изображаются все состояния автомата и внутри кружков записываются номера состояний, соответствующие меткам на блок-схеме q1, q2, q3.

На блок-схеме находим все пути между двумя соседними состояниями qi и qj.

По правилам разметки внутренние состояния автомата на блок-схеме отмечены перед входами в логические операторы.

Каждый логический оператор имеет две выходные дуги: одна из которых помечено знаком «+», другая – знаком «˗».

Из метки q1 по дуге со знаком «+» существует путь третьего вида. Путь содержит логический оператор (с меткой x1), его выходную дугу, помеченную знаком «плюс», и заканчивается дугой ведущей в логический оператор x2. Автомат переходит из состояния q1 в состояние q2. В этом случае в диаграмме имеется дуга, как на рис. 4.1.2в.

Из метки q1 по дуге со знаком «˗» существует переход второго вида. Путь проходит через логический оператор (с меткой x1), его выходную дугу, не помеченную знаком «+», и вычислительный оператор с меткой y1 . Автомат возвращается в состояние q1. В диаграмме появляется петля.

Из метки q2 по дуге со знаком «+» существует путь третьего вида. Путь проходит через логический оператор (с меткой x2), его выходную дугу, помеченную знаком «+». Автомат переходит из состояния q2 в состояние q1. На диаграмме имеется дуга, как на рис. 4.1.2в.

Из метки q2 по дуге со знаком «˗» имеется переход четвёртого вида. Путь проходит через логический оператор (с меткой x2), его выходную дугу, помеченную знаком «˗». Этот путь соответствует переходу их состояния q2 в состояние q3. На диаграмме имеется дуга, как на рис. 4.1.2г.

Из метки q3 по дуге со знаком «+» существует путь первого вида. Путь проходит через логический оператор (с меткой x3), его выходную дугу, помеченную знаком «+» и вычислительный оператор с меткой y1. Автомат переходит из состояния q3 в состояние q1. На диаграмме имеется дуга, как на рис. 4.1.2а.

Из метки q3 по дуге со знаком «˗» существует путь второго вида. Путь проходит через логический оператор (с меткой x3), его выходную дугу, не помеченную знаком «+» и вычислительный оператор с меткой y2. Этот путь соответствует переходу их состояния q3 в состояние q1. На диаграмме имеется дуга, как на рис. 4.1.2б.

Рис. 4.1.3в. Автомат, у которого заключительное состояние совпадает с начальным

Если надо выделить заключительное состояние, отличное от начального, то диаграмма выглядит, как на рис. 4.1.3г.

Рис. 4.1.3г. Автомат с четырьмя состояниями. Отдельно выделено начальное и заключительное состояние

Итак, автомат на входе имеет некоторую последовательность входных сигналов, в зависимости от которых переходит из одного состояния в другое, выдавая некоторую последовательность выходных сигналов.

На этом выполнение абстрактного синтеза заканчивается.

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

Для каждого состояния подберем уникальный код, используя при этом двоичное число из двух разрядов. Введём обозначения - , а - , где - двоичный код состояния.

Таблица кодирования состояний

1	00
2	01
3	10
4	11

Таблица переходов и выходов

qt	qt+1	x1 x2 x3	y1 y2
00	01	1--	00
00	11	0--	10
01	00	-1-	00
01	10	-0-	00
10	11	--1	10
10	11	--0	01

В таблице шесть строк, которые соответствуют шести дугам на графе.

По таблице видим, что из состояния 00 автомат переходит в состояние 01 при условии . При условии автомат из этого состояния переходит в состояние 11, и при этом получаем выходной сигнал .

Из состояния 01 автомат переходит в состояние 00 при условии и в состояние 10 при условии .

Из состояния 10 автомат при условии переходит в состояние 11, и при этом на выходе получаем сигнал . При условии осуществляется переход из состояния 10 в состояние 11 и при этом выдаётся сигнал .

По таблице переходов можно записать уравнения функций состояний и функций выходов.

По полученным уравнениям функций состояний и выходов создаём схему в LabVIEW. Схема приведена на рис. 4.1.3е.

Рис. 4.1.3е. Схема автомата, синтезированная с использованием комбинационных схем.

Так как данный автомат весьма прост, то для него легко осуществить построение его схемы средствами системы LabVIEW. Эти схемы приведены на рис. 4.1.3ж и 4.1.3з.

Рис. 4.1.3ж. Схема автомата, реализованная по шаблону в LabVIEW

Рис. 4.1.3з. Схема с использованием функционального элемента Formula Node