Обобщенное представление конечного автомата.
Конечные автоматы получили своё название из-за того, что схема с k-регистрами может находиться в одном из 2k , то есть в конечном числе, состояний. У КА М входов, N выходов и k бит состояний. На вход КА так же подается тактовый сигнал и, возможно, сигнал сброса. КА состоит из двух блоков комбинационной логики: логики перехода в следующее состояние и выходной логики, – и из регистра, в котором хранится текущее состояние. По фронту каждого тактового импульса автомат переходит в следующее состояние, которое определяется текущим состоянием и значениями на входах. Существует два основных класса конечных автоматов, которые отличаются своими функциональными описаниями. В автомате Мура выходные значения зависят лишь от текущего состояния, в то время как в автомате Мили выход зависит как от текущего состояния, так и от входных данных. Конечные автоматы предоставляют систематический способ проектирования синхронных последовательностных схем по заданному функциональному описанию.
Автомат Мили.
Автомат
Мили
(англ. Mealy machine) — конечный автомат,
выходная
последовательность которого (в отличие
от автомата Мура) зависит от состояния
автомата и входных сигналов.
Это означает, что в графе состояний
каждому ребру соответствует некоторое
значение (выходной символ). В вершины
графа автомата Мили записываются
выходящие сигналы, а дугам графа
приписывают условие перехода из одного
состояния в другое, а также входящие
сигналы.
Граф переходов:
ai – входная комбинация, приводит к изменению состояния qi на qi+1 (i+1 – новое состояние), выход V зависит от входа ai и состояния qi
Для фиксации текущего состояния автомата Q используется регистр состояния, имеющий системные сигналы, общие с внешними регистрами. Выходные сигналы V вырабатываются комбинационной логической схемой CL_F, реализующей функцию выходов F. Следующее состояние автомата QNXT формируется комбинационной логической схемой CL_G, реализующей функцию переходов G.
Автоматная таблица:
Недостатки:
- отсутствие развязки по входам, что может привести к длинным цепочкам из комбинационных схем
- задержки прохождения сигналов между регистрами приводит к снижению тактовой частоты синхросигнала
- есть вероятность нестабильного переходного процесса
Преимущества: Возможность реакции автомата в течение текущего такта, что обусловлено зависимостью текущей выходной комбинации v0 от текущей входной комбинации ai.
Автомат Мура.
Автомат Мура (абстрактный автомат второго рода) в теории вычислений — конечный автомат, выходное значение сигнала в котором зависит лишь от текущего состояния данного автомата, и не зависит напрямую, в отличие от автомата Мили, от входных значений. Для любого автомата Мура существует эквивалентный ему автомат Мили: любой автомат Мура путём добавления ряда внутренних состояний может быть преобразован в автомат Мили.
Граф переходов:
ai – входная комбинация, приводит к изменению состояния qi на qi+1 (i+1 – новое состояние), выход V зависит от состояния qi
Автоматная таблица:
Недостатки:
- значительная задержка выхода, обусловленная переключением комбинационной схемы
- возможность возникновения нестабильного переходного процесса на выходе автомата вследствие поочередного переключения каскадов выходной комбинационной схемы F.
- автомат вносит задержку на один такт
Преимущества: отсутствие сквозного прохождения от входа на выход