Общее понятие цифрового автомата с памятью

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

Далее рассмотрим устройство с одним входом и одним выходом , функционирующее в соответствии с временной диаграммой, изображенной на рис. 5.2.

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

Работа данного устройства может быть описана графом, изображенным на рис. 5.3.

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

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

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

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

Совокупности входных символов ЦА образуют входной алфавит автомата. Отдельные символы алфавита называются буквами. Законченные последовательности букв называются словами.

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

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

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

В данном учебном пособии наибольшее внимание уделено синхронным автоматам.

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