Министерствообразования РФ
УфимскийГосударственный Авиационный Технический Университет
КафедраВычислительной Техники и Защиты Информации
ТЕОРИЯ АВТОМАТОВ
КУРСОВАЯ
Выполнил: ст. гр. ВМ-311
Герон С. В.
Проверил: д. т. н. Фрид А. С.
Г. Уфа 2001 г.
Задание
Разработать алгоритм сложения в коде 8421 в обратном коде вформате с фиксированной запятой:
разрядность операндов n = 17;
математическая модель – автомат Мура;
элементный базис “И – НЕ”;
минимизацию комбинационной схемы производить аналитическимметодом;
в качестве элементов памяти использовать D – триггер;Построить алгоритм выполнения операции. Разработать функциональную схему операционного устройства. Синтезировать логическую схему микропрограммного автомата. Построить ГСА, граф автомата, таблицу переходов- выходов. Построить логическую схему автомата в заданном базисе с заданным типом триггера.
Раздел 1
Разработка машинногоалгоритма выполнения операции.
Построение алгоритмавыполнения операции.
Шаг 1. Заносим в РгА значение первого слагаемогоотводя 2 разряда под знак. В РгВ-значение второго слагаемого отводя 2 разрядапод знак. Инициализируем сумматор нулем. Инициализируем счетчик четверкой.
Шаг 2. Суммируем старшие четыре разряда регистровРгА и РгВ и младшие 5 разрядов сумматора, результат заносим в младшие 5разрядов сумматора. Уменьшаем содержимое счетчика на 1.
Шаг 3. Проверка: нужноликорректировать получившуюся тераду. Если нужно, то прибавляем 6.
Шаг 4. Проверка: все ли тетрады обработаны. Еслисодержимое счетчика равно 0, то перейти к шагу 6.
Шаг 5. Сдвигаем мантиссу регистров РгА, РгВ и младшие 17 разряда сумматора на 4 вправо. Переходим к шагу 2.
Шаг 6. Приравниваем мантиссе регистра РгА значениеразрядов 1-16 сумматора. Суммируем 1-й разряд регистров РгА и РгВ и 0-й разрядсумматора. Записываем результат в старшие два разряда сумматора.
Шаг 7. Проверка: есть ли еденица переполнения. Еслизначение разряда 17 сумматора равно нулю, то переходим к шагу 9.
Шаг 8. Присваиваем разряду 1 регистра РгА значениеразряда 18 сумматора ( знак получившегося числа ). Сбрасываем сумматор.Записываем в счётчик четыре. В старшие 17 разрядов регистра РгВ записываемеденицу. Переходим к шагу 2.
Шаг 9. Проверка: если есть преполнение выбрасываемфлаг РгF.
Пример выполнения операции приведен в таблице 1.
А8421= 1.0001 0111 0010 0100
В8421= 1.1000 0101 0100 0011
А8421+В8421 = 1.0000 00100110 1000
СМ
РгА
РгВ
Примечание
0 0000 0000 0000 0000 00
+0 0100
+0 0011
+0 0000
=0 0111 0000 0000 0000 00
0 0000 0111 0000 0000 00
+0 0010
+0 0100
+0 0000
=0 0110 0111 0000 0000 00
0 0000 0110 0111 0000 00
+0 0111
+0 0101
+0 0000
=0 1100 0110 0111 0000 00
0 0000 1100 0110 0111 00
+0 0001
+0 1000
+0 0000
=0 1001 1100 0110 0111 00
+ 1
+ 1
+ 0
=0 1001 1100 0110 0111 10
0 00000000 0000 000010
+0 0111
+0 0001
+0 0000
=0 1000 0000 0000 0000 10
0 0000 1000 0000 0000 10
+0 0110
+0 0000
+0 0000
=0 0110 1000 0000 0000 10
0 0000 0110 1000 0000 10
+0 1100
+0 0000
+0 0000
=0 1100 0110 1000 0000 10
+0 0110
=1 0010 0110 1000 0000 10
0 0001 0010 0110 1000 10
+0 1001
+0 0000
+0 0000
=0 1010 0010 0110 1000 10
+0 0110
=1 0000 0010 0110 1000 00
+ 0
+ 0
+ 1
=1 0000 0010 0110 1000 01
11 0001 0111 0010 0100
11 0000 0001 0111 0010
11 0000 0000 0001 0111
11 0000 0000 0000 0001
11 1001 1100 0110 0111
101001 1100 0110 0111
100000 1001 1100 0110
100000 0000 1001 1100
100000 0000 0000 1001
100000 0010 0110 1000
11 1000 0101 0100 0011
11 0000 1000 0101 0100
11 0000 0000 1000 0101
11 0000 0000 0000 1000
10 0000 0000 0000 0001
10 0000 0000 0000 0000
10 0000 0000 0000 0000
10 0000 0000 0000 0000
РгА:=SgA.А; РгВ:=SgB.В;
СМ(0:4):=РгА(14:17)+ РгВ(14:17)+СМ(0:4);
[СМ(0:16)];[РгА(2:17)];[РгВ(2:17)];
СМ(0:4):=РгА(14:17)+ РгВ(14:17)+СМ(0:4);
[СМ(0:16)];[РгА(2:17)];[РгВ(2:17)];
СМ(0:4):=РгА(14:17)+ РгВ(14:17)+СМ(0:4);
[СМ(0:16)];[РгА(2:17)];[РгВ(2:17)];
СМ(0:4):=РгА(14:17)+ РгВ(14:17)+СМ(0:4);
РгА(2:17):=СМ(1:16);
СМ(17:18):=РгА(1)+РгВ(1)+СМ(0);
РгА(1):=СМ(18); СМ(0:16):=0;
РгВ(1:17):=1;
СМ(0:4):=РгА(14:17)+ РгВ(14:17)+СМ(0:4);
[СМ(0:16)];[РгА(2:17)];[РгВ(2:17)];
СМ(0:4):=РгА(14:17)+ РгВ(14:17)+СМ(0:4);
[СМ(0:16)];[РгА(2:17)];[РгВ(2:17)];
СМ(0:4):=РгА(14:17)+ РгВ(14:17)+СМ(0:4);
СМ(0:4):=СМ(0:4)+6;
[СМ(0:16)];[РгА(2:17)];[РгВ(2:17)];
СМ(0:4):=РгА(14:17)+ РгВ(14:17)+СМ(0:4);
СМ(0:4):=СМ(0:4)+6;
РгА(2:17):=СМ(1:16);
СМ(17:18):=РгА(1)+РгВ(1)+СМ(0);
РгF:=0;
Конец.
Ответ:
Мантисса = СМ(1:16);
Знак = СМ(18);
1.0000 0010 0110 1000
( таблица 1 )
начало
Содержательный граф автомата
РгF := ù[ РгА(0) Å РгВ(0)]Ù Ù[ РгА(0) Å СМ(18)];
1
1
РгА(2:17) := СМ(1:16);
СМ(17:18) := РгА(1) + + РгВ(1) + СМ(0);
СМ(0:4) := РгА(14:17) + + РгА(14:17) + СМ(0:4); СЧ := СЧ — 1;
РгА := A(0).A;
РгВ := B(0).B;
СМ(0:16) := 0; СЧ := 410;
СМ(0) Ú СМ(1) Ù [СМ(2) Ú СМ(3)]
СМ(0:4) := СМ(0:4) + 610;
СЧ = 0
РгА(2:17) := 0000.РгА(2:13);
РгВ(2:17) := 0000.РгВ(2:13);
СМ(0:16) := 0000.СМ(0:12);
РгА(1) := СМ(18); СМ(0:16) := 0;
СЧ := 410; РгВ(1:17) := 1;
СМ(17)
1
Лист
Изм.
Лист
№ докум.
Подпись
Дата
конец
Раздел 2
Разработка ГСА ифункциональной схемы операционной части автомата
2.1
В соответствии сзаданием разрядность операндов n= 17. Так как алгоритм предусматривает еще один разряд под знак то длинаразрядной сетки регистров РгА и РгВ равна 18. Так как результат суммирования,как и операнды, имеет разрядность 17 и алгоритмом предусматривается еще 2разряда для определения переполнения, то длина разрядной сетки сумматора равна19.
Описание словпредставлено в таблице 2.
Тип
Слово
Пояснение
IL
А(0:17)
первое слагаемое
IL
В(0:17)
второе слагаемое
LO
СМ(0:18)
Сумматор
O
F
флаг переполнения
L
CЧ(0:1)
Счётчик
( таблица 2)
2.2
Обозначение
микрооперации
Микрооперация
Обозначение логич. условия
Логическое условие
У1
РгА := A(0).A
Х1
СМ(0) Ú СМ(1) Ù [ СМ(2) Ú СМ(3) ]
У2
РгВ := B(0).B
Х2
СЧ = 0
У3
СМ(0:16) := 0
Х3
СМ(17)
У4
СЧ := 410
У5
СМ(0:4) := РгА(14:17) + РгА(14:17) + СМ(0:4)
У6
СЧ := СЧ — 1
У7
СМ(0:4) := СМ(0:4) + 610
У8
РгА(2:17) := 0000.РгА(2:13)
У9
РгВ(2:17) := 0000.РгВ(2:13)
У10
СМ(0:16) := 0000.СМ(0:12)
У11
РгА(2:17) := СМ(1:16)
У12
СМ(17:18) := РгА(1) + РгВ(1) + СМ(0)
У13
РгА(1) := СМ(18)
У14
РгВ(1:17) := 110
У15
РгF :=ù[ РгА(0) Å РгВ(0)]Ù Ù [ РгА(0) Å СМ(18)]
( таблица 3 )
B
A1/-
A2/ У1, У2, У3, У4
A6/ У11, У12
A8/ У15
A7/ У13, У3, У4, У14
A3/ У5, У6
A4/ У7
A5/ У8, У9, У10
X2
X2
X1
X3
X3
X1X2
X1X2
Лист
Изм.
Лист
№ докум.
Подпись
Дата
Раздел 3
Разработка логическойсхемы управляющей части автомата
3.1 Составление таблицы переходов – выходов:
Исходное сосотояние
Входной набор
Следующее состояние
A1
В
A2
A2
-
A3
A3
X1
A4
3
X1X2
A5
3
X1X2
A6
4
X2
A5
A4
X2
A6
A5
-
A3
A6
X3
A7
6
X3
A8
A7
-
A3
A8
-
A1
3.2 Кодировкасостояний автомата:
A1= 111
A2= 110
A3= 000
A4= 001
A5= 100
A6= 010
A7= 101
A8= 011
3.3
По графу автоматаМура строится структурная таблица автомата
Исходное сосотояние
Код исх. состояния
Следующее состояние
Код след. состояния
Входной набор
Сигналы возбуждения
D1
D2
D3
A1
111
A2
110
В
1
1
A2
110
A3
000
-
A3
000
A4
001
X1
1
3
000
A5
100
X1X2
1
3
000
A6
010
X1X2
1
A4
001
A5
100
X2
1
A4
001
A6
010
X2
1
A5
100
A3
000
-
A6
010
A7
101
X3
1
1
6
010
A8
011
X3
1
1
A7
101
A3
000
-
A8
011
A1
111
-
1
1
1
Переведем кодировку состояний и соответственно функцийавтомата Мура в базис “И-НЕ”
1= T1T2T3= T1|T2|T3
2= У1 = У2= У3= У4 = T1T2T3 = T1|T2|T3
3= У5= У6= T1T2T3= T1|T2|T3
4= У7= T1T2T3 = T1|T2|T3
5= У8= У9= У10= T1T2T3 = T1|T2|T3
6= У11= У12 = T1T2T3 = T1|T2|T3
7= У13= У14= У15= У16 = T1T2T3= T1|T2|T3
8= У17= T1T2T3 = T1|T2|T3
Возможные функции возбуждения триггеров
Устойчивая работауправляющего автомата обеспечивается работой синхронных статических триггеров.
Функциональная схемаоперационного устройства
РгВ
РгA
См
1
&
1
1
Å
Å
&
РгF
СЧ
+
У1
У8
У5
У3
У7
У10
У3
У11
У13
У15
У12
У4
У6
У4
У2
У9
У14
X3
X2
X1
Лист
Изм.
Лист
№ докум.
Подпись
Дата