Реферат: Теория автоматов (Разработать автомата для сложения в коде 8421 в обратном коде в формате с фиксированной запятой)
Министерствообразования РФ
УфимскийГосударственный Авиационный Технический Университет
КафедраВычислительной Техники и Защиты Информации
ТЕОРИЯ АВТОМАТОВ
КУРСОВАЯ
Выполнил: ст. гр. ВМ-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 )
<img src="/cache/referats/8091/image001.gif" v:shapes="_x0000_s1090">
начало
<img src="/cache/referats/8091/image002.gif" v:shapes="_x0000_s1027"><div v:shape="_x0000_s1642">Содержательный граф автомата
РгF := <span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol">ù
[ РгА(0) <span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol">Å РгВ(0)]<span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type: symbol;mso-symbol-font-family:Symbol">Ù <span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-char-type:symbol;mso-symbol-font-family:Symbol">Ù[ РгА(0) <span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol">Å СМ(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) <span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol">Ú
СМ(1) <span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol">Ù [СМ(2) <span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol">Ú СМ(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
<img src="/cache/referats/8091/image003.gif" v:shapes="_x0000_s1082 _x0000_s1083 _x0000_s1084 _x0000_s1086 _x0000_s1039 _x0000_s1028 _x0000_s1030 _x0000_s1035 _x0000_s1036 _x0000_s1037 _x0000_s1038 _x0000_s1040 _x0000_s1042 _x0000_s1063 _x0000_s1064 _x0000_s1067 _x0000_s1070 _x0000_s1081 _x0000_s1085 _x0000_s1087 _x0000_s1636 _x0000_s1637 _x0000_s1638 _x0000_s1639 _x0000_s1640 _x0000_s1641 _x0000_s1644 _x0000_s1645 _x0000_s1646 _x0000_s1647 _x0000_s1648 _x0000_s1649 _x0000_s1650 _x0000_s1651 _x0000_s1652 _x0000_s1653 _x0000_s1654 _x0000_s1655 _x0000_s1656"> <img src="/cache/referats/8091/image004.gif" v:shapes="_x0000_s1043 _x0000_s1633 _x0000_s1634 _x0000_s1635">Лист
Изм.
Лист
№ докум.
Подпись
Дата
конец
<img src="/cache/referats/8091/image005.gif" v:shapes="_x0000_s1044">Раздел 2
Разработка ГСА ифункциональной схемы операционной части автомата
2.1<span Times New Roman"">
В соответствии сзаданием разрядность операндов 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<span Times New Roman"">
Обозначение
микрооперации
Микрооперация
Обозначение логич. условия
Логическое условие
У1
РгА := A(0).A
Х1
СМ(0) <span Times New Roman";mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol; mso-symbol-font-family:Symbol">Ú
СМ(1) <span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-char-type:symbol;mso-symbol-font-family:Symbol">Ù [ СМ(2) <span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">Ú СМ(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 :=<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-char-type:symbol;mso-symbol-font-family: Symbol">ù
[ РгА(0) <span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">Å РгВ(0)]<span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">Ù <span Times New Roman";mso-hansi-font-family:«Times New Roman»; mso-char-type:symbol;mso-symbol-font-family:Symbol">Ù [ РгА(0) <span Times New Roman";mso-hansi-font-family: «Times New Roman»;mso-char-type:symbol;mso-symbol-font-family:Symbol">Å СМ(18)]( таблица 3 )
<img src="/cache/referats/8091/image006.gif" v:shapes="_x0000_s1229">
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
<img src="/cache/referats/8091/image007.gif" v:shapes="_x0000_s1196 _x0000_s1170 _x0000_s1171 _x0000_s1172 _x0000_s1173 _x0000_s1174 _x0000_s1175 _x0000_s1176 _x0000_s1177 _x0000_s1178 _x0000_s1180 _x0000_s1181 _x0000_s1182 _x0000_s1183 _x0000_s1184 _x0000_s1185 _x0000_s1188 _x0000_s1189 _x0000_s1191 _x0000_s1192 _x0000_s1193 _x0000_s1195 _x0000_s1197 _x0000_s1198 _x0000_s1199 _x0000_s1200 _x0000_s1201 _x0000_s1202 _x0000_s1203 _x0000_s1204 _x0000_s1205 _x0000_s1206 _x0000_s1207 _x0000_s1208">Лист
Изм.
Лист
№ докум.
Подпись
Дата
Раздел 3
Разработка логическойсхемы управляющей части автомата
3.1 Составление таблицы переходов – выходов:
Исходное сосотояние
Входной набор
Следующее состояние
A1
В
A2
A2
-
A3
A3
X1
A4
<img src="/cache/referats/8091/image008.gif" v:shapes="_x0000_s1219"><img src="/cache/referats/8091/image008.gif" v:shapes="_x0000_s1221">3
X1X2
A5
<img src="/cache/referats/8091/image009.gif" v:shapes="_x0000_s1220">3
X1X2
A6
<img src="/cache/referats/8091/image009.gif" v:shapes="_x0000_s1218">4
X2
A5
A4
X2
A6
A5
-
A3
A6
X3
A7
<img src="/cache/referats/8091/image010.gif" v:shapes="_x0000_s1216">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<span Times New Roman"">
По графу автоматаМура строится структурная таблица автомата
Исходное сосотояние
Код исх. состояния
Следующее состояние
Код след. состояния
Входной набор
Сигналы возбуждения
D1
D2
D3
A1
111
A2
110
В
1
1
A2
110
A3
000
-
A3
000
A4
001
X1
1
<img src="/cache/referats/8091/image011.gif" v:shapes="_x0000_s1226"><img src="/cache/referats/8091/image008.gif" v:shapes="_x0000_s1224"><img src="/cache/referats/8091/image012.gif" v:shapes="_x0000_s1213">3
000
A5
100
X1X2
1
<img src="/cache/referats/8091/image013.gif" v:shapes="_x0000_s1225">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
<img src="/cache/referats/8091/image009.gif" v:shapes="_x0000_s1212">6
010
A8
011
X3
1
1
A7
101
A3
000
-
A8
011
A1
111
-
1
1
1
Переведем кодировку состояний и соответственно функцийавтомата Мура в базис “И-НЕ”
<img src="/cache/referats/8091/image014.gif" v:shapes="_x0000_s1658"><img src="/cache/referats/8091/image015.gif" v:shapes="_x0000_s1230">1= T1T2T3= T1|T2|T3
<img src="/cache/referats/8091/image016.gif" v:shapes="_x0000_s1240"><img src="/cache/referats/8091/image017.gif" v:shapes="_x0000_s1236"><img src="/cache/referats/8091/image018.gif" v:shapes="_x0000_s1231">2= У1 = У2= У3= У4 = T1T2T3 = T1|T2|T3
<img src="/cache/referats/8091/image019.gif" v:shapes="_x0000_s1248"><img src="/cache/referats/8091/image020.gif" v:shapes="_x0000_s1238"><img src="/cache/referats/8091/image008.gif" v:shapes="_x0000_s1239"><img src="/cache/referats/8091/image018.gif" v:shapes="_x0000_s1237"><img src="/cache/referats/8091/image008.gif" v:shapes="_x0000_s1243"><img src="/cache/referats/8091/image021.gif" v:shapes="_x0000_s1242"><img src="/cache/referats/8091/image008.gif" v:shapes="_x0000_s1241">3= У5= У6= T1T2T3= T1|T2|T3
<img src="/cache/referats/8091/image022.gif" v:shapes="_x0000_s1251"><img src="/cache/referats/8091/image008.gif" v:shapes="_x0000_s1247"><img src="/cache/referats/8091/image021.gif" v:shapes="_x0000_s1246"><img src="/cache/referats/8091/image010.gif" v:shapes="_x0000_s1244"><img src="/cache/referats/8091/image008.gif" v:shapes="_x0000_s1245">4= У7= T1T2T3 = T1|T2|T3
<img src="/cache/referats/8091/image023.gif" v:shapes="_x0000_s1260"><img src="/cache/referats/8091/image020.gif" v:shapes="_x0000_s1252"><img src="/cache/referats/8091/image010.gif" v:shapes="_x0000_s1253"><img src="/cache/referats/8091/image008.gif" v:shapes="_x0000_s1250"><img src="/cache/referats/8091/image017.gif" v:shapes="_x0000_s1249">5= У8= У9= У10= T1T2T3 = T1|T2|T3
<img src="/cache/referats/8091/image024.gif" v:shapes="_x0000_s1263"><img src="/cache/referats/8091/image021.gif" v:shapes="_x0000_s1256"><img src="/cache/referats/8091/image017.gif" v:shapes="_x0000_s1254"><img src="/cache/referats/8091/image021.gif" v:shapes="_x0000_s1259"><img src="/cache/referats/8091/image021.gif" v:shapes="_x0000_s1257">6= У11= У12 = T1T2T3 = T1|T2|T3
<img src="/cache/referats/8091/image025.gif" v:shapes="_x0000_s1269"><img src="/cache/referats/8091/image008.gif" v:shapes="_x0000_s1262"><img src="/cache/referats/8091/image008.gif" v:shapes="_x0000_s1261">7= У13= У14= У15= У16 = T1T2T3= T1|T2|T3
<img src="/cache/referats/8091/image021.gif" v:shapes="_x0000_s1268"><img src="/cache/referats/8091/image018.gif" v:shapes="_x0000_s1266">8= У17= T1T2T3 = T1|T2|T3
Возможные функции возбуждения триггеров
Устойчивая работауправляющего автомата обеспечивается работой синхронных статических триггеров.
<img src="/cache/referats/8091/image026.gif" v:shapes="_x0000_s1547">
Функциональная схемаоперационного устройства
РгВ
РгA
См
1
&
1
1
<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-ansi-language:EN-US;mso-char-type: symbol;mso-symbol-font-family:Symbol">Å
<span Times New Roman"; mso-hansi-font-family:«Times New Roman»;mso-ansi-language:EN-US;mso-char-type: symbol;mso-symbol-font-family:Symbol">Å
&
РгF
СЧ
+
У1
У8
У5
У3
У7
У10
У3
У11
У13
У15
У12
У4
У6
У4
У2
У9
У14
X3
X2
X1
<img src="/cache/referats/8091/image027.gif" v:shapes="_x0000_s1297 _x0000_s1281 _x0000_s1284 _x0000_s1285 _x0000_s1286 _x0000_s1301 _x0000_s1282 _x0000_s1287 _x0000_s1288 _x0000_s1289 _x0000_s1302 _x0000_s1303 _x0000_s1304 _x0000_s1305 _x0000_s1306 _x0000_s1307 _x0000_s1308 _x0000_s1309 _x0000_s1283 _x0000_s1290 _x0000_s1291 _x0000_s1292 _x0000_s1293 _x0000_s1294 _x0000_s1295 _x0000_s1296 _x0000_s1310 _x0000_s1311 _x0000_s1313 _x0000_s1315 _x0000_s1316 _x0000_s1317 _x0000_s1318 _x0000_s1319 _x0000_s1320 _x0000_s1321 _x0000_s1322 _x0000_s1323 _x0000_s1324 _x0000_s1325 _x0000_s1345 _x0000_s1346 _x0000_s1347 _x0000_s1348 _x0000_s1351 _x0000_s1352 _x0000_s1353 _x0000_s1354 _x0000_s1355 _x0000_s1356 _x0000_s1357 _x0000_s1359 _x0000_s1360 _x0000_s1361 _x0000_s1362 _x0000_s1363 _x0000_s1364 _x0000_s1365 _x0000_s1366 _x0000_s1367 _x0000_s1368 _x0000_s1369 _x0000_s1370 _x0000_s1372 _x0000_s1373 _x0000_s1374 _x0000_s1375 _x0000_s1376 _x0000_s1377 _x0000_s1378 _x0000_s1379 _x0000_s1380 _x0000_s1381 _x0000_s1382 _x0000_s1383 _x0000_s1384 _x0000_s1387 _x0000_s1388 _x0000_s1389 _x0000_s1391 _x0000_s1392 _x0000_s1514 _x0000_s1515 _x0000_s1516 _x0000_s1517 _x0000_s1518 _x0000_s1520 _x0000_s1524 _x0000_s1525 _x0000_s1526 _x0000_s1527 _x0000_s1528 _x0000_s1529 _x0000_s1530 _x0000_s1531 _x0000_s1532 _x0000_s1533 _x0000_s1534 _x0000_s1535 _x0000_s1536 _x0000_s1537 _x0000_s1538 _x0000_s1539 _x0000_s1540 _x0000_s1541 _x0000_s1542 _x0000_s1543 _x0000_s1544 _x0000_s1545 _x0000_s1546">Лист
Изм.
Лист
№ докум.
Подпись
Дата