Определение абстрактного цифрового автомата

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

С помощью импульсов синхронизации исключается возможность некорректной работы цифрового автомата во время протекания переходных процессов в элементах блока памяти и в комбинационных схемах. Цифровые автоматы, работающие под управлением системы задания дискретного автоматного времени, называются синхронизированными цифровыми автоматами. Наличие системы задания дискретного автоматного времени накладывает ограничения и на порядок изменения входных управляющих сигналов множества X. Поскольку сигналы множества X формируются в других блоках сложной информационной системы, то учёт ограничений системы задания дискретного времени приводит к практической необходимости включения в информационную систему любой сложности единой системы синхронизации.

Для абстрактного математического описания цифрового автомата как кодопреобразователя (рис.1) используется его представление как шестиэлементного множества:

S ={A, X ,Y, d, l, a₁}, (32)

где: A = {a₁, .., a_m, ..., a_M} - множество состояний автомата (алфавит состояний); X = {z₁, ..., z_f, ..., z_F} - множество входных сигналов автомата (входной алфавит); Y = {w₁, ..., w_g, ..., w_G} - множество выходных сигналов (выходной алфавит);

d - функция переходов абстрактного цифрового автомата, реализующая отображение множества D_d в A (D_d является подмножеством прямого произведения множеств A´X, то есть D_d Í A´X). Таким образом, любое состояние цифрового автомата a_s = d(a_m, z_f), поскольку множество A´X является множеством всевозможных пар (a, z) и a_s Î A.

l - функция выходов абстрактного цифрового автомата, реализующая отображение множества D_l в Y (D_l является подмножеством прямого произведения множеств A´X, то есть D_l Í A´X). Таким образом, любой выходной сигнал множества Y w_g = l(a_m, z_f);

a₁ - начальное состояние автомата (a₁ Î A). Поведение цифрового автомата существенно зависит от начального состояния. Для однозначного управления цифровым автоматом необходимо, чтобы он начинал работу из определённого начального состояния. Цифровой автомат с установленным (выделенным) начальным состоянием a₁ называется инициальным.

Автомат является конечным, если A, X и Y - не являются бесконечными множествами.

Автомат является полностью определённым, если D_d = D_l = A´X. Иными словами, у полностью определённого автомата области определения функций d и l совпадают с множеством A´X - множеством всевозможных пар (a_m, z_f). У частичного автомата функции d и l определены не для всех пар (a_m, z_f) Í A´X.

Теоретически все элементы множеств A, X ,Y могут быть закодированы числами в системах счисления с любым основанием, но практически всегда используется двоичная система счисления (двоичный структурный алфавит).

Для двоичной системы счисления обозначим:

A = {a₁, .., a_m, ..., a_M}, X = {x₁, ...,x_f, ...,x_F}, Y = {y₁, ..., y_g, ...,y_G} и определим разрядность двоичных кодов состояний, входного сигнала и выходного сигнала. Количество разрядов двоичного кода всегда целое число.

Количество разрядов двоичного кода состояний

p = ]log₂M[. (33)

Количество разрядов двоичного кода входных сигналов

r = ]log₂F[. (34)

Количество разрядов двоичного кода выходных сигналов

d = ]log₂G[. (35)

В этих формулах ]...[ - означает ближайшее большее к значению внутреннего выражения целое число.

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

Максимально возможное количество запрещённых кодов наборов переменных комбинационных схем определится как:

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

Часто на практике используется две разновидности цифровых автоматов, отличающихся способом формирования выходных сигналов:

- при описании функционирования автомата выражениями:

a(t+1) = d[a(t), z(t)],

w(t) = l[a(t), z(t)] - он называется автоматом Мили;

- при описании функционирования автомата выражениями:

a(t+1) = d[a(t), z(t)],

w(t) = l[a(t)] - он называется автоматом Мура.

В этих выражениях t - текущий момент дискретного автоматного времени, t+1 - следующий момент дискретного автоматного времени.