Синхронные и асинхронные цифровые автоматы

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 21:35, 30 июня 2016.

Некоторые понятия теории автоматов

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

TemplateDifinitionIcon.svg Определение «Определение - Конечный автомат»
Конечный автомат - математическая модель устройства с конечной памятью. Конечный автомат перерабатывает множество входных дискретных сигналов в множество выходных сигналов. С точки зрения информатики это такие автоматы, которые представляют собой дискретные пре­образователи информации. К ним относятся преобразователи, в которых содержится конечное мно­жество входных и конечное выходных сигналов, а также конечное множество внут­ренних состояний

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

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

Для того, чтобы дать определения этим понятиям, необходимо ввести понятие устойчивого состояния.

TemplateDifinitionIcon.svg Определение «Определение - Устойчивое состояние»
Устойчивое состояние - такое состояние, для выхода из которого необходим сигнал, отличный от того, что был входным для перехода в текущее состояние.

Состояние называется устойчивым, если при переходе в это состояние под воздействием входного символа автомат остается в этом состоянии до тех пор, пока на его вход не поступит символ, отличный от

Adeos architecture.
Устойчивое состояние

Синхронный автомат

TemplateDifinitionIcon.svg Определение «Определение - Синхронный автомат»

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

  • - генератор тактовых импульсов воздействует на автомат;
  • - выходные сигналы считываются только во время выдачи тактовых импульсов, когда под воздействием входных и промежуточных сигналов автомат уже перешел в новое состояние.
Adeos architecture.
Синхронный цифровой автомат

Для синхронных автоматов характерно следующее:

  1. Входной сигнал воздействует на автомат в строго фиксированные моменты времени, то есть .
  2. Изменение внутреннего состояния автомата осуществляется в моменты времени, когда нет воздействия входных сигналов.

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

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

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

Асинхронный автомат

TemplateDifinitionIcon.svg Определение «Определение - Асинхронный автомат»
Асинхронный автомат - конечный автомат, в котором выходные сигналы считываются в любое время, а переход в новое состояние определяется лишь временем срабатывания всех логических элементов, входящих в логический преобразователь.

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

Соответственно, каким бы продолжительным не был интервал времени, в течение которого остается неизменным состояние входа, он будет восприниматься автоматом как один и тот же интервал (такт). Следовательно, двум последовательным интервалам и всегда должны соответствовать различные состояния входа.

Изменение внутреннего состояния асинхронного автомата происходит при неизменном состоянии входа.

TemplateExampleIcon.svg Пример Пример асинхронного цифрого автомата
Adeos architecture.
Асинхронный цифровой автомат


Для асинхронного автомата характерно следующее:

  1. Длительность интервалов является величиной переменной и определяется изменением состояния входов автомата.
  2. Переход в новое внутреннее состояние осуществляется при неизменном состоянии входа.

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

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

Перечисленные свойства позволяют считать, что асинхронный автомат работает в непрерывном времени.

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

Преобразование

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

Рассмотрим способы построения таких графов асинхронного и синхронного автомата.

Пусть задан синхронный автомат со следующей таблицей переходов-выходов.

Z\X 01 10
1 1/0 2/0
2 3/0 2/0
3 1/1 2/0

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

Adeos architecture.
Графы синхронного(а) и соответсвующего асинхронного (б) автомата

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

Литература

  1. В.М. Пестриков, В.С. Дудкин, Г.А. Петров Дискретная математика: учеб. пособие – СПб.: СПб ГТУРП, 2013.- 136 с
  2. Фомичев В.С. Формальные языки, грамматики и автоматы
  3. В.С. Выхованец Теория автоматов: учеб. пособие для вузов – Тирасполь, РИО ПГУ, 2001 - 87 с
  4. Теория автоматов (часть I). Конспект лекций. Составитель: к.т.н., доцент каф. ЭВМ В.Ю. Мельцов – Киров, Вятский государственный университет, 2010, 56с.