Блок управления для выполнения операций сложения и вычитания в арифметико-логическом устройстве (АЛУ)

Размещено на http://www.allbest.ru/

МИНИСТЕРСТВО ТРАНСПОРТА РФ

ГОСУДАРСТВЕННАЯ СЛУЖБА ГРАЖДАНСКОЙ АВИАЦИИ

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ ГРАЖДАНСКОЙ АВИАЦИИ

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

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

на тему "Блок управления для выполнения операций сложения и вычитания в арифметико-логическом устройстве (АЛУ)"

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

Вариант № 13

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

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

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

Москва 2007

Содержание

Введение

1. Задание

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Заключение

Литература

Введение

сложение вычитание автомат алгоритм

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

Рисунок 1

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

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

1. Задание

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

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

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

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

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

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

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

С - сумма.

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

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

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

С - разность.

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

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

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

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

Рисунок 2

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

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

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

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

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

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

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

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

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

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

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

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

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

Рисунок 3

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

5.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.

Рисунок 4

Таблица 1

№ п/п	Выходные сигналы	Микрооперации
0		Сигнал готовности
1		Прием числа А из ОП в регистр РгА
2		Прием числа В из ОП в регистр РгВ
3		Отправка числа А в сумматор в обратном коде
4		Отправка числа В в сумматор в обратном коде
5		Отправка числа А в сумматор в прямом коде
6		Отправка числа В в сумматор в прямом коде
7		Формирование признака результата
8		Преобразование результата в прямой код
9		Выдача результата из регистра сумматора в ОП

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

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

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

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

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

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

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

Рисунок 5

5.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

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

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

n = (N) ,

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

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

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

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

n = ( 10) = 4.

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

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

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

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

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

Таблица 3

Входы	Y0	Y1	Y2	Y3	Y4	Y5
	0000	0001	0010	0011	0100	0101
SBRK	- - - -	- - -	- - -	- -	- - -	- -
0 - - - -	0000	-	-	-	-	-
1 0 0 0 0	0001	0010	0101	-	0111	0100
1 0 0 0 1	0001	0010	0101	-	0111	0100
1 0 0 1 0	0001	0010	0101	-	-	0110
1 0 0 1 1	0001	0010	0101	-	-	0110
1 0 1 0 0	0001	0010	0011	0100	0111	-
1 0 1 0 1	0001	0010	0011	0100	0111	-
1 0 1 1 0	0001	0010	0011	0110	-	-
1 0 1 1 1	0001	0010	0011	0110	-	-
1 1 0 0 0	0001	0010	0101	-	0111	-
1 1 0 0 1	0001	0010	0101	-	0111	-
1 1 0 1 0	0001	0010	0101	-	0111	0100
1 1 0 1 1	0001	0010	0101	-	0111	0100
1 1 1 0 0	0001	0010	0011	0110	-	0100
1 1 1 0 1	0001	0010	0011	0110	-	0100
1 1 1 1 0	0001	0010	0011	0100	0111	-
1 1 1 1 1	0001	0010	0011	0100	0111	-

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

Входы	Y6	Y7	Y8	Y9
	0110	0111	1000	1001
SBRK	- -	-	- - -	- -
0 - - - -	-	-	-	-
1 0 0 0 0	-	0000	-	-
1 0 0 0 1	-	1000	1001	0000
1 0 0 1 0	0111	0000	-	-
1 0 0 1 1	0111	1000	1001	0000
1 0 1 0 0	-	0000	-	-
1 0 1 0 1	-	1000	1001	0000
1 0 1 1 0	0111	0000	-	-
1 0 1 1 1	0111	1000	1001	0000
1 1 0 0 0	-	0000	-	-
1 1 0 0 1	-	1000	1001	0000
1 1 0 1 0	-	0000	-	-
1 1 0 1 1	-	1000	1001	0000
1 1 1 0 0	0111	0000	-	-
1 1 1 0 1	0111	1000	1001	0000
1 1 1 1 0	-	0000	-	-
1 1 1 1 1	-	1000	1001	0000

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

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

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

Таблица 4

Входы	Y0	Y1	Y2	Y3	Y4	Y5
	0000	0001	0010	0011	0100	0101
nkabs	- - - -	- - -	- - -	- -	- - -	- -
0 - - - -	0000	-	-	-	-	-
1 0 0 0 0	0001	0011	0111	-	0011	0001
1 0 0 0 1	0001	0011	0111	-	0011	0001
1 0 0 1 0	0001	0011	0111	-	-	0011
1 0 0 1 1	0001	0011	0111	-	-	0011
1 0 1 0 0	0001	0011	0001	0111	0011	-
1 0 1 0 1	0001	0011	0001	0111	0011	-
1 0 1 1 0	0001	0011	0001	0101	-	-
1 0 1 1 1	0001	0011	0001	0101	-	-
1 1 0 0 0	0001	0011	0111	-	0011	-
1 1 0 0 1	0001	0011	0111	-	0011	-
1 1 0 1 0	0001	0011	0111	-	0011	0001
1 1 0 1 1	0001	0011	0111	-	0011	0001
1 1 1 0 0	0001	0011	0001	0101	-	0001
1 1 1 0 1	0001	0011	0001	0101	-	0001
1 1 1 1 0	0001	0011	0001	0111	0011	-
1 1 1 1 1	0001	0011	0001	0111	0011	-

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

Входы	Y6	Y7	Y8	Y9
	0110	0111	1000	1001
nkabs	- -	-	- - -	- -
0 - - - -	-	-	-	-
1 0 0 0 0	-	0111	-	-
1 0 0 0 1	-	1111	0001	1001
1 0 0 1 0	0001	0111	-	-
1 0 0 1 1	0001	1111	0001	1001
1 0 1 0 0	-	0111	-	-
1 0 1 0 1	-	1111	0001	1001
1 0 1 1 0	0001	0111	-	-
1 0 1 1 1	0001	1111	0001	1001
1 1 0 0 0	-	0111	-	-
1 1 0 0 1	-	1111	0001	1001
1 1 0 1 0	-	0111	-	-
1 1 0 1 1	-	1111	0001	1001
1 1 1 0 0	0001	0111	-	-
1 1 1 0 1	0001	1111	0001	1001
1 1 1 1 0	-	0111	-	-
1 1 1 1 1	-	1111	0001	1001

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

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

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

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

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

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

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

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

В результате минимизации получим следующие выражения для функций D - триггеров:

Диаграммы Карно для функций

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

T - триггеров:

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

После минимизации получили следующие функции выходов:

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

В качестве логических заданы элементы И - НЕ.

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

Применяя правило двойной инверсии, получим следующие выражения:

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

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

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

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

С учетом количества и вида функций возбуждения T - триггеров и функций выходов для реализации схемы блока управления потребуются элементы, количество и тип которых приведены в таблице 6.

Таблица 6

Тип элемента	Количество входов элемента	Количество элементов	Общее количество входов элементов
И - НЕ	2	2	4
И - НЕ	3	9	27
И - НЕ	4	6	24
И - НЕ	8	5	40
Итого	22	95

Таким образом, для построения блока управления с использованием T - триггеров потребуется 22 логических элемента с общим количеством входов, равным 95.

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

При контроле работоспособности автомата определяется правильность смены состояний и выходных сигналов для определенной последовательности входных сигналов и исходного состояния. Пусть автомат находится в состоянии , и на входы автомата поступают сигналы n=1, k=0, a=0, b=1 и s=0. Для каждого такта известны набор входных сигналов и текущее состояние автомата, представленное в виде сигналов на выходах элементов памяти (). Эти сигналы подаются на входы функциональной схемы.

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

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

Таблица 7

Входы	Текущее состояние	Следующее состояние	Выход
nkabs	()	()
1 0 0 1 0	0 0 1 0 (Q2)	0 1 0 1 (Q5)	Y5
1 0 0 1 1	0 1 0 1 (Q5)	0 1 1 0 (Q6)	Y6
1 0 1 0 0	0 1 0 0 (Q4)	0 1 1 1 (Q7)	Y7
1 0 1 0 1	1 0 0 1 (Q9)	0 0 0 0 (Q0)	Y0

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

Заключение

В результате выполнения задания синтезирован блок управления операций сложения и вычитания в АЛУ.

Блок управления построен в виде автомата Мура с использованием в качестве элементов памяти

T - триггеров и логических элементов И - НЕ. Для реализации блока управления требуется 4

T - триггера и 22 логических элемента с общим количеством входов 95. Блок управления имеет минимальный аппаратурный состав и обеспечивает формирование выходных сигналов при любых сочетаниях сигналов на входах блока.

Рисунок 6

Литература

1. Савельев А.Я. Прикладная теория цифровых автоматов: Учебное пособие для вузов. - М.: Высшая школа, 1987.

2. Рощин А. Г., Половов Р. М. Пособие к выполнению курсовой работы по дисциплине “Теория автоматов” для студентов курса специальности 2201 дневного обучения. - М.:МГТУГА,2001.

3. Рощин А. Г., Половов Р. М. Тексты лекций по дисциплине “Теория автоматов”. Ч. 1. - М.:МГТУГА, 1998.

4. Рощин А. Г., Половов Р. М. Тексты лекций по дисциплине “Теория автоматов”. Ч. 2. - М.:МГТУГА, 1998.

Размещено на Allbest.ru

...