 |
Способы задания цифровых автоматов
|
|
|
|
Можно выделить два класса языков для описания функционирования цифровых автоматов: начальные языки и стандартные или автоматные языки.
Начальные языки задают функцию переходов и функцию выходов в неявном виде. Поведение автомата описывается в терминах входных и выходных последовательностей, реализуемых оператором, или последовательностей управляющих сигналов, воздействующих на управляющий автомат.
Для описания функционирования абстрактных ЦА на начальном языке можно использовать:
- язык регулярных выражений алгебры событий;
- язык исчисления предикатов;
- язык логических схем алгоритмов (ЛСА);
- язык граф схем алгоритмов (ГСА).
Язык ГСА совместно с языком ЛСА называют одним общим термином: язык операторных схем алгоритмов (ОСА). На практике наиболее часто используется язык ГСА.
3.3.1 Задание цифровых автоматов на стандартных
языках
Стандартные или автоматные языки задают функции переходов выходов в явном виде. К ним относятся таблицы, графы, матрицы переходов и выходов и их аналитическая интерпретация. Для того, чтобы задать автомат, необходимо описать все компоненты вектора
S = (A, Z, W, d, l, a 1).
При табличном способе задания автомат Мили описывается с помощью двух таблиц: таблицы переходов и таблицы выходов. Таблица переходов задает функцию d (табл.3.4.), таблица выходов функцию - l (табл.3.5.). Каждому столбцу табл.3.4 и 3.5 поставлено в соответствие одно состояние из множества А, каждой строке – один входной сигнал из множества Z. На пересечении столбца am и строки zf в табл.3.4 записывается состояние
as, в которое должен перейти автомат из состояния am, под действием входного сигнала zf, т.е. as = d (am, zf). На пересечении столбца am и строки zf в табл.3.5 записывается выходной сигнал wg, выдаваемый автоматом в состоянии am при поступлении на его вход сигнала zf, т.е.
wg = l (am, zf).
|
|
|
Таблица 3.4 Таблица 3.5
| Таблица переходов автомата Мили | Таблица выходов автомата Мили | |||||||||
| a 1 | a 2 | a 3 | a 4 | a 1 | a 2 | a 3 | a 4 | |||
| z 1 | a 2 | a 2 | a 1 | a 1 | z 1 | w 1 | w 1 | w 2 | w 4 | |
| z 2 | a 4 | a 3 | a 4 | a 3 | z 2 | w 5 | w 3 | w 4 | w 5 |
Для указанных таблиц А = { a 1, a 2, a 3, a 4 }; Z = { z 1, z 2 };
W = { w 1, w 2, w 3, w 4, w 5}.
Автомат Мили может быть задан также одной совмещенной таблицей переходов и выходов (табл.3.6), в которой каждый элемент as / wg, записанный на пересечении столбца am и строки zf, определяется следующим образом:
as = d (am, zf); wg = l (am, zf).
Автомат Мура задается одной отмеченной таблицей переходов (табл.3.7), в которой каждому столбцу приписаны не только состояния am, но еще и выходной сигнал wg, соответствующий этому состоянию, где wg = l (am). Для табл. 3.7 A = { a 4, a 2, a 3, a 4}; Z = { z 1, z 2};
W = { w 1, w 2, w 3}.
Одним из преимуществ этого способа задания является то, что любая таблица переходов и выходов задает конечный автомат. При этом должны удовлетворяться два условия:
- условие однозначности (детерминированности), которое означает, что для любой пары am zf задано единственное состояние перехода as и единственный выходной сигнал wg, выдаваемый на переходе.
- условие полной определенности, которое означает, что для всех возможных пар am zf всегда указано состояние и выходной сигнал.
Таблица 3.6 Таблица 3.7
| Совмещенная таблица переходов и выходов автомата Мили | Отмеченная таблица переходов и выходов автомата Мура | |||||||||
| a 1 | a 2 | a 3 | a 4 | w 3 | w 2 | w 3 | w 1 | |||
| z 1 | a 2/ w 1 | a 2/ w 1 | a 1/ w 2 | a 1/ w 4 | a 1 | a 2 | a 3 | a 4 | ||
| z 2 | a 4/ w 5 | a 3/ w 3 | a 4/ w 4 | a 3/ w 5 | z 1 | a 1 | a 3 | a 1 | a 4 | |
| z 2 | a 2 | a 4 | a 4 | a 1 |
Автомат называется неполностью определенным или частичным, если либо функция d определена не на всех парах (am zf) Î A x Z, либо функция l определена не на всех указанных парах в случае автомата Мили и на множестве не всех внутренних состояний для автомата Мура. Для частичных автоматов Мили и Мура в рассмотренных таблицах на месте неопределенных состояний и выходных сигналов ставится прочерк.
|
|
|
Граф автомата – это ориентированный граф, вершины которого соответствуют состояниям, а дуги – переходам между ними. Дуга, направленная из вершины am в вершину as, задает переход в автомате из состояния am в состояние as. В начале этой дуги записывается входной сигнал zf Î Z, вызывающий данный переход: as = d (am, zf). Для графа автомата Мили выходной сигнал wg Î W, формируемый на переходе, записывается в конце дуги, а для автомата Мура рядом с вершиной, отмеченной состоянием am, в котором он формируется. Если переход в автомате из состояния am в состояние as производится под действием нескольких входных сигналов, то дуге графа, направленной из am в as, приписываются все эти входные и соответствующие выходные сигналы. Графы автоматов Мили и Мура, построенные по табл.3.6 и 3.7 приведены соответственно на рис.3.7. а, б.
Применительно к графу условия однозначности и полной определенности будут заключены в следующем:
- не существует двух ребер с одинаковыми входными пометками, выходящих из одной и той же вершины;
- для всякой вершины am и для всякого входного сигнала zf имеется такое ребро, помеченное символом zf, которое выходит из am.
Рис.3.7. Графы автоматов: a – Мили; б – Мура
При задании графов с большим числом состояний и переходов наглядность теряется, поэтому оказывается предпочтительным задавать этот граф в виде списка – таблицы переходов.
Прямая таблица переходов – таблица, в которой последовательно перечисляются все переходы сначала из первого состояния, затем из второго и т.д. Табл.3.8 – прямая таблица переходов автомата Мили, построенная по графу, приведенному на рис.3.7.а.
В ряде случаев оказывается удобным пользоваться обратной таблицей переходов, в которой столбцы обозначены точно так же, но сначала записываются все переходы в первое состояние, затем во второе и т.д. Табл.3.9 – обратная таблица переходов автомата Мили, построенная по графу, приведенному на рис.3.7,а.
Как и граф таблицы переходов должны удовлетворять условиям однозначности и полноты переходов.
|
|
|
| Таблица 3.8 Прямая таблица переходов автомата Мили | Таблица 3.9 Обратная таблица переходов автомата Мили | |||||||
| am (t) | zf (t) | as (t+ 1 ) | wg (t) | am (t) | zf (t) | as (t+ 1 ) | wg (t) | |
| a 1 | z 1 | a 2 | w 1 | a 3 | z 1 | a 1 | w 2 | |
| z 2 | a 4 | w 5 | a 4 | z 1 | w 4 | |||
| a 2 | z 1 | a 2 | w 1 | a 1 | z 1 | a 2 | w 1 | |
| z 2 | a 3 | w 3 | a 2 | z 1 | w 1 | |||
| a 3 | z 1 | a 1 | w 2 | a 2 | z 2 | a 3 | w 3 | |
| z 2 | a 4 | w 4 | a 4 | z 2 | w 5 | |||
| a 4 | z 1 | a 1 | w 4 | a 1 | z 2 | a 4 | w 5 | |
| z 2 | a 3 | w 5 | a 3 | z 2 | w 4 |
Прямая таблица переходов автомата Мура строится так же как и для автомата Мили. Разница лишь в том, что выходной сигнал wg (t) приписывается состоянию автомата am (t) (табл. 3.10), либо выходной сигнал wg (t +1) приписывается состоянию автомата as (t+ 1) (табл. 3.11).
Обратная таблица переходов автомата Мура строится так же как и для автомата Мили. Разница лишь в том, что выходной сигнал wg (t +1) приписывается состоянию автомата as (t+ 1) (табл. 3.12).
В некоторых случаях для задания автомата используются матрицы переходов и выходов, которые представляют собой таблицу с двумя входами. Строки и столбцы таблицы отмечены состояниями. Если существует переход из am под действием zf в as с выдачей wg, то на пересечении строки am и столбца as записывается пара zf wg. Ясно, что не всякая матрица задает автомат. Как граф и таблица переходов и выходов она должна удовлетворять условиям однозначности и полноты переходов.
| Таблица 3.10 Прямая таблица переходов автомата Мура Вариант 1 | Таблица 3.11 Прямая таблица переходов автомата Мура Вариант 2 | |||||||
| am (t) | wg (t) | zf (t) | as (t+ 1 ) | am (t) | zf (t) | as (t+ 1 ) | wg (t +1) | |
| a 1 | w 3 | z 1 | a 1 | a 1 | z 1 | a 1 | w 3 | |
| z 2 | a 2 | z 2 | a 2 | w 2 | ||||
| a 2 | w 2 | z 1 | a 3 | a 2 | z 1 | a 3 | w 3 | |
| z 2 | a 4 | z 2 | a 4 | w 1 | ||||
| a 3 | w 3 | z 1 | a 1 | a 3 | z 1 | a 1 | w 3 | |
| z 2 | a 4 | z 2 | a 4 | w 1 | ||||
| a 4 | w 1 | z 1 | a 4 | a 4 | z 1 | a 4 | w 1 | |
| z 2 | a 1 | z 2 | a 1 | w 3 |
| Таблица 3.12 Обратная таблица переходов автомата Мура Вариант 2 | |||
| am (t) | zf (t) | as (t+ 1 ) | wg (t +1) |
| a 1 | z 1 | a 1 | w 3 |
| a 3 | z 1 | ||
| a 4 | z 2 | ||
| a 1 | z 2 | a 2 | w 2 |
| a 2 | z 1 | a 3 | w 3 |
| a 2 | z 2 | a 4 | w 1 |
| a 3 | z 2 | ||
| a 4 | z 1 |
Системы канонических уравнений (СКУ) и системы выходных функций (СВФ) являются аналитической интерпретацией таблиц переходов и выходов или графов автоматов. СКУ – определяет функции переходов ЦА, а СВФ – определяет функции выходов ЦА.
|
|
|
Каждое состояние ЦА интерпретируется как событие, соответствующее множеству переходов в это состояние:
(3.10)
Для сокращения записи СКУ и СВФ будем в дальнейшем везде, где это возможно, опускать знаки конъюнкции и времени t в правой части уравнений типа (3.10).
Для автомата Мили, заданного табл.3.8 или табл. 3.9 запишем СКУ и СВФ (3.811и 3.12. соответственно):
| a 1(t +1) = z 1 a 3 Ú z 1 a 4; a 2(t +1) = z 1 a 1 Ú z 1 a 2; a 3(t +1) = z 2 a 2 Ú z 2 a 4; a 4(t +1) = z 2 a 1 Ú z 2 a 3. | (3.11) | w 1(t) = z 1 a 1 Ú z 1 a 2; w 2(t) = z 1 a 3; w 3(t) = z 2 a 2; w 4(t) = z 1 a 4 Ú z 2 a 3; w 5(t) = z 2 a 1 Ú z 2 a 4. | (3.12) |
Запишем СКУ и СВФ для автомата Мура, заданного табл. 3.10 - 3.12, (3.13 и 3.14 соответственно):
| (3.13) |
| (3.14) |
|
|
|
