Алгоритм отметки ГСА и построение автомата Мили

Алгоритм отметки ГСА для построение автомата Мили состоит в следующем:

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

· Метками a1, a2, …, aM отмечаются входы всех вершин, следующих за операторными вершинами;

· Вход вершины отмечается не более одного раза.

Далее строится таблица переходов-выходов, включающая следующие столбцы:

· Столбец a_m, обозначает метку, из которой начинается переход, столбец a_s, в котором переход заканчивается.

· Столбец X(a_m, a_s), в котором указываются все условия, проверяемые при переходе из метки a_m в метку a_s, означающий путь перехода.

· Рассматриваются условные и безусловные пути перехода. Путь перехода в ГСА вида: a_m X(a_m, a_s)Y(a_m, a_s)a_s – условный переход; ему сопоставляется конъюнкция X(a_m, a_s) входных условий, проверяемых при выполнении перехода из метки a_m в метку a_s. Отсутствие выходного сигнала в условном переходе допускается только для путей вида a_m X(a_m, a₀)a₀. Безусловному переходу a_mY(a_m, a_s)a_s сопоставляется пустая конъюнкция, равная по определению 1.

· если в конъюнкцию X(am, as) какая-либо переменная входит одновременно с отрицанием и без него, то соответствующий переход при проектировании автомата не рассматривается;

Таблица переходов-выходов автомата Мили представлена в Табл. 31.

Таблица 31 Расширенная таблица переходов-выходов автомата Мили

am	as	X(am, as) x1x2…xn	Y(am, as)	[am] t1t2…tk	[as] t1t2…tk	R1S1 R2S2 …RKSK	[Y(am, as)] y1y2…yr

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

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

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

Тривиальная реализация цифрового автомата

При решении даже достаточно простых задач суммарное число внутренних и внешних переменных автомат оказывается достаточно большим. Существующие алгоритмические и табличные способы минимизации булевых функций позволяют выполнить минимизацию в полном объеме для построения автомата. Однако затраты времени и ресурсов могут оказаться неприемлемыми. Поэтому в некоторых случаях, когда затраты аппаратных средств не очень критичны, используется тривиальная реализация. При такой реализации автомата минимизация функций возбуждения элементов памяти и выходных функций не производится вовсе. Из выходных сигналов элементов памяти с помощью комбинационной схемы, например, дешифратора, формируются сигналы состояний a_i, которые используются для построения ДНФ указанных функций непосредственно по таблице переходов-выходов.  Логические слагаемые в ДНФ представляют собой в этом случае конъюнкции внешних переменных, проверяемых при переходе из метки a_m, и метки a_m. Очевидно, в каждом такте именно метка a_m=1, а остальные метки принимают значение 0.

⇐ Предыдущая78910111213141516Следующая ⇒

Поделиться: