Реферат: Устройство управления синхронного цифрового автомата

3) произвольное множество Q состояний автомата:

Q={q₁(t), q₂(t) … q_s(t)};

4) начальное состояние автомата q₀, как элемент множества Q:

q₀(t)Q;

5) функция (q, x) (функция перехода автомата из одного состояния в другое);

6) функция (q, х) (функция выходов автомата).

Через понятие "абстрактный автомат" реализуется некоторое отображение множества слов входного алфавита Х во множество слов выходного алфавита Y.

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

Время для цифрового автомата имеет также важное значение. Для решения задач анализа и синтеза цифровых автоматов обычно вводится автоматное время. Функционирование автомата рассматривается через дискретные интервалы времени конечной продолжительности (интервал дискретности).

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

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

Автоматы классифицируют по двум наиболее распространенным признакам:

1. Объем памяти. Памятью автомата называют число его состояний.

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

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

В теории автоматов наиболее полно описаны синхронные автоматы. В зависимости от способа определения выходного сигнала в синхронных автоматах существует две возможности:

1) выходной сигнал y(t) однозначно определяется входным сигналом x(t) и состоянием q(t-1) автомата в предшествующий момент;

2) выходной сигнал y(t) однозначно определяется входным сигналом x(t) и состоянием q(t) в данный момент времени. Следовательно, закон функционирования абстрактного автомата может быть задан следующим образом:

для автомата первого рода

q(t)=(q(t-1), х(t)),

y(t)=(q(t-1), x(t), t=1, 2…);

для автомата второго рода

q(t)=(q(y-1), x(t)),

y(t)=(q(t), x(t)), t=1,2...).

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

₁(q, x)=((q, х), x).

Для дальнейшего изложения примем, что произвольные автоматы первого рода будут называться автоматами Мили, а частный случай автоматов второго рода, для которых сдвинутая функция выходов (q, х) не зависит от второй переменной х — автоматами Мура.

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

q(t)=(q-1), x(t)),