Проектирование элементов ЭВУ

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

Рубрика Коммуникации, связь, цифровые приборы и радиоэлектроника
Вид курсовая работа
Язык русский
Дата добавления 21.05.2013
Размер файла 714,7 K

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru

Министерство общего и профессионального образования

Российской Федерации

НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ

ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

Кафедра РП и РПУ

Проектирование элементов ЭВУ

Пояснительная записка к курсовой работе по дисциплине

“Цифровые устройства и микропроцессоры”

Новосибирск

2013

Оглавление

Задание на курсовую работу

Построение графа синтезируемого автомата

Определение количества элементов памяти

Составление таблицы переходов и выходов КА

Составление таблиц возбуждения памяти КА

Синтез комбинационной части Ка

Переход от исходного автомата Мили к эквивалентному автомату Мура

Кодирование автомата Мура

Алгоритмы вычисления функций

Текст программы

Список используемой литературы

конечный автомат граф алгоритм

Задание на курсовую работу

Синтез конечного автомата (КА) Мили:

Построить граф конечного автомата для заданного варианта;

Определить количество элементов памяти

составить таблицы перехода и выходов КА;

составить таблицу возбуждения элементов памяти (Т -триггер);

синтезировать комбинационную часть КА;

реализовать КА на микросхемах одной из серии: К564. Составить полную логическую схему автомата.

Программная реализация автомата:

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

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

Вариант:

номер варианта: последние четыре цифры индивидуального шифра 0213.

Вариант задания - 26

Реализация автомата Мили на микросхемах серии - К564

Построение графа синтезируемого автомата

Граф синтезируемого автомата Мили получается путем исключения некоторых ветвей обобщенного графа автомата, имеющего 4 внутренних состояния (рис.1). У такого графа из каждой вершины выходят 4 ветви (и столько же входят). Каждая ветвь символизирует переход автомата в другое внутреннее состояние при совместном воздействии входного сигнала и выходного сигнала обозначается их комбинацией при конкретном значении индексов.

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

Вершина

графа

Сигнал

Номер выходящей из вершины ветви

1234

1234

1234

1234

1234

1234

1234

1234

Вариант 13

2314

3114

1200

2200

0432

0414

0010

0020

Рис. 1. Граф синтезируемого автомата Мили.

Определения количества элементов памяти

Выбираем в качестве элементов памяти JK-триггеры. Базис логических элементов - произвольный.

Для данного примера видно:

- число внутренних состояний ();

- число входных сигналов ();

- число выходных сигналов ().

Находим:

- число элементов памяти ;

- число разрядов входной шины ;

- число разрядов выходной шины .

Составление таблицы переходов и выходов КА

По графу автомата Мили (Рис. 1.) составим таблицу переходов и выходов. Строки таблиц отмечены входными сигналами, а столбцы - внутренними состояниями. Крайний левый столбец таблиц отмечается начальным состоянием автомата а1. Входные сигналы и состояния, отмечающие строки и столбцы таблиц, относятся к моменту времени t, т.е. отражают и . На пересечение столбца и строки в таблице переходов ставится состояние , определяемое функцией переходов . В состояние автомат переключается из состояния под действием сигнала .

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

Кодируем автомат, ставя в соответствие каждому символическому сигналу произвольный двоичный код (число разрядов в кодах соответствует найденным r, n, m).

С учетом введенных кодов переводим таблицы выходов и переходов в двоичный алфавит.

По таблице выходов составляем логические уравнения для выходных сигналов y1 и y2. Учтем, что в каждой клетке таблицы левый бит характеризует сигнал y1, а правый - y2. Записывая уравнение «по единицам», получаем СДНФ:

Минимизируем эти функции при помощи карт Карно.

Рис 2. Карты Карно для выходных сигналов y1 и y2.

Получим эти функции после минимизации:

Составление таблиц возбуждения памяти Ка

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

Таблица 8.

Q(t)

Сигналы для перехода в состояние Q(t+1)

Q(t+1)

Т

0

0

0

0

1

1

1

1

0

1

0

1

Таблица возбуждения памяти автомата после рассмотрения переходов по всем столбцам:

x1x2

Q1Q2

00

01

10

11

00

10

01

-

10

01

00

11

11

-

10

01

-

10

-

11

11

-

01

-

По таблице возбуждения памяти составляем логические уравнения сигналов на каждом информационном входе каждого триггера. Записывая их "по единицам", получаем СДНФ:

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

Т1:

Т2:

Рис 3. Карты Карно для входных сигналов триггеров Т1, Т2.

Получим эти функции после минимизации:

Синтез комбинационной части КА

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

Рис 3. Структурная схема КА Мили.

Рис.5. Логическая схема комбинационной части автомата на дискретных элементах.

Рис.6. Схема комбинационной части автомата на микросхемах выбранной серии.

Переход от исходного автомата Мили к эквивалентному автомату Мура

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

(a)

(б)

Рис. 7. Автомат Мили (a) и Мура (б).

Построим совмещённую таблицу переходов автомата Мили, которой соответствует граф, изображённый на рис.1.

Таблица 11.

Сост.

входа

а1

а2

а3

а4

Z1

а3

W1

а1

W2

-

а2

W2

Z2

а1

W3

а3

W2

а2

W4

-

Z3

а2

W1

-

а1

W1

-

Z4

а4

W4

-

а4

W4

-

Переход к автомату Мура осуществляется в следующем порядке:

Находим множества , определяемые числом различных выходных сигналов на дугах, входящих в данное состояние.

Составим таблицу переходов автомата Мура на основании таблицы переходов автомата Мили и состояний .

Таблица 12.

а1

а2

а3

а4

b1/W1

b2/W2

b3/W3

b4/W1

b5/W2

b6/W4

b7/W1

b8/W2

b9/W4

Z1

b7

b7

b7

-

b2

b2

-

-

b5

Z2

b3

b3

b3

b7

b8

b8

b6

b6

-

Z3

b4

b4

b4

-

-

-

b1

b1

-

Z4

b9

b9

b9

-

-

-

b9

b9

-

Построим граф автомата Мура:

Рис. 8. Граф автомата Мура.

Кодирование автомата Мура

Программа, моделирующая работу автомата Мура, должна реализовывать алгоритм его работы в соответствии с уравнениями:

Найдем количество двоичных разрядов, необходимых для кодирования всех входных сигналов:

И всех внутренних состояний (выходных сигналов)

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

Таблица 13.

Входные сигналы

Состояние входа

Биты кода

x1

x2

Z1

0

0

Z2

0

1

Z3

1

0

Z4

1

1

Таблица 14.

Внутренние состояния и выходные сигналы

Внутреннее

состояние

Биты кода

Биты кода

Выходной сигнал

автомата Мили

b1

0

0

0

0

0

0

W1

b2

0

0

0

1

0

1

W2

b3

0

0

1

0

1

0

W3

b4

0

0

1

1

0

0

W1

b5

0

1

0

0

0

1

W2

b6

0

1

0

1

1

1

W4

b7

0

1

1

0

0

0

W1

b8

0

1

1

1

0

1

W2

b9

1

0

0

0

1

1

W4

Переводим таблицу переходов (выходов) в двоичный алфавит.

Таблица 15.

/

0000/

00

0001/

01

0010/

10

0011/

00

0100/

01

0101/

00

110/

01

0111/

01

1000/

11

00

0110

0110

0110

0001

0001

0001

-

-

0100

01

0010

0010

0010

0111

0111

0111

0101

0101

-

10

0011

0011

0011

-

-

-

0000

0000

-

11

1000

1000

1000

-

-

-

1000

1000

-

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

E1:

E2:

E3:

E4:

Рис 9. Карты Карно E1, E2, E3, E4.

Получаем минимизированные выражения:

Алгоритмы вычисления функцій

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

Текст программы

Принят следующий формат написания программ на ассемблере. Каждая строка программы делится на четыре поля: поле метки, поле мнемокода, поле операндов, поле комментариев. Метка ассоциируется с 16-битным адресом ячейки памяти, в которую будет помещен первый байт отмеченной меткой команды.

В приведенной программе предполагается, что коды входных сигналов поступают в порт ввода, выходные сигналы засылаются в порт вывода, состояния сохраняются в регистре С. Байты входного сигнала и исходного внутреннего состояния предварительно объединяются в один байт данных вида 000x1x2Q1Q2. Таблицы переходов и выходов автомата Мили записываются в память так, что входной сигнал и исходное состояние с начальным адресом таблицы определяют адрес следующего состояния и выходной сигнал, из которых формируются байт очередного внутреннего состояния 000000Q*1Q*2 и соответствующий этому состоянию байт выходного сигнала 000000у1у2.

Совмещенная таблица переходов и выходов:

Таблица 16.

x1x2

00

01

10

11

00

00/10

01/00

-

01/01

01

10/00

01/10

11/01

-

10

00/01

-

00/00

-

11

11/11

-

11/11

-

Для более ясного понимания алгоритма программной реализации перепишем совмещенную таблицу переходов и выходов (Таблица 16) в следующей форме (Таблица 17):

номер ячейки памяти от нуля

x1x2Q1Q2

у1у2/ Q1Q2

16-ричные коды состояний и выходов

0

0000

00 10

02h

1

0001

01 00

04h

2

0010

-

00h

3

0011

01 01

05h

4

0100

10 00

08h

5

0101

01 10

06h

6

0110

11 01

0Dh

7

0111

-

00h

8

1000

00 01

01h

9

1001

-

00h

10

1010

-

00h

11

1011

-

00h

12

1100

11 11

0Fh

13

1101

-

00h

14

1110

11 11

0Fh

15

1111

-

00h

Программа:

Метка

Мнемокод команды

Операнды

Комментарий

LXI

H,TABLE

Загрузка в HL двухбайтового начального адреса таблицы переходов и выходов

MOV

A.PORTx

Пересылка кода входного сигнала x1x2 из порта ввода в А

RLC

Сдвиг содержимого аккумулятора на один разряд влево

RLC

Повторный сдвиг содержимого А на один разряд влево в результате получаем байт 000x1x200 в А

ORA

C

Логическим сложением содержимого А и С вычисляется адрес смещения 000x1x2Q1Q2 таблицы

MOV

E,A

Сохраняем в Е (старший байт DE) байт адреса смещения

MVI

D,0h

Обнуляем младший байт DE

DAD

D

Сложением содержимого HL и DE вычисляется абсолютный адрес кода нового состояния и выхода автомата

MOV

A,M

Пересылка из таблицы в А кода нового состояния и выхода

MOV

E,A

Сразу же сохраняем байт нового состояния и выхода в Е, в А код нового состояния и выхода остается

LXI

B,0C03h

Загружаем в регистровую пару BC 16-ричные коды масок выходов 00001100 и состояний 00000011

ANA

B

Логическим умножением содержимого А и младшего байта регистровой пары BC выделяем в А выходные сигналы 000x1x200

RRC

Сдвиг содержимого аккумулятора на один разряд вправо

RRC

Повторный сдвиг содержимого А на один разряд вправо, в результате получаем байт 000000 x1x2 в А

MOV

PORTy,A

Вывод кода выходных сигналов из А в порт вывода

MOV

A,E

Восстанавливаем в А считанный из таблицы байт выходов и состояний

ANA

C

Логическим умножением содержимого А и маски старшего байта регистровой пары ВС выделяем в А состояния 000000Q1Q2

MOV

C,A

Пересылка кода состояния 000000Q1Q2 из А в С

HLT

Остановка

Таблица 18.

Метка

Мнемокод команды

16-ричные коды состояний и выходов

Записываемые коды состояний и выходов

TABLE:

00h

00/00

01h

00/01

02h

00/10

05h

01/01

06h

01/10

08h

10/00

0Dh

11/01

0Fh

11/11

Список используемой литературы

Цифровые устройства и микропроцессоры: методическое указание к курсовой работе по ЦУ и МП / Сост.: В.В.Родников, С.Н. Савченко, А.М. Сажнев. - НГТУ. - Новосибирск, 1998.

Цифровые устройства и микропроцессоры: учеб. пособие/ А. В. Микушин, А. М. Сажнев, В. И. Сединин. - СПб.: БХВ-Петербург, 2010. - 832 с.: ил. - (Учебная литература для вузов).

Размещено на http://www.allbest.ru


Подобные документы

  • Алгоритм работы автомата Мили в табличном виде. Графический способ задания автомата. Синтез автомата Мили на Т-триггерах. Кодирование состояний автомата. Таблицы кодирования входных и выходных сигналов. Таблица переходов и выходов абстрактного автомата.

    курсовая работа [24,7 K], добавлен 01.04.2010

  • Проектирование цифровых автоматов Мили и Мура с памятью в булевом базисе по заданной ГСА. Составление частично структурированной таблицы переходов-выходов. Построение функций выходов, логической схемы автомата. Особенности его экспериментальной проверки.

    курсовая работа [628,7 K], добавлен 14.07.2012

  • Управляющий цифрового автомат типа Мура. Абстрактный и структурный синтез автомата, построена функциональная схема. Функции выходов и возбуждения элементов памяти. Моделирование на ПК с использованием симулятора ModelSim. Описание автомата на языке VHD.

    курсовая работа [214,2 K], добавлен 07.11.2010

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

    курсовая работа [2,8 M], добавлен 04.02.2013

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

    курсовая работа [66,3 K], добавлен 10.11.2010

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

    контрольная работа [1,2 M], добавлен 23.06.2012

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

    курсовая работа [868,4 K], добавлен 07.04.2012

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

    курсовая работа [1,6 M], добавлен 22.10.2012

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

    курсовая работа [57,9 K], добавлен 29.12.2011

  • Структурная схема и синтез цифрового автомата. Построение алгоритма, графа и таблицы его функционирования в микрокомандах. Кодирование состояний автомата. Функции возбуждения триггеров и формирования управляющих сигналов. Схема управляющего устройства.

    курсовая работа [789,4 K], добавлен 25.11.2010

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.