Понятие о математическом описании цифрового автомата

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

Z=f[X].

В цифровых автоматах с памятью значения выходных сигналов зависят не только от входных сигналов, но и от порядка их поступления, поэтому математическая модель функционирования такого автомата должна учитывать время работы.

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

Состояние памяти автомата в произвольный момент времени t+1определяется состоянием входов и состоянием памяти автомата в момент времени t и описывается выражением

Y(t+1)= [X(t), Y(t)].

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

Выходной сигнал автомата в произвольный момент времени определяется состоянием входов и состоянием памяти в тот же момент времени

Z(t)= [X(t), Y(t)] (1.1)

либо только состоянием памяти

Z(t)= [Y(t)] (1.2)

Эти функциональные зависимости называются функциями выхода автомата. Функция выходов (1.1) описывает функционирование автомата Мили, а функция выходов (1.2) - функционирование автомата Мура. Эти автоматы получили наибольшее распространение на практике и названы по имени ученых, впервые исследовавших их модели. Анализ структурных схем, приведенных в предыдущих параграфах, позволяет сделать вывод, что на рис.1.2,а изображен цифровой автомат Мили, а на рис.1.2,б - автомат Мура.

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

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

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

- множество входных сигналов , которое определяется множеством входов:

X={x₁, x₂, ...,x_n} ( ) ;

- множество выходных сигналов , , которое определяется множеством выходов:

Z={z₁, z₂, ...,z_m} ( );

- множество состояний памяти , которое определяется множеством элементов памяти:

Y={ y₁, y₂, ...,y_k} ( );

- начальное состояние памяти автомата s₀;

- функция переходов автомата:

Y(t+1)= [X(t), Y(t)];

- функция выходов автомата:

Z(t)= [X(t)]

или

Z(t)= [X(t), Y(t)].

Рассмотренные множества и функциональные зависимости между их элементами могут задаваться различными способами, в зависимости от типа исходных данных и выбранного метода решения задачи анализа или синтеза цифрового автомата.