Проектирование элементов ЭВУ
Министерство
общего и профессионального образования
Российской
Федерации
НОВОСИБИРСКИЙ
ГОСУДАРСТВЕННЫЙ
ТЕХНИЧЕСКИЙ
УНИВЕРСИТЕТ
Кафедра
РП и РПУ
Проектирование
элементов ЭВУ
Пояснительная
записка к курсовой работе по дисциплине
“Цифровые
устройства и микропроцессоры”
Новосибирск
Оглавление
Задание
на курсовую работу
Построение
графа синтезируемого автомата
Определение
количества элементов памяти
Составление
таблицы переходов и выходов КА
Составление
таблиц возбуждения памяти КА
Синтез
комбинационной части Ка
Переход
от исходного автомата Мили к эквивалентному автомату Мура
Кодирование
автомата Мура
Алгоритмы
вычисления функций
Текст
программы
Список
используемой литературы
конечный автомат граф алгоритм
Задание на курсовую работу
Синтез конечного автомата (КА) Мили:
Построить граф конечного автомата для заданного
варианта;
Определить количество элементов памяти
составить таблицы перехода и выходов КА;
составить таблицу возбуждения элементов памяти
(Т -триггер);
синтезировать комбинационную часть КА;
реализовать КА на микросхемах одной из серии:
К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).
С учетом введенных кодов переводим
таблицы выходов и переходов в двоичный алфавит.
По таблице выходов l составляем логические
уравнения для выходных сигналов 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
|
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:
:
E3:
:
Рис 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 с.: ил. - (Учебная литература для
вузов).