Использование триггеров.

При большом числе состояний автомата обычно выгоднее использовать D — триггеры.

Если граф переходов автомата имеет относительно небольшое число состояний и почти не содержит петель, предпочтение можно отдать использованию Т—триггера.

При большом количестве петель или требовании установки автомата в начальное состояние потребуется использовать RS-триггер.

Наиболее известным методом решения данной задачи является канонический метод структурного синтеза, предусматривающий выполнение следующих шагов:

Шаг 1. Выбор набора элементов памяти (ЭП) (триггеров) и системы логических элементов;

В качестве системы логических элементов используются элементы булева базиса – И ИЛИ НЕ и их комбинации.

Шаг 2. Кодирование входных, выходных сигналов и внутренних состояний автомата. Для этого первоначально необходимо определить наименьшее количество букв для кодирования полученных на этапе абстрактного синтеза входных и выходных сигналов.

Наименьшее число ЭП определяется величиной , где п — число внутренних состояний автомата. Эта же формула используется и для определения количества букв для кодирования входных и выходных сигналов:

, где п — число входных сигналов (букв входного алфавита X).

, где п — число выходных сигналов (букв выходного алфавита Y).

Для борьбы с «состязаниями»/гонками ЭП применяется методика противогоночного кодирования, предотвращая любую возможность перехода в «чужое» состояние под воздействием входных сигналов.

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

В результате строится кодированная таблица (или кодированный граф) переходов и выходов.

Шаг 3. Формирование по имеющейся кодированной таблице (графу) переходов и выходов функций возбуждения для каждого ЭП и выходных функций в виде соответствующих ФАЛ;

Шаг 3. Синтез входной и выходной КЛС; для этой цели применяются классические методы минимизации ФАЛ.

Пример проведения структурного синтеза по графу автомата

Синтезировать структурный автомат, представленный таблично и графом.

	S0	S1	S2	S3
X1	S1 Y1	S0 Y2	S1 Y1	S0 Y1
X2	S2 Y2	S2 Y2	S3 Y1	S1 Y2

1. Выбор элементного базиса

– логические элементы И ИЛИ НЕ

– В качестве элементов памяти выбран Т-триггер, т.к. число состояний графа небольшое и нет петель.

		T	Q t	Q t+1
		0	0	0
		0	1	1
		1	0	1
		1	1	0

2. Кодирование

– входные сигналы ,

- потребуется минимум 1 буква для кодирования

– выходные сигналы

- потребуется минимум 1 буква для кодирования

– внутренние состояния

- потребуется минимум 2 Т-триггера

X	a		Y	b
X1	0		Y1	0
X2	1		Y2	1

S	Z1	Z2
S0	0	1
S1	0	0
S2	1	0
S3	1	1

Данный вариант кодирования основан на следующем: состояние автомата с наибольшем числом заходящих дуг кодируется нулями, т.о. состояние, куда заходит наименьшее число дуг кодируется единицами. Остальные – промежуточными вариантами.