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

1.

Введение

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

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

Вариант № 1.

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

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

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

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

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

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

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

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

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

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

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

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

4. Мантисса, как трехбайтное целое число в ячейках (600 316−600 516). Старший байт записывается в старшем адресе!

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

2.

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

3.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. Как только разряд достигает предела (т. е. единицы) появляется новый разряд, а старый обнуляется.

0 — это ноль

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

10 — это два

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

100 — это четыре и т. д.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

1 / 2 = 0 (1 остаток) Остатки на каждом шаге — это и есть число 77 в двоичной системе счисления (1 001 101).

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

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

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

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

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

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

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

23 578 = (2· 83)+(3·82)+(5·81)+(7·80) = 2· 512 + 3· 64 + 5· 8 + 7· 1 = 126 310

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

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

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

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

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

333 610: 8 = 41 710

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

41 710: 8 = 5210

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

5210: 8 = 610

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

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

В итоге получим — 64 108.

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

Шестнадцатеричная система счисления — это позиционная система счисления с основанием 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=16 410

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

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

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

25 310: 16 = 1510

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

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

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

3.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 60 559:1989.

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

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

Стандарты 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.3 142, 3.142е3.

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

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

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

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

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

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

C1 70 FD A4

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

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

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

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

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

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

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

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

Возьмем:

81 3E 2 °F CC

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

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

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

4.

5. Использованные при проектировании средства система счисление подпрограмма данные При проектировании был использован ноутбук 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.0

Microsoft Visio Professional 2003

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

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

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

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

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

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

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

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