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

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

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

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

Выполнил студент группы ВВ-62-02

Ильин Дмитрий Викторович

Шифр: 021114

Москва 2004 год.

ФИО: Ильин Дмитрий Викторович.

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

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

1. Перевод из кода с плавающей точкой (мантисса в прямом коде) в целое в дополнительном коде.

2. Перевод правильной двоичной дроби в десятичную.

УА. Схема с адресным ПЗУ, конвейерный вариант.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Первый операционный автомат должен реализовывать перевод из кода с плавающей точкой (мантисса в прямом коде) в целое в дополнительном коде.

По условию мантисса нормализована и должна лежать в полуотрезке [0,1 – 1), т.к. она представляет собой. Порядок должен быть в смещённом коде и ≥ 0. Порядок занимает 8 разрядов.

Алгоритм преобразования:

1. Если порядок не равен нулю то сдвигаем мантиссу влево с добавлением нуля в младший разряд.

2. Уменьшаем порядок на единицу.

3. Повторяем пункты 1 и 2 пока порядок не станет равным нулю или пока не наступит переполнение.

4. Перевод мантиссы в дополнительный код.

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

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

• Регистр сдвига RG1 используется для реализации сдвига мантиссы влево. Регистр 56 разрядный и первые 32 разряда записываются нули, а остальные 24 мантисса и знак. При сдвиге мантиссы влево нули будут вытесняться мантиссой, преобразованной в целое число.

• Для уменьшения порядка на единицу используется регистр RG2 и декриментор.

• Для перевода мантиссы в дополнительный код используется последовательное соединение инвертора и инкрементора.

• Для проверки равенства порядка нулю можно использовать дизъюнкцию от всех разрядов кроме старшего.

• Для обнаружения переполнения мантиссы можно определить присутствие единицы в разряде 1 (разряд 0 это знаковый разряд и мантисса не должна его занимать) разряде, что означает, что следующий сдвиг приведёт к потере знакового разряда.

• Если нет переполнения, на выход проходит все 32 разряда сдвигового регистра RG1 после преобразования в дополнительный код, если есть переполнение, то на выход поступают только 24 разряда мантиссы, преобразованные в дополнительный код, а остальные 8 разрядов заменяются порядком. MX2 выбирает способ вывода ответа в соответствии с сигналом переполнения.

• Для переключения уменьшение/запись порядка можно использовать мультиплексор.

• Для сохранения результата преобразования достаточно прекратить подачу синхросигнала на регистры.

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

1. Y1 – переключение режимов запись/сдвиг (0 – сдвиг, 1 – запись)

2. Y2 – сохранение результата (0 – работа, 1 – вывод ответа)

Условия (признаки):

1. УСЛ1 – завершение работы (0 – работа, 1 – завершение). Означает или равенство всех разрядов порядка кроме старшего нулю (завершение преобразования), или единица в разряде 1 мантиссы, означающая переполнение в следующем такте (невозможность преобразования).

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

Перед началом преобразования необходимо записать данные. Для этого на первом такте нужно подать управляющие сигналы Y1 = 1, Y2 = 0. После записи данных для начала преобразования нужно подать управляющие сигналы Y1 = 0, Y2 = 0. Об окончании преобразования сигнализирует УСЛ1. Для сохранения результата нужно подать управляющие сигналы Y1 = 0, Y2 = 1.

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

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

Алгоритм преобразования:

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

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

1. Сначала сумма равна 0

2. Делим сумму на 2

3. Прибавляем младший разряд двоичной дроби к целой части десятичной дроби

4. Сдвигаем двоичную дробь вправо

5. Повторяем 2 - 4 пока не прибавим последний разряд (32 раза)

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

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

• Основное действие в этом алгоритме – деление десятичного числа на 2. Его можно реализовать при помощи модификации каскадного сумматора. Деление надо начинать со старшего разряда. Разделить на 2 десятичную цифру, закодированную тетрадой можно при помощи передачи со сдвигом вправо. Если при этом потерянный младший разряд был равен единице, то в следующем разряде после сдвига нужно прибавить 5. После деления на 2 десятичной цифры максимальная цифра будет 4, поэтому переполнение невозможно. Элемент :2 реализует деление на 2 одного десятичного разряда. При каскадном соединении этих элементов получается деление на 2 всего десятичного числа (не обязательно дроби).

• Поскольку мы имеем дело с двоичной дроби, к целой части может быть прибавлены или 0 или 1. После деления на 2 в обоих случаях в целой части остаётся 0. Поэтому вместо прибавления 0 или 1 к целой части можно просто заменять старший разряд десятичной дроби после деления на 2 на текущий младший разряд двоичной дроби. Поскольку старший разряд десятичной дроби представлен тетрадой нужно просто приравнять к нулю её первые 3 разряда и заменить четвёртый.

• Для сдвига десятичной дроби вправо и потактной выдачи её текущего младшего разряда используется регистр сдвига RG1. Для хранения текущей десятичной дроби и замены старшей тетрады используется регистр RG2.

• На схеме показана конструкция элемента :2 и структура каскадного делителя на 2.

• Для определения числа прошедших тактов используется пятиразрядный счётчик CT. После прошествия 32 тактов все его разряды становятся равны 1 и конъюнкция выдаёт сигнал – условие окончания преобразования.

• Для записи управляющий сигнал Y1 разрешает запись в RG1 и обнуляет RG2 и счётчик CT.

• Для сохранения результата используется управляющий сигнал Y2, который прекращает подачу синхросигнала на RG2.

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

1. Y1 – обнуление, запись (0 – работа, 1 – запись)

2. Y2 - сохранение результата (0 – работа, 1 – вывод ответа)

Условия (признаки):

1. УСЛ2 – завершение работы (0 – работа, 1 – завершение). С начала работы прошло 32 такта. Вся дробь преобразована.

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

Перед началом преобразования необходимо записать данные. Для этого на первом такте нужно подать управляющие сигналы Y1 = 1, Y2 = 0. После записи данных для начала преобразования нужно подать управляющие сигналы Y1 = 0, Y2 = 0. Об окончании преобразования сигнализирует УСЛ2. Для сохранения результата нужно подать управляющие сигналы Y1 = 0, Y2 = 1 (комбинации управляющих сигналов совпадают с комбинациями в первом операционном автомате, что позволяет использовать одинаковые микропрограммы).

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

По условию должен быть управляющий автомат с адресным ПЗУ, конвейерный вариант. Следовательно нужно использовать схему, содержащую функцию переходов, функцию выходов, регистр состояний (флагов) и регистр микрокоманд. Функции перехода и выхода можно реализовать с помощью двух ROM.

Диаграмма Мура Управляющего Автомата

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

Микропрограммы	Описание	Y1	Y2
M0	Начало	0	0
M1	Запись	1	0
M2	Работа	0	0
M3	Окончание	0	1

xx00	xxx
xx01	001
xx10	100
xx11	000
	НС	Операция 1			Операция 2
У1,У2,К1,К2	000	001	010	011	100	101	110
0000	000	010	010	011	101	101	110
0100	000	010	010	011	101	110	110
1000	000	010	011	011	101	101	110
1100	000	010	011	011	101	110	110
Выход	M0	M1	M2	M3	M1	M2	M3

ROM Перехода
Адрес	У	Переход
000	0	000
000	1	000
001	0	010
001	1	010
010	0	010
010	1	011
011	0	011
011	1	011
100	1	101
100	0	101
101	1	101
101	0	110
110	1	110
110	0	110
К1 K2	Переход
00	Xxx
01	001
10	100
11	000

ROM Выхода
Адрес	Описание	Микропрограмма	H
000	Начальное состояние	M0	x
001	Первая операция, запись	M1	0
010	Первая операция, работа	M2	0
011	Первая операция, окончание	M3	0
100	Вторая операция, запись	M1	1
101	Вторая операция, работа	M2	1
110	Вторая операция, окончание	M3	1

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

• Для реализации функций перехода и выхода используется два ROM: ROM перехода и ROM выхода.

• RG1 используется для хранения текущего состояния управляющего автомата.

• Так как управляющий автомат должен быть автоматом Мура, его выходные сигналы должны иметь задержку в 1 такт по отношению к соответствующему автомату Мили. Для этого используется регистр микрокоманд RG2.

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

• Работой управляющего автомата управляют сигналы K1 и K2. С их помощью задаётся код операции и возвращение автомата в начальное состояние.

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