12 Способы задания цифровых конечных автоматов

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

12.1 Математические модели ца

Мы уже рассматривали законы функционирования (математические модели) комбинационных схем, временных булевых функций.

Рассмотрим теперь закон функционирования цифровых автоматов с точки зрения абстрактной теории автоматов.

Абстрактный автомат (АА) это обобщенное представление цифрового дискретного устройства, которое определяют множества:

-множество входных сигналов Х={х₁, х₂, ...,х_n;

-множество выходных сигналов Y={y₁, y₂, ...,y_m;

-множество внутренних состояний Z={z₀, z₁, ...,z_k,

включая и начальное, нулевое состояние z₀;

-функцией переходов φ отображения XZ множества входных сигналов на множество внутренних состояний Z= φ (X,Z);

-функций выходов  отображения (XZ)Y множества входных сигналов X и состояний Z на множество выходных сигналов Y=(X, Z).

Тогда обобщенный закон или модель абстрактного автомата будет выглядеть как математический кортеж:

А={Х, Y, Z, φ, .

Автомат называется конечным, если конечны множества X, Y, Z. Абстрактный автомат реализует отображение множества слов входного алфавита X в множество слов выходного алфавита Y.

Обобщенный закон функционирования автомата не отражает его поведение во времени, а именно этот вопрос и является иногда основным при анализе и синтезе ЦУ. Среди многих попыток описания поведения ЦА во времени наибольшее распространение получили автоматы Мили и Мура.

Закон функционирования автомата Мили:

Z(t+1) = φ ( z(t), x(t) ),

Y(t) = ( z(t), x(t) ).

Последующее состояние автомата z(t+l) зависит от функции переходов φ, настоящего состояния z(t) и входных сигналов в этот момент x(t). Выходные сигналы зависят от функции выходов , входных сигналов x(t) и внутренних состояний z(t), где t=0, 1, 2 - автоматное время; Z(0)=z₀- начальное, нулевое состояние.

Закон функционирования автомата Мура:

z(t + l) = φ (z(t),x(t)),

y(t) =(z(t)),

т.е. в автомате Мура выходные сигналы y(t) зависят от состояния автомата в данный момент и не зависят от входных сигналов.

12.2 Табличный способ задания ца

Существует несколько способов задания работы автоматов. Для простых автоматов, получили распространение табличные способы задания автомата в виде таблиц переходов и выходов автомата Мили; отмеченных таблиц переходов автомата Мура (см. таблицу 12.1).

Автомат Мили может не иметь некоторых состояний и некоторых выходных сигналов. Такие автоматы называются частично определенными. Если автомат имеет только одно состояние, то он называется тривиальным автоматом. Абстрактный автомат всегда имеет один входной и один выходной каналы и в каждый момент времени он находиться в каком-то одном определенном состоянии z(t).

12.3 Задание цифрового автомата графом

Абстрактный автомат часто задают с помощью графа.

Граф автомата это ориентированный связный граф, каждая вершина которого соответствует определенному состоянию ЦА, а дуги указывают направления их возможных переходов, входное и выходное воздействие (слово). Вершины Zi и Zs соединяют дугой, направленной к Zs, если есть переход из состояния Zi в состояние Zs. Этой дуге приписывают входной сигнал Хj и выходной Yn, если они определены в ЦА, и ставят прочерк при их отсутствии. Если таких сигналов несколько, то пишут все как по входу, так и выходу.

На рисунке 12.2 показан граф частичного автомата заданного таблицей переходов и выходов (таблица 12.4).

Таблица 12.4-Переходов и выходов частичного автомата