Разновидности цифровых автоматов и выражения, описывающие их функционирование

Автомат является полностью определённым, если Dδ = Dλ = A×X. Иными словами, у полностью определённого автомата области определения функций δ и λ совпадают с множеством A×X – множеством всевозможных пар (am, zf). У частичного автомата функции δ и λ определены не для всех пар (am, zf) ⊆ A×X.

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

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

A = {a1, .., am, ..., aM},

X = {x1, ...,xf, ...,xF},

Y = {y1, ..., yg, ...,yG}и определим разрядность двоичных кодов состояний, входного сигнала и выходного сигнала. Количество разрядов двоичного кода всегда целое число.

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

p = ]log2M[. (33)

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

r = ]log2F[. (34)

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

d = ]log2G[. (35)

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

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

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

(36)

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

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

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

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 – следующий момент дискретного автоматного времени.

3. Синтез цифровых автоматов. Синтез абстрактных цифровых автоматов.