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

БЕЛОРУССКИЙ   ГОСУДАРСТВЕННЫЙ

УНИВЕРСИТЕТ   ТРАНСПОРТА

 Кафедра  автоматики и телемеханики

, 

СИНТЕЗ СИНХРОННЫХ АВТОМАТОВ

Методические указания к расчетно-практической работе

по дисциплине

«Теория дискретных устройств»

г. Гомель 1999

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

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

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

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

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

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

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

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

Временная диаграмма (см. рис.1) отражает основные моменты работы СА, имеющего структуру, показанную на рис.2. Рассмотрим эти особенности работы автомата. В момент времени t0 происходит изменение значений переменных Х_j на входе схемы синхронизации (СС). Новые значения запоминаются в схеме СС и передаются на вход логического преобразователя (ЛП) в момент времени t1 (по переднему фронту импульса Т). В момент времени t1 (с учетом состояния ЭП блока памяти, в которые они перешли в предыдущий момент времени ) вычисляются новые значения функций включения ЭП. Однако переключение линии задержки (например, из состояния ”0” в состояние ”1”) происходит через время t и поэтому подача новых значений состояний ЭП на вход ЛП происходит также через время t (в паузе между импульсами синхронизации). В момент времени t3 опять происходит изменение значений входных переменных Х_j, но их новое значение запоминается в схеме СС и передается на вход ЛП по переднему фронту следующего импульса синхронизации, т.е. в момент времени t4 и т.д.

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

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

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

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

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

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

S(t)=б (а(t), S(t-1))                                                   (1)

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

v(t)=H(a(t), S(t-1))                                                    (2)

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

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

v - выходное состояние - двоичный вектор значений выходных переменных z1,…,zq ;

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

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

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