Что такое цифровой автомат
Перейти к содержимому

Что такое цифровой автомат

  • автор:

Понятие «цифровой автомат»

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

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

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

Рис. 1.1. Цифровое устройство обработки информации

Число входных и выходных сигналов конечно вследствие ограниченной разрядности АЦП и ЦАП, а также цифровых устройств ввода/вывода.

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

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

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

1.2. Функционирование абстрактного автомата
в дискретном времени

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

В момент времени 0Т автомат устанавливается в начальное состояние а0, и формируется функция перехода δ(а0, xj), где xj – текущий входной сигнал. Если входной сигнал в течение такта остается неизменным, то в момент времени 1Т формируется функция перехода δ(а0, xj), и автомат переходит в состояние aS, т. е. δ(а0, xj) = aS. Если входной сигнал меняется, то в момент времени 1Т δ(а0, xm) = am (рис. 1.2).

Рис. 1.2. Иллюстрация функционирования цифрового автомата в дискретном времени

Тогда можно записать:

δ[nT] = f(a[(n – 1)T], x[nT]), (1.1)

где квадратными скобками обозначен момент дискретного времени.

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

λ(t) = φ(a[nT], x(t)), (1.2)

где nT ≤ t < (n + 1)T.

Например, в промежутке t Î [3T, 4T] функция выхода λ(t) определяется из соотношения λ(t) = φ(a[3T], x(t)). Правая граница интервала не включается, т. к. в момент времени 4T автомат совершит новый переход из состояния в состояние.

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

ВВЕДЕНИЕ

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

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

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

ОБЩИЕ СВЕДЕНИЯ О ЦИФРОВОМ АВТОМАТЕ

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

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

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

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

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

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

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

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

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

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

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

Закон функционирования автоматов Мили может быть задан следующим образом:

а t+1 — новое состояние цифрового автомата;

а t — предыдущее состояние автомата;

y t — выходные сигналы текущего времени;

x t — сигналы на входе в данный момент времени.

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

Функции переходов и выходов автомата Мура:

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

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

— память — фиксирует внутреннее состояние цифрового автомата.

— комбинационная схема управления памятью.

— комбинационная схема формирования выходных сигналов.

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

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

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

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

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

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

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

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

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

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

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

Пример Пример графического способа — Граф автомата Мура S 3 <\displaystyle S_<3>>

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

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

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

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

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

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

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

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

Пример Пример аналитического способа — Аналитическая запись автомата Мура S 3 <\displaystyle S_<3>>

Добавить комментарий

Ваш адрес email не будет опубликован.