Разработка алгоритма и программная реализация на эмуляторе микро-ЭВМ СМ-1800

Разработка алгоритма и программная реализация на эмуляторе микро-ЭВМ СМ-1800

1. Введение

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

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

Вариант №1.

. Аналитическая часть

Подготовить для аналитической части реферативный материал на следующие темы:

ñ  Двоичная, восьмеричная и шестнадцатеричная системы счисления.

ñ  Правила переводов десятичных чисел в них и обратно.

ñ  Форматы хранения чисел с плавающей точкой.

Числа для примеров в обзоре взять из второго пункта настоящего задания.

. Практическая часть

Задача для разработки алгоритма и программной реализации на эмуляторе микро-ЭВМ СМ-1800.

Пользуясь программой Монитор занести в память ЭВМ, начиная с адреса 500016, следующий массив констант:

Будем рассматривать эти четыре байта как число в формате с плавающей точкой (1+8+23). (старший байт числа записан в старшем адресе!) Восьмиразрядный порядок имеет смещение pсм=12810. Двоичная двадцатитрехразрядная мантисса не содержит старшей единицы, получаемой в результате нормализации.

Составить программу, формирующую следующие 4 числа:

.        «Знак числа» в ячейке 600016 (однобайтное целое число «+» -00 и «-» -01),

.        «Знак порядка» в ячейке 600116 (однобайтное целое число «+» -00 и «-» -01),

.        Модуль порядка в ячейке 600216 (однобайтное целое число),

.        Мантисса, как трехбайтное целое число в ячейках (600316-600516). Старший байт записывается в старшем адресе!

Программу располагать в памяти с ячейки 400016.

.       

.        Аналитическая часть

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

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

Непозиционная система счисления - система, в которой значение символа не зависит от его положения в числе системы. Например римская система.

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

Основание(базис) - количество знаков или символов, используемых в разрядах для изображения числа в данной системе. Обозначим основание целым числом b>1. Тогда позиционная система счисления с основанием b будет также называется b-ричной (в частности, двоичной, троичной, десятичной и т. п.).

Целое число x в b-ричной системе счисления представляется в виде конечной линейной комбинации степеней числа b:

,где аk -это целые числа, называемые цифрами, удовлетворяющие неравенству 0 ≤ ak ≤ b-1, а каждая степень bk в такой записи называется разрядом (позицией), старшинство разрядов и соответствующих им цифр определяется значением показателя степени k. Обычно для ненулевого числа x требуют, чтобы старшая цифра an-1 в b-ричном представлении x была также ненулевой.

Двоичная система счисления - это позиционная система счисления с основанием два. В этой системе счисления цифры записываются при помощи двух символов - 0 и 1.

Основная система для информационных технологий и цифровой техники в особенности. Процессор любой вычислительной техники работает на этой системе счисления.

Между тем уже в XI веке китайский ученый и философ Шао Юн использует двоичную систему в текстах Книги Перемен.

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

Рассмотрим, как формируются числа в двоичной системе.

В привычной для нас десятеричной системе счисления мы располагаем десятью знаками-цифрами (от 0 до 9). Когда счет достигает 9, то вводится новый разряд (десятки), а единицы обнуляются и счет начинается снова. После 19 разряд десятков увеличивается на 1, а единицы снова обнуляются. И так далее.

Двоичная система счисления аналогична десятеричной, за исключением того, что в ней участвуют не 10 символов, а всего 2. Как только разряд достигает предела (т. е. единицы) появляется новый разряд, а старый обнуляется.

- это ноль

- это один (и это предел разряда)

- это два

- это три (и это снова предел)

- это четыре

и т.д.

Преобразование двоичной системы в десятичную и обратно.

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

Точка, которая стоит после 1 называется двоичной точкой.

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

Таким образом, каждое следующее число умножается на двойку в степени на 1 выше и складывается.

Обратную операцию удобно выполнять методом «в столбик», но можно хоть в уме.

Для примера возьмем число 77, которое мы хотим перевести в двоичную систему.

Теперь выполним процесс его деления на 2:

/ 2 = 38 (1 остаток)

/ 2 = 19 (0 остаток)

/ 2 = 9 (1 остаток)

/ 2 = 4 (1 остаток)

/ 2 = 2 (0 остаток)

/ 2 = 1 (0 остаток)

/ 2 = 0 (1 остаток)

Остатки на каждом шаге - это и есть число 77 в двоичной системе счисления (1001101).

Восьмеричная система счисления.

Восьмеричная система счисления - это позиционная система счисления с основанием 8. Для представления в ней используются числа от 0 до 7.

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

Перевод восьмеричной системы в десятичную и обратно.

Алгоритм действий аналогичен уже ранее рассмотренному в двоичной системе счисления.

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

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

= (2·83)+(3·82)+(5·81)+(7·80) = 2·512 + 3·64 + 5·8 + 7·1 = 126310

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

.        Делим десятичное число А на 8. Частное Q запоминаем для следующего шага, а остаток a записываем как младший бит восьмеричного числа.

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

.        Алгоритм продолжается до тех пор, пока в результате выполнения шагов 1 и 2 не получится частное Q = 0 и остаток a меньше 8.

Переведем, для примера, число 333610 в восьмеричную систему:

: 8 = 41710

- 333610 = 0, остаток 0 записываем в МБ восьмеричного числа.

: 8 = 5210

- 41610 = 1, остаток 1 записываем в следующий после МБ разряд восьмеричного числа.

: 8 = 610

- 4810 = 4, остаток 4 записываем в старший разряд восьмеричного числа.

: 8 = 010, остаток 0, записываем 6 в самый старший разряд восьмеричного числа.

В итоге получим - 64108.

Шестнадцатеричная система счисления.

Шестнадцатеричная система счисления - это позиционная система счисления с основанием 16.

Для отображения цифр используются следующие символы: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, A, B, C, D, E, F. То есть после обычных для десятичной системы счисления 0...9 идут латинские буквы A, B, C, D, E, F.

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

Так же в стандарте текста Юникод номер символа записывается в шестнадцатеричным виде, используя не менее 4 цифр.

Есть так же шестнадцатеричный стандарт записи цветов.

Для обозначения шестнадцатеричной системы в ассемблерах можно не только использовать нижний регистр (пример: A416), но и латинскую букву h (A4h).

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

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

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

A416 = 4·160+10·161 = 4·1+10·16= 4+160=16410

Соответственно для этого нужно помнить что А16=1010. Для этого можно пользоваться таблицей:

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

Переведем число 253 из десятичной в шестнадцатеричную систему.

: 16 = 1510

- 24010 = 1310, остаток 13 в виде D записываем в МБ шестнадцатеричного числа.

делить уже не надо, поскольку этому числу и так соответствует F16.

Записав по начиная со старшего разряда получаем число из практической части - FD16.

.2 Форматы хранения чисел с плавающей точкой

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

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

,

где N - записываемое число, М - мантисса, n - основание показательной степени, р(целое) - порядок.

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

Стандарт IEEE - Институт инженеров по электротехнике и электронике (англ. Institute of Electrical and Electronics Engineers) (I triple E - «Ай трипл и»), международная некоммерческая ассоциация специалистов в области техники, мировой лидер в области разработки стандартов по радиоэлектронике и электротехнике.

Итак, IEEE разработал международные стандарты, которые описывают представление чисел с плавающей запятой:

ñ  Стандарт ANSI/IEEE 754:1985 определяет требования к реализации двоичной плавающей арифметике.

ñ  Стандарт ANSI/IEEE 854:1987 обобщает прежний стандарт, допуская дополнительно, кроме двоичного, десятичное основание представлений мантиссы и экспоненты и произвольную длину машинного слова.

Позднее требования этих стандартов были отражены в стандарте IEC 60559:1989.

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

В большинстве современных платформ, таких как Intel реализована плавающая арифметика, соответствующая стандарту IEC 60559.

Стандарты IEEE определяют следующие форматы хранения вещественных чисел:

ñ  С простой точностью (соответствует типам real*4 в языке Фортран и float в С)

ñ  с двойной точностью (соответствует типам real*4 в языке Фортран и double в С)

ñ  с расширенной точностью (соответствует типам real*10 и более в языке Фортран и long double в С)

Число в представлении с простой точностью занимает 32 двоичных разряда: 23 разряда занимает мантисса и 8 разрядов отведено для порядка. Старший разряд является знаковым.

Числа с плавающей точкой хранятся в нормализованном виде:

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

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

Мантисса нормализованного числа, если она не равна нулю, принадлежит диапазону [0.5, 1), в общем случае:

Порядок задается в формате с избытком (смещением) - истинное значение порядка увеличивается на 127, сумма всегда положительна. Фактическое значение порядка находится в промежутке от -126 до +127. Основанием является 2.

Младший бит мантиссы в формате с простой точностью представляет значение 2-24 (примерно 10-7), что соответствует 7 значащим цифрам десятичного представления.

Значащие цифры числа допускают точное представление. Следующие значения имеют одинаковое (равное четырем) число значащих цифр: 3.142, 0.003142, 3.142е3.

В формате с простой точностью не имеет смысла хранить значения, содержащие более 8 десятичных разрядов мантиссы. Минимальное значение порядка -126 определяет минимальное по модулю, отличное от нуля, машинное число (около 1.17х10-38). Максимальное значение порядка составляет 127, что приблизительно соответствует значению 1.70х1038.

Число в представлении с двойной точностью занимает 64 двоичных разряда, из которых 52 разряда отводятся мантиссе и 11 разрядов порядку.

Для чисел с двойной точностью в десятичной системе диапазон значений составляет 2.22х10-308 до 1.79х10308

Количество значащих цифр и пределы изменения в этом случае больше, чем в формате с простой точностью (до 16 значащих цифр).

Расширенный формат используется для повышения точности промежуточных результатов вычислений. Диапазон значений от 3.4х10-4932 до 1.2х104932.

Рассмотрим полученные знания на примере числа, заданного в моем варианте курсового проекта:

C1 70 FD A4

Где 1 в старшем разряде (стоит помнить, что старший разряд тут A4, т. е. с конца) - знак числа, в нашем случае, как видно, отрицательный.

Последующие 8 разрядов - это смещенный порядок (01001001), т. е. в нашем случае это 4916 и 7310. Теперь, что бы найти знак числа и модуль порядка, нужно отнять из этого числа порядок смещения p128. В 16-ричной системе это 4916-8016. Очевидно, что порядок отрицательный, поэтому, как и будет происходить в моей программе, делаем наоборот: 8016-4916=3716. Это и есть модуль порядка. Теперь необходимо вернуть мантиссе 1 в старший разряд (так называемый неявный бит). Но т. к. она была и так, то ничего не меняется, и мантисса остается FD 70 C1 (в памяти мантисса будет выглядеть наоборот, т. к., по условию задания, старший байт числа записывается в старшем адресе).

. Практическая часть. Блок-схема

Подпрограмма вывода служебных слов и полученных данных.

.1 Распределение памяти и листинг программы с комментарием

До старта программы в памяти находятся:

После выполнения программы, в памяти появятся:

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

Проверим одно из тестируемых чисел вручную.

Возьмем:

3E 2F CC

Сразу видно, что знак числа 1 - т. е. отрицательный. Порядок следующие 8 битов - 00000010, т. е. 210. Если вычесть по модулю из 2 смещение порядка 128, то получим 126, что в 16-ричной системе есть 7E. Вернув мантиссе в первый бит старшего байта 1, получим 10111110, что есть BE. Таким образом мантисса будет выглядеть BE 2F CC. Таким образом, т. к. в программе вышли те же значения, можно сделать вывод, что она работает корректно, ч.т.д.

Служебные слова:

В программе были задействованы служебные слова (см. скриншот выше), закодированные в КОИ-7. Они расположены в ячейках памяти 504F-507E и разделены 00 между собой:

4.     

.        Использованные при проектировании средства

система счисление подпрограмма данные

При проектировании был использован ноутбук Acer Aspire 5530 с техническими характеристиками:

Процессор: AMD Athlon X2 Dual-Core 1900 MHz

Оперативная память: 2048 Мб

Видео-карта: ATI Radeon HD 3200 2048 Мб

Жёсткий диск: 160 Гб

Встроенная клавиатура и компьютерная мышь Genius.

Программное обеспечение на ноутбуке:

Microsoft Windows XP Professional 2002 SP3

OpenOffice Professional 3.3.0Visio Professional 2003

Выводы

Программа спроектирована в соответствии с заданием.

Альтернативные варианты решения, как и всегда в программировании, существуют, но считаю предложенный мной наименее русурсоёмким, а значит наиболее оптимальным. В процессе проектирования был задействован всего 1 флажок (CY) и минимальное количество ячеек памяти. Программа включает в себя 78 строк (байтов) шестнадцатеричного кода и может обработать любое эспоненциальное число в коротком формате.

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

Список использованной литературы

1.      Гиляров В.Н. МикроЭВМ СМ-1800 и её эмулятор на ПК: методические указания. - СПб.: СПбГТИ(ТУ), 2006.

.        Гиляров В.Н. Стандартное программное обеспечение. Монитор: методические указания. - СПб.: СПбГТИ(ТУ), 2006.

.        Гиляров В.Н. Программирование в кодах для микроЭВМ СМ-1800: методические указания. - СПб.: СПбГТИ(ТУ), 2006.

.        Фомин С.В. Системы счисления: лекции по математике. - М.: Наука, 1987.

.        Юров В.И. Assembler: Учебник для вузов. - СПб.: Питер, 2003.