Автоматы с памятью

Узлы и устройства, содержащие элементы памяти относятся к классу автоматов с памятью (цифровых автоматов). Наличие элементов памяти позволяет автомату иметь некоторое внутреннее состояние Q, определяемое совокупностью состояний всех элементов памяти. В зависимости от внутреннего состояния автомат с памятью по-разному реагирует на один и тот же набор входных сигналов X. При этом автомат переходит в новое состояние и вырабатывает набор выходных сигналов Y /4/. Общую схему автомата с памятью условно можно представить следующим образом (Рисунок 2.8):

Рисунок 2.8 – Общая схема автомата с памятью

X – совокупность одновременно действующих входных сигналов; Y – совокупность выходных сигналов; Q – совокупность внутренних состояний.

Переходы автомата из одного состояния в другое начинаются с некоторого исходного состояния Q₀. При этом переход из текущего состояния в новое выполняется по правилам, задаваемым функцией переходов f: и зависит как от текущего состояния Q_т, так и от входных сигналов в текущий момент времени X_т. Выходные сигналы в текущий момент времени Y_т формируются по правилам, задаваемым функцией выходов φ: и зависит от текущего состояния автомата Q_т и текущих входных сигналов X_т. Вся последовательность входных сигналов определяет последовательность состояний автомата и его входных сигналов. Это объясняет название «последовательные схемы», применяемое также и для обозначения автоматов с памятью /4/.

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

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

По видам зависимости состояний перехода и выходных сигналов, цифровые автоматы делят на два класса /4/:

1) Автоматы Мили – в них новое состояние и выходные сигналы зависят как от текущего состояния автомата, так и от текущих входных сигналов, что описывают формулы 2.1 и 2.2.

(2.1)

(2.2)

2) Автоматы Мура – в них новое состояние зависит от текущего состояния и текущих входных сигналов, а выходные сигналы – только от текущего состояния, что описывают формулы 2.3 и 2.4.

(2.3)

(2.4)

Названия автоматов даны по фамилиям их изобретателей Джорджа Мили (George H. Mealy, 31.12.1927 – 21.06.2010) и Эдварда Мура (Edvard F. Moore, 23.11.1925 – 14.06.2003), американских профессоров в области математики и информатики.

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

Элементарный автомат с памятью – это цифровой автомат, обладающий следующими свойствами:

1) является автоматом Мура;

2) число состояний автомата равно двум;

3) является детерминированным (правило переходов и выходов являются однозначными):

4) имеет полную систему переходов и выходов (функции переходов f и выходов φ описаны для всех допустимых состояний и входных сигналов);

5) структурные каналы автомата несут двоичную информацию.

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