1.1Реализация конечного автомата

КА реализуются двумя способами – программно и аппаратно.

Программную реализацию можно выполнить на любом языке высокого уровня различными способами.

Аппаратная реализация требует построения устройств памяти для запоминания текущего состояния автомата. На практике обычно используются двоичные элементы памяти (триггеры), запоминающие значение только одного двоичного разряда.

Общий подход к аппаратной реализации КА следующий:

• по графу работы КА составляются таблицы переходов и таблицы выходов;

• по таблицам определяется число входных сигналов, число выходных сигналов и число возможных состояний;

• входные и выходные сигналы и внутренние состояния КА кодируются двоичными кодами;

• по таблицам переходов и выходов составляются кодированные таблицы переходов и выходов;

• по кодированным таблицам переходов и выходов составляется минимальная ДНФ;

• решаются вопросы синхронизации – привязка моментов выдачи выходного сигнала и изменения состояния автомата к моментам поступления входных сигналов.

1.2 Пример

Работа КА описывается следующим графом:

Рисунок 1.2 Граф работы КА

1. По графу работы КА составляем таблицы переходов и таблицы выходов.

Таблица переходов Таблица выходов

δ	x1	x2		λ	x1	x2
s0	s1	s3		s0	y2	y4
s1	s2	s0		s1	y3	y1
s2	s2	s0		s2	y0	y3
s3	s1	s3		s3	y2	y5

2. По таблицам определяем число входных сигналов, число выходных сигналов и число возможных состояний:

входных сигналов 2 – x₁ и x₂;

выходных сигналов 6 – y₀, y₁, y₂, y₃, y₄, y₅;

состояний 4 – s₀, s₁, s₂, s₃.

3. Входные и выходные сигналы, а также внутренние состояния КА кодируем двоичными кодами:

• для входного сигнала достаточно одного разряда - x₁ 0 и x₂→1;

• для выходных сигналов необходимо три разряда, принимаем

y₀→000, y₁→001, y₂→010, y₃→011, y₄→100, y₅→101;

• для кодирования состояний достаточно два разряда, принимаем

s₀→00, s₁→01, s₂→10, s₃→11.

Структурная схема этого автомата после двоичного кодирования может быть представлена в виде:

Рисунок 1.3 Структурная схема КА

(на рисунке БП – блок памяти, который хранит

информацию о текущем состоянии автомата)

4. По таблицам переходов и выходов составляем кодированные таблицы переходов и выходов:

Кодированная таблица переходов и выходов

(q1и q2 кодирует исходное состояние,

Q1и Q2 кодирует следующее состояние)

x	q1	q2	Q1	Q2	z1	z2	z3
0	0	0	0	1	0	1	0
0	0	1	1	0	0	0	1
0	1	0	1	0	0	0	0
0	1	1	0	1	0	1	0
1	0	0	1	1	1	0	0
1	0	1	0	0	0	1	1
1	1	0	0	0	0	1	1
1	1	1	1	1	1	0	1

5. По кодированной таблице переходов и выходов составляется минимальная ДНФ (например, с помощью карты Карно). Минимальная ДНФ составляется отдельно для каждой двоичной переменной (Q₁, Q₂, z₁,z₂,z₃).