Определение цифрового автомата

Основные понятия теории автоматов

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

Реальные цифровые автоматы конечны, т. е. множество входных и выходных сигналов, а также число входных и выходных каналов и множество состояний автомата конечны.

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

Для цифрового автомата синхронного действия входные сигналы действуют в строго определённые моменты времени при Т = const, определяемые генератором синхронизирующих импульсов, в которые возможен переход автомата из одного состояния в другое.

Для цифрового автомата асинхронного действия Т ¹ const и определяется моментами поступления входных сигналов, а переход автомата из одного состояния в другое осуществляется при неизменном состоянии входа.

Для идеализированных цифровых автоматов, когда не учитываются переходные процессы в элементах схемы автомата, разница в фактических величинах Т для правильного функционирования автомата не имеет значения, поэтому для описания законов функционирования цифровых автоматов вводят абстрактное время, принимающее целые неотрицательные значения t = 0, 1, 2,....

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

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

Математической моделью конечного цифрового автомата является абстрактный автомат, определяемый как шестикомпонентный кортеж S = { A, z, w, d, l, a ₁}, у которого:

1) A = { a ₁ ,..., a_m,..., a_M } – множество состояний (алфавит состояний);

2) Z = { z ₁ ,..., z_f,...,z_F } – множество входных сигналов (входной алфавит);

3) W = { w ₁ ,...,w_g,...,w_G } – множество выходных сигналов (выходной алфавит);

4) функция переходов d определяет правила перехода автомата из одного состояния в другое в зависимости от значений входных сигналов и состояния автомата: d (a, z);

5) функция выходов l определяет правила формирования выходных сигналов автомата: l (a, z);

6) a ₁ – начальное состояние автомата (a ₁ Î A).

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

Автомат имеет один вход и один выход (рис.3.1) и работает в некотором идеализированном дискретном времени, принимающим целые неотрицательные значения t = 0, 1, 2,....

 

 

Рис. 3.1. Абстрактный автомат

 

В каждый момент t дискретного времени автомат находится в некотором состоянии а (t) Î A, причём в начальный момент t = 0 он всегда находится в начальном состоянии a (0) = a _2. Будучи в момент времени t в состоянии a (t), автомат способен воспринимать на своём входе сигнал z (t) Î Z. В соответствии с функцией выходов в этот же момент времени он выдает выходной сигнал w (t) Î W и в следующий момент времени (t+ 1) согласно функции переходов перейдёт в состояние a (t+ 1) Î A. Смысл понятия абстрактного автомата состоит в том, что он реализует некоторое отображение множества слов входного алфавита Z в множество слов выходного алфавита W. Иначе, если на вход автомата, установленного в начальное состояние a ₁, подавать буква за буквой некоторую последовательность букв входного алфавита z (0), z (1), z (2),... – входное слово, то на выходе автомата будут после­до­вательно появляться буквы выходного алфавита w (0) ,w (1) ,w (2) ,... – выходное слово. Относя к каждому входному слову, соответствующее ему выходное слово, получаем отображение, индуцированное абстрактным автоматом. Термин “абстрактный” используется в связи с идеализированным дискретным временем, а также потому, что в этой модели абстрагируются от реальной физической природы входных и выходных сигналов, рассматривая их как буквы некоторого алфавита.

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

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

 

Варианты цифровых автоматов

На практике наибольшее распространение получили два класса автоматов – автоматы Мили и Мура, названные по имени впервые исследовавших эти модели американских учёных G.H. Mealy и E.F. Moore.

Автомат Мили. Закон функционирования автомата Мили задаётся уравнениями:

а (t+ 1) = d (a (t) ,z (t));

w (t) = l (a (t) ,z (t)); (3.1)

a (0) = a ₁, t = 0,1,2,....

Автомат Мура. Закон функционирования автомата Мура задаётся уравнениями:

a (t+ 1) = d (a (t) ,z (t));

w (t) = l (a (t)); (3.2)

a (0) = a ₁, t = 0,1,2,....

 

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

Отметим важное отличие в функционировании этих автоматов. Выходные сигналы автомата Мура отстают на один такт от выходных сигналов автомата Мили, эквивалентного ему.

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

S = { A, Z, W, U, d, l ₁, l ₂, a ₁},

где А = { а ₁ ,..., а_М } – множество состояний;

Z = { z ₁ ,..., z_F } – входной алфавит;

W = { w ₁ ,..., w_G } – выходной алфавит автомата Мили;

U = { u ₁ ,..., u_H } – выходной алфавит автомата Мура;

d = (а, z) – функция переходов автомата;

l ₁ – функция выходов автомата Мили;

l ₂ – функция выходов автомата Мура;

а ₁ Î А – начальное состояние автомата.

 

Абстрактный С -автомат можно представить в виде устройства (рис.3.2) с одним входом, на который поступают сигналы из входного алфавита Z, и двумя выходами, на которых появляются сигналы из алфавитов W и U.

 

Рис.3.2. Абстрактный С – автомат

 

Отличие С -автомата в том, что он одновременно реализует две функции выходов l ₁ и l ₂, каждая из которых характерна для модели Мили и модели Мура в отдельности.

Закон функционирования С -автомата можно описать уравнениями:

а (t + 1) = d (а (t), z (t));

w (t) = l ₁(a (t), z (t)); (3.3)

u (t) = l ₂(a (t));

a (0) = a ₁; t = 0,1,2,....

Выходной сигнал u_h=l ₂(a_m) выдаётся всё время, пока автомат находится в состоянии a_m. Выходной сигнал w_g= l ₁ (a_m, z_f) выдаётся во время действия входного сигнала z_f при нахождении автомата в состоянии a_m.

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

Автомат без памяти (комбинационная схема). Алфавит состояний такого автомата содержит единственную букву, поэтому понятие функции переходов вырождается и становится ненужным для описания работы автомата. Автомат задается тремя объектами: Z, W, l. Функция выходов принимает вид

w (t) = l (z (t)), (3.4)

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

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

Автономный автомат. В таком автомате входной алфавит состоит из одной буквы. Автомат задается четырьмя объектами: А, W, d, l с возможным выделением начального состояния а _2.

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

a (t+ 1) = d (a (t));

w (t) = l (a (t)). (3.5)

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

w (1) w (2) w (3)...

a (1) a (2) a (3)... (3.6)

Если автономный автомат конечен и число его состояний равно k, то среди значений а (1), а (2),..., à (ê) найдутся повторяющиеся состояния. Следовательно, каждая из последовательностей (2.6) окажется периодической с длиной периода не больше числа состояний автомата и, возможно, с некоторым предпериодом.

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

Автомат без выхода. В таком автомате выходной алфавит содержит только одну букву. Автомат задается тремя объектами: А, Z, d. Из функций, задающих поведение автомата, сохраняется лишь функция переходов

a (t+ 1) = d (a (t), z (t)). (3.7)

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

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

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

На рис.3.3 представлена обобщенная структура произвольного операционного устройства, где D ₁ и D ₂ – шины, по которым поступает исходная информация и результаты ее обработки соответственно;
Х – шины, по которым поступают сигналы, характеризующие состояние ОА (например, отрицательный результат, переполнение сумматора и т.д.). Эти сигналы часто называет осведомительными; Y – шины, по которым поступают управляющие сигналы из УА на ОА в соответствии с алгоритмом выполняемой в ОА операции; g – шины, по которым поступают сигналы, определяющие выполняемую операцию;
СС – стартовый сигнал пуска операционного устройства; КР – сигнал, характеризующий конец работы алгоритма.

 

Рис.3.3. Обобщенная структура операционного устройства

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

Управляющие автоматы используются не только в операционных устройствах вычислительной техники в системе УА – ОА, но и в разнообразных системах автоматики по управлению технологическими процессами и объектами, которые обобщенно можно назвать объектами управления (ОУ). В этом случае УА, в соответствии с алгоритмом функционирования ОУ и в зависимости от значений осведомительных сигналов о состоянии ОУ, поступающих от датчиков ОУ, и возможных внешних сигналов, вырабатывает и подает на исполнительные механизмы ОУ последовательность управляющих сигналов, обеспечивающих выполнение операций или процедур, предусмотренных целями управления. Для сложных систем управления, когда требуется выполнять большой объем работ по обработке информации о состоянии ОУ и выработки управляющих воздействий на ОУ в зависимости от целевой функции управления, в качестве УА могут выступать ЭВМ соответствующего класса.

Микропрограммные автоматы. Управляющий автомат, реализующий микропрограмму выполнения операции обработки информации, часто называют микропрограммным автоматом (МПА). Это вытекает из следующей интерпретации взаимодействия ОА и УА в процессе выполнения каких-либо операций по обработке информации:

а) Любая операция, реализуемая операционным устройством, рассматривается в виде последовательности элементарных неделимых актов обработки информации, выполняемых в течение одного такта автоматного времени (одного шага алгоритма), называемых микрооперациями. Множество микроопераций и сигналов, инициирующих их выполнение, обозначают одними и теми же символами, кото­рые составляют выходной структурный алфавит УА Y = { y ₁, y ₂ ,..., y_N }. В случае, если несколько микроопераций реализуются в ОА одновременно, то это подмножество микроопераций называют микрокомандой.

б) Для управления порядком следования микрокоманд используются логические условия (ЛУ), которые в зависимости от результатов преобразования информации в ОА могут принимать значения 1 или 0. Множество ЛУ (осведомительных сигналов) обозначают символами, которые составляют входной структурный алфавит X = { x ₁, x ₂ ,..., x_L }.

в) Последовательность выполнения микрокоманд, определяемая функциями перехода УА, записывается в виде алгоритма, представленного в терминах микроопераций и ЛУ и называемого микропрограммой. В качестве начального языка для описания микропрограмм выполнения операций чаще всего используется язык операторных схем алгоритмов ГСА и ЛСА.

Микропрограммные автоматы с жесткой и программируемой логикой. Управляющие микропрограммные автоматы аппаратно могут быть реализованы на основе так называемой жесткой логики и программируемой логики.

Автомат с жесткой логикой строится на базе использования логи­ческих элементов (ЛЭ) и элементов памяти (элементарных автоматов с двумя внутренними состояниями). Изменить алгоритм работы такого автомата нельзя, не изменяя соединений между элементами. Для таких автоматов характерны высокое быстродействие, определяемое только задержками используемых ЛЭ и элементов памяти, пропорциональный рост объема оборудования в зависимости от сложности реализуемого алгоритма и малые удельные затраты оборудования при реализации простых микропрограмм. Однако автоматы с жесткой логикой не обладают гибкостью при внесении изменений в алгоритм их функционирования, необходимость в которых особенно часто возникает в процесс проектирования цифровых устройств.

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

123Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: