Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Построение кодопреобразователя (вариант 22) - файл 1.doc


Построение кодопреобразователя (вариант 22)
скачать (1797 kb.)

Доступные файлы (1):

1.doc1797kb.16.11.2011 10:01скачать

содержание

1.doc

  1   2   3   4   5   6   7   8   9



МИНИСТЕРСТВО ОБРАЗОВАНИЯ Российской Федерации

Южно-Уральский государственный университет


ЗАОЧНЫЙ ИНЖЕНЕРНО-ЭКОНОМИЧЕСКИЙ ФАКУЛЬТЕТ

КАФЕДРА АВТОМаТИКИ И УПРАВЛЕНИЯ


Курсовая работа


По курсу: «ЦИФРОВЫЕ АВТОМАТЫ»


Вариант № 22: «Построение кодопреобразователя»


Выполнил: Зубков А.А.

Группа: УИТС-228-С


Проверил: Радкевич И.А.

Челябинск 2003г.


Задание.


Построить устройство для преобразования последовательного двоично-десятичного кода х=(х3210), соответствующего десятичным цифрам 0,1,2,3,…9, который подается на вход устройства, в последовательный двоично-десятичный код z=(z3,z2,z1,z0).

Десятичный эквивалент Х двоично-десятичного кода может быть вычислен следующим образом: , где xi=0,1 – цифра двоично-десятичного кода; pi – вес i-го разряда кода.

Вариант задания представлен в таблице:


№ варианта

x

P3P2P1P0

z

P3P2P1P0

27

4221

8421

1 8421 5321

Аннотация.




В ходе выполнения курсовой работы на практике было реализовано построение кодопреобразователя по заданным параметрам функций входа и выхода.

На первом этапе реализации работы была составлена таблица соответствий входного и выходного сигналов для десяти заданных значений и произведены преобразования для соблюдения условия автоматности.

На втором этапе работы произведено построение граф-дерева для абстрактного автомата Мура и преобразование его в граф-дерево абстрактного автомата Мили. Затем по графу составлены таблицы переходов и выходов для автомата Мили.

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

Четвертым этапом работы произведен структурный синтез цифрового автомата с кодированием двоичным кодом входной, выходной функций автомата, а также функции состояний.

Определена таблица состояний выбранного для реализации кодопреобразователя D-триггера.

Пятым этапом выполнения работы была минимизирована методом Мак-Класки выходная функция полученного автомата и реализована в базисе И, ИЛИ, НЕ.

По этим таблицам определены и минимизированы, функции выхода кодопреобразователя и функции возбуждения D-триггера.

Заключительным этапом выполнения работы была произведена минимизация методом Мак-Класки функция возбуждения выбранного D-триггера и составлена схема последовательного кодопреобразователя заданной входного кода в заданный выходной на простейших цифровых автоматах с памятью.

Оглавление.


Аннотация. 2

Оглавление. 3

Содержание работы. 4

Основные понятия алгебры логики. 4

1.2 Составление таблицы соответствия. 5

2. Основные понятия теории графов. 6

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

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

2.3 Таблица переходов по графу Мили. 9

2.4 Таблица выходов по графу Мили. 9

3. Минимизация абстрактного автомата Мили. 10

3.1. Таблица переходов с распределением неопределенностей. 10

3.2 Исключение недостижимых состояний. 10

3.3 Определение классов совместимости. 10

4.Структурный синтез цифрового автомата. 17

1. Минимизация с помощью минимизирующих карт. 20

2. Минимизация функций алгебры логики по методу Квайна 21

3. минимизация функций алгебры логики по методу Мак-Класки 21

Заключение. 41
^

Содержание работы.

Основные понятия алгебры логики.


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

Для формального описания цифровых автоматов применяется аппарат алгебры логики, созданной английским математиком Джорджем Булем (1815-1864). Поэтому алгебру логики называют алгеброй Буля или булевой алгеброй.

В алгебре логики применительно к описанию цифровых автоматов, работающих в двоичном представлении кодов (или цифровой информации) основными понятиями являются логическая (булева) переменная и логическая функция (функция алгебры логики - ФАЛ).

^ Логическая (булева) переменная - такая величина x, которая может принимать только два значения : x = {0,1} (ложное или истинное высказывание).

Логическая функция (функция алгебры логики - ФАЛ) - функция многих аргументов f(xn-1, xn-2,, ..., x0), принимающая значения равные нулю или единице на наборах логических переменных xn-1, xn-2,, ..., x0.

В дальнейшем в формальных описаниях наборов переменных и логических функций сами наборы переменных интерпретируются как двоичные коды (числа). В двоичных кодах расположение логических переменных упорядочено в порядке уменьшения индекса слева направо и каждая логическая переменная имеет вес в зависимости от позиции в коде, увеличивающийся справа налево. Вес каждой i - той логической переменной, являющейся значением разряда двоичного числа равен 2i (i = 0, ... , n-1).

Для n - разрядного кода общее количество уникальных наборов переменных

N = 2n;

Максимальное числовое значение двоичного кода равно

Aмакс = 2n-1;

Значения всех логических функций от одной переменной представлены в таблице 1.





Функция f0(x) называется константой нуля, а функция f3(x) - константой единицы. Функция f1(x), повторяющая значения логической переменной, - тождественная функция (f1(x) x), а функция f2(x), принимающая значения, обратные значениям переменной x, - логическое отрицание или инверсия (НЕ) (f2(x) = ).

Над элементами алгебры логики можно выполнять следующие операции:

Конъюнкция (И, логическое умножение) – произведение двух высказываний Р и Q, результатом которого является истина если оба высказывания истинны и ложное во всех других случаях;

Дизъюнкция (ИЛИ, логическая сумма) – сумма двух высказываний Р и Q, называется высказывание ложное если оба высказывания ложные и истинное во всех других случаях;

Инверсия (отрицание) – отрицание высказывания Р называется высказывание истинное, когда само высказывание Р ложное или наоборот.


^

1.2 Составление таблицы соответствия.



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





десятичные

цифры

входной код

4221 8421

выходной код

8421 5321







0

0000

0000







1

0001

0001







2

0010

0010







3

0011

0011







4

0110

0100







5

1001

0101







6

1100

0110







7

1101

0111







8

1110

1000







9

1111

1001





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

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

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

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





десятичные

цифры

входной код

4221 8421

выходной код

8421 5321







0

0000000

0000000







1

0001000

0000001







2

0010000

0000010







3

0011000

0000011







4

0110000

0000100







5

1001000

0000101







6

1100000

0000110







7

1101000

0000111







8

1110000

0001000







9

1111000

0001001





После того как условие автоматности для проектируемого автомата выполнено, переходим к следующему этапу – построение граф-дерева для абстрактного автомата Мура.

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

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

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

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

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

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

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

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

^

2. Основные понятия теории графов.



Для определения основных понятий теории графов необходимо ввести определение множества. Множество - это совокупность некоторых объектов, объедененное общими свойствами. Множество может содержать n число компонентов. Множество может быть, конечно, или бесконечно.

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


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


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


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


Общий вид графов.





Неориентированный граф Ориентированный граф


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


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


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

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

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

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



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



0

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

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



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


^




    1. Таблица переходов по графу Мили.



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


х / а

а0

а1

а2

а3

а4

а5

а6

а7

а8

а9

а10

а11

0

а1

а3

а5

а7

-

а10

а11

а13

а15

а17

-

а19

1

а2

а4

а6

а8

а9

-

а12

а14

а16

-

а18

а20




х / а

а12

а13

а14

а15

а16

а17

а18

а19

а20

а21

а22

а23

0

а21

а23

а24

а25

а26

а27

а28

а29

а30

а31

а32

а33

1

а22

-

-

-

-

-

-

-

-

-

-

-




х / а

а24

а25

а26

а27

а28

а29

а30

а31

а32

а33

а34

а35

0

а34

а35

а36

а37

а38

а39

а40

а41

а42

а0

а0

а0

1

-

-

-

-

-

-

-

-

-

-

-

-
  1   2   3   4   5   6   7   8   9



Скачать файл (1797 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации