Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
|
[1] Оглавление |
6 Основные понятия и определения теории абстрактных авто матов (лекция №9)
Цифровой (дискретный) автомат (ЦА) – устройство, которое осуществляет прием, хранение и/или преобразование дискретной информации по некоторому алгоритму. Примерами ЦА могут служить живые организмы, процессоры, бытовая техника калькуляторы – это реальные устройства, а также есть абстрактные, например, модели алгоритмов. ЦА относятся к последовательным устройствам. Этот класс устройств определяется тем, что значение выходов зависит не только от входных значений, но и от текущего состояния устройства. Т.е. вводится понятие – состояние. Для того чтобы хранить данные о состоянии, в котором находится устройство в ЦА используются запоминающие элементы – триггеры.
6.1 Математическая модель цифрового автомата
Цифровой автомат - устройство, характеризующееся набором внутренних состояний в которое оно попадет под воз действием команд заложенной в него программы. Переход автомата из одного состояния в другое осуществляется в определенный момент времени.
Математической моделью ЦА (а в общем случае любого дискретного устройства) является так называемый абстракт ный автомат, определенный как 6-компонентный кортеж: S=(A,X,Y,,,а1) у которого:
Под алфавитом здесь понимается непустое множество попарно различных символов. Элементы алфавита называются буквами, а конечная упорядоченная последовательность букв - словом в данном алфавите.
Рисунок 6.1 – Абстрактный автомат
Абстрактный автомат (рисунок 6.1) имеет один вход и один выход. Автомат работает в дискретном времени, принимающем целые неотрицательные значения t = 0,1,2,... В каждый момент t дискретного времени автомат находится в некотором состоянии a(t) из множества состояний автомата, причем в начальный момент t = 0 он всегда находится в начальном со стоянии a(0)=a1. В момент t, будучи в состоянии a(t), автомат способен воспринять на входе букву входного алфавита X(t) Z. В соответствии с функцией выходов он выдаст в тот же момент времени t букву выходного алфавита y(t)=(a(t), z(t)) и в соответствии с функцией переходов перейдет в следующее состояние a(t+1)=[a(t), x(t)], a(t) A, y(t) Y.
Смысл понятия абстрактного автомата состоит в том, что он реализует некоторое отображение множества слов вход ного алфавита X во множество слов выходного алфавита Y. Т.е. если на вход автомата, установленного в начальное состояние a1, подавать буква за буквой некоторую последовательность букв входного алфавита x(0), x(1),... - входное слово, то на выходе автомата будут последовательно появляться буквы выходного алфавита y(0), y(1),... - выходное слово. Т.о. выходное слово = (входное слово), где - отображение, осуществляемое абстрактным автоматом.
На уровне абстрактной теории понятие "работа автомата" понимается как преобразование входных слов в выходные. Можно сказать, что в абстрактном автомате отвлекаемся от его структуры - содержимого прямоугольника (рисунок 6.1), рассматривая его как "черный ящик", т.е. основное внимание уделяем поведению автомата относительно внешней среды.
Понятие состояния в определении автомата введено в связи с тем, что часто возникает необходимость в описании пове дения систем, выходы которых зависят не только от состояния входов в данный момент времени, но и от некоторой пре дыстории, т.е. от сигналов, которые поступали на входы системы ранее. Состояния как раз и соответствуют некоторой памяти о прошлом, позволяя устранить время как явную переменную и выразить выходной сигнал как функцию со стояния и входа в данный момент времени.
6.2 Классификация цифровых автоматов
Рассмотренные выше абстрактные автоматы можно разделить на:
Полностью определенным называется абстрактный цифровой автомат, у которого функция переходов и функция выходов определены для всех пар ( ai, zj ).
Частичным называется абстрактный автомат, у которого функция переходов или функция выходов, или обе эти функ ции определены не для всех пар ( ai, zj ).
К детерминированным относятся автоматы, у которых выполнено условие однозначности переходов : автомат, находя щийся в некотором состоянии ai, под действием любого входного сигнала zj не может перейти более, чем в одно состоя ние.
В противном случае это будет вероятностный автомат, в котором при заданном состоянии ai и заданном входном сиг нале zj возможен переход с заданной вероятностью в различные состояния.
Для определения синхронных и асинхронных автоматов вводится понятие устойчивого состояния. Состояние as автомата называется устойчивым, если для любого состояния ai и входного сигнала zj таких, что ( ai, zj ) = as имеет место ( as, zj ) = as, т.е. состояние устойчиво, если попав в это состояние под действием некоторого сиг нала zj, автомат выйдет из него только под действием другого сигнала zk, отличного от zj.
Автомат, у которого все состояния устойчивы - асинхронный.
Автомат называется синхронным, если он не является асинхронным.
Абстрактный автомат называется конечным, если конечны множества А = {a1, a2, ..., am}, Z = {z1, z2, ..., zf}, W = {w1, w2, ..., wg}. Автомат носит название инициального, если в нем выделено начальное состояние a1.
6.3 Разновидности цифровых автоматов
На практике наибольшее распространение получили два класса автоматов - автоматы Мили (Mealy) и Мура (Moore).
Закон функционирования автомата Мили задается уравнениями:
a(t+1) = (a(t), z(t)); w(t) = (a(t), z(t)), t = 0,1,2,...
Закон функционирования автомата Мура задается уравнениями:
a(t+1)=(a(t), z(t)); w(t) = (a(t)), t = 0,1,2,...
Из сравнения законов функционирования видно, что, в отличие от автомата Мили, выходной сигнал в автомате Мура зависит только от текущего состояния автомата и в явном виде не зависит от входного сигнала. Для полного задания автомата Мили или Мура дополнительно к законам функционирования, необходимо указать начальное состояние и оп ределить внутренний, входной и выходной алфавиты.
Кроме автоматов Мили и Мура иногда оказывается удобным пользоваться совмещенной моделью автомата, так на зываемым С- автоматом.
Абстрактный С- автомат можно представить в виде устройства с одним входом, на который поступают сигналы из входного алфавита X, и двумя выходами, на которых появляются сигналы из алфавитов Y и U. Отличие С - автомата от моделей Мили и Мура состоит в том, что он одновременно реализует две функции выходов 1 и 2, каждая из которых характерна для этих моделей в отдельности. Закон функционирования С- автомата можно описать следующими уравнениями:
а(t+1) =(a(t), z( t )); w(t) =1(a(t), z(t)); u(t) = 2(a( t )); t = 0, 1, 2, ...
Выходной сигнал Uh=2(am ) выдается все время, пока автомат находится в состоянии am. Выходной сигнал Wg=1( am, zf ) выдается во время действия входного сигнала Zf при нахождении автомата в состоянии am.
7 Способы описания и задания автоматов (лекция№10)
Для того, чтобы задать автомат, необходимо описать все компоненты кортежа S=(A, X, Y, , , а1 ). Множества А, X, Y описываются и задаются простым перечислением своих элементов. Среди многообразия различных способов заданий функций и (следовательно и всего автомата в целом) наибольшее распространение получили табличный и графиче ский.
7.1 Табличный способ описания цифровых автоматов
При табличном способе описания цифровых автоматов применяется два вида таблиц – таблица переходов и таблица выходов.
Таблица переходов отображает функцию переходов. Строкам таблицы соответствуют состояния автомата, т.е. в таблице столько строк, сколько состояний у автомата. Столбцам таблицы соответствуют входные значения, которые могут поступать на входы ЦА, т.е. столбцом столько – сколько элементов во входном алфавите. На пересечении i-столбца и j-строки в ячейке таблицы указывается состояние в которое перейдет ЦА под воздействием входного сигнала xi (которому соответствует i-й столбец) из состояния aj (которому соответствует j-я строка). Таблица переходов приведена на рисунке 6.2
|
x1 |
x2 |
… |
xm |
|
|
a1 |
a2 |
a1 |
… |
a2 |
|
a2 |
an-1 |
a3 |
… |
a1 |
|
… |
… |
|||
|
an |
- |
an |
… |
a2 |
Рисунок 6.2 – Таблица переходов ЦА
Таблица переходов имеет одинаковый вид как для автомата Мура, так и для автомата Мили. Для частичных автоматов Мили и Мура в рассмотренных таблицах на месте не определенных состояний и выходных сигналов ставится прочерк. В таких автоматах выходной сигнал на каком-либо переходе всегда не определен, если неопределенным является состояние перехода
Таблица выходов для автомата Мили имеет такой же вид как и таблица переходов, только на пересечении i-столбца и j-строки в ячейке таблицы указывается выходное значение, которое сформирует ЦА под воздействием входного сигнала xi (которому соответствует i-й столбец) в состоянии aj (которому соответствует j-я строка). Таблица выходов автомата Мили приведена на рисунке 6.3
|
x1 |
x2 |
… |
xm |
|
|
a1 |
y1 |
y3 |
… |
y1 |
|
a2 |
yn-1 |
y2 |
… |
yn-1 |
|
… |
… |
|||
|
an |
- |
y1 |
… |
y2 |
Рисунок 6.3 – Таблица выходов автомата Мили
Таблица выходов для автомата Мура состоит из одного столбца. Строкам таблицы соответствуют состояния автомата, т.е. в таблице столько строк, сколько состояний у автомата. Пример таблицы приведен на рисунке 6.4
|
x1 |
|
|
a1 |
y1 |
|
a2 |
yn-1 |
|
… |
|
|
an |
y2 |
Рисунок 6.4 – Таблица выходов автомата Мура
В некоторых случаях вместо двух таблиц определяющих ЦА удобно применять совмещенную таблицу переходов и выходов. На рисунке 6.5 приведена совмещенная таблица для автомата Мили. На рисунке 6.6 приведена совмещенная таблица переходов для автомата Мура.
|
x1 |
x2 |
… |
xm |
|
|
a1 |
a2/y1 |
a1/y3 |
… |
a2/y1 |
|
a2 |
an-1/yn-1 |
a3/y2 |
… |
a1/yn-1 |
|
… |
… |
|||
|
an |
- |
an /y1 |
… |
a2/y2 |
Рисунок 6.5 – Совмещенная таблица переходов и выходов автомата Мили
|
x1 |
x2 |
… |
xm |
Y |
|
|
a1 |
a2 |
a1 |
… |
a2 |
y2 |
|
a2 |
an-1 |
a3 |
… |
a1 |
y1 |
|
… |
… |
||||
|
an |
- |
an |
… |
a2 |
y2 |
Рисунок 6.6 – Совмещенная таблица переходов автомата Мура
7.2 Графический способ задания цифровых автоматов
При графическом способе автомат задается в виде ориентированного графа, вершины которого соответствуют состояниям, а дуги - переходам между ними. Дуга, направленная из вершины am, задает переход в автомате из состояния am в состояние as. В начале этой дуги записывается входной сигнал XfX, вызывающий данный переход as=(am,xf). Для графа автомата Мили выходной сигнал ygY, формируемый на переходе, записывается в конце дуги, а для автомата Мура - рядом с вершиной am, отмеченной состоянием am, в котором он формируется. Если переход в автомате из состояния am в состояние as производится под действием нескольких входных сигналов, то дуге графа, направленной из am в as, приписываются все эти входные и соответствующие выходные сигналы. Граф С-автомата содержит выходные сигналы двух типов и они обозначаются на графе как на графах соответствующих автоматов. Граф автомата Мура представлен на рисунке 6.7, а автомата Мили – на рисунке 6.8.
Рисунок 6.7 –Графическое представление автомата Мура
Рисунок 6.8 –Графическое представление автомата Мили
8 Абстрактный синтез цифровых автоматов
Теория цифровых автоматов рассматривает абстрактный и структурный синтез цифровых автоматов. Абстрактный синтез не описывает внутреннего строения автомата, а дает описание взаимодействия с окружающей средой. К абстрактному синтезу относят:
8.1 Структура цифрового автомата
Внутреннюю структуру цифрового автомата можно изобразить, как показано на рисунке 8.1.
Рисунок 8.1 – Структурная схема цифрового автомата.
Комбинационная схема №1 реализует переходы автомата из одного состояния в другое под воздействием входных сигналов. Схема проектируется исходя из закодированной таблицы переходов и подграфа переходов выбранного запоминающего элемента.
Блок памяти представляет собой набор триггеров, которые хранят разряды закодированного номера состояния. Количество триггеров зависит от количества состояний, в которых может находиться автомат. И вычисляется как:
N=log2M
где M – количество состояний, а N –количество триггеров
Комбинационная схема №2 реализует функцию выходов автомата и на ее выходе устанавливаются выходные значения автомата в соответствии с текущим состоянием автомата и входными значениями.
8.2 Минимизация числа состояний цифрового автомата
Часто при выполнении абстрактного синтеза вводятся избыточные состояния, эквивалентность которых не является очевидной. Избыточное количество состояний может привести к применению лишних триггеров, что усложнит КС1 и КС2. Поэтому очень важно выполнять минимизацию числа состояний перед его структурным синтезом.
Алгоритм минимизации основан на разбиении всего множества состояний на попарно непересекающиеся классы эквивалентных состояний и замене всего класса эквивалентности одним состоянием. Полученный в результате минимизированный автомат будет содержать столько состояний на сколько классов эквивалентности было разбито исходное множество состояний.
Определение Два состояния as и am являются эквивалентными, если
(as, E) = (am, E), где - функция перехода, E – входное слово произвольной длины.
Другими словами, состояния эквивалентны, если в ответ на одни и те же входные слова вырабатывается одна и та же последовательность состояний, независимо от того в каком из двух состояний as или am находился автомат в начальный момент времени. Если два состояния эквивалентны, то одно состояние можно заменить на другое.
Кроме эквивалентных состояний существует понятие k-эквивалентных состояний: 1-эквивалентные, 2-эквивалентные и т.д.
Определение Два состояния as и am являются k-эквивалентными, если
(as, Ek) = (am, Ek), где - функция перехода, Ek – входное слово длины k.
Алгоритм минимизации:
8.3 Пример минимизации числа состояний автомата Мура
Шаг 1 – Автомат задан совмещенной таблицей переходов/выходов
|
0 |
1 |
y |
|
|
a0 |
a2 |
a1 |
0 |
|
a1 |
a3 |
a4 |
0 |
|
a2 |
a4 |
a3 |
0 |
|
a3 |
a5 |
a6 |
0 |
|
a4 |
a6 |
a5 |
0 |
|
a5 |
a2 |
a1 |
1 |
|
a6 |
a2 |
a1 |
0 |
Шаг 2 – Выполняется разбиение на 0-эквивалентные множества по значению выходов автомата
|
0 |
1 |
y |
|
|
a0 |
a2 |
a1 |
0 |
|
a1 |
a3 |
a4 |
0 |
|
a2 |
a4 |
a3 |
0 |
|
a3 |
a5 |
a6 |
0 |
|
a4 |
a6 |
a5 |
0 |
|
a5 |
a2 |
a1 |
1 |
|
a6 |
a2 |
a1 |
0 |
Шаг 3 – Таблица переходов автомата записывается без выделенных «звездочкой» состояний. В ячейках таблицы вместо названий состояний записываются названия классов эквивалентности, к которым они относятся.
|
0 |
1 |
|
|
a0 |
A0 |
A0 |
|
a1 |
A0 |
A0 |
|
a2 |
A0 |
A0 |
|
a3 |
A1 |
A0 |
|
a4 |
A0 |
A1 |
|
a5 |
a2 |
a1 |
|
a6 |
A0 |
A0 |
Шаг 4 – Таблица переходов автомата записывается без выделенных «звездочкой» состояний. В ячейках таблицы вместо названий состояний записываются названия классов эквивалентности, к которым они относятся.
|
0 |
1 |
|
|
a0 |
B0 |
B0 |
|
a1 |
B1 |
B2 |
|
a2 |
B2 |
B1 |
|
a3 |
A1 |
A0 |
|
a4 |
A0 |
A1 |
|
a5 |
a2 |
a1 |
|
a6 |
B0 |
B0 |
Шаг 5 – Таблица переходов автомата записывается без выделенных «звездочкой» состояний. В ячейках таблицы вместо названий состояний записываются названия классов эквивалентности, к которым они относятся.
|
0 |
1 |
|
|
a0 |
C1 |
C2 |
|
a1 |
B1 |
B2 |
|
a2 |
B2 |
B1 |
|
a3 |
A1 |
A0 |
|
a4 |
A0 |
A1 |
|
a5 |
a2 |
a1 |
|
a6 |
C1 |
C2 |
На данном шаге минимизация окончена, т.к. выделено множество полностью эквивалентных состояний, а все остальные состояния не имеют эквивалентных т.к. они попали в множества из одного элемента.
В исходной таблице переходов/выходов цифрового автомата вычеркивается строка, которая соответствует состоянию a6, а в остальных строках a6 заменяется на a0
|
0 |
1 |
y |
|
|
a0 |
a2 |
a1 |
0 |
|
a1 |
a3 |
a4 |
0 |
|
a2 |
a4 |
a3 |
0 |
|
a3 |
a5 |
a6 |
0 |
|
a4 |
a6 |
a5 |
0 |
|
a5 |
a2 |
a1 |
1 |
|
a6 |
a2 |
a1 |
0 |
Таблица переходов/выходов автомата после минимизации будет иметь следующий вид:
|
0 |
1 |
y |
|
|
a0 |
a2 |
a1 |
0 |
|
a1 |
a3 |
a4 |
0 |
|
a2 |
a4 |
a3 |
0 |
|
a3 |
a5 |
a0 |
0 |
|
a4 |
A0 |
a5 |
0 |
|
a5 |
a2 |
a1 |
1 |
9 Структурный синтез цифровых автоматов
Структурный синтез ЦА выполняется с привязкой к запоминающим элементам и внутренней структуре. Структурный синтез включает:
В простейшем случае под кодированием понимают назначение всем символам алфавитов двоичных кодов. Как правило, длину кода выбирают исходя из количества букв в алфавите. Например, если у автомата три возможных входных значения, то каждое значение кодируется двумя битами, если 5, то уже тремя.
1-2 буквы – 1 бит
2-4 буквы – 2 бита
3-8 букв – 3 бита
и т.д.
При таком подходе к кодированию состояний автомата сложность КС1 и КС2 может быть далеко не оптимальной. А при переключении автомата из состояния в состояние следует стремиться к минимальному количеству переключаемых триггеров.
9.1 Эвристический алгоритм кодирования синхронних автоматов
Данный алгоритм минимизирует суммарное число переключений элементов памяти на всех переходах автомата и используется для кодирования состояний автомата при синтезе на базе T, RS, JK-триггеров. Для данных типов триггеров (в отличие от D-триггеров!) на каждом переходе, где триггер меняет свое значение на противоположное, одна из функций возбуждения обязательно равна 1. Уменьшение числа переключений триггеров приводит к уменьшению количества единиц соответствующих функций возбуждения, что при отсутствии минимизации однозначно приводит к упрощению комбинационной схемы автомата.
Введем некоторые определения.
Пусть Г(S) – неориентированный граф переходов автомата S. Вершины графа отождествляются с состояниями автомата. Вершины i и j соединены ребром, если есть переход из аi и аj или наоборот.
Обозначим q(i, j) число всевозможных переходов автомата из аi в аj. Каждому ребру (i, j) графа Г(S) поставим в соответствие вес ребра р(i, j) = q(i, j) + q(j, i).
Введем функцию w(i, j) = р(i, j) d(i, j), где d(i, j) – число компонентов, которыми коды состояний аi в аj отличаются друг от друга (т.е. кодовое расстояние между кодами аi в аj).
Функция w(i ,j) имеет простой физический смысл. Перход автомата из аi в аj (или наоборот) сопровождается переключением стольких триггеров, сколькими компонентами отличаются коды этих состояний, т.е. их число равно w(i ,j). Следовательно, при переходе автомата по всем ребрам, соединяющим состояниям аi и аj (их число p(i, j)!) всего переключится количество триггеров, равное p(i, j)d(i ,j) =w(i ,j).
Но тогда функция показывает, сколько всего переключается триггеров при прохождении автомата по всем возможным переходам. Функция w показывает, сколько всего единиц в функции возбуждения, т.е. позволяет оценивать сложность комбинационной схемы автомата. W можно рассматривать как некую целевую функцию, минимум которой определит такое кодирование, при котором комбинационная схема наиболее простая. Кстати, миинмальное кодовое расстояние между различными состояниями равно 1 и если удается закодировать все состояния соседним кодированием, то очевидно, что w будет минимально возможным и равным , т.е. суммарному числу переходов для автомата.
Из выражения для w следует, что переход из аi в аi, для которого d(i,i)=0, не влияет на w (что вполне очевидно, если учесть, что на этом переходе ни один триггер не переключается).
Рассмотрим применение эвристического алгоритма на конкретном примере автомата, заданного таблицами переходов и выходов (рис.41. ). Для данного автомата можно построить ориентированный граф (без учета петель), представленный на рисунке 11.6. На каждом ребре указан его вес.
Алгоритм состоит из следующих шагов.
1. Строим матрицу , состоящую из всех пар номеров (i, j), для которых р(i, j) 0 (т.е. в автомате есть переход из аi в аj или наоборот) и i<j. Для каждой пары в матрице указываем ее вес р(i, j), совпадающий с весом ребра соединяющего аi и аj.
|
i |
j |
p(i,j) |
||
|
1 |
2 |
2 |
||
|
1 |
3 |
1 |
||
|
T |
= |
1 |
5 |
1 |
|
2 |
3 |
3 |
||
|
2 |
4 |
1 |
||
|
2 |
5 |
1 |
||
|
3 |
4 |
2 |
||
|
3 |
5 |
2 |
2. Упорядочим строки матрицы , для чего построим матрицу следующим образом. В первую строку матрицы поместим пару (,) с наибольшим весом р(,). В нашем случае (,) = (2,3), р(2,3) = 3. Из всех пар, имеющих общий компонент с парой (,) выбирается пара (,) с наибольшим весом и заносится во вторую строку матрицы . Ясно, что {,}{,}0. Затем из всех пар, имеющих общий компонент хотя бы с одной из внесенных уже в матрицу пар выбирается пара с наибольшим весом и заносится в матрицу и т.д.. В случае равенства весов пар вычисляются суммы весов компонентов пар (весом р() компонента называется число появлений в матрице ) и в матрицу заносится пара с наибольшей суммой весов. В рассматриваемом автомате на второе место вслед за парой (2,3) претендуют пары: (1,2) с р(1,2) = 2; (3,4) с р(3,4) = 2, (3,5) с р(3,5) = 2.
Для определения того, какая пара займет второе место в матрице находим веса компонентов пар:
р(1) = 3 р(2) = 3 р(1) + р(2) = 6
р(3) = 4 р(4) = 2 р(3) + р(4) = 6
р(3) = 4 р(5) = 2 р(3) + р(5) = 6
В данном случае для всех пар совпадают и их веса и веса их компонентов. Поэтому на второе место матрицы может быть поставлена любая из пар (1,2), (3,4), (3,5). Но тогда на 3-м и 4-м будут остальные две. Выполнив упорядочивание всех пар, получим матрицу в виде:
|
i |
j |
p(i,j) |
||
|
2 |
3 |
3 |
||
|
1 |
2 |
2 |
||
|
M |
= |
3 |
4 |
2 |
|
3 |
5 |
2 |
||
|
1 |
3 |
1 |
||
|
1 |
5 |
1 |
||
|
2 |
4 |
1 |
||
|
2 |
5 |
1 |
3. Определяем разрядность кода для кодирования состояний автомата (количество элементов памяти – триггеров). Всего состояний M=5. Тогда
R = ]log2M[ = ]log25[ =3.
Закодируем состояния из первой строки матрицы следующим образом: K2 = K(а2) = 000; K3 = K(а3) = 001.
Для удобства кодирования будем иллюстрировать этот процесс картой Карно:
|
i |
j |
p(i,j) |
||
|
1 |
2 |
2 |
||
|
3 |
4 |
2 |
||
|
M’ |
= |
3 |
5 |
2 |
|
1 |
3 |
1 |
||
|
1 |
5 |
1 |
||
|
2 |
4 |
1 |
||
|
2 |
5 |
1 |
5. В силу упорядочивания п.2 в первой строке закодирован ровно один элемент. Выберем из первой строки незакодированный элемент и обозначим его . (В нашем случае = 1).
6. Строим матрицу , выбрав из строчки, содержащие .
|
i |
j |
p(i,j) |
||||
|
1 |
2 |
2 |
||||
|
M |
= |
M’ |
= |
1 |
3 |
1 |
|
1 |
5 |
1 |
Пусть B = {1,...,F} – множество элементов из матрицы , которые уже закодированы. Их коды К1,..., KF соответственно. В нашем случае:
B = B3 = {2,3} K2 = 000 K3 = 001.
7. Для каждого Kf (f=1, ..., F) найдем – множество кодов, соседних с и еще не занятых для кодирования состояний автомата. (Для соседних кодов кодовое расстояние d=1).
K2 = 000 = {100, 010}
K3 = 001 = {011, 101}.
Построим множество
Если оказывается, что , то строим новое множество , где – множество кодов, у которых кодовое расстояние до кода равно 2 и т.д..
8. Для каждого кода из множества D находим кодовое расстояние до кода .
K2 = 000 K3 = 001
d(100, 000) = 1 d(100, 001) = 2
d(010, 000) = 1 d(010, 001) = 2
d(011, 000) = 2 d(011, 001) = 1
d(101, 000) = 2 d(100, 001) = 1
9. Находим значение функции w для каждого кода из множества D.
10. Из множества D выбираем код K, у которого получилось минимальное значение w в п.9. Выбираем код для состояния a1 К1 =100.
11. Из матрицы вычеркиваем строки, в которых оба элемента уже закодированы, в результате чего получим новую матрицу . Если в новой матрице не осталось ни одной строки, то кодирование закончено. В противном случае возвращаемся к п.5. В нашем случае имеем:
|
i |
j |
p(i,j) |
||
|
3 |
4 |
2 |
||
|
3 |
5 |
2 |
||
|
M’ |
= |
1 |
5 |
1 |
|
2 |
4 |
1 |
||
|
2 |
5 |
1 |
К2 = 000 = {010}
K3 = 001 = {011, 101}
K2 = 000 K3 = 001
d(010, 000) = 1 d(010, 001) = 2
d(011, 000) = 2 d(011, 001) = 1
d(101, 000) = 2 d(101, 001) = 1
Выбираем К4 = 101.
К1 = 100 = {110}
K2 = 000 = {010}
К3 = 001 = {011}
К1 = 100 K2 = 000 K3 = 001
d(110, 100) = 1 d(110, 000) = 2 d(110, 001) = 3
d(010, 100) = 2 d(010, 000) = 1 d(010, 001) = 2
d(011, 100) = 3 d(011, 000) = 2 d(011, 001) = 1
Выбираем К5 = 011.
Т.к. все состояния автомата закодированы, то работа алгоритма заканчивается. Общее количество переключений триггеров:
Минимально возможное количество переключений (если бы состояния были закодированы соседним кодированием)
Коэффициент эффективности кодирования:
Рассмотренный алгоритм кодирования является машино-ориентированным, существуют программы, реализующие этот алгоритм.
Необходимо отметить в заключении, что использование алгоритма кодирования обеспечивает наиболее простую с точки зрения реализации схему, но при этом возможны гонки. Для радикального устранения последних используют аппаратные методы – триггеры с двойной памятью: триггеры, управляемые фронтом и т.д..
9.2 Пример структурного синтеза синхронного автомата
Выполнить синтез синхронного цифрового автомата заданный совмещенной таблицей переходов/выходов.
|
0 |
1 |
y |
|
|
a0 |
a2 |
a1 |
0 |
|
a1 |
a3 |
a4 |
0 |
|
a2 |
a4 |
a3 |
0 |
|
a3 |
a5 |
a0 |
0 |
|
a4 |
a0 |
a5 |
0 |
|
a5 |
a2 |
a1 |
1 |
Шаг 1 - Для упрощения примера кодирование выполняется не эвристическим алгоритмом, а наиболее простым последовательным способом. В лабораторной работе необходимо выполнить кодирование состояний с помощью эвристического алгоритма.
|
Двоичный код |
|
|
a0 |
000 |
|
a1 |
001 |
|
a2 |
010 |
|
a3 |
011 |
|
a4 |
100 |
|
a5 |
101 |
Шаг 2 – Переписывается таблица переходов в закодированном виде, вместо букв состояний подставляются двоичные коды состояний. Данная таблица показывает как должны переключатся триггеры под влиянием входных сигналов автомата.
|
0 |
1 |
y |
|
|
000 |
010 |
001 |
0 |
|
001 |
011 |
100 |
0 |
|
010 |
100 |
011 |
0 |
|
011 |
101 |
000 |
0 |
|
100 |
000 |
101 |
0 |
|
101 |
010 |
001 |
1 |
Шаг 3 – Записывается подграф переходов для триггера (JK, RS, T, D), на котором будет построен автомат. В данном случае будем строить на Т-триггере.
|
T |
|||
|
0 |
0 |
0 |
|
|
0 |
1 |
1 |
|
|
1 |
1 |
0 |
|
|
1 |
0 |
1 |
|
Шаг 4 – Из закодированной таблицы переходов, полученной на шаге 2 и подрафа переходов для триггера (шаг 3) составляется таблица истинности для входных сигналов триггера, т.е. таблица истинности для функции переходов
|
Q1 |
Q2 |
Q3 |
X=0 |
X=1 |
||||
|
T2 |
T3 |
T1 |
T2 |
T3 |
||||
|
0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
|
0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
|
0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
|
0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
|
1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
|
1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
Шаг 5 – По полученной на шаге 4 таблице строят карты Карно для всех входов триггеров. В данном случае три карты Карно для Т1, Т2, Т3
|
Q3X Q1Q2 |
00 |
01 |
11 |
10 |
|
00 |
0 |
0 |
1 |
0 |
|
01 |
1 |
0 |
0 |
1 |
|
11 |
- |
- |
- |
- |
|
10 |
1 |
0 |
1 |
1 |
T1=(nQ2Q3X)U(Q1 nX)U(Q2 nX)
|
Q3X Q1Q2 |
00 |
01 |
11 |
10 |
|
00 |
1 |
0 |
0 |
1 |
|
01 |
1 |
0 |
1 |
1 |
|
11 |
- |
- |
- |
- |
|
10 |
0 |
0 |
0 |
1 |
T2=(nQ1Q3)U(Q1 nX)U(Q2 nX)
|
Q3X Q1Q2 |
00 |
01 |
11 |
10 |
|
00 |
0 |
1 |
1 |
0 |
|
01 |
0 |
1 |
1 |
0 |
|
11 |
- |
- |
- |
- |
|
10 |
0 |
1 |
0 |
1 |
T2=(Q3x)U(nQ1 X)U(Q1 Q3 nX)
Шаг 6 – По таблице выходов строится таблица для получения функции выходов автомата.
|
Q1 |
Q2 |
Q3 |
y |
|
0 |
0 |
0 |
0 |
|
0 |
0 |
1 |
0 |
|
0 |
1 |
0 |
0 |
|
0 |
1 |
1 |
0 |
|
1 |
0 |
0 |
0 |
|
1 |
0 |
1 |
1 |
y= Q1 nQ2 Q3
Шаг 7 – по уравнениям, полученным на шаге 5 и 6, строится схема автомата, приведенная на рисунке.
ПТЦА
?