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

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

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

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

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

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

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

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

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

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

Новосибирск

2013

Оглавление

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Вариант:

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

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

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

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

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

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

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

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

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

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

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

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

Находим:

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

E1:

E2:

E3:

E4:

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

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

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

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

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

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

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

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

Таблица 16.

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

Программа:

Таблица 18.

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

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

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

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