Представление систем с конечной памятью

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

быть записано в форме

где принято, что 0 ≤ l ₁ < l ₂ <... < i_u и 1 ≤j₁ < j₂ <... < j _v. Если добавить ряд несущественных переменных [35] и принять l _u = µ₁ и j₀ = µ₂, то уравнение (6.1) можно записать в виде

Для того чтобы преобразовать приведенное характеристическое уравнение в характеристические стандартные функции f_z и f_s конечного автомата, переменную s определим так, чтобы s_v являлась упорядоченным набором значений (µ₁ + µ₂) переменных (x_v-1, x_v-2,..., x_v-µ1, z_v-1, z_v-2,..., z_v-µ2),. Равенство (6.2) тогда примет вид

Уравнения (6.3) и (6.6) могут рассматриваться как характеристические функции конечного автомата. Следовательно, множество упорядоченных наборов значений (µ₁-µ₂) переменных (x_v-1, x_v-2,..., x_v-µ1, z_v-1, z_v-2,..., z_v-µ2) адекватно множеству состояний системы, представленной урав-

нением (6.2). Если число символов входного и выходного алфавитов для системы соответственно равно р и q, то мощность множества состояний будет

В качестве примера рассмотрим устройство А27. На устройство периодически поступают цифры 0 и 1, выход его в момент t_v равен сумме по модулю 2 выхода в момент t_v-1 и входа в момент t_v-2. Обозначая сложение по модулю 2 знаком [36], Л27 может быть охарактеризовано равенством

Добавляя несущественные переменные x_v и x_v-1 вместо (6.8) получим:

Входной алфавит в этом случае

X={0, 1},

а выходной алфавит

Z={0. 1}.

Множество состояний является множеством всех упорядоченных наборов значений трех переменных (x_v-1, x_v-2, z_v-1):

Зависимость между x_v, s_v, s_v+1 и z_v может быть представлена в табличной форме, как показано в таблице 6.1. Столбцы таблицы под «s_v» представляют все упорядоченные наборы значений трех переменных; каждый набор записан дважды (по одному разу для каждого значения x_v). Столбцы, озаглавленные «s_v+1», могут быть заполнены путем воспроизведения ранее заполненных столбцов (таких как x_v и x_v-1) и

путем использования соотношения (6.8) (для столбца z_v). Показанную таблицу удобно использовать для определения характеристических функций f_z и f_s автомата А27. Например,

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

В общем случае автомат, полученный описанным способом, не минимальный. Однако, минимальная форма всегда может быть определена любым из методов минимизации, описанных в главе 3. Минимальная форма автомата А27 показана на рис. 6.2, где состояния 1, 2, 3 и 4 представляют эквивалентные классы {(1, 0, 0), (1,1, 1)}, {(0, 0, 1), (0, 1, 0)}, {(0, 0, 0), (0, 1. 1)} и {(1, 0, 1), (1, 1, 0)} соответственно.