7.7.2. Операция обратной связи
Пусть A = {a0, . . . , an} некоторый алфавит. Определим специальный автомат Z = (A, A, A, , ) следующими каноническими уравнениями:
q(t0) = a0;
q(t+1) = x(t);
y(t) = q(t).
Нетрудно видеть, что на первом шаге работы автомат Z находится в состоянии, обозначенном первым символом алфавита A, и подает на выход именно этот символ. В каждый последующий момент автомат Z подает на выход символ, который равен символу на входе этого автомата в предыдущий момент времени.
Автомат Z называется автоматом задержки на один такт или один шаг.
Пусть = (Am, An, Q, , ) произвольный конечный автомат, имеющий m входов и n выходов. При этом m, n 2.
Определение
Операцией обратной связи называется преобразование конечного автомата , при котором один из выходов подключается к входу автомата Z, а выход Z подсоединяется к одному из входов .
В результате операции обратной связи образуется новый автомат с m 1 входами и n 1 выходами.
Пример. На рис.7.14 изображен конечный автомат , который получается из автомата , имеющего по два входа и выхода, применением обратной связи:
x(t) y(t)
Z
Рис. 7.14
Состояниями являются пары (qi, qj), где qi состояние , а qj состояние автомата задержки Z.
Пусть q0 начальное состояние автомата .
Тогда функционирование автомата для заданных начальных состояний q0 и a0 представляется следующими каноническими уравнениями:
-
q1(t0)
=
q0;
q2(t0)
=
a0;
q1(t+1)
=
((x(t), q2(t)), q1(t));
q2(t+1)
=
2((x(t), q2(t)), q1(t));
y(t)
=
1((x(t), q2(t)), q1(t)).
Здесь q1(t) и q2(t) состояния и Z в момент t, а 1 и 2 функции, определяющие символы на первом и втором выходах автомата соответственно.
Входные символы для автомата представляют собой пары символов (x1(t), x2(t)).
Упражнение. Записать канонические уравнения для автомата задержки на два шага, изображенного на рис. 7.15.
Z Z
Рис. 7.15
Определение
Последовательность применений операций композиции и обратной связи к заданному множеству автоматов, для которой допускается разветвление выходов автоматов и запрещаются циклы, не содержащие элементов задержки, называется автоматной схемой.
7.8. Схемы из элементарных автоматов
П
усть
A
= {0,
1}.
Следующие автоматы называются
элементарными (см. рис. 7.16):
&
Z
Рис. 7.16
Здесь первые три автомата представляют собой уже известные функциональные элементы, которые для любых входных наборов вычисляют значения соответствующих булевских функций.
Эти автоматы имеют по одному внутреннему состоянию.
Автомат Z является задержкой для алфавита A = {0, 1}.
Рассмотрим как с помощью схем, составленных из элементарных автоматов, можно представлять произвольные автоматы.
Пусть = (A, B, Q, , ) произвольный автомат, для которого:
A = {a1, . . . , am}, B = {b1, . . . , bn}, Q = {q0, . . . , qr}, и q0 это начальное состояние автомата .
Будем представлять символы алфавитов A и B, а также элементы множества состояний Q с помощью двоичных наборов длины p = ]log2(m)[, d = ]log2(n)[ и s = ]log2(r+1)[ соответственно.
Заметим, что значения p, d и s выбраны из соображений минимальности длины наборов, которых должно быть не меньше, чем элементов соответствующих множеств.
Для определенности положим, что начальное состояние , равное q0, представляется набором, состоящим из s нулей.
Рассмотрим автомат , имеющий p входов и d выходов, который моделирует работу автомата .
Состояния представляются двоичными наборами, имеющими длину s, которые соответствуют состояниям .
Начальным состоянием автомата является состояние, представляющее состояние q0 автомата .
Если в некоторый момент времени на вход поступает набор, представляющий символ входного алфавита ai и автомат находится в состоянии, соответствующем состоянию qj, то на выходе появляется двоичный набор, представляющий (ai, qj). При этом сам автомат переходит в состояние, представляющее состояние (ai, qj).
Канонические уравнения для автомата можно записать в виде:
-
q1(t0)
=
0;
. . .
qs(t0)
=
0;
q1(t+1)
=
1(x1(t), ... , xp(t), q1(t), . . . , qs(t));
. . .
qs(t+1)
=
s(x1(t), ... , xp(t), q1(t), . . . , qs(t));
y1(t)
=
1(x1(t), ... , xp(t), q1(t), . . . , qs(t));
. . .
yd(t)
=
d(x1(t), ... , xp(t), q1(t), . . . , qs(t)).
Здесь (x1(t), ... , xp(t)) обозначает набор символов, поступающих на входы в момент t, а (q1(t), . . . , qs(t)) набор, задающий состояние автомата в тот же момент времени.
Функция i, i = 1, . . . , s, определяет значение iй компоненты состояния автомата , в которое он переходит из состояния (q1(t), . . . , qs(t)) под действием входного символа (x1(t), . . . , xs(t)).
Функция j, j = 1, . . . , d, определяет значения символа на j-м выходе в момент t, для входного символа (x1(t), . . . , xs(t)) и текущего состояния (q1(t), . . . , qs(t)).
Поскольку функции i, i = 1, . . . , s, и j, j = 1, . . . , d являются булевскими функциями, то они могут быть реализованы схемами из функциональных элементов, которые изображены на рис. 7.17.
.
. . . . . . .
1 . . . d 1 . . . s
Рис. 7.17
Рассмотрим автоматную схему, представляющую автомат , которая изображена на рис. 7.18:
x1 . . . x p q 1 . . . q s
. . . . . . . . . . . .
1 . . . d 1 . . . s . . .
. . . Z . . Z
y1 yd Рис. 7.18
Данная схема задает автомат, имеющий p входов и d выходов. В ней каждый из p входов, помеченных символами переменных, и s выходов элементов задержек является одним из входов схем из функциональных элементов, вычисляющих функции 1, . . . , d, 1, . . . , s.
В начальный момент времени находится в состоянии, которое представляется набором из s нулей.
По определению функций i и j(i = 1, . . . , d, j = 1, . . . , s) построенная автоматная схема функционирует так же, как и автомат , c точностью до кодирования входных и выходных символов. То есть если на входе автомата появляется слово , которое перерабатывается в выходное слово , то автомат из своего начального состояния перерабатывает слово, получаемое из заменой входящих в него символов их двоичными представлениями, в слово, получаемое из аналогичной заменой сомволов алфавита B их двоичными представлениями.