Назначение и свойства цифровых автоматов. Комбинационные схемы или автоматы без памяти

термин «автомат» обозначает математическую модель реальных технических автоматов, т.е. представляется как «черный ящик», имеющий конечное число входов и выходов и некоторое множество внутренних состояний, которые он может изменять мгновенно. Устройства, служащие для преобразования дискретной информации, называются дискретными (цифровыми) автоматами. Их делят на синхронные и асинхронные. В синхронных автоматах моменты времени, в которые оказывается возможным изменение состояния автомата, определяются специальным устройством – генератором синхронизирующих импульсов. Соседние моменты времени оказываются при этом обычно разделенными равными временными промежутками. Автомат называется конечным, если множество его внутренних состояний и множество значений входных сигналов – конечные множества. Конечные автоматы разделяют на автоматы без памяти и автоматы с памятью. Автоматом с памятью называют автомат, описываемый функциями переходов и выходов, оператор которого является оператором с памятью. Выходные слова автомата с памятью зависят не только от входных слов, но и от последовательности их поступления. Автомат с памятью имеет множество внутренних состояний, в которое он переходит под воздействием слов входного алфавита. Наличие множества внутренних состояний придает автомату способность запоминания входной информации, поступившей на вход автомата в прошлом.

Любой абстрактный автомат задается совокупностью из 6 объектов:

A=(X, Y, Q, q0,?,?)

где Х – конечное множество входных сигналов, называемое входным алфавитом автомата; Y – конечное множество выходных сигналов, называемое выходным алфавитом автомата; Q – произвольное множество, называемое множеством состояний автомата; q0 – элемент из множества Q, называемый начальным состоянием автомата;

?(q, x),?(q, x) - две функции, задающие однозначные отображения множества пар (q, x), где q?Q и x?X, в множества Q и Х. Функция?(q, x) называется функцией переходов автомата, а функция?(q, x) – функцией выходов, либо сдвинутой функцией выходов.

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

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

Автоматами Мура называют такие автоматы, у которых выходной сигнал Y(t) не зависит явно от входного сигнала X(t), а определяется лишь внутренним состоянием автомата в момент времени t.Автомат Мура задается уравнениями:

В данной системе уравнений первая строка есть функция перехода, вторая – функция выхода.

В автомате Мили выходной сигнал в момент времени t, зависит как от внутреннего состояния автомата в момент t, так и от входного сигнала в момент времени t.