(Общие сведения).
Все многообразие элементов, узлов, блоков, устройств, из которых состоит любая ЭВМ, является примером различных типов преобразователей информации - цифровых автоматов. Методы теории цифровых автоматов (ЦА), являющихся математической моделью цифровых устройств, используются в качестве теоретической базы для анализа и синтеза различных цифровых устройств ЭВМ.
Под цифровым автоматом будем понимать устройство предназначенное для преобразования цифровой (дискретной) информации, способное переходить под воздействием входных сигналов из одного состояния в другие и выдавать выходные сигналы. Отличительные особенности ЦА заключаются в том, что они имеют дискретное множество внутренних состояний и переход из одного в другое осуществляется скачкообразно.
Дискретность информации проявляется в том, что она представляется посредством набора слов конечной длины в некотором алфавите.
Реальные ЦА конечны, т. е. множество входных и выходных сигналов, а также число входных и выходных каналов и множество состояний автомата конечны.
ЦА функционируют в дискретные моменты времени, временной интервал между которыми Т называется тактом. В зависимости от того, чем определяется время Т, различают автоматы синхронного и асинхронного действия.
Для ЦА синхронного действия входные сигналы действуют в строго определенные моменты времени при Т = const, определенные генератором синхроимпульсов, в которые возможен переход из одного состояния в другое.
Для ЦА асинхронного действия Т ¹ const и работа ЦА определяется моментами поступления входных сигналов, а переход из одного состояния в другое осуществляется при неизменном состоянии входа.
Для идеализированных ЦА не учитывается переходные процессы в схемах и разница в фактических величинах Т для правильного функционирования не имеет значение. Для описания законов функционирования ЦА вводят абстрактное время.
По степени детализации описания ЦА различают автоматы абстрактные и структурные. В соответствии с этим различают абстрактную и структурную теорию ЦА.
Абстрактные ЦА рассматриваются как " черный ящик ", имеющий один вход и один выход, т. е. отвлекаются от структуры ЦА и его входных Х (t) и выходных Y (t) сигналов.
|
Для задания абстрактного автомата необходимо задать три алфавита:
- входной X = { 
}
- выходной Y = { 
}
- состояний S = { 
}
Тогда закон функционирования абстрактного автомата может быть задан уравнениями:
1.1
где ¦ (s, x) - функция переходов автомата;
r (x, s) - функция выходов автомата;
- начальное состояние автомата.
ЦА, закон функционирования которых определяется уравнениями (1.1), называются автоматами Мили.
ЦА, выходные сигналы в которых только от состояния автомата и не зависят от значения входных сигналов, называются автоматами Мура, т. е. для них уравнения (1.1) преобразуются в форму
1.2
где m [ s (t) ] -сдвинутая функция выхода.
ЦА, имеющая более одного внутреннего состояния, называются автоматами с памятью. Частный случай абстрактных ЦА - автоматы с одним внутренним состоянием. Такие тривиальные автоматы называют автоматами без памяти или комбинационными схемами. Закон функционирования таких автоматов будет определяться одним уравнением:
Y (t) = ¦ [ x(t)],
т.е. каждому входному сигналу х(t) сопоставляется свой выходной сигнал y(t).
Наиболее распространенными стандартными способами задания абстрактных цифровых автоматов является задание их с помощью матриц, таблиц переходов и выходов или одной совмещенной таблицей, с помощью направленных графов, вершины которого отождествляются с состояниями автомата, а соединяющие их стрелки – с входными и выходными сигналами. Таблица переходов и выходов или граф цифрового автомата в явном виде задает функцию переходов и выходов и реализует отображение множества слов входного алфавита в множество слов выходного алфавита, т.е. любому входному слову из входного алфавита автомата будет соответствовать вполне определенное выходное слово из выходного алфавита. Наряду со стандартными способами задания абстрактных цифровых автоматов существуют так называемые начальные языки, с помощью которых цифровой автомат описывается на поведенческом уровне, т.е. могут быть заданы отображения последовательностей состояний входа в последовательность состояний выхода. Функция переходов и выходов с помощью таких языков в явном виде не задается. К таким языкам, например, относят языки регулярных выражений алгебры событий, предикатный, операторных схем алгоритмов и др. Одна из задач абстрактной теории цифровых автоматов – рассмотрение вопросов преобразования описания цифрового автомата на начальном языке в описание на одном из стандартных языков.
Структурный цифровой автомат в отличие от абстрактного является его дальнейшей детализацией, когда рассматривается как его внутренняя структура, так и структура входных и выходных сигналов. Это означает, что в теории таких автоматов изучаются методы построения автоматов из элементарных автоматов, способы кодирования внутренних состояний автомата, а также способы кодирования входных и выходных сигналов элементарными сигналами, подаваемыми по реальным физическим входным и выходным каналам. При решении вопросов кодирования каждому состоянию абстрактного автомата ставится в соответствие комбинации состояний элементарных автоматов, имеющих два внутренних состояния, а каждому входному (выходному) сигналу – комбинация элементарных двузначных сигналов.
Одна из основных задач теории цифровых автоматов, решаемых применительно к построению различных цифровых устройств ЭВМ, заключается в том, чтобы задачу анализа и синтеза таких устройств свести к задаче анализа и синтеза комбинационных схем. При этом в качестве основного математического аппарата используется аппарат алгебры логики, что связано с двоичным представлением структурного алфавита цифровых устройств ЭВМ.