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

Пусть A = {0, 1}. Следующие автоматы называются элементарными (см. рис. 7.16):

& - Z

Рис. 7.16

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

Эти автоматы имеют по одному внутреннему состоянию.

Автомат Z является задержкой для алфавита A = {0, 1}.

Рассмотрим как с помощью схем, составленных из элементарных автоматов, можно представлять произвольные автоматы.

Пусть Â = (A, B, Q, j, y) - произвольный автомат, для которого:

A = {a₁, . . . , a_m}, B = {b₁, . . . , b_n}, Q = {q₀, . . . , q_r}, и q₀ - это начальное состояние автомата Â.

Будем представлять символы алфавитов A и B, а также элементы множества состояний Q с помощью двоичных наборов длины p = ]log₂(m)[, d = ]log₂(n)[ и s = ]log₂(r+1)[ соответственно.

Заметим, что значения p, d и sвыбраны из соображений минимальности длины наборов, которых должно быть не меньше, чем элементов соответствующих множеств.

Для определенности положим, что начальное состояние Â, равное q₀, представляется набором, состоящим из s нулей.

Рассмотрим автомат Á, имеющий p входов и d выходов, который моделирует работу автомата Â.

Состояния Áпредставляются двоичными наборами, имеющими длину s, которые соответствуют состояниям Â.

Начальным состоянием автомата Áявляется состояние, представляющее состояние q₀ автомата Â.

Если в некоторый момент времени на вход Á поступает набор, представляющий символ входного алфавита a_i и автомат находится в состоянии, соответствующем состоянию q_j, то на выходе Á появляется двоичный набор, представляющий
y(a_i, q_j). При этом сам автомат Áпереходит в состояние, представляющее состояние j(a_i, q_j).

Канонические уравнения для автомата Á можно записать в виде:

Здесь (x₁(t), ... , x_p(t)) обозначает набор символов, поступающих на входы Á в момент t, а (q₁(t), . . . , q_s(t)) - набор, задающий состояние автомата Á в тот же момент времени.

Функция j_i, i = 1, . . . , s, определяет значение i-й компоненты состояния автомата Á, в которое он переходит из состояния (q₁(t), . . . , q_s(t)) под действием входного символа (x₁(t), . . . , x_s(t)).

Функция y_j, j = 1, . . . , d, определяет значения символа на j-м выходе Á в момент t, для входного символа (x₁(t), . . . , x_s(t)) и текущего состояния (q₁(t), . . . , q_s(t)).

Поскольку функции j_i, i = 1, . . . , s, и y_j, j = 1, . . . , d являются булевскими функциями, то они могут быть реализованы схемами из функциональных элементов, которые изображены на рис. 7.17.

. . . . . . . .

y₁ . . .y_d j₁ . . . j_s

Рис. 7.17

Рассмотрим автоматную схему, представляющую автомат Á, которая изображена на рис. 7.18:

x₁ . . . x _pq ₁ . . . q _s