допущена к защите студентка группы ЭВМ 3-2

Кафедра вычислительных машин, комплексов, систем и сетей.

Курсовая работа

Защищена с оценкой

(подпись, дата)

КУРСОВАЯ РАБОТА

По дисциплине “Теория автоматов”

Вариант № 13

Тема: Блок управления для выполнения

операций сложения и вычитания в АЛУ

Курсовая работа Выполнила

допущена к защите студентка группы ЭВМ 3-2

Легалова О. А.

(подпись, дата) (Ф. И. О.)

Руководитель Рощин А. Г.

(Ф. И. О.)

Содержание

1. Введение……………………………………………………………………...

2. Задание……………………………………………………………………….

3. Общая последовательность сложения и вычитания чисел с ФТ………….

4. Структурная схема АЛУ…………………………………………………….

5. Алгоритм сложения и вычитания чисел в АЛУ……………………………

6. Разработка функциональной схемы блока управления…………………...

6.1 Общая последовательность разработки……………………………….

6.2 Формализация задания……………………………………………….…

6.3 Выбор типа автомата…………………………………………………...

6.4 Разметка схемы алгоритма ……………………………………………

6.5 Составление таблиц переходов и выходов……………………………

6.6 Кодирование состояний………………………………………………..

6.7 Составление кодированной таблицы переходов и выходов…………

6.8 Выбор типа триггера……………………………………………………

6.9 Преобразование таблицы переходов в таблицу функций

возбуждения триггеров…………………………………………………

6.10 Запись функций возбуждения и функций выходов в СДНФ………..

6.11 Минимизация функций возбуждения и функций выходов………….

6.12 Выбор типа логических элементов……………………………………

6.13 Преобразование функций переходов и функций выходов…………..

6.14 Построение функциональной схемы блока управления……………..

6.15 Проверка правильности работы блока управления……...…………..

7. Заключение……………………………………………………………..…….

8. Литература…………………………………………………………………....

1. Введение

В большинстве устройств ЭВМ можно выделить два основных блока: операционный блок и блок управления. Типовая структура устройства ЭВМ представлена на рисунке 1.

… …

	Код операции

Рисунок 1

В операционном блоке реализуются функции, для которых предназначено устройство. Такими функциями могут быть арифметические или логические операции над данными, хранение данных, преобразование формы представления данных и т.д. На вход операционного блока поступают операнды, на его выходе формируются результаты выполнения операции. Кроме этого, операционный блок может выдавать признаки операндов, промежуточных или окончательных результатов. Такими признаками могут быть, например, знаки операндов, значение очередного разряда множителя, знак остатка при делении и т.д.

Операции в операционном блоке выполняются под воздействием управляющих сигналов, которые формируются в блоке управления. На вход блока управления подается код операции, который задает тип операции, выполняемой в операционном блоке. Синтез блоков управления может осуществляться различными методами. В данной работе рассматривается синтез блока управления, реализованного в виде автомата с памятью.

2. Задание

Задание: Разработать схему блока управления в АЛУ, выполняющего операции сложения и вычитания чисел с фиксированной точкой.

Исходные данные: Тип автомата – автомат Мура.

Тип триггеров – D-триггеры и T-триггеры.

Тип логических элементов – И-НЕ.

3. Общая последовательность сложения и вычитания чисел с ФТ

При сложении определяется сумма С = А + В, где:

А, В - слагаемые;

С – сумма.

При вычитании определяется разность С=А – В, где:

А - уменьшаемое;

В – вычитаемое;

С – разность.

Перед выполнением операции числа записаны в оперативной памяти в прямом коде. Для выполнения операции числа должны быть считаны из памяти и переданы в АЛУ. Так как операции сложения и вычитания проводятся с учетом знака, то числа представляются в дополнительном коде. При сложении в дополнительном коде представляются оба слагаемых, если они отрицательны. При вычитании в дополнительном коде представляется уменьшаемое, если оно отрицательно, а также вычитаемое, если оно положительно. В остальных случаях числа представляются в прямом коде. Сложение и вычитание выполняются в сумматоре, на выходе которого формируется результат операции сложения или вычитания.

Полученный результат может быть отрицательный, в этом случае он представлен в дополнительном коде. Перед записью результата в оперативную память результат преобразуется в прямой код. Кроме результата с помощью специальных схем определяются признаки результата.

4. Структурная схема АЛУ

Структурная схема АЛУ строится в соответствии с общей последовательностью операции сложения и вычитания. АЛУ имеет типовую структуру, представленную на рисунке 2.

Шина данных

Сигнал знак А

начала

операции

знак В

ПК ОК ПК ОК

Сигнал

готов-

ности

Признаки результата

Рисунок 2

Для выполнения каждого действия в операционном блоке АЛУ должны быть предусмотрены соответствующие узлы. Так для хранения исходных чисел (А и В) на время выполнения операции в состав АЛУ должны входить два регистра, Для сложения или вычитания чисел в операционном блоке должен быть сумматор. Обычно сумматор выполняется в виде комбинационной схемы, поэтому для фиксации результата операции он должен иметь регистр сумматора.

Для определения признака результата должны использоваться схемы, которые объединяются в общую схему формирования признаков результата.

Соединив основные узлы операционного блока между собой информационными связями,

а также операционный блок и блок управления управляющими связями, получим структурную схему АЛУ, представленную на рисунке 2.

5. Алгоритм сложения и вычитания чисел в АЛУ

Алгоритм сложения и вычитания составляется в соответствии с общей последовательностью сложения и вычитания и структурной схемой АЛУ. При составлении схемы алгоритма необходимо учесть, что каждому безусловному оператору должна соответствовать одна микрооперация или несколько совместимых микроопераций, которые могут выполняться одновременно. Здесь под микрооперацией понимается элементарная операция, для управления которой достаточно одного управляющего сигнала.

Упорядоченная последовательность микроопераций составляет микропрограмму. Микропрограмма сложения и вычитания чисел в АЛУ в виде схемы алгоритма представлена на рисунке 3.

Перед началом операции числа находятся в оперативной памяти. Если АЛУ не занято выполнением очередной операции, то блок управления находится в исходном состоянии

и выдает сигнал готовности (оператор 1).

Блок управления начинает работу, если на него поступает код операции.

Выполнение операции начинается с того, что числа А и В последовательно считываются из оперативной памяти и записываются в регистры РгА и РгВ (операторы 2 и 3). Согласованная работа оперативной памяти и АЛУ обеспечивается центральным устройством управления, которое в определенные моменты времени выдает сигнал начала работы ОП в режиме чтения.

В зависимости от кода операции, будет выполняться операция сложения или вычитания (оператор 4).

Выбранная операция выполняется в сумматоре, при этом числа подаются в сумматор в прямом или обратном коде в зависимости от их знаков. Анализ знаков производится операторами 5, 6, 7. Далее оба числа одновременно поступают на входы сумматора, при этом на его выходах формируется значение выбранной операции (сумма или разность), которое записывается в регистр сумматора (операторы).

Для получения дополнительного кода числа в младший разряд сумматора поступает сигнал +1.

Полученный результат анализируется в схеме формирования признака результата (оператор). При отрицательном результате (S=1) он преобразуется в прямой код и записывается в оперативную память (операторы). На этом операция в АЛУ заканчивается.

Рисунок 3

6. Разработка функциональной схемы блока управления

6.1 Общая последовательность разработки

Блок управления представляет собой автомат с памятью. Алгоритм работы блока управления задан в виде микропрограммы. В этом случае разработка блока управления включает следующие этапы:

ü Формализация задания.

ü Выбор типа автомата.

ü Разметка схемы алгоритма.

ü Составление таблицы переходов и выходов автоматов.

ü Кодирование состояний.

ü Составление кодированной таблицы переходов и выходов.

ü Выбор типа триггеров.

ü Преобразование таблицы переходов в таблицу функций возбуждения триггеров.

ü Запись функций возбуждения и функций выходов в СДНФ.

ü Минимизация функций возбуждения и функций выходов.

ü Выбор типа логических элементов.

ü Преобразование функций переходов и выходов.

ü Построение функциональной схемы блока управления.

ü Проверка правильности работы блока управления.

6.2 Формализация задания

При задании автомата микропрограммой количество входных сигналов равно числу различных условных операторов микропрограммы. В данном случае число условных операторов равно 5.

Для упрощения записи логических функций на рисунке 3 приняты следующие обозначения:

- n – сигнал готовности;

- k – сигнал кода операции;

- a – знак числа А;

- b – знак числа В;

- s – знак результата операции.

Тогда входными сигналами блока управления являются сигналы n, k, a, b, s, каждый из которых может принимать значение 0 или 1.

Число выходных сигналов блока управления равно числу микроопераций в микропрограмме.

При анализе микропрограммы можно установить, что безусловные операторы 2, 3, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 29, 30 содержат по одной микрооперации. Однако операторы, кроме 2, 3, 29, 30, повторяющиеся операторы 11, 13, 20, 21 Кроме того, начальному оператору соответствует выходной сигнал, который сообщает о готовности блока управления к выполнению операции. Таким образом, общее число выходных сигналов равно 10. Обозначение выходных сигналов и соответствующие им микрооперации приведены в таблице 1.

С учетом числа входных и выходных сигналов общая схема блока управления может быть представлена в виде рисунка 4.

n

b

s

Рисунок 4

Таблица 1

№ № п/п	Выходные сигналы	Микрооперации
		Сигнал готовности
		Прием числа А из ОП в регистр РгА
		Прием числа В из ОП в регистр РгВ
		Отправка числа А в сумматор в обратном коде
		Отправка числа В в сумматор в обратном коде
		Отправка числа А в сумматор в прямом коде
		Отправка числа В в сумматор в прямом коде
		Формирование признака результата
		Преобразование результата в прямой код
		Выдача результата из регистра сумматора в ОП

6.3 Выбор типа автомата

Заданием предусмотрена реализация блока управления в виде автомата Мура.

6.4 Разметка схемы алгоритма

Для разметки используется формальная схема алгоритма, в которой названия микроопераций заменяются на соответствующие управляющие сигналы из таблицы 1. При разметке используются следующие правила:

1. Начальный и конечный операторы помечаются символами начального состояния ().

2. Все безусловные операторы помечаются символами последовательно пронумерованных состояний , , …

Размеченная схема алгоритма представлена на рисунке 5. Как видно по результатам разметки, автомат имеет 10 состояний (, , …, ).

Рисунок 5

6.5 Составление таблицы переходов и выходов

Таблица переходов и выходов составляется по размеченной схеме алгоритма. Число строк таблицы (без заглавной) равно числу комбинаций входных сигналов, а число столбцов (без заглавного) равно числу состояний автомата.

В каждой клетке таблицы указывается новое состояние автомата и выходной сигнал, выдаваемый автоматом. Для сокращения размеров таблицы следует учесть, что при входном сигнале S = 0 автомат может находиться только в состоянии . Таблица переходов и выходов автомата приведена в виде таблицы 2.

Таблица 2

Входы	Состояния
Y0	Y1	Y2	Y3	Y4	Y5	Y6	Y7	Y8	Y9
nkabs
0 - - - -	Q0	-	-	-	-	-	-	-	-	-
1 0 0 0 0	Q1	Q2	Q5	-	Q7	Q4	-	Q0	-
1 0 0 0 1	Q1	Q2	Q5	-	Q7	Q4	-	Q8	Q9	Q0
1 0 0 1 0	Q1	Q2	Q5	-	-	Q6	Q7	Q0	-	-
1 0 0 1 1	Q1	Q2	Q5	-	-	Q6	Q7	Q8	Q9	Q0
1 0 1 0 0	Q1	Q2	Q3	Q4	Q7	-	-	Q0	-	-
1 0 1 0 1	Q1	Q2	Q3	Q4	Q7	-	-	Q8	Q9	Q0
1 0 1 1 0	Q1	Q2	Q3	Q6	-	-	Q7	Q0	-	-
1 0 1 1 1	Q1	Q2	Q3	Q6	-	-	Q7	Q8	Q9	Q0
1 1 0 0 0	Q1	Q2	Q5	-	Q7	-	-	Q0	-	-
1 1 0 0 1	Q1	Q2	Q5	-	Q7	-	-	Q8	Q9	Q0
1 1 0 1 0	Q1	Q2	Q5	-	Q7	Q4	-	Q0	-	-
1 1 0 1 1	Q1	Q2	Q5	-	Q7	Q4	-	Q8	Q9	Q0
1 1 1 0 0	Q1	Q2	Q3	Q6	-	Q4	Q7	Q0	-	-
1 1 1 0 1	Q1	Q2	Q3	Q6	-	Q4	Q7	Q8	Q9	Q0
1 1 1 1 0	Q1	Q2	Q3	Q4	Q5	-	-	Q0	-	-
1 1 1 1 1	Q1	Q2	Q3	Q4	Q5	-	-	Q8	Q9	Q0

6.6 Кодирование состояний

Принимаем естественный способ кодирования. Число элементов памяти при этом будет равно

n = ( N) ­,

где: n – число элементов памяти;

N – число S состояний автомата;

­ - знак округления в большую сторону до целого.

При N = 10 получим:

n = ( 10) ­ = 4.

Обозначим элементы памяти символами , , и . Далее каждому состоянию поставим в соответствие двоичный код его номера и набор состояний элементов памяти. В результате получим следующее кодирование состояний:

- - - - - -

® 0000 ® ® 0101 ®

- - - - -

® 0001 ® ® 0110 ®

- - - -

® 0010 ® ® 0111 ®

- - - - -

® 0011 ® ® 1000 ®

- - - - -

® 0100 ® ® 1001 ®

6.7 Составление кодированной таблицы переходов и выходов

Для составления кодированной таблицы переходов заменим в таблице 2 состояния их двоичными номерами в соответствии с принятым кодированием. В результате получим кодированную таблицу переходов и выходов, которая имеет вид таблицы 3. В таблице 3 приведены как двоичные Q номера состояний, так и состояния каждого элемента памяти. Кроме этого, в таблице приведены значения выходных сигналов, которые остаются теми же, что и в таблице 2.

6.8 Выбор типа триггера

Выбор типа триггера производится методом перебора. При этом поочередно выполняется синтез автомата для всех рассматриваемых типов триггеров. Для реализации выбирается тип триггера, при использовании которого автомат имеет меньшую сложность. В данном случае синтез производится для T - триггера и D – триггера.

Таблица 3

Входы	Y0	Y1	Y2	Y3	Y4	Y5	Y6	Y7
SB RK	- - - -	- - -	- - -	- -	- - -	- -	- -	-
0 - - - -		-	-	-	-	-	-	-
1 0 0 0 0				-			-
1 0 0 0 1				-			-
1 0 0 1 0				-	-
1 0 0 1 1				-	-
1 0 1 0 0						-	-
1 0 1 0 1						-	-
1 0 1 1 0					-	-
1 0 1 1 1					-	-
1 1 0 0 0				-		-	-
1 1 0 0 1				-		-	-
1 1 0 1 0				-			-
1 1 0 1 1				-			-
1 1 1 0 0					-
1 1 1 0 1					-
1 1 1 1 0						-	-
1 1 1 1 1						-	-

Продолжение таблицы 3

Входы	Y8	Y9
SB RK	- - -	- -
0 - - - -	-	-
1 0 0 0 0	-	-
1 0 0 0 1
1 0 0 1 0	-	-
1 0 0 1 1
1 0 1 0 0	-	-
1 0 1 0 1
1 0 1 1 0	-	-
1 0 1 1 1
1 1 0 0 0	-	-
1 1 0 0 1
1 1 0 1 0	-	-
1 1 0 1 1
1 1 1 0 0	-	-
1 1 1 0 1
1 1 1 1 0	-	-
1 1 1 1 1

6.9 Преобразование таблицы переходов в таблицу функций возбуждения триггеров

При использовании D – триггеров преобразование таблицы переходов не выполняется.

Поэтому приведем преобразование таблицы переходов в таблицу функций возбуждения для Т – триггеров. Эта таблица имеет вид таблицы 4.

Таблица 4

Входы	Y0	Y1	Y2	Y3	Y4	Y5	Y6	Y7
nkabs	- - - -	- - -	- - -	- -	- - -	- -	- -	-
0 - - - -		-	-	-	-	-	-	-
1 0 0 0 0				-			-
1 0 0 0 1				-			-
1 0 0 1 0				-	-
1 0 0 1 1				-	-
1 0 1 0 0						-	-
1 0 1 0 1						-	-
1 0 1 1 0					-	-
1 0 1 1 1					-	-
1 1 0 0 0				-		-	-
1 1 0 0 1				-		-	-
1 1 0 1 0				-			-
1 1 0 1 1				-			-
1 1 1 0 0					-
1 1 1 0 1					-
1 1 1 1 0						-	-
1 1 1 1 1						-	-

Продолжение таблицы 4

Входы	Y8	Y9
nkabs	- - -	- -
0 - - - -	-	-
1 0 0 0 0	-	-
1 0 0 0 1
1 0 0 1 0	-	-
1 0 0 1 1
1 0 1 0 0	-	-
1 0 1 0 1
1 0 1 1 0	-	-
1 0 1 1 1
1 1 0 0 0	-	-
1 1 0 0 1
1 1 0 1 0	-	-
1 1 0 1 1
1 1 1 0 0	-	-
1 1 1 0 1
1 1 1 1 0	-	-
1 1 1 1 1

6. 10 Запись функций возбуждения и функций выходов в СДНФ

Функции возбуждения D – триггера:

- - - - - - - - - - - - -

(kabs Ú kabs Ú kabs Ú kabs Ú kabs Ú kabs Ú kabs Ú kabs) n

- - -

Ú n

- - - - - - - - - - - - - - - - - - - - - - -

(kabs Ú kabs Ú kabs Ú kabs Ú kabs Ú kabs Ú kabs Ú kabs) n

- - - - - - - - -

Ú ( Ú Ú Ú ) n

- - - - - - - - - - - - - - - - - -

n Ú n (kabs Ú kabs Ú kabs Ú kabs Ú kabs Ú kabs Ú kabs Ú kabs)

- - - - - - - - - - - - - - - - - -

Ú n (kabs Ú kabs Ú kabs Ú kabs) Ú n Ú(kabs Ú kabs) n

-

Ú n

- - - - - - - - - - - - - - -

n ( Ú Ú Ú Ú )

Выражения в скобках можно упростить методом непосредственных преобразований. В результате получим следующие выражения:

- - - -

n (s Ú )

- - - - - - - - - - - - -

n (a Ú Ú Ú Ú )

- - - - - - - - - - - - - - - - - -

n ( Ú a Ú kb Ú kb Ú Ú kb

- -

Ú )

- - - - - - - - - - - - - - -

n ( Ú Ú Ú Ú )

Функции возбуждения T – триггера:

- - - - - - - - - - - - - - -

(kabs Ú kabs Ú kabs Ú kabs Ú kabs Ú kabs Ú kabs Ú kabs) (n Ú n )

- - - - - - - - - - - - -- - -- - - - - - -

(kabs Ú kabs Ú kabs Ú kabs Ú kabs Ú kabs Ú kabs Ú kabs) n

- - -

Ú n Ú ns

- - - - - - - - - - - - - - - - - - -

n( Ú a Ú )Ú (kabs Ú kabs) n Ú ns

1

Аналогично функциям возбуждения D-триггера упрощаем функции возбуждения T-триггера.

- - -

ns ( Ú )

- - - - - - -

n (a Ú Ú s )

- - - - - - - - - - - - - - - - - - -

n ( Ú a Ú Ú kbs Ú kbs Ú s )

1

Функции выходов:

- - - - -

= ;

- - - - - - - -

; ; ;

- - -

- - - -

;

- - - - - -

; ; ;

6.11 Минимизация функций возбуждения и функций выходов

Для окончательной минимизации функций используется метод Карно. При минимизации следует учесть, что все функции являются не полностью определенными, так как в таблице переходов не использованы состояния Q10, Q11, Q12, Q13, Q14 и Q15. Стоит отметить, что метод Карно применим непосредственно только к функциям не более четырех переменных. В случае более сложных функций они минимизируются по частям.

- - - -

n (s Ú ) = n (s Ú )

- - - - - - - - - - - - -

n (a Ú Ú Ú Ú ) = n (s Ú )

- - - - - - - - - - - - - - - - - -

n ( Ú a Ú kb Ú kb Ú Ú kb

- -

Ú )

Поиск по сайту: