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

2016-07-30СтудИзба

Описание файла

Документ из архива "Построение кодопреобразователя", который расположен в категории "". Всё это находится в предмете "информатика" из 1 семестр, которые можно найти в файловом архиве . Не смотря на прямую связь этого архива с , его также можно найти и в других разделах. Архив можно найти в разделе "курсовые/домашние работы", в предмете "информатика, программирование" в общих файлах.

Онлайн просмотр документа "48125"

Текст 2 страницы из документа "48125"

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

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

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

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

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

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

Десятичные цифры

Входной код 4311

Выходной код 5311

0

0000

0000

1

0001

0001

2

0010

0010

3

0011

0011

4

0100

0100

5

0101

0101

6

1000

1010

7

1001

1011

8

1100

1110

9

1101

1111

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

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

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

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

Десятичные цифры

Входной код 4311

Выходной код 5311

0

0000000

0000000

1

0001000

0000001

2

0010000

0000010

3

0011000

0000011

4

0100000

0000100

5

0101000

0000101

6

1000000

0001010

7

1001000

0001011

8

1100000

0001110

9

1101000

0001111

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

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

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 -следующий момент дискретного автоматного времени.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

10



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

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

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

x/a

a0

a1

a2

a3

a4

a5

a6

a7

a8

a9

a10

a11

a12

a13

a14

a15

a16

a17

a18

a19

a20

a21

0

a1

a3

a5

a7

a9

a10

a11

a12

a14

a16

a18

a20

a22

a23

a24

a25

a26

a27

a28

a29

a30

a31

1

a2

a4

a6

a8

-

-

-

a13

a15

a17

a19

a21

-

-

-

-

-

-

-

-

-

-

x/a

a22

a23

a24

a25

a26

a27

a28

a29

a30

a31

a32

a33

a34

a35

a.36

a37

a38

a39

a40

a41

0

a32

a33

a34

a35

a36

a37

a38

a39

a40

a41

a0

a0

a0

a0

a0

a0

a0

a0

a0

a0

1

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

-

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

Свежие статьи
Популярно сейчас
Почему делать на заказ в разы дороже, чем купить готовую учебную работу на СтудИзбе? Наши учебные работы продаются каждый год, тогда как большинство заказов выполняются с нуля. Найдите подходящий учебный материал на СтудИзбе!
Ответы на популярные вопросы
Да! Наши авторы собирают и выкладывают те работы, которые сдаются в Вашем учебном заведении ежегодно и уже проверены преподавателями.
Да! У нас любой человек может выложить любую учебную работу и зарабатывать на её продажах! Но каждый учебный материал публикуется только после тщательной проверки администрацией.
Вернём деньги! А если быть более точными, то автору даётся немного времени на исправление, а если не исправит или выйдет время, то вернём деньги в полном объёме!
Нет! Мы не выполняем работы на заказ, однако Вы можете попросить что-то выложить в наших социальных сетях.
Добавляйте материалы
и зарабатывайте!
Продажи идут автоматически
4144
Авторов
на СтудИзбе
666
Средний доход
с одного платного файла
Обучение Подробнее