4. Синтез синхронных автоматов

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

4.1. Основные положения

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

Известно, что конечный автомат функционирует в дискретные моменты времени, т.е. непрерывная шкала времени разделена на интервалы, которые занумерованы целыми положительными числами t₁ = 0,1,2,…,n и которые называются тактами работы схемы. В течение одного такта сохраняются неизменными состояния входов, состояния выходов и внутренние состояния автомата. Время, в течение которого не происходит изменения состояния входа автомата, обозначим через Т. В зависимости от того, чем определяется длительность интервала Т, различают два класса автоматов: синхронные и асинхронные.

Синхронный автомат характеризуется тем, что он имеет генератор тактовых (или синхронизирующих) сигналов (ТГ). Входные сигнала (х_j) могут воздействовать на автомат лишь при наличии сигналов ТГ (рис 4.1), т.е. время Т в СА строго фиксировано и определяется длительностью сигнала ТГ.

В асинхронном автомате отсутствует ТГ, время Т является переменной величиной и определяется длительностью входного сигнала ТГ.

Итак, время Т в СА фиксировано, и автомат может воспринимать новое состояние входа лишь после того, как он перешел в определенное внутреннее состояние. Поэтому частота ТГ выбирается такой, чтобы до появления сигнала от ТГ автомат успел перейти в это внутренне состояние. Время перехода автомата из одного внутреннего состояния в другое (время изменения состояния элементов памяти ЭП, например построенных на линиях задержки ЛЗ) будем обозначать . Следовательно, при работе автомата необходимо обеспечить следующее соотношение:

 >> _макс.

_­

где  = Т +  ;  - интервал времени между двумя соседними сигналами (тактами) ТГ. Обычно сигнал _макс выбирают такой, что Т <_мин. В свою очередь, изменение внутреннего состояния автомата происходит лишь в интервалах между двумя соседними сигналами от ТГ.

Рис.4. 1

Временная диаграмма (см. рис. 4.1) отражает основные моменты работы СА, имеющего структуру показанную на рис. 4.2. Рассмотрим эти особенности работы автомата.

В момент времени t₀ происходит изменение значений переменных х_j на входе схемы синхронизации (СС). Новые значения запоминаются в схеме СС и передаются на вход логического преобразователя (ЛП) в момент времени t₁ (по переднему фронту импульса Т). В момент времени t₁ (с учетом состояния ЭП блока памяти, в которые они перешли в предыдущий момент времени) вычисляются новые значения функций включения ЭП. Однако переключение линии задержки (например из состояния “0” в сотояние “1”) происходит через время , и поэтому подача новых значений состояний ЭП на вход ЛП происходит также через время  (в паузе между импульсами синхронизации). В момент времени t₃ опять происходит изменение значений входных переменных х_j, но их новое значение запоминается в схеме СС и передается на вход ЛП по переднему фронту следующего импульса синхронизации, т.е. в момент времени t₄, и т.д.

Рис. 4.2

Таким образом, для СА можно выделить две характерные особенности:

- входные сигналы воздействуют на автомат в строго фиксированные моменты времени.

- изменение внутренних состояний автомата осуществляется в интервалах ремени между синхронизирующимими импульсами ТГ.

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

Функционирование СА определяется функцией переходов и функцией выходов, в классе СА рассматривают два типа автоматов: модель Мили и модель Мура.

Модель Мили описывается функцией переходов

S(t) = ( a(t) , S(t-1) ) (4.1)

и функцией выходов

(t) = ( a(t) , S(t-1) ) (4.2)

где а – входное состояние (входной набор) – двоичный вектор значений входных переменных х₁, …, х_n;

S – внутреннее состояние – двоичный вектор значений внутренних переменных y₁,…, y_k;

 - выходное состояние – двоичный вектор значений выходных переменных z₁, … , z_q;

 - функция переходов схемы (определяется таблицей переходов);

 - функция выходов (определяется таблицей выходов).

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

Модель Мура определяется функцией перехода (4.1), а функция выходов определяется уравнением

(t) = ( S(t) ) (4.3)

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

Практическая реализация СА имеет много вариантов реализации его структуры. Рассмотрим некоторые из них.

На рис 4.2 представлен вариант структуры СА в виде автомата Мили 1 рода. Для данной структуры можно выделить 4 типа блоков:

СС – схема синхронизации – обеспечивает синхронизацию поступления входных сигналов х₁, … ,х_n ;

ЛП – логический преобразователь – реализует функции включения внутренних элементов памяти y₁, … ,y_k ;

БП – блок памяти – производит задержку сигналов у на время , для чего используются линии задержки;

ВП – выходной преобразователь – реализует выходные функции z₁, … ,z_q;

Рассмотрим работу автомата в момент времени t (t = 1,2,3, … ,n). Автомат работает в соответствии с временной диаграммой (см. рис. 4.1.). На вход ЛП поступают синхронизированные тактовым генератором ТГ значения сигналов х₁(t), … ,х_n(t) и занчения сигналов y₁(t-1), … ,y_k(t-1), вычиленные в предшествующий момент времени t-1. Логический преобразователь вычисляет новые значения сигналов y₁(t), … ,y_k(t). Однако эти значения не поступают на вход ЛП, так как они задерживаются линиями задержки на время . Таким образом снимается проблема критических состязаний. В момент времени t блок ВП вычисляет значения выходных сигналов z₁(t), … ,z_q(t).

На рис. 4.3. показана структурная схема синхронного автомата Мили, имеющая две последовательности импульсов синхронизации СС₁ и СС₂.

Рис. 3. 4

Схема работает следующим образом. В момент времени t по импульсу синхронизации ТГ₁ (импульс 1) срабатывает схема CC₁ и на вход ЛП поступают сигналы х(t) и y(t). Вычисляются значения функций y₁(t), … ,y_k(t). Затем, когда все переходные процессы в ЛП закончены, поступает синхроимпульс ТГ₂ (импульс 2) и происходит переключение ЭП. Формируются сигналы y(t-1). На вход ЛП эти сигналы подаются только в следующий момент времени при поступлении нового импульса от ТГ₁ (импульс 3), чем и достигается исключение критических состязаний. Принципиальное отличие схемы на рис. 4.3 от схемы на рис. 4.2 состоит в том, что время задержки формируется не линией задержки (как это сделано в схеме рис. 4.2), а разницей во времени между импульсами 2 и 3 (см. рис. 4.3).

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

В связи с этим отметим следующие преимущества СА по сравнению с асинхронными:

1) для построения схемы требуется меньше ЭП, так как не надо вводить избыточность для исключения состязаний;

2) алгоритм синтеза СА проще по этой же причине;

3) быстродействи СА выше, так как отсутствуют многотактные переходы.

Недостатком СА является усложнение схем за счет наличия синхронизации и генераторов тактов.