 |
Способы задания абстрактных автоматов.
|
|
|
|
Автоматы задаются либо в виде графов, либо в виде таблиц. Рассмотрим способы задания автоматов МИЛИ.
При графическом задании автомата МИЛИ изображается граф автомата, у которого каждая вершина соответствует одному состоянию автомата, а каждое ребро одному такту его работы. Начало ребра определяет начальное состояние, конец конечное для данного перехода. Около каждого ребра записывается входное слово, определяющее переход и в скобках – выдаваемый сигнал. Пример графа автомата МИЛИ приведен на Рис 3.1.1.
 |
Z1(W1) Z2(W3)
 | |||
 | |||
Z1(W1) Z1(W1)
Z2(W2)
Z2(W2)
Рис 3.1.1 Пример графа автомата МИЛИ.
Графическое представление автоматов является, пожалуй, наиболее наглядным и удобным для человека. К сожалению, при большом числе вершин графа автомата наглядность существенно теряется. Отметим, что графическое представление является также не самым удобным для ввода информации в компьютер.
Очень часто работу автоматов описывают в виде таблиц. Для задания автомата МИЛИ нужно расписать две таблицы: таблицу определяющую функцию выходов и таблицу задающую функцию переходов.
В таблице 1 приведена функцию выходов для автомата, представленного на Рис 3.1.1. а в таблице 2 – функция переходов.
Таблица 1.
Функция выходов автомата МИЛИ.
| Состояние | Входные и выходные сигналы. | |
| Z1 | Z2 | |
| S0 | W1 | W2 |
| S1 | W2 | W3 |
| S2 | W1 | W2 |
Таблица 2.
Функция переходов автомата МИЛИ.
| Состояние | Входные сигналы и новые состояния. | |
| Z1 | Z2 | |
| S0 | S1 | S2 |
| S1 | S0 | S2 |
| S2 | S1 | S2 |
При графическом задании автомата МУРА изображается граф автомата, у которого каждая вершина соответствует одному состоянию автомата, а каждое ребро одному такту его работы. Начало ребра определяет начальное состояние, конец конечное для конкретного перехода. Около каждого ребра записывается входное слово, определяющее переход, а у каждой вершины – выдаваемый сигнал. Пример графа автомата МУРА приведен на Рис 3.1.2.
|
|
|
Z1 Z1
 |
Z2
 | |||
 | |||
Z2
Z2
 |
Z1 Z1
Z2
 | |||
 | |||
Рис 3.1.2. Пример автомата МУРА
. Для задания автомата МУРА нужно расписать только таблицу, задающую функцию переходов, поскольку выходной сигнал для автомата однозначно определяется его состоянием.
В таблице 3 приведена комплексная информация, определяющая функцию переходов и выходные сигналы для автомата, представленного на Рис 3.1.2
Таблица 3.
Описание автомата МУРА.
| Состояние | Выходной сигнал | Входные сигналы и новые состояния. | |
| Z1 | Z2 | ||
| S0 | W0 | S0 | S1 |
| S1 | W1 | S1 | S2 |
| S2 | W2 | S2 | S3 |
| S3 | W3 | S3 | S0 |
Элементы памяти на которых реализуются автоматы, представляют собой обычные синхронные триггеры. Число триггеров, необходимых для задания всех состояний автомата определяется числом состояний и схемой их кодирования.
При двоичном кодировании (Binary coding) число необходимых триггеров n определяется выражением:
n = ]log2N[, где ] [ - операция округления до ближайшего большего целого.
При линейном кодировании по принципу одно состояние – один триггер (One Hot State), число необходимых триггеров
n = N, где N – число состояний.
Для СБИС программируемой логики семейства МАХ, содержащих относительно небольшое число макроячеек, в каждой из которых имеется многовходовая программируемая матрица «И», матрица «ИЛИ» и триггер, приемлемы оба способа кодирования. Поэтому для таких СБИС пакет MAX+PLUSII с помощью опции One Hot State Machine Encoding (меню Assign – Global Project Logic Synthesis) позволяет выбирать способ кодирования (по умолчанию применяется двоичное кодирование).
|
|
|
Для СБИС программируемой логики семейства FLEX, содержащих много логических элементов, в каждом из которых есть четырех входовая таблица перекодировки и триггер, оптимальным является кодирование по принципу: одно состояние – один триггер, так как при этом существенно упрощается комбинационная схема управления переходами автомата. Поэтому для СБИС семейства FLEX в пакете MAX+PLUSII всегда применяется данный способ кодирования состояний.
|
|
|
