Длина кода равна , где - число вершин или количество состояний (округляем до 3 наибольшего значения). Структурный синтез автоматов

Для автомата (рис. 7) проведем структурный синтез.

Начнем с кодирования состояний автомата. Для этого первоначально построим матрицу :

.

Так как матрица - нулевая, то состояниям может быть присвоен произвольный код. При этом кодирование не влияет на аппаратную сложность функций состояния и выходов.

Присвоим следующий код:

Количество разрядов кода (округляем полученный результат до наибольшего значения, где - количество состояний).

Теперь подошли к структурному синтезу.

1. Строим кодированную таблицу переходов, отображающую изменение состояний элементов памяти.

Таблица 1

	00	01	11
0	00 ( )	11 ( )	00 ( )
1	01 ( )	11 ( )	01 ( )

2. Для синтеза схемы возьмем синхронный - триггер.

3. Для первого элемента памяти строим таблицу истинности функции состояния (берутся старшие разряды кода из таблицы 1).

Таблица 2

	00	01	11
0	0	1	0
1	0	1	0

4. Для второго элемента памяти строим таблицу истинности функции состояния (берутся младшие разряды кода из таблицы 1).

Таблица 3

	00	01	11
0	0	1	0
1	1	1	1

5. Перепишем таблицу истинности для функции состояния первого элемента памяти .

Таблица 4

0	0	0	0
0	0	1	1
0	1	0	-
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	-
1	1	1	0

Осуществим минимизацию ДНФ, используя метод Квайна Мак-Класски.

1. Сначала берем те наборы, где функция равна 0.

З атем те наборы, где функция равна 1.

2. 

	- 0 0	- 1 1
-	0	0
0	0	1
1	1	0

Минимальная ДНФ:

.

6. Перепишем таблицу истинности для функции состояния второго элемента памяти .

Таблица 5

0	0	0	0
0	0	1	1
0	1	0	-
0	1	1	0
1	0	0	1
1	0	1	1
1	1	0	-
1	1	1	1

Минимальная ДНФ:

.

7. Строим таблицу истинности выходов по графу (рис. 7).

Таблица 6

	00	01	11
0	1	0	0
1	0	1	1

8. Таблица истинности для выходной функции

Таблица 7

0	0	0	1
0	0	1	0
0	1	0	-
0	1	1	0
1	0	0	0
1	0	1	1
1	1	0	-
1	1	1	1

Минимальная ДНФ:

.

9. Структурная схема изображена на рис. 8.