Введение в теорию автоматов и структурный синтез цифровых автоматов

 

10.1. Основные понятия и определения

 

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

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

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

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

Как отмечалось в главе 1, абстрактный автомат с одним входом и одним выходом можно представить следующим образом:

 

X Y

 

 

Для задания конечного автомата фиксируются три конечных множества (алфавита):

- множество возможных входных сигналов:

X = {x1, x2,..., xm};

- множество возможных выходных сигналов:

Y = {y1, y2,..., yk};

- множество возможных внутренних состояний автомата:

A = {a0, a1,..., an}.

На этих множествах задают два логических оператора:

- функцию переходов f, определяющую состояние автомата a(t + 1) в момент дискретного времени t + 1 в зависимости от состояния автомата a(t) и значения входного сигнала x(t) в момент времени t:

a(t + 1) = f[a(t), x(t)]; (10.1)

- функцию выходов, определяющую зависимость выходного сигнала автомата y(t) от состояния автомата a(t) и входного сигнала x(t) в момент времени t:

y(t) = [a(t), x(t)]. (10.2)

Кроме того, на множестве состояний автомата фиксируют одно из внутренних состояний а0 в качестве начального состояния.

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

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

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

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

К примеру, рассмотрим таблицы переходов и выходов некоторого автомата.

Таблица переходов автомата

 

Входной Состояние

сигнал a0 a1 a2 a3

x1 a1 a2 a3 a3

x2 a0 a0 a0 a0

 

Таблица выходов автомата

 

Входной Состояние

сигнал a0 a1 a2 a3

x1 y2 y2 y1 y2

x2 y2 y2 y2 y3

 

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

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

 

Таблица переходов и выходов автомата

 

Выходной Cостояние

сигнал a0 a1 a2 a3

x1 a1 y2 a2 y2 a3 y1 a3 y2

x2 a0 y2 a0 y2 a0 y2 a0 y3

 

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

Граф автомата состоит из узлов, соединенных ветвями. Узлы (кружки на схеме графа) отождествляют внутренние состояния автомата. Каждая ветвь графа, т.е. ориентированная линия, стрелка которой указывает следующее состояние автомата, отмечается входным сигналом, вызывающим в автомате соответствующий данной ветви переход, и выходным сигналом, который возникает при этом переходе. Входной и соответствующий ему выходной сигналы разделяются на чертеже запятой или косой чертой. Если некоторый входной сигнал не меняет состояния автомата, то соответствующая ветвь замыкается на кружке (узле), из которого она выходит.

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

В настоящее время в классе синхронных атоматов рассматривают, в основном, два типа автоматов: автомат Мили и автомат Мура.

Графа атомата Мили, заданного вышеприведенными таблицами, отражен на рис. 10.1. Закон функционирования автоматов Мили может быть задан следующим образом:

a(t + 1) = f[a(t), x(t)];

y(t) = [a(t), x(t)],

где t = 1, 2,.....

Отличительная особенность автоматов Мили состоит в том, что их выходные сигналы в некоторый момент времени е зависят как от состояния автомата, так и от значения входного сигнала в этот же момент времени.

 

Рис. 10.1. Граф автомата Мили.

 

У автоматов Мура выходные сигналы в момент времени t однозначно определяются состоянием автомата в этот же момент времени и в явном виде не зависят от значения входных сигналов xi(t).

Функции переходов и выходов автомата Мура, заданного на множестве входных сигналов X, множестве внутренних состояний A = {a0, a1,,an} и множестве выходных сигналов Y, можно записать в виде

 

a(t + 1) = f[a(t), x(t)], (10.3)

y(t) = [a(t)]. (10.4)

 

эти операторы удобно задавать отмеченной таблицей переходов.

Такие таблицы строятся так же, как и таблицы переходов автомата Мили, но над символами каждого внутреннего состояния записываются выходные сигналы, которые выдает автомат в данном состоянии.

 

Отмеченная таблица переходов автомата

 

Выходной сигнал

y2 y2 y2 y1 y2 y3

Входной Состояние

сигнал a0 a1 a2 a3 a4 a5

x1 a1 a2 a3 a4 a4 a1

x2 a0 a0 a0 a5 a5 a0

Граф автомата Мура, заданного этой таблицей, приведен на рис. 10.2.

На этом рисунке состояния автомата обозначаются сиволами b i.

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

Рис. 10.2. Автомат Мура.

 

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

Помимо автоматов Мили и Мура выделяют еще, так называемый, совмещенный автомат - С-автомат. Абстрактный С-автомат можно представить в виде устройства с одним входом, на который поступают входные сигналы X, и двумя выходами, на которых появляются выходные сигналы Y и U.

 

Y

X

 

U

рис. 10.3

 

Здесь X - входной алфавит; A - множество состояний; Y - выходной алфавит первого типа; U = {u1(t)... um(t)} - выходной алфавит второго типа.

Отличие С-автомата от моделей Мили и Мура состоит в том, что он одновременно реализует две функции выходов 1 и 2, каждая из которых характерна для этих моделей в отдельности. Этот автомат можно описать следующей системой уравнений:

 

a(t+1) = f [a(t), x(t)]; (10.5)

y(t) = 1[a(t), x(t)];

u(t) = 2[a(t)].

 

Выходной сигнал u = 2(as) выделяется все время, пока автомат находится в состоянии as. Выходной сигнал yk = 1(as, xn) выдается во время действия входного сигнала xn при нахождении автомата в состоянии as. От С-автомата легко перейти к автоматам Мили или Мура (с учетом возможных сдвигов во времени на один такт), так же как возможна трансформация автомата Мили в автомат Мура и наоборот.