Структурный синтез конечного автомата

Материал из Национальной библиотеки им. Н. Э. Баумана
Последнее изменение этой страницы: 15:04, 14 марта 2019.

Введение

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

Этапы структурного синтеза:

1 шаг. Построение диаграммы переходов (графа конечного автомата).
2 шаг. Для заданной ДС составляем таблицы переходов и выходов.
3 шаг. Определяем количество ЭП, количество входов и выходов.
4 шаг. Кодируем состояния, входы и выходы конечного автомата.
5 шаг. Составляем по таблице выходов - минимальные функции выходов.
6 шаг. Составляем таблицу возбуждения памяти и функции ВП (миним.).
7 шаг. Все логические функции приводим к единому базису И-НЕ.
8 шаг. Составляем логическую функцию КА в базисе И-НЕ.
9 шаг. Составляем схему электрическую принципиальную (Э3).
10 шаг. Минимизируем количество корпусов ИС полученной схемы КА.

Вариант 1

Рис. 1. Исходный автомат

Составление таблице переходов автомата

Анализируя таблицу переходов можно сделать вывод, что данный автомат является минимальным.

Составление таблицы выходов автомата

Определение разрядности автомата

  • Количество состояний (ЭП):
  • Количество разрядов входной шины:
  • Количество разрядов выходной шины:

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


00 01 10 11
00 01 11 10 10
01 00 10 10 00
10 11 01 00 11
11 00 01 01 11

Таблица выходов


00 01 10 11
00 01 11 01 10
01 00 10 01 00
10 11 01 00 11
11 00 01 01 11

Минимизация выходных функций

Рис. 2. Минимизация функции
Рис. 3. Минимизация функции

Таблица возбуждения памяти

Используем D-триггер.

0 0 0 1 1 0 1 1
00 0 1 0 1 1 0 1 0
01 - - 0 0 1 1 1 1
10 - - 1 1 0 0 1 1
11 0 1 0 1 0 1 1 1

Минимизация

Рис. 4. Минимизация функции
Рис. 5. Минимизация функции

Схема

Рис. 6. Реализация на логических элементах

Реализация на ПЛИС:

Рис. 7. Реализация на регистровой ПМЛ AMD PAL16R6

Вариант 3

Рис. 8. Исходный автомат

Составление таблицы переходов автомата

Составление таблицы выходов автомата

Разрядность автомата:

  • Количество состояний (ЭП):
  • Количество разрядов входной шины:
  • Количество разрядов выходной шины:

Кодирование автомата

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


00 01 10 11
00 01 01 10 10
01 - 00 11 11
10 - 11 00 11
11 00 01 01 11

Таблица выходов


00 01 10 11
00 00 00 10 00
01 - 00 10 01
10 - 11 10 00
11 00 11 10 01

Минимизация выходных функций

Рис. 9. Минимизация выходных функций

Таблица возбуждения памяти

Используем D-триггер.

0 0 0 1 1 0 1 1
00 0 1 0 1 1 0 1 0
01 - - 0 0 1 1 1 1
10 - - 1 1 0 0 1 1
11 0 1 0 1 0 1 1 1

Минимизация

Рис. 10. Минимизация с помощью карт Карно

Схема

Рис. 11. Схема

Реализация на ПЛИС:

Рис. 12. ПЛИС