Автомат Мили для операции умножения с фиксированной запятой

ЧУВАШСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ

ИМ. И.Н. УЛЬЯНОВА

Кафедра информационно-вычислительных систем

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

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

тема «Автомат Мили для операции умножения с фиксированной запятой»

Выполнила: Николаева Е.В.

Проверил: Малетин Т.

Чебоксары 2006 г.

Оглавление

1. Задание на курсовой проект

2. Введение

3. Алгоритм выполнения заданной арифметической операции

3.1 Словесное описание алгоритма

3.2 Реализация алгоритма на примере

3.3 Определение погрешностей

4. Построение микропрограммы

5. Схема АО

6.Заключение

7. Литература

1. Задание на курсовой проект

Курсовая работа выполняется по индивидуальным заданиям. Вариант данной работы №46.

Определение точности результата выполнения заданной математической операции на примере заданных десятичных чисел;

Разработка микропрограммы выполнения заданной математической операции;

Уточнение системы операционного автомата в соответствии со своим вариантом;

Построение граф-схемы алгоритма (ГСА) и логической схемы алгоритма (ЛСА);

Дано:

Таблица 1.1

Таблица 1.2

2. Введение

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

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

3. Алгоритм выполнения заданной арифметической операции

Операнды А и В, заданные в таблице 1.2 в десятичной системе счисления, необходимо представить в двоичной системе счисления в заданной форме представления (в обратном коде).

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

3.1 Словесное описание алгоритма

I. Представление операндов А и В в двоичной системе счисления

Представление чисел с фиксированной запятой (точкой).

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

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

, (9)

где - машинное изображение числа для формы представления с фиксированной запятой.

Тогда число будет представлено в виде .

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

Так как числа бывают положительные и отрицательные, то формат (разрядная сетка) автоматного изображения разбивается на знаковую часть и после числа (рисунок №1, ). В знаковую часть записывается информация о знаке. Примем, что знак положительного числа «» изображается символом , а знак отрицательного числа «?» изображается символом .

Рисунок 1. Представление чисел в форме с фиксированной запятой

Диапазон представимых чисел в этом случае от до , где - количество разрядов без знаковой части.

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

Для того, чтобы выполнить условие (9), необходимо число, большее по абсолютному значению, записать в виде . Отсюда , что соответствует величине масштабного коэффициента . Число должно войти в разрядную сетку автомата с сохранением соответствия разрядов, т.е. . Следовательно, , или (рисунок 1, , ).

II. Операция умножения.

Умножение чисел на двоичном сумматоре обратного кода.

Рассмотрим правила умножения операндов, заданных в обратном коде. Произведение обратных кодов сомножителей равно обратному коду результата только в случае положительного множителя. Пусть множимое А = [А]о6, а множитель В > 0. Тогда

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

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

Пример 1. Умножить на сумматоре обратного кода числа А = -0,10011 и В = 0,11001.

Решение. Сначала записываются машинные изображения чисел:

Последовательность действий, проводимых над числами, представлена в таблице 3.1.

Таблица 3.1

Пусть А = [А]о6 и В<0. Тогда [B]ОБ = 1, b1 b2 …bn . В соответствии с (2.10) [В]о6 =2 + В-2-n . Следовательно, В = 0, b1 b2 …bn + 2-n -1.

На основании (12) можно сформулировать правило: если множитель отрицательный, то произведение чисел на сумматоре обратного кода получается прибавлением поправок [А] и [А]о6 * 2-n к произведению обратных кодов сомножителей.

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

3.2 Реализация алгоритма на примере

Требуется умножить в обратных кодах с фиксированной запятой операнды В = 0.35 и А = -0.1.

Сначала представим операнды А и В в двоичной системе счисления в форме представления с фиксированной запятой.

Перевод операнда В=0.35 Перевод операнда А=-0,1

В=0.3510=00.010110012 А= -0.1= -0.000110012=10.000110012

Выполним умножение в обратных кодах.

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

Сначала запишем машинные изображения чисел.

=11.11100110; =00.01011001

Последовательность действий, проводимых над числами, представлена в таблице (таблица 3.2)

Таблица 3.2

3.3 Определение погрешностей

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

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

Относительная погрешность представления - величина

.

Усредненная абсолютная погрешность перевода чисел в двоичную систему счисления .

Для представления чисел в форме с фиксированной запятой абсолютное значение машинного изображения числа:

. (13)

Следовательно, относительные погрешности представления для минимального значения числа .

Для ЭВМ, как правило, , поэтому , откуда

.

Аналогично, для максимального значения:

. (14)

Из (16) видно, что погрешности представления малых чисел в форме с фиксированной запятой могут быть очень значительными.

=0,001953125

=0,0019607843

=0,001953125

=0,0019607843

Погрешности операции умножения.

==0,00390625

0,0015996

4. Построение микропрограммы

Содержательная граф-схема алгоритма должна удовлетворять всем условиям, предъявляемым к ГСА.

При разработке содержательной ГСА используем следующие условные обозначения микроопераций:

сложение на сумматоре с содержимым регистра А в кодах:

СМ: = [СМ] + ;

сдвиг вправо на один разряд: B := RI(B); СМ= RI(СМ).

Логическая схема алгоритма (ЛСА):

5. Схема АО

6. Заключение

Курсовая работа завершает изучение курса «Теория автоматов». Она предназначена для закрепления и углубления знаний по алгоритмам выполнения арифметических операций, основам алгебраической логике, теории комбинационных систем, а также по методам структурного синтеза цифровых автоматов, полученных в процессе изучения курса.

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

Кроме того, были подсчитаны погрешности представления данных в разрядной сетке и выполнения самой операции. Это может быть связано с тем, что представление числовой информации в цифровом автомате, как правило, влечет за собой появление погрешностей (ошибок), величина которых зависит от формы представления чисел и от длины разрядной сетки автоматов.

Знания и навыки, полученные в процессе выполнения курсовой работы, в дальнейшем послужат базой для изучения курсов «Расчет и проектирование элементов ЭВМ», «Основы теории и проектирования ЭВМ», а также при курсовом и дипломном проектировании.

7. Литература

1. Савельев А.Я. Основы информатики.2001г.

2. Савельев А.Я. Арифметические и логические основы цифровых автоматов. - М.: Высшая школа, 1997

3. Власов В.В. Крайников А.В., Чепайкин В.Л. Вычислительные машины и системы: арифметические и логические основы построения ЭВМ: текст лекций. Чебоксары 1991г.