Проектирование элементов ЭВУ
В приведенной программе предполагается, что коды входных сигналов поступают в порт ввода, выходные сигналы засылаются в порт вывода, состояния сохраняются в регистре С. Байты входного сигнала и исходного внутреннего состояния предварительно объединяются в один байт данных вида 000x1x2Q1Q2. Таблицы переходов и выходов автомата Мили записываются в память так, что входной сигнал и исходное состояние… Читать ещё >
Проектирование элементов ЭВУ (реферат, курсовая, диплом, контрольная)
Министерство общего и профессионального образования Российской Федерации НОВОСИБИРСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ Кафедра РП и РПУ Проектирование элементов ЭВУ Пояснительная записка к курсовой работе по дисциплине
«Цифровые устройства и микропроцессоры»
Новосибирск
Оглавление Задание на курсовую работу
Построение графа синтезируемого автомата Определение количества элементов памяти Составление таблицы переходов и выходов КА Составление таблиц возбуждения памяти КА Синтез комбинационной части Ка Переход от исходного автомата Мили к эквивалентному автомату Мура Кодирование автомата Мура
Алгоритмы вычисления функций Текст программы
Список используемой литературы
конечный автомат граф алгоритм Задание на курсовую работу Синтез конечного автомата (КА) Мили:
Построить граф конечного автомата для заданного варианта;
Определить количество элементов памяти
составить таблицы перехода и выходов КА;
составить таблицу возбуждения элементов памяти (Ттриггер);
синтезировать комбинационную часть КА;
реализовать КА на микросхемах одной из серии: К564. Составить полную логическую схему автомата.
Программная реализация автомата:
Путем эквивалентного преобразования исходного автомата Мили в автомат Мура построить граф и таблицу переходов автомата Мура.
Составить схему алгоритма и программу, реализующую автомат Мура на языке ассемблера микропроцессора (МП) К564. Каждую команду программы сопроводить четкими комментариями, поясняющими смысл выполняемых в команде действий.
Вариант:
номер варианта: последние четыре цифры индивидуального шифра 0213.
Вариант задания — 26
Реализация автомата Мили на микросхемах серии — К564
Построение графа синтезируемого автомата Граф синтезируемого автомата Мили получается путем исключения некоторых ветвей обобщенного графа автомата, имеющего 4 внутренних состояния (рис.1). У такого графа из каждой вершины выходят 4 ветви (и столько же входят). Каждая ветвь символизирует переход автомата в другое внутреннее состояние при совместном воздействии входного сигнала и выходного сигнала обозначается их комбинацией при конкретном значении индексов.
При построении графа следует для каждой ветви, выходящей из каждой вершины, сформировать комбинацию и указать ее на графе в соответствии с порядковой нумерацией выходящих ветвей.
Вершина графа | |||||||||
Сигнал | |||||||||
Номер выходящей из вершины ветви | |||||||||
Вариант 13 | |||||||||
Рис. 1. Граф синтезируемого автомата Мили. | |||||||||
Определения количества элементов памяти Выбираем в качестве элементов памяти JK-триггеры. Базис логических элементов — произвольный.
Для данного примера видно:
— число внутренних состояний ();
— число входных сигналов ();
— число выходных сигналов ().
Находим:
— число элементов памяти ;
— число разрядов входной шины ;
— число разрядов выходной шины .
Составление таблицы переходов и выходов КА По графу автомата Мили (Рис. 1.) составим таблицу переходов и выходов. Строки таблиц отмечены входными сигналами, а столбцы — внутренними состояниями. Крайний левый столбец таблиц отмечается начальным состоянием автомата а1. Входные сигналы и состояния, отмечающие строки и столбцы таблиц, относятся к моменту времени t, т. е. отражают и. На пересечение столбца и строки в таблице переходов ставится состояние, определяемое функцией переходов. В состояние автомат переключается из состояния под действием сигнала .
В таблице выходов на пересечении столбца и строки ставится соответствующий этому переходу выходной сигнал, определяемый функцией выходов .
Кодируем автомат, ставя в соответствие каждому символическому сигналу произвольный двоичный код (число разрядов в кодах соответствует найденным r, n, m).
С учетом введенных кодов переводим таблицы выходов и переходов в двоичный алфавит.
По таблице выходов составляем логические уравнения для выходных сигналов y1 и y2. Учтем, что в каждой клетке таблицы левый бит характеризует сигнал y1, а правый — y2. Записывая уравнение «по единицам», получаем СДНФ:
Минимизируем эти функции при помощи карт Карно.
Рис 2. Карты Карно для выходных сигналов y1 и y2.
Получим эти функции после минимизации:
Составление таблиц возбуждения памяти Ка Преобразуем таблицу переходов автомата в таблицу возбуждения памяти. Т.к. в качестве элемента памяти используется синхронный Т-триггер, воспользуемся словарем Т-триггера.
Таблица 8. | |||
Q (t) | Сигналы для перехода в состояние Q (t+1) | Q (t+1) | |
Т | |||
Таблица возбуждения памяти автомата после рассмотрения переходов по всем столбцам:
x1x2 | Q1Q2 | ||||
; | |||||
; | |||||
; | ; | ||||
; | ; | ||||
По таблице возбуждения памяти составляем логические уравнения сигналов на каждом информационном входе каждого триггера. Записывая их «по единицам», получаем СДНФ:
Минимизируем уравнения при помощи карт Карно. Так как функции переходов и выходов не определены на некоторых наборах аргументов, доопределяем карты Карно на этих наборах единицами с целью проведения контуров наиболее высокого ранга. Так для Т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 | |||
Z2 | |||
Z3 | |||
Z4 | |||
Таблица 14. | ||||||||
Внутренние состояния и выходные сигналы | ||||||||
Внутреннее состояние | Биты кода | Биты кода | Выходной сигнал автомата Мили | |||||
b1 | W1 | |||||||
b2 | W2 | |||||||
b3 | W3 | |||||||
b4 | W1 | |||||||
b5 | W2 | |||||||
b6 | W4 | |||||||
b7 | W1 | |||||||
b8 | W2 | |||||||
b9 | W4 | |||||||
Переводим таблицу переходов (выходов) в двоичный алфавит.
Таблица 15. | ||||||||||
0000/ | 0001/ | 0010/ | 0011/ | 0100/ | 0101/ | 110/ | 0111/ | 1000/ | ||
; | ; | |||||||||
; | ||||||||||
; | ; | ; | ; | |||||||
; | ; | ; | ; | |||||||
Обозначим символами внутренние состояния автомата в последующем такте (,) и составляем для них по единицам логические уравнения, используя таблицу переходов (в каждой клетке таблицы левый бит характеризует сигнал, средний бит —, а правый бит —).
E1:
E2:
E3:
E4:
Рис 9. Карты Карно E1, E2, E3, E4.
Получаем минимизированные выражения:
Алгоритмы вычисления функцій Составим алгоритм для вычисления одного внутреннего состояния, скажем, E1, в качестве примера.
Текст программы Принят следующий формат написания программ на ассемблере. Каждая строка программы делится на четыре поля: поле метки, поле мнемокода, поле операндов, поле комментариев. Метка ассоциируется с 16-битным адресом ячейки памяти, в которую будет помещен первый байт отмеченной меткой команды.
В приведенной программе предполагается, что коды входных сигналов поступают в порт ввода, выходные сигналы засылаются в порт вывода, состояния сохраняются в регистре С. Байты входного сигнала и исходного внутреннего состояния предварительно объединяются в один байт данных вида 000x1x2Q1Q2. Таблицы переходов и выходов автомата Мили записываются в память так, что входной сигнал и исходное состояние с начальным адресом таблицы определяют адрес следующего состояния и выходной сигнал, из которых формируются байт очередного внутреннего состояния 00Q*1Q*2 и соответствующий этому состоянию байт выходного сигнала 0у1у2.
Совмещенная таблица переходов и выходов:
Таблица 16.
x1x2 | |||||
00/10 | 01/00 | ; | 01/01 | ||
10/00 | 01/10 | 11/01 | ; | ||
00/01 | ; | 00/00 | ; | ||
11/11 | ; | 11/11 | ; | ||
Для более ясного понимания алгоритма программной реализации перепишем совмещенную таблицу переходов и выходов (Таблица 16) в следующей форме (Таблица 17):
номер ячейки памяти от нуля | x1x2Q1Q2 | у1у2/ Q1Q2 | 16-ричные коды состояний и выходов | |
00 10 | 02h | |||
01 00 | 04h | |||
; | 00h | |||
01 01 | 05h | |||
10 00 | 08h | |||
01 10 | 06h | |||
11 01 | 0Dh | |||
; | 00h | |||
00 01 | 01h | |||
; | 00h | |||
; | 00h | |||
; | 00h | |||
11 11 | 0Fh | |||
; | 00h | |||
11 11 | 0Fh | |||
; | 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-ричные коды масок выходов 1 100 и состояний 11 | ||
ANA | B | Логическим умножением содержимого, А и младшего байта регистровой пары BC выделяем в, А выходные сигналы 000x1x200 | ||
RRC | Сдвиг содержимого аккумулятора на один разряд вправо | |||
RRC | Повторный сдвиг содержимого, А на один разряд вправо, в результате получаем байт 0 x1x2 в А | |||
MOV | PORTy, A | Вывод кода выходных сигналов из, А в порт вывода | ||
MOV | A, E | Восстанавливаем в, А считанный из таблицы байт выходов и состояний | ||
ANA | C | Логическим умножением содержимого, А и маски старшего байта регистровой пары ВС выделяем в, А состояния 00Q1Q2 | ||
MOV | C, A | Пересылка кода состояния 00Q1Q2 из, А в С | ||
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 с.: ил. — (Учебная литература для вузов).