Курсовик ТА Пидорченко

Министерство Образования Российской Федерации

Московский Государственный Институт Радиотехники Электроники и Автоматики (Технический Университет)

Студент: Пидорченко Александр Сергеевич

Группа: ВВ-61-02

Шифр: 021105

Курсовой проект по Теории Автоматов

Москва 2004 год.

ФИО: Пидорченко Александр Сергеевич

Группа/Шифр: ВВ-62-02/1105.

Разработать вычислительное устройство, состоящее из двух взаимосвязанных частей: операционного и управляющего автоматов и выполняющее следующие операции:

1. Среднее арифметическое двух целых чисел в дополнительном коде.

2. Возведение в квадрат числа в плавающем формате.

УА. Схема с регулярной адресацией, конвейерный вариант.

Числа 32 разрядные.

Суммарное число входных и выходных контактов ≤ 40.

Должны быть разработаны и представлены:

1. Интерфейс разрабатываемого устройства.

2. Математические обоснования используемых алгоритмов.

3. Тестовые примеры.

4. Микропрограммы в содержательном виде.

5. Таблицы заполнения управляющей памяти.

6. Функциональные схемы операционного и управляющего автоматов.

Функциональные схемы разрабатываются с использованием многоразрядных канонических мультиплексоров, дешифраторов, сумматоров, регистров, счётчиков, ПЗУ с чётким указанием информационных, управляющих и синхронизирующих входов.

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

Разработку вычислительного устройства можно разбить на четыре этапа:

1. Разработка первого операционного автомата.

2. Разработка второго операционного автомата.

3. Разработка управляющего автомата.

4. Разработка схемы взаимодействия первых трёх автоматов.

Интерфейс разрабатываемого устройства

• Запись и считывание информации будет происходить по 32 разрядной шине ввода/вывода.

• Выбор операции происходит по управляющему входу К.

Операционный автомат № 1

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

Числа 32 разрядные. Первый разряд знаковый.

Алгоритм нахождения среднего арифметического:

1. Сложение двух чисел.

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

С оставим блок-схему преобразования:

Р – знаковые разряды чисел А и В одинаковы.

(1 – да. 0 – нет.)

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

• Регистры А и В используются для записи исходных чисел.

• Сумматор используется для сложения этих чисел.

• Регистр В используется для записи ответа.

• Элемент М2 и мультиплексор выбирают, заменять старший разряд после сдвига суммы на 0 или перенос из сумматора.

Управляющие сигналы:

Y1 – разрешение на запись в RG_A (0 – нет, 1 – да)

Y2 – разрешение на запись в RG_В (0 – нет, 1 – да)

Y3 – разрешение на запись в RG_С (0 – нет, 1 – да)

Описание работы автомата

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

Операционный автомат № 2

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

Алгоритм возведения в квадрат:

1. Сумма равна нулю. А и В равны числу.

2. Если ещё не прошло 24 такта, то, если старший разряд B =1 прибавляем к S A, если нулю, то не прибавляем.

3. Сдвигаем вправо S и В.

4. Повторяем 2 и 3 пока не пройдет 24 такта. Когда пройдёт умножаем порядок на 2 и пишем ответ.

Составим блок-схему преобразования:

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

• Регистры А и В используются для записи исходного числа. Регистр S для записи мантиссы ответа. RG2 для записи всего ответа.

• Счётчик используется для определения того, что прошло 24 такта.

• Сумматор складывает S и А. Мультиплексор выбирает, прибавлять ли А в соответствии со старшим разрядом В.

• Входное число имеет разрядность 32. Выходное – 34 (два разряда на случай переполнения мантиссы и порядка при возведении в квадрат).

• В ответ записывается 1 разряд – знак (всегда 0), 9 разрядов порядка и 24 разряда мантиссы.

Управляющие сигналы:

Y1 – разрешить синхросигнал на RG_B (0 – нет, 1 – да)

Y2 – разрешить синхросигнал на RG_A (0 – нет, 1 – да)

Y3 – разрешить синхросигнал на RG_S (0 – нет, 1 – да)

Y4 – разрешить синхросигнал на RG2 (0 – нет, 1 – да)

R – обнуление/запись (0 – нет, 1 – да)

Описание работы автомата

Перед началом сложения необходимо записать в регистры А и В исходное число. Следующие 24 такта автомат должен сдвигать В и переписывать S пока не будет условия Е. После этого происходит запись ответа.

Управляющий автомат

По условию должен быть управляющий автомат с регулярной адресацией, конвейерный вариант. В этой схеме рис.1. при разветвлении процесса вычислений пара альтернативных адресов получается следующим образом: один адрес всегда на единицу больше, чем текущий (т.е. изменяется «регулярным» образом), второй адрес - произвольный и содержится вместе с микрокомандой в микроинструкции.

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

В схему введен элемент М2, позволяющий инвертировать значение входного сигнала, что облегчает распределение микроинструкций по ячейкам управляющей памяти.

Работой управляющего автомата должны управлять входные сигналы.

К – код операции (0 – операция 1, 1 – операция 2)

E – завершение операции 2 (0 – нет, 1 – да)

В каждой строке таблицы ROM пишем: Y – микрокоманда, H – новый адрес входного сигнала, который автомат будет использовать на следующем такте (0 – переход в следующий адрес, 1 – переход в текущий S адрес), S – новый адрес перехода, если не происходит перехода в следующий по счету адрес, e – инверсия входного сигнала в следующем такте (0 – нет, 1 – да), N – текущая операция (0 – первая, 1 – вторая).

Таблицы заполнения памяти

Таблица Микрокоманд
	Операция 1				Операция 2
M	Y1	Y2	Y3	Y1	Y2	Y3	R	D
M0	0	0	0	0	0	0	0	0
M1	1	0	0	x	x	x	x	0
M2	0	1	1	x	x	x	x	1
M3	x	x	x	1	1	0	1	0
M4	x	x	x	1	0	1	0	0
M5	x	x	x	0	0	0	0	1

	Таблица заполнения ROM
	A	Y	H	S	e	N
	000	M0	01	011	1	x
	001	M1	01	010	1	0
	010	M2	00	000	0	0
	011	M3	10	100	1	1
	100	M4	10	100	1	1
	101	M5	01	110	1	1
	110	M6	00	000	0	1

Блок-схема Управляющего Автомата

Разработка Управляющего Автомата

• Регистр используется для хранения текущих значений адресов и флагов.

• Нижний мультиплексор используется для выбора входного сигнала в соответствии в текущим адресом входного сигнала Н.

• Верхний мультиплексор используется для выбора в соответствии с управляющим сигналом (инвертным, если текущий флаг инверсии e =1) использовать ли переход в следующий адрес с помощью инкрементора, или переход в текущий адрес перехода S.

• В ROM записаны микрокоманды, флаги и адреса, которые он выбирает в соответствии с текущим состоянием A.

• Регистр на выходе используется для превращения управляющего автомата в автомат Мура, для задержки выходных сигналов на один такт по отношению к входным, чтобы не возникала гонка значений в операционных автоматах.

Функциональная схема Управляющего Автомата

Описание работы автомата

Свою работу управляющий автомат начинает в состоянии 000 (начальное состояние). Из него возможны переходы в следующее состояние 001, если К =0, или по адресу перехода в 000 (начальное состояние S = 000, H =00, e=0), если K = 1. Переход из начального состояния в 001 или 011 сразу не возможен из-за того, что S=000. Поэтому для перехода в начало второй операции нужно подать K=1 для перехода в то же состояние но с S=011, H=01 и e=1, что на следующем такте приведёт к безусловному переходу в состояние начала второй операции 011. При переходе в 001 на следующем такте безусловный переход в 010, потом в 000. При переходе в 011, переход в 100, из 100 произойдёт переход в 101 когда придёт сигнал E=1 – окончание операции, из 101 нельзя сразу безусловно перейти в 000 т.к. входной сигнал установлен на Е, поэтому используется переходное состояние 101, из которого происходит безусловный переход в 000.