Цифровой автомат

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 23:41, 19 мая 2016.
TemplateDifinitionIcon.svg Определение «Определение - Цифровой автомат»
Цифрово́й автома́т - это логическое устройство, способное находиться в одном из нескольких устойчивых состояний, осуществлять обработку, хранение и получение дискретной информации согласно некоторому алгоритму.

Понятие

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

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

Структурная схема

Структурная схема содержит запоминающие элементы и комбинационные схемы.

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

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

Способы описания

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

Наиболее распространёнными способами описания цифрового автомата являются табличный, графический и аналитический.

Графический способ

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

TemplateExampleIcon.svg Пример Пример графического способа - Граф автомата Мура
Граф автомата Мура

Табличный способ

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

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

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

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

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

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

- - -
- - -
- - -
- - -
- - -

Аналитический способ

При аналитическом способе задания для каждого состояния автомата указываются отображения, представляющее собой множество всех троек, первый параметр которых – входной сигнал, второй – выходное состояние, третий – выходной сигнал, который выдаёт автомат при переходе из одного состояния в другое.

TemplateExampleIcon.svg Пример Пример аналитического способа - Аналитическая запись автомата Мура

Типы цифровых автоматов

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

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

Описанный выше автомат – синхронный.

Преобразования цифровых автоматов

Цифровой автомат преобразовывает слова входного алфавита в слова в выходном алфавите.

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

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

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

TemplateDifinitionIcon.svg Определение «Определение - Автомат Мура»
Автомат Мура - автомат, функция выходов которого определяет значение выходного символа только по состоянию автомата (функция меток).

Автомат Мура можно рассматривать как частный случай автомата Мили.

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

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

Преобразование из автомата Мура в автомат Мили

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

Граф автомата Мили , эквивалентный автомату Мура

Выделение совмещенной таблицы переходов и выходов автомата Мили

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

Таблица выходов эквивалентного автомата Мили

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

Преобразование из автомата Мили в автомат Мура

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

Автомат Мили с преходящим состоянием

Совмещенная таблица автомата Мили

Вход Состояние
Автомат Мура , эквивалентный автомату Мили

Отмеченная таблица эквивалентного автомата Мура

Выход -
Вход Состояние

Преходящее состояние в автомате Мура порождает состояние с неопределённым выходным сигналом в эквивалентном автомате Мура.

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

Литература

  1. Гудилин А.Е. Цифровая схемотехника: Учебное пособие – Челябинск: Издательство ЮУрГУ, 2000. – С. 130. – ISBN 5–696–01724–X .
  2. Каган Б. М. Цифровые вычислительные машины и системы – М. : Энергия, 1973. – C. 680.

См. также