Конечные автоматы

Теория автоматов
Абстрактный автомат
Абстрактный автомат – позволяет абстрагироваться от конкретной схемы, можно рассматривать как «черный ящик»
Для построения УАЖЛ, используется теория абстрактных конечных автоматов (КА). Для построения используется две базовые модели КА, функционально аналогичные: автомат Мура и автомат Мили.
Любой ЦА описывается следующем кортежем: М = {X, Y, A\S, δ, λ, s 0 }, где X, Y, S – соответственно множества входных, выходных значений ЦА и внутренних состояний.

Теория автоматов
Абстрактный автомат
Абстрактный автомат – обобщенная схема.

Теория автоматов
Автомат Мили.
В автомате Мили функция выходов λ определяет значение выходного символа по классической схеме абстрактного автомата. Математическая модель автомата Мили и схема рекуррентных соотношений не отличаются от математической модели и схемы рекуррентных соотношений абстрактного автомата.
Законы функционирования: a(t +1) = δ[a(t), x(t)]
y(t) = λ [a(t), x(t)]
Отображения δ и λ получили названия, соответственно, функции перехода и функции выхода автомата.
Особенностью автомата Мили является то, что функция выходов является двухаргументной и символ в выходном канале y(t) обнаруживается только при наличии символа во входном канале x(t). Функциональная схема не отличается от схемы абстрактного автомата.

Теория автоматов
Автомат Мили.
a(t +1) = δ[a(t), x(t)]
y(t) = λ [a(t), x(t)]

Теория автоматов
Автомат Мили
Граф автомата, заданного приведенными таблицами, переходов и выходов будет иметь вид:
δ
λ
X2/y2

Теория автоматов
Автомат Мура.
Зависимость выходного сигнала только от состояния автомата представлена в автоматах Мура. В автомате Мура функция выходов определяет значение выходного символа только по одному аргументу — состоянию автомата. Эту функцию называют также функцией меток, так как она каждому состоянию автомата ставит метку на выходе.
Законы функционирования: a(t +1) = δ[a(t), x(t)]
y(t) = λ [a(t)]
Пример автомата Мура:
Очевидно, что автомат Мура можно рассматривать как частный случай автомата Мили.

Теория автоматов
Автомат Мура. a(t +1) = δ[a(t), x(t)]
y(t) = λ [a(t)]

Теория автоматов
Автомат Мура

Теория автоматов
Абстрактный синтез автоматов
Задача структурного синтеза состоит в построении схемы автомата минимальной сложности. На первом этапе необходимо получить минимальную структуру абстрактного автомата.
Будем рассматривать в качестве
примера следующий автомат:
Входные сигналы: 0, 1.
Таблица переходов:
Выходные сигналы: 0, 1, 2.
S0 – начальное состояние.:
а8

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

Теория автоматов
Абстрактный синтез автоматов
Для упрощения автомата в первую очередь необходимо выделить эквивалентные состояния.
Условия эквивалентности Колдуэлла:
1. Необходимое условие: внутренние состояния ai и aj называются эквивалентными, если при подаче произвольной входной последовательности с начальными состояниями ai и aj образуются одинаковые выходные последовательности.
2. Достаточное условие: если две одинаковые строки выходят в следующее состояние, то эти состояния эквивалентны.
Условия эквивалентности Колдуэлла состоит из 2 условий:
Условие совпадения выходов (необходимое)
Условие совпадения следующих состояний (достаточное)
Для нашего примера:
G1 = {(a0,al,a3,a5),(a2,a6,a8),(a4,a7)}

Теория автоматов
Абстрактный синтез автоматов
Далее необходимо рассмотреть все возможные пары состояний для каждого из классов и отбросить те из них, которые переводятся по какому-либо символу входного алфавита за пределы этого класса. Эту процедуру нужно повторять до тех пор, пока следующее множество классов эквивалентности не совпадёт с предыдущем. В нашем примере окончательным будет уже второе разбиение:
G2 = {(a0),(al,a5)(a3),(a2,a6,as),(a4,a7)}
Новая таблица переходов:

Теория автоматов
Абстрактный синтез автоматов
Граф минимизированного автомата:

Теория автоматов
Автомат Мура ? Автомат Мили
Автомат Мура и соответствующий ему автомат Мили:
Переход от автомата Мили к автомату Мура:
От каждого автомата Мили можно перейти к эквивалентному ему автомату Мура. Если к одной вершине подходят дуги, отмеченные разными выходными сигналами, то производится разбиение на несколько вершин, каждая из которых отмечается своим выходным сигналом, и от каждой из этих вершин выводятся все дуги, существующие в графе автомата Мили.

Теория автоматов
Автомат Мили ? Автомат Мура
Переход от автомата Мили к эквивалентному автомату Мура:

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

Теория автоматов
Синтез конечных автоматов (v.1)
1 шаг. Построение диаграммы переходов.
Автомат Мили

Теория автоматов
Синтез конечных автоматов (v.1)
2 шаг. Таблицы переходов и выходов.
Автомат Мили

Теория автоматов
Синтез конечных автоматов (v.1)
3 шаг. Определение входных данных
Автомат Мили

Теория автоматов
Синтез конечных автоматов (v.1)
4 шаг. Кодируем состояния, входы и выходы.
Автомат Мили

Теория автоматов
Синтез конечных автоматов (v.1)
4 шаг. Кодируем переходы и выходы. Таблица переходов δ
Таблица выходов λ
Автомат Мили

Теория автоматов
Синтез конечных автоматов (v.1)
5 шаг. Минимизация функций выходов.
Автомат Мили

Теория автоматов
Синтез конечных автоматов (v.1)
6 шаг. Функции возбуждения памяти (ВП) строятся на основе таблицы переходов и таблицы истинности триггеров различных типов, которые являются основой элементов памяти (ЭП) конечного автомата .
Автомат Мили

Теория автоматов
Синтез конечных автоматов (v.1)
6 шаг. Таблица функций ВП.
Автомат Мили

Теория автоматов
Синтез конечных автоматов (v.1)
6 шаг. Минимизация функций ВП.
Автомат Мили

Теория автоматов
Синтез конечных автоматов (v.1)
7 шаг. Система уравнений (И-НЕ) – структура КА
Автомат Мили

Теория автоматов
Синтез конечных автоматов (v.1)
7 шаг. Логическая структура КА
Автомат Мили

Теория автоматов
Синтез конечных автоматов (v.1)
7 шаг. Система уравнений (И-НЕ) ? структура КА
на ИС средней и малой степени интеграции.
Автомат Мили
НЕ (6) 8И-НЕ (1) RS\D-триггер: 133ТМ2 (2)

Теория автоматов
Синтез конечных автоматов (v.1)
7 шаг. Система уравнений (И-НЕ) ? структура КА
Автомат Мили

Теория автоматов
Синтез конечных автоматов (v.2)
1 шаг. Построение диаграммы переходов.
Автомат Мили

Теория автоматов
Синтез конечных автоматов (v.2)
2 шаг.
Таблица переходов: Таблица выходов:

Теория автоматов
Синтез конечных автоматов (v.2)
3 шаг.
Определение разрядности автомата.
Число элементов памяти r:
Число разрядов входной шины n:
Число разрядов выходной шины m:

Теория автоматов
Структурный синтез конечных автоматов
4 шаг.
Кодирование автомата.

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

Теория автоматов
Структурный синтез конечных автоматов
6 шаг. Минимизация функций выходов Y0 и Y1

Теория автоматов
Структурный синтез конечных автоматов
6 шаг. Получаем функции выходов:
7 шаг. Построение таблицы возбуждения памяти
В качестве элементной базы используем элементы памяти RS-триггеры, JK-триггеры, D-триггеры (получаются наиболее простые логические выражения)

Теория автоматов
Структурный синтез конечных автоматов
7 шаг. Построение таблицы возбуждения памяти
Таблица истинности RS-, JK- и D-триггеров
Функция возбуждения памяти, построенной на D-триггерах

Теория автоматов
Алгоритм синтеза конечных автоматов
7 шаг. Составляем и минимизируем функции ВП
По таблица возбуждения памяти автомата, построенной на D-триггерах, запишем ФВП D0 и D1
Функции возбуждения памяти автомата, построенной на D-триггерах выглядят таким образом.

Теория автоматов
Структурный синтез конечных автоматов
7 шаг. Получаем
Функции возбуждения памяти D0 и D1 автомата, построенной на D-триггерах – T0 и T1:
В базисе И-НЕ

Теория автоматов
Структурный синтез конечных автоматов
8 шаг. Составляем схему Э2(3)* для аппаратного КА
в базисе 2И, НЕ, 2И-НЕ.

Теория автоматов
Структурный синтез конечных автоматов
9 шаг. Минимизируем количество корпусов ТТЛШ ИС для аппаратного КА в базисе 2И, НЕ, 2И-НЕ.

Теория автоматов
Синтез конечных автоматов на ПЛИС
Основные задачи и цели
PLD – Programmable logic devices или
ПЛИС – программируемые интегральные схемы
позволяют путем конфигурирования исходной структуры получать различные комбинационные или последовательностные схемы. Любая ФАЛ или КА, которые можно синтезировать на жесткой логике, могут быть синтезированы на ПЛИС.
Общее требование – наличие средств изменения взаимных связей м\д элементами для формирования требуемых логических конфигураций.
Типы ПЛИС
1. ПЛМ (Программируемые логические матрицы) (programmable logic arrays – PLA)
2. ПМЛ (Программируемая матричная логика) (programmable array logic -PAL)
3. Регистровые ПЛИС – (PAL xxRx)
4. CPLD, FPGA…

Теория автоматов
Синтез конечных автоматов на ПЛИС
Функциональная схема ПЛМ

Теория автоматов
Синтез конечных автоматов на ПЛИС
Упрощенная функциональная схема ПЛМ

Теория автоматов
Синтез конечных автоматов на ПЛИС
Основные константы и переменные ПЛМ

Теория автоматов
Синтез конечных автоматов на ПЛИС
Основные типы ПЛИС

Теория автоматов
Синтез конечных автоматов на ПЛИС
ПЛМ AMD PAL 16L8

Теория автоматов
Синтез конечных автоматов на ПЛИС
Процесс программирования ПЛМ

Теория автоматов
Синтез конечных автоматов на ПЛИС
Запрограммированная ПЛМ

Теория автоматов
Синтез конечных автоматов на ПЛИС
Автомат Мили на ПЛМ или комбинационной ПМЛ

Теория автоматов
Синтез конечных автоматов на ПЛИС
Автомат Мили на ПМЛ

Теория автоматов
Синтез конечных автоматов на ПЛИС
ПМЛ AMD PAL 16R6