УЗБЕКСКОЕ АГЕНТСТВО СВЯЗИ И
ИНФОРМАТИЗАЦИИ
ТАШКЕНТСКИЙ УНИВЕРСИТЕТ ИНФОРМАЦИОННЫХ ТЕХНОЛОГИЙ
Кафедра
КС и С
Методические указания
для выполнения курсовой работы по дисциплине "ИНФОРМАЦИОННЫЕ ОСНОВЫ ВЫЧИСЛИТЕЛЬНЫХ
СИСТЕМ"
Ташкент - 2008
С.К. Ганиев, А.А. Ганиев. Методическое указание для выполнения курсовой работы по дисциплине "Информационные основы вычислительных систем"./ ТУИТ. 26с. Ташкент, 2008.
Информационно – логические основы построения вычислительных систем охватывают круг вопросов, связанных с формами и системами представления информации, с логико-математическим синтезом вычислительных схем, а также схемотехникой компонентов компьютера. В методических указаниях к курсовой работе рассмотрены вопросы построения структуры управляющего автомата, реализующего конкретную операцию.
Методические указания предназначены для студентов бакалавриатуры направлений "Информатика и информационное технологии", «Безопасность информации», «Профессиональное образование» (Информатика и информационные технологии).
Напечатано по решению учебно-методического Совета ТУИТ.
(протокол №____ от ____________ 2008г.)
Рецензенты:
Доцент кафедры
"Прикладная информатика"
ТУИТ, к.т.н. Расулова С.С.
Доцент кафедры
"Автоматизация и управление"
ТГТУ, к.т.н. Абдуллаев М.М.
Ташкентский университет информационных технологий, 2008
Основной целью курсовой работы является приобретение
практических навыков по разработке граф-схемы алгоритма (ГСА) выполнения арифметических
операций и построению структуры управляющих автоматов, реализующих эти
алгоритмы.
Поставленная цель достигается путем самостоятельной
разработки студентом алгоритмов выполнения ряда микрооперации на заданной структуре
операционной части автомата, построение управляющего автомата, реализующего эти
алгоритмы на типовых логических схемах заданного базиса.
Обощенная тема курсовой работы: "Синтез
управляющего автомата устройства, реализующего заданный алгоритм выполнения арифметических
операций".
II. Задания
Задания на курсовую работу включают набор исходных
данных и ограничений для синтеза управляющего автомата. Все варианты задания сведены
в табл.1.
Строка таблицы представляет один вариант задания,
причем номер варианта определяется порядковым номером по списку группы.
Табл.1.
Варианты задания курсовой работы
|
№ |
Операции |
Код выполнения операций |
Тип элемента памяти |
Тип автомата |
|
1 |
± |
ОК |
D |
Мур |
|
2 |
х |
ПК |
RS |
Мили |
|
3 |
÷1 |
ПК |
JK |
Мур |
|
4 |
÷2 |
ПК |
D |
Мили |
|
5 |
х2 |
ПК |
JK |
Мур |
|
6 |
± |
ОК |
JK |
Мили |
|
7 |
х |
ПК |
D |
Мур |
|
8 |
х2 |
ПК |
RS |
Мили |
|
9 |
÷1 |
ПК |
D |
Мили |
|
10 |
÷2 |
ПК |
RS |
Мур |
|
11 |
± |
ДК |
T |
Мили |
|
12 |
х |
ПК |
T |
Мур |
|
13 |
÷1 |
ПК |
D |
Мили |
|
14 |
÷2 |
ПК |
RS |
Мур |
|
15 |
х2 |
ПК |
T |
Мили |
|
16 |
± |
ДК |
D |
Мур |
|
17 |
х |
ПК |
JK |
Мили |
|
18 |
х2 |
ПК |
T |
Мили |
|
19 |
÷1 |
ПК |
T |
Мур |
|
20 |
÷2 |
ПК |
JK |
Мур |
Варианты операций обозначены в табл.1. следующим
образом:
± - алгебраическое сложение/вычитание;
х – умножение обыкновенное;
х2 – умножение ускоренное (с анализом двух разрядов
множителя).
÷1 – деление с восстановлением остатка;
÷2 – деление без восстановления остатка;
ПК – прямой код;
ОК – обратный код;
ДК – дополнительный код.
III. Этапы
выполнения работы
При синтезе управляющего автомата с жесткой (схемной)
логикой можно выделить следующие этапы:
1.
Разработка
структуры операционной части автомата.
2.
Разработка
содержательной ГСА выполняемой операции.
3.
Получение
функциональной ГСА.
4.
Получение
отмеченной ГСА.
5.
Построение граф
автомата.
6.
Кодирование
состояния автомата.
7.
Составление
структурную таблицу переходов.
8.
Определение
систем логических функций для выходных сигналов и сигналов возбуждения и их совместная
минимизация.
9.
Построение
функциональной схемы управляющего автомата.
IV. Пример
синтеза управляющего автомата с жесткой (схемной) логикой
Ниже приведена реализация вышеприведенных этапов
синтеза управляющего автомата с жесткой (схемной) логикой, обеспечивающего выполнение
операций сложения (вычитания) чисел, представленных с фиксированной запятой.
При параллельном способе выполнения операции сложения
(вычитания), для представления чисел используются модифицированные коды, где
для знака отводятся два разряда (00), (11), (01) и (10). Сложение
осуществляется согласно следующему алгоритму:
- если знак операнда положителен, то операнд вступает
в операцию в прямом модифицированном коде. Если знак операнда отрицателен, то
операнд вступает в операцию в обратном модифицированном коде.
- производится сложение двоичных кодов операндов
включая знаковые разряды. При этом спадающая единица из старшего знакового разряда
передается в качестве единицы переноса в младший разряд суммы.
- если знак суммы имеет значение "00", то
это означает, что сумма имеет положительное значение и представлена в прямом
коде.
- если знак суммы имеет значение "11", то
это означает, что сумма имеет отрицательное значение и представлена в обратном
коде. Для получения прямого кода необходимо инвертировать цифровые коды суммы.
- если знак суммы "01" "10", это
означает, что результат переполняет разрядную сетку машины.
1. Разработка структуры
операционной части автомата.
Структура операционной части автомата, предназначенная
для реализации операции сложения по вышеприведенному алгоритму приведена на
рис.1
В данной структуре используется n+2 разрядный накопительный сумматор. Сумматор охвачен
цепью циклической обратной связи, по которой сигнал переноса со старшего
знакового разряда сумматора передается в его младший разряд.
Предполагается, что первое слагаемое хранится в
сумматоре. Второе слагаемое хранится в регистре. А результат формируется в
выходной шине в параллельном коде.
В операционной части автомата выполняется следующие
микрооперации:
(для операции вычитания)
В операционной части автомата используются следующие
логические условия (осведомительные сигналы)
2.
Разработка содержательной граф-схемы алгоритма
операций сложения (вычитания).
Содержательная граф-схема алгоритма операции сложения
(вычитания) приведена на рис.2.
3. Получение
функциональной ГСА.
На этапе получения функциональной ГСА операторные
вершины графа алгоритма обозначаются символами микрокоманд, а условные вершины
символами логических условий, которые вписываются во внутр соответствующих
вершин.
Для нашего примера
y5=Y1; y2y3=Y2; y1,y3=Y3; y9=Y4 SignSM=P1, SignRG=P2 
Функциональная граф-схема алгоритма операции сложения (вычитания)
приведена на рис.3.
4. Получение отмеченной
ГСА.
При синтезе управляющего автомата на базе автомата
Мили получение отмеченной ГСА производится по следующим правилам:
-
символом "а1" отмечаются вход вершины следующим за
начальным и вход конечной вершины;
-
входы всех вершин, следующих за операторными, должны быть отмечены;
-
если входы вершин отмечаются, то только одним символом;
-
входы всех вершин, за исключением конечной, отмечаются различными символами.
При синтезе управляющего автомата на базе автомата
Мура получение отмеченной ГСА производится по следующим правилам:
- символом "а1"
отмечаются начальный и конечный вершины;
- все операторные вершины
должны быть отмечены;
- различные операторные
вершины отмечаются различными символами.
На рис.4 "а" и "б" приведены
отмеченные ГСА, в случаях синтеза управляющих автоматов Мили и Мура,
соответственно:
5. Построение
графа автомата.
Граф автомата Мили строится по отмеченной ГСА
следующим образом. Проставляются вершины графа, соответствующих состояниям
автомата. Определяется дуги графа автомата выходящие из вершины аi. При этом каждой дуге графа ставится в соответствие путь точки из аi на
ГСА через единственную операторную вершину в любую точку аj, причем 
. Исключение составляют дуги, идущие к конечной или начальной
вершины.
Граф автомата Мура строится по отмеченной ГСА
следующим образом. Проставляются вершины графа, соответствующих состояниям
автомата. Каждому пути перехода 
ставится в
соответствие переход автомата из состояния аi в
состояние 
под воздействием входного сигнала P(ai, aj),
в пути перехода aiaj – переход из ai в aj под воздействием сигнала единицы.
На рис.5 "а" и "б" приведены графы
автоматов Мили и Мура, соответственно.
6. Кодирование
состояния автомата.
Кодирование состояния автомата заключается в
установлении взаимно-однозначного соответствия между множеством состояний автомата
и множеством элемента памяти. Для простоты ограничимся использованием в качестве
элементов памяти RS – триггеров, которые будем
обозначать Т1,…,Тr.
Переход автомата из одного состояния в другое
осуществляется за счет изменения состояний элементов памяти. Так, если автомат
переходит из состояния с кодом 0101 в состояние с кодом 1001, то это означает,
что триггер T1 переходит из состояния "0" в состояние
"1" триггер T2 – из состояния "1" в состояние
"0", а состояние триггеров Т3 и Т4 не
изменяются.
В нашем примере для автомата Мили имеем четыре
состояний, следовательно достаточно иметь два триггера, т.е.
А для автомата Мура имеем шесть состояний,
следовательно достаточно иметь три триггера.
7. Составление
структурных таблиц переходов.
При использовании графов для задания автоматов с
большим числом состояний и переходов наглядность теряется, поэтому оказывается
предпочтительным задавать эти графы в виде структурных таблиц. Структурные
таблицы переходов бывают прямые и обратные. В прямой структурной таблице
последовательно перечисляются все переходы сначала из первого состояния, затем
из второго и т.д. В обратной структурной таблице сначала записываются все
переходы в первое состояние, затем во второе и т.д.
Очевидно, что структурную таблицу переходов автомата
(прямую и обратную) целесообразно составлять непосредственно по отмеченной ГСА,
записывая в нее все пути переходов, т.е. не нужно предварительно рисовать граф
автомата, поскольку эта таблица и есть граф, заданный в виде списка.
В таблицах 2 и 3 приведены обратные структурные
таблицы автоматов Мили и Мура, соответственно.
Табл.2.
|
Исходное состояние |
Код исходного состояния |
Состояние перехода |
Код состояния перехода |
Входные сигналы |
Выходные сигналы |
Сигналы возбуждения |
|
а3 а3 а4 а4 |
01 01 11 11 |
а1 |
00 |
|
Y4 - Y4 - |
R2 R2 R1 R2 R1 R2 |
|
a1 |
00 |
a2 |
10 |
P1 |
Y1 |
S1 |
|
а1 a1 а2 а2 |
00 00 10 10 |
a3 |
01 |
|
Y2 Y3 Y2 Y3 |
S2 S2 R1 S2 R1 S2 |
|
а3 |
00 |
a4 |
11 |
P1 |
Y1 |
S1 |
Табл.3.
|
Исходное состояние |
Код исходного состояния |
Состояние перехода |
Код состояния перехода |
Входные сигналы |
Сигналы возбуждения |
|
а3 а4 а5 а6 |
010 110 001 101 |
а1(-) |
000 000 000 000 |
1 |
R2 R1R2 R3 R1 R3 |
|
a1 |
000 |
a2(Y1) |
100 |
P1 |
S1 |
|
a1 а2 |
000 100 |
a3(Y2) |
010 |
|
S2 R1 S2 |
|
a1 a2 |
000 100 |
a4(Y3) |
110 |
|
S1 S2 S2 |
|
a3 a4 |
010 110 |
a5(Y1) |
001 |
P1
|
R2 S3 R1R2 S3 |
|
a3 a4 a5 |
010 110 001 |
a6(Y4) |
101 |
|
S1R2 S3 R2 S3 S1 |
Обратная структурная таблица автомата Мура будет иметь
на один столбец меньше, если выходной сигнал записывать рядом с состоянием перехода.
8. Определение
систем логических функций для выходных сигналов и сигналов возбуждения и их
совместная минимизация.
Системы логических функций для выходных сигналов и
сигналов возбуждения для таблицы 2 имеют следующий вид:
(1)
В результате совместной минимизации данных систем
логических функций получим:
(2)
Системы логических функций для выходных сигналов и
сигналов возбуждения для таблицы 3 имеют следующий вид:
(3)
В результате минимизации данных систем логических
функций получим:
(4)
9. Построение
функциональной схемы управляющего автомата.
Зависимости 2 и 4 являются математическими моделями
комбинационных частей синтезируемых автоматов Мили и Мура, соответственно.
На рис.6 и 7 приведены функциональные схемы
микропрограммных автоматов Мили и Мура, обеспечивающих выполнение операций
сложения и вычитания чисел, представленных с фиксированной запятой,
соответственно.
При включении вычислительного устройства триггеры
автомата устанавливаются в произвольное состояние. Для перевода автомата в
начальное состояние используется сигнал "ПУСК".
V. Содержание
пояснительной записки
Пояснительная
записка к курсовой работе должна включать следующую информацию.
1. Титульный лист. (Приложение 1)
2. Задание на синтез управляющего автомата. (Приложение
2)
3. Алгоритм выполняемой операций.
4. Структурная схема операционной части управляющего
автомата.
5. Назначение управляющих и осведомительных сигналов.
6. Содержательная ГСА выполняемой операции.
7. Функциональная ГСА выполняемой операции.
8. Отмеченная ГСА выполняемой операции.
9. Граф управляющего автомата.
10. Кодирование состояния управляющего автомата.
11. Обратная структурная таблица переходов.
12. Система логических функций для выходных сигналов и
сигналов возбуждения и их совместная минимизация.
13. Функциональная схема управляющего автомата.
14. Заключение.
15. Список использованной литературы.
Литература
1.
А.П.Жмакин.
Архитектура ЭВМ. Уч.пособие. Санкт Петербург, БХВ-Петербург, 2006.
2.
Б.Я. Цилькер,
С.А., Орлов. Организация ЭВМ и систем: Учебник для вузов. – СПб: Питер,2004.
3.
С.К.Ғаниев,
М.М.Каримов, Н.М.Мамбетов. "Ҳисоблаш системаларининг информацион асослари:
Олий ўқув юрт.талаб. учун дарслик. – Тошкент Давлат техника университети,
2002.
4.
А.Я. Савельев.
Основы информатики. Учеб. для ВУЗов- М.: Изд-во МГТУ им А.Э. Баумана, 2001.