Классические понятия цифровых автоматов

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

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

Чтобы задать конечный автомат надо определить шестерку [8]:

       A={ S, X, Y, F, V, s(0)},

где S – множество допустимых состояний;

       X – множество возможных входов;

     Y –  множество выходов;

                 F – функция переходов автомата;

                 V– функция выходов автомата;

                 s(0) – начальное состояние.

Множества S, X, Y – конечные, причем каждый элемент множества имеет собственное имя. В пределах данного параграфа всем элементам множеств будем присваивать одинаковые имена и индексы, соответствующие порядковому номеру их вхождения во множество, то есть

S={ s₀, s₁,….s_p,…….s_n};

X={ x₀, x₁,….x_r,…….s_m};

Y={ y_o, y₁,….y_s,…….y_k};

Запись вида s(n) будет означать состояние автомата в n -ном такте, и  при этом s(n) может принимать значение из множества S. Сигналы x(N) и у(N)     определены аналогично. Необходимо указать, что в данном контексте вход и выход отражают не состояние отдельных входных и выходных линий, а полные совокупности (коды) информационных сигналов, поступающих на входы и снимаемых с выходов.  В списках можно использовать любые слова, кроме ключевых слов языка, но проектировщики обычно используют имена, отражающие  смысл функционирования.

Функция переходов F определяет состояние автомата в n-ном такте работы в зависимости от состояния автомата и входа в n-1-ом  такте:

                      F : S–>S,   s(n)=F(s(n-1), y(n-1)).                                                               

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

В модели Мура (рис. 5.1) выход   определяется состоянием автомата в текущий момент времени и зависит от выходной комбинационной логики

                   V: S–>Y, y(n)=V(s(n)) .                                                            (1)

Рис. 5.1. Структурная модель цифрового автомата Мура

Подкласс   автоматов Мура, в котором функция выходов определяется только состоянием автомата в текущий момент времени, в современной литературе носит название автомата Медведева [9]. На рис. 5.2 приведена структурная модель автомата Медведева. Выходные сигналы совпадают с выходными сигналами триггеров регистра состояний.

Рис. 5.2. Структурная модель цифрового автомата Медведева

Каноническая модель Мили предполагает, что выход определяется состоянием автомата и входными сигналами в текущем такте. На рис.5.3 приведена структурная модель автомата Мили. В модели Мили выход   определяется не только состоянием автомата в текущий момент времени и выходной комбинационной логикой, но и зависит от сигналов на входных линиях

       V: S × Y–>Y, y(n)=V(s(n), y(n)),                                   (2)

где символ× означает декартово произведение.

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

Рис. 5.3. Структурная модель цифрового автомата Мили

Во всех вариантах используются регистры с динамическим управлением от сигнала  clk. На рисунках вход динамического управления обозначается стрелкой.

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

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

Приведем для примера классическое задание функционирования автомата Мили, функция переходов которого представлена таблицей 5.1, а функция выходов таблицей 5.2.

Таблица 5.1                                       Таблица 5.2

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

Рис. 5.5. Графический стиль описания автомата Мили

Графический стиль описания этого же устройства (граф переходов автомата) может иметь вид, представленный на рис. 5.5. Хотя в данном случае замена коснулась лишь имен сигналов: “плюс” вместо X1 и “минус” вместо X2, поведение автомата стало значительно яснее. При сигналах “плюс” автомат последовательно проходит состоянияс повышением номера от текущего до тех пор, пока либо не придет сигнал “минус” и движение начнется в противоположном направлении, либо при отсутствии сигналов “плюс” и “минус” автомат будет оставаться в последнем состоянии. Ясно видны и условия формирования выходных сигналов Y1 и Y2. Совершенно очевидно, что стиль формы описания не влияет на результирующий текст программы.

5.2. Инженерный подход к проектированию  цифровых автоматов

Важность цифровых автоматов в проектировании разнообразных цифровых устройств и определенная специфика их синтеза вызывала и продолжает вызывать огромный интерес разработчиков электронной аппаратуры. Большое количество работ посвящено способам перехода от описаний автоматов к их схемной реализации [10]. На ранних этапах развития вычислительной техники методики перехода в основном ориентировались на ручные  методы синтеза (например, [6]). В ряде работ  [11]    предлагались методики, пригодные  для формального перехода от описания поведения автоматов к структуре вычислительных устройств.  Эти работы послужили основой для разработки современных автоматизированных систем проектирования автоматов. Теперь разработчик в зависимости от опыта и имеющихся ресурсов может выбирать способ создания описания синтезируемого автомата: ручной, полуавтоматический или автоматический.