Дискретные автоматы

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

Автоматом называют любое устройство, осуществляющее преобразование информации.

Классификация:

1. В зависимости от типа сигналов, используемых для представления информации в автомате, и характера работы автомата во времени автоматы делят на два класса:

- автоматы непрерывного действия;

- автоматы дискретного действия (дискретные автоматы).

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

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

2. В зависимости от характера преобразования информации во времени дискретные автоматы делятся на

- синхронные;

- асинхронные.

В синхронном дискретном автомате возможны 2 способа изменения значений уровня сигналов:

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

На Рис. 1, а изображен график изменения дискретного по уровню сигнала U в функции автоматного времени t.

Рис. 1 Изменение дискретного по уровню сигнала в функции автоматного времени

2). Сигналы могут принимать отличные от нуля значения лишь в отдельные фиксированные моменты времени. В данном случае номеруются не интервалы времени, а моменты времени, и автоматное время выражается в номерах моментов времени (Рис. 1, б).

В синхронном дискретном автомате как при использовании непрерывных во времени сигналов (Рис. 1, а), так и при использовании дискретных во времени сигналов (Рис. 1, б) моменты автоматного времени, в которые происходят изменения сигналов или в которые существуют сигналы, разделены одинаковыми интервалами времени длительностью t, получившими название тактов. В реальном автомате эти моменты времени задаются с помощью специального устройства, называемого генератором тактовых сигналов.

В асинхронных дискретных автоматах моменты автоматного времени не задаются принудительно с помощью генератора и могут занимать любое положение во времени.

3. По зависимости сигналов на m выходах от сигналов на n входах.

1). Значения сигналов на выходах автомата в данный момент времени зависят только от значений сигналов на входах в тот же момент времени:

y_j(t) = F_j[x_i(t)]; i=1,..., n; j=1,..., m.

Такой автомат называется автоматом без памяти или комбинационной схемой (Рис. 2, а), что тоже самое - логическая схема.

Рис. 2 Дискретные автоматы: а - автомат без памяти, б - автомат с памятью

2). Значения сигналов на выходах автомата в данный момент времени зависят от значений сигналов на входах автомата в этот же момент времени и предшествующие моменты времени:

y_j(t)=F_j[x_i(t), x_i(t-1),..., x_i(0)]; i=1,..., n, j=1,..., m.

Такой автомат называется автоматом с памятью (Рис. 2, б).

Очевидно, что автомат без памяти представляет собой частный случай автомата с памятью.

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

Отдельные значения дискретных по уровню сигналов в дискретных автоматах кодируются буквами некоторого алфавита. В ЦС, как правило, для кодирования сигналов используется алфавит, состоящий из двух букв (цифр) - нуля и единицы. Автоматы с кодированием значений сигналов цифрами (0 и 1) часто называют цифровыми автоматами.

Для описания работы цифрового автомата используют специальный математический аппарат - аппарат двоичных функций. В теории двоичных функций рассматриваются двоичные функции двоичных аргументов и двоичные функции, аргументы которых могут принимать более чем два значения. Математический аппарат, в котором используются двоичные функции двоичных аргументов, называется исчислением высказываний или алгеброй логики или булевой алгеброй. Математический аппарат, в котором используются двоичные функции недвоичных аргументов, называется исчислением предикатов.