48125 (Построение кодопреобразователя), страница 2

Y = {у₁.. .,у_п} - множество выходных сигналов,

- функция переходов абстрактного цифрового автомата,

- функция выходов абстрактного цифрового автомата,

a₁ - начальное состояние автомата (a_i принадлежит А).

Для однозначного управления цифровым автоматом необходимо, чтобы он начинал работу с определённого начального состояния. Автомат является конечным, если А, X и Y не являются бесконечными множествами. Теоретически все элементы множеств А, X, Y могут быть закодированы числами в системе счисления с любым основанием, но на практике всегда используется двоичная система счисления. Согласно структурной схеме (рис.1), коды наборов переменных комбинационных схем определяются в результате конкатенации кодов входных сигналов и кодов состояний блока памяти. Как наборы входных переменных, так и коды состояний блока памяти в общем случае содержат запрещённые комбинации, поэтому системы функций алгебры логики, описывающие комбинационные схемы, не будут полностью определёнными.

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

При рассмотрении конечного автомата необходимо рассмотреть условие автоматности, то есть выполнение следующих условий:

1. Длина входного слова должна соответствовать длине выходного слова. В общем случае при несоответствии входного и выходного слов недостающие фрагменты заполняются пустыми символами (0);

2. Минимум три первых символа входных и выходных слов должны соответствовать друг другу. В нашем случае это условие частично не выполняется, поэтому для соблюдения условия автоматности кодопреобразователя к входному и выходному словам добавим пустые символы (0).

При этом таблица соответствия примет вид:

Часто на практике используется две разновидности цифровых автоматов, отличающихся способом формирования выходных сигналов:

- при описании функционирования автомата выражениями:

a(t+l) = 5[a(t),z(t)],

w(t) = [a(t), z(t)] - он называется автоматом Мили;

- при описании функционирования автомата выражениями:

a(t+1) = [a(t),z(t)],

w(t) = [а(t)] - он называется автоматом Мура.

В этих выражениях t - текущий момент дискретного автоматного времени, t+1 -следующий момент дискретного автоматного времени.

Понятия теории графов

Графами называют взаимосвязь двух множеств состоящих из множества вершин и множества рёбер, индуцируемых (связанных) между собой.

Полный граф - это граф, не имеющий петель, кратности ребер, и все его вершины связаны между собой.

Неориентированный граф - граф, не имеющий указания направлений ребер, при переходе из одной вершины в другую.

Ориентированный (полный) граф - граф с ребрами, указывающими конкретное направление при переходе из одной вершины в другую.

Граф-дерево - это слабосвязанный граф, у которого если удалить одно ребро, то он распадается на два графа.

Граф автомата - ориентированный связный граф, вершины которого соответствуют состояниям, а дуги - переходам между ними.

Теория графов имеет большие приложения, так как язык теории, с одной стороны, очевиден, а, с другой стороны, удобен в нормальном исследовании. При полном изображении графа не все детали рисунка имеют одинаковое значение, а именно геометрические свойства рёбер (кривизна, длина и т.д.) и расположение вершин на плоскости относительно друг друга.

Две вершины графа автомата а_т и a_s (исходное состояние и состояние перехода) соединяются дугой (ребром), направленной от а_т в a_s. Дуге (а_т, a_s) графа автомата приписывается входной сигнал х и выходной сигнал у, если он определён, и, в противном случае, ставится прочерк. Если переход автомата из состояния а_т в состояние a_s происходит под действием нескольких входных сигналов, то дуге (a_m, a_s) приписываются все эти входные и соответствующие выходные сигналы.

При описании автомата Мура в виде графа выходной сигнал y записывается внутри вершины а_т или рядом с ней, а входной сигнал х над дугой (ребром), демонстрирующей переход из одного состояния в другое.

При описании автомата Мили в виде графа внутри вершины записывается состояние, в которое переходит автомат, а над дугой (ребром), демонстрирующей переход из одного состояния автомата в другое, записывается дробь, в числителе которой указывается входной сигнал, а в знаменателе - выходной сигнал.

Для задания функций переходов и выходов построим граф-дерево автомата Мура, а затем автомата Мили. При использовании табличного описания автомата Мура таблицы переходов автоматов Мили и Мура совпадут, а таблица выходов автомата Мили получится из таблицы переходов заменой a_s символом выходного сигнала.

В технических целях используются только детерминированные цифровые автоматы, в которых выполнено условие однозначности переходов: - автомат, находящийся в некотором состоянии, под действием любого входного сигнала не может перейти более чем в одно состояние. Применительно к табличному способу задания описания автоматов это означает, что в клетках переходов/выходов указывается только по одному состоянию/выходному сигналу. Применительно к графическому способу задания описания автоматов это означает, что в графе автомата из любой вершины не могут выходить две или более дуги, отмеченные одним и тем же входным сигналом.

Устойчивым состоянием автомата называется такое состояние, что для любого х, (a_m, x) = a_s, имеет место (a_s, x) = a_s. Это значит, что если автомат перешёл в некоторое состояние х, то выйти из этого состояния может только под действием другого сигнала.

Синхронным называется автомат, если он не является асинхронным и каждое его состояние устойчиво.

Если для некоторой пары (a_m, z_f) выходной сигнал автомата не определён, то для этой пары не определяется и функция перехода, так как не определено допустимое слово, осуществляющее переход из этого состояния.

Граф-дерево автомата Мура.

Для построения графа-дерево автомата Мура используем таблицу соответствия, дополненную до выполнения условия автоматности. После выполнения условия автоматности граф-дерево примет вид:

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

Граф-дерево автомата Мили.

10

В ходе этапа построения кодопреобразователя осуществляется преобразование графа-дерево автомата Мура в граф-дерево автомата Мили. Для этого все конечные состояния автомата Мура заменяются нулевым состоянием. Граф-дерево автомата Мили:

Таблица переходов по автомату Мили

Следующим шагом является построение кодопреобразователя по полученному графу автомата Мили - построение таблицы переходов автомата из одного состояния в другое под действием входных переменных.

Таблица выходов по автомату Мили