Структурный синтез конечных автоматов

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

Работа подобных цифровых устройств описывается набором входных сигналов Z = {Z₁, Z_{2, …,} Z_p}, набором выходных сигналов W= { W_1, Z_2, …, Z_s }, множеством внутренних состояний (выходных сигна­лов элементов памяти) А = {a₁, a_2, …, a_k}, двумя характеристи­ческими функциями: функцией переходов δ и функцией выходов, λ, а также начальным состоянием автомата a₁ ∈ A.

Различают два типа автоматов: автоматы Мили и Мура. Для каж­дого из них внутреннее состояние в последующем такте полностью оп­ределяется входным сигналом и внутренним состоянием в данном так­те, что отражается в записи функций переходов

а(t+1) = δ [z(t), a(t)],

где t - автоматное время.

Отличаются автоматы Мили и Мура лишь записью функции выходов. Если в автомате Мили выходной сигнал зависит как от внутреннего состояния автомата, так и от входного сигнала в том же такте

W(t) = λ [z(t), a(t)],

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

W(t) = λ [a(t)],

В частном случае возможно и W(t) = а(t), т.е. выходной сигнал авто­мата одновременно является выходным сигналом памяти.

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

Каждое состояние входа и выхода любого автомата однозначно за­дается комбинацией двоичных сигналов на соответствующих n-разряд­ных шинах, поэтому условимся каждое отдельное состояние кодировать набором двоичных символов (битов):

Z_i ~ х(t) ={ x₁, x₂. x_n} - входной сигнал;

W_i ~ y(t) ={ y₁, y₂. y_m} - выходной сигнал;

a_i ~ Q(t) ={ Q₁, Q₂. Q_r} - сигнал внутреннего состояния (состояния триггеров памяти);

U(t) ={ u₁, u₂... u_k} - входной сигнал памяти.

В такой записи символическим обозначениям Z_i, W_i и a_i соот­ветствуют двоичные кодовые комбинации х(t), у(t) и Q(t), где х_j, y_j, Q_j, и u_j - отдельные биты кода, каждый из которых передается по своей информационной шине. Структурные схемы автоматов Мили и Мура показаны на рис. 4 и 5. Исходными данными для их синтеза являются таблицы переходов и выходов.

Рисунок 4. Структурная схема КА Мили

Рисунок 5. Структурная схема КА Мура

Структурный синтез КА Мили предполагает выполнение ряда эта­пов.

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

2. Определяют недостающие входные данные:

- число элементов памяти r ≥ log ₂ k

- число разрядов входной шины n ≥ log ₂ p

- число разрядов выходной шины m≥ log ₂ s,

где k, p, s - количество внутренних состояний, входных Z_i и выход­ных W_i сигналов соответственно. Числа r, п, т - целые.

3. Кодируют автомат. Это означает, что каждому входному и вы­ходному сигналу и внутреннему состоянию ставят в соответст­вие определенный двоичный код.

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

5. По таблице выходов составляют систему логических уравнений, связывающих выходные, сигналы КА у_j с внутренними состояниями и входными сигналами х_j. Общий вид такого уравнения

У_j = f_j (x₁, x₂, …, x_n, Q₁, Q₂, …, Q_r).

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

Таблица 3 - Словари переходов триггеров

Для синтезируемого КА с помощью словаря следует преобразо­вать его таблицу переходов в таблицу возбуждения памяти (процесс преобразования поясняется ниже на конкретном примере).

7. По таблице возбуждения памяти составляют систему логичес­ких уравнений, связывающих входные сигналы памяти U_j с внутренними состояниями Q_j и входными сигналами х_j:

U_j = φ _j (x₁, x₂, …, x_n, Q₁, Q₂… Q_r).

8. Все уравнения, полученные в пп.5 и 7, минимизируют при помощи карт Карно.

9. По минимальным формам составляют полную логическую схему КА на микросхемах заданной серии.