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

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

Рис. 2.1. Абстрактный цифровой автомат

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

S ={A, X ,Y, , , a₁}, (1)

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

 - функция переходов абстрактного цифрового автомата, реализующая ото­бражение множества D_ в A (D_ является подмножеством прямого произведения множеств AX, то есть D_  AX). Таким образом, любое состояние цифрового ав­томата a_s = (a_m, z_f), поскольку множество AX является множеством всевозможных пар (a, z) и a_s  A.

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

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

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

p = ]log₂M[. (2)

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

r = ]log₂F[. (3)

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

d = ]log₂G[. (4)

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

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

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

(5)

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

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

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

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

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

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

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

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