1. Наименование работы.

2. Цель работы.

3. Краткие теоретические сведения.

4. Все проведенные расчеты.

5. Схемы всех запоминающих элементов и триггеров.

6. Временные диаграммы работы схем.

7. Выводы по работе.

3РГР №4. ПРОЕКТИРОВАНИЕ И ИССЛЕДОВАНИЕ СИНХРОННЫХ АВТОМАТОВ

3.1Цель работы

Изучить принципы и провести абстрактное и структурное проектирование синхронного автомата.

3.2Теоретические сведения

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

Теория автоматов разделяется на абстрактную и структурную. Абстрактная теория проектирования автоматов включает определение реакции автомата на внешнюю среду. Структурная теория изучает как структуру самого автомата так и структуру входных воздействий и реакцию автомата на выход.

При синтезе автомата необходимо определить: Х–входной алфавит, Y–выходной алфавит, А–алфавит состояний автомата, функцию переходов , которая описывает переход автомата из одного состояния в другое под воздействием входного сигнала, функцию выхода , определяющую выходной сигнал, которая зависит от состояния, в котором находится автомат в данный момент, и может зависеть от входного сигнала. Состояние—это абстрактное понятие, которое характеризует состояние автомата в данный момент, хранит всю предысторию. Для автомата Мура выходной сигнал является функцией от состояния, для Мили—от состояния и входного сигнала.

Автомат Мура полностью описывается системой уравнений:

a(t+1)= (a(t),x(t)),

y(t)=(a(t)),

где a(t+1) состояние автомата в момент времени t+1, a(t) состояние автомата в момент времени t, x(t) сигналы на входе автомата в момент времени t.

Для автомата Мили система уравнений имеет вид:

a(t+1)= (a(t),x(t)),

y(t)=(a(t),x(t)).

Рассмотрим проектирование автоматов на примере.

3.3Абстрактный синтез автомата

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

На вход автомата подается двоичный сигнал, т. е. входной алфавит Х={0, 1}.

Выходной алфавит Y={0, 1}.

Определим алфавит состояний А={ a₀, a₁, a₂, a₃, a₄ }.

a₀—начальное состояние автомата. Из него автомат под воздействием сигнала 0 переходит в новое состояние a₁, под воздействием единичного сигнала автомат не изменяет своего состояния. Из состояния a₁ при появлении на входе сигнала 0 автомат переходит в следующее состояние a₂, таким образом, автомат находится в состоянии a₂ в случае, если пришли два нуля. При сигнале 1 на входе автомат из состояния a₁ переходит в начальное состояние. Находясь в состоянии a₂ автомат по 0 должен остаться в текущем состоянии a₂, так как предыдущие два сигнала на входе были двумя нулями, по 1 автомат перейдёт в следующее состояние a₃. Из состояния a₃ автомат при нулевом сигнале установится в начальное состояние и будет ожидать начала следующей последовательности, при единичном — установится в состояние a₄, которое определяет, что на вход автомата поступила последовательность сигналов 0,0,1,1. Следовательно, сигналу a₄ приписывается выходной сигнал 1, всем остальным состояниям — 0. Из состояния a₄ при подаче на вход 1 автомат переходит в начальное состояние, 0 — в состояние a₁, так как сигнал 0 является началом новой последовательности.

Таблица 4.1 - Таблица переходов автомата.

А\х	0	1
a0	a1	a0
a1	a2	a0
a2	a2	a3
a3	a1	a4
a4	a1	a0

Таблица 4.2 - Таблица выходов автомата Мура.

А	y
a0	0
a1	0
a2	0
a3	0
a4	1

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

Таблица 4.3 - Таблица выходов для автомата Мили.

А\х	0	1
a0	0	0
a1	0	0
a2	0	0
a3	0	1
a4	0	0