9. Асинхронные автоматы

9.2 Общие положения.

Особенности асинхронного автомата, или точнее асинхронной модели автомата, определяются свойствами входных сигналов. Напомним, что при построении модели автомата синхронного типа мы пользовались понятием дискретного времени. Входные сигналы такого автомата подобны сигналам импульсного типа (рис. 1,а). При этом были приняты следующие ограничения:

- сигналы могут поступать на вход автомата только в строго определенные моменты времени, задаваемые тактирующей последовательностью СИ с постоянным периодом Т; - длительность входных сигналов t пренебрежимо мала (t ® 0); - в промежутках между тактирующими сигналами на входе автомата сигнал отсутствует. Модель автомата, построенная для токого сигнала, соответствует схемам, работающим с сигналами импульсного типа, элементы которых не имеют гальванической связи. Входные сигналы асинхронного автомата подобны сигналам потенциального типа (рис. 1,б ). Такие сигналы должны обладать следующими свойствами: - сигнал присктствует на входе автомата в каждый момент времени; - длительность входного сигнала не ограничена и превышает некоторую минимальную величину t₀; - изменения входного сигнала могут происодить в произвоьные моменты времени.

Перечисленные свойства позволяют считать, что асинхронный автомат работает в непрерывном времени. Ограничимся, так же как и для синхронного автомата, рассмотрением только двоичных входных сигналов. При этом модель асинхронного автомата может быть использована для описания работы схем, построенных из элементов потенциального типа. Допустим, что под действием входного сигнала pk синхронный автомат А переходит в состояние si. Согласно приведенным свойствам сигналов потенциального типа, pk присутствует на входе автомата и после того, как свершится переход, причем момент его окончания заранее не известен. Следовательно, выполнив такой переход, автомат должен оставаться в состоянии si до следующего изменения сигнала на входе. Описанную ситуацию можно обобщить в виде следующего определения. Если автомат совершает переход из некоторого состояния sj под действием сигнала pk в состояние si, т. е. j(sj, pk) = si, и остается под действием сигнала pk в этом же состоянии j(sj, pk) = si, то такое состояние называется устойчивым. Приведенное определение позволяет нам уточнить понятие асинхронного автомата. Автомат, все состояния которого устойчивы, называется асинхронным. Следует заметить, что в дальнейшем при более детальном анализе процесса работы автомата придется отказаться от этого определения и допустить наличие неустойчивых состояний.

9.2.1. Описание работы асинхронного автомата

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

В асинхронном автомате все переходы осуществляются между устойчивыми состояниями, что создает дополнительные сложности при построении таблицы переходов. Если состояние si является устойчивым, то в клетке таблицы переходов, определяемой строкой, отмеченной состоянием si, и столбцом, отмеченным входным сигналом pk, должен быть записан символ состояния si, поскольку j(si, pk) = si. Таким образом, для устойчивых состояний в таблице переходов асинхронного автомата необходимы дополнительные средства, указывающие, в какое состояние должен перейти автомат при изменении входного сигнала. Это затруднение решается следующим образом. Процесс изменения состояния автомата разбивается на два этапа, полагая, что вначале происходит изменение входных сигналов, а состояние автомата остается неизменным, а затем уже происходит изменение состояния при новых значениях входных сигналов.Первому этапу этого процесса соответствует перемещение по строке таблицы переходов, отмеченной старым состоянием, в столбец отмеченный новыми значениями входных сигналов. Итак, первый этап однозначным образом определяет новую клетку таблицы, которая соответствует переходному состоянию автомата. Такие состояния будем называтьтранзитивными. Запишем в этой клетке символ того состояния, в которое должен перейти автомат. При этом второму этапу изменения состояния соответствует перемещение по столбцу, определяемому новыми входными сигралами, в строку, отмеченную тем состоянием, в которое автомат должен перейти. Для того чтобы не путать устойчивые состояния с указателями перехода, используемыми на втором этапе, условимся заключать символы, соответствующие устойчивым состояниям, в круглые скобки. Примером таблицы переходов и выходов асинхронного автомата является табл. 1. Эта таблица построена по графу, приведенному на рис. 2,б.

 

   Рассмотрим, как выполняются переходы в табл. 1 на примере. Допустим, что автомат находится в состоянии 3 под действием входных сигналов 00. Согласно таблице переходов, это состояние является устойчивым. Если теперь значение входных сигналов изменится на 10, то для того, чтобы найти в какое состояние перейдет автомат, необходимо выполнять перемещение по третьей строке в столбец, отмеченный сигналами 10. В определенной таким образом клетке таблицы находится номер состояния, в которое переходит автомат - это состояние 5*. Перемещаясь по вертикали в столбце 10 до строки 5*, находим, что это состояние является устойчивым. Следовательно, переход завершен. В рассмотренном примере при переходе из одного устойчивого состояния в другое автомат миновал одно транзитное состояние. В общем случае изменение состояния автомата может происходить с переходом через несколько транзитных состояний, которые, конечно, должны быть расположены в одном и том же столбце таблицы переходов. Примеры таких переходов будут приведены в следующем параграфе.