в которой основание s и все коэффициенты еi выражены в новой h-системе, и выполнить в h-системе все необходимые для вычисления этой суммы действия.
Пример 1. Перевести в десятичную систему шестнадцатеричное число у = (2Е5,А)16 . Для этого представляют у в виде:
Пример 2. Перевести в десятичную систему двоичное число z = (11011,101)2 :
Рассмотрим теперь перевод числа из s-системы в h-систему посредством арифметических операций исходной s-системы. В этом случае правила для перевода целых чисел и дробей различны.
Перевод целых чисел
Пусть целое число у, представленное в s-системе, требуется перевести в h-систему. Искомая запись числа у в h-системе имеет вид:
Разделив у на h, получим:
Отсюда
где у1 есть частное от деления числа у на основание системы h, а младшая цифра искомого представления числа у в h-системе есть остаток от этого деления.
Если теперь разделить у1 на h, то получим:
В силу
остаток от второго деления есть цифра у2 следующего разряда в представлении числа у в h-системе и т.д. Таким образом, получаем правило: для перевода целого числа из s-системы счисления в h-систему нужно последовательно делить это число и получаемые частные на Основание h новой системы, представленное в старой s-системе, до тех пор, пока частное не станет меньше h. Старшей цифрой в записи числа в h-системе служит последнее частное, а следующие за ней цифры дают остатки, выписываемые s последовательности, обратной их получению.
Перевод дробных чисел
Перевод в h-систему правильной дроби z представленной в системе счисления с основанием s, означает запись этой дроби в виде:
Умножая z на h получаем:
где у-1 и z1 соответственно целая и дробные части этого произведения. При этом целая часть у-1 есть старшая цифра в представлении числа z в h-системе.
Если теперь умножить на h правильную дробь z1, то целая часть произведения дает следующую цифру у-2 в представлении числа в h системе.
Следовательно, можно сформулировать правило: для перевода правильной дроби из s-системы в систему счисления с основанием h нужно умножить исходную дробь и дробные части получающихся произведений на основание h, представленное в старой s-системе. Целые части получающихся произведений дают последовательность цифр в представлении дроби в h-системе.
Обычно перевод дробей из одной системы в другую производят приближенно.
При переводе неправильной дроби переводят отдельно целую и дробную части, руководствуясь соответствующими правилами.
Прямой, обратный и дополнительный коды
При проектировании вычислительных устройств необходимо решить вопрос о способе представления в машине положительных и отрицательных чисел и о признаке переполнения разрядной сетки. Указанный вопрос решается применением специальных колов для представления чисел. При помощи этих кодов операция вычитания (или алгебраического сложения) сводится к арифметическому сложению. В результате упрощаются арифметические устройства машин.
Для представления двоичных чисел в машине применяют прямой, обратный и дополнительный коды. Во всех этих кодах предусматривается дополнительный разряд для представления знака числа, причем знак «+» кодируется цифрой 0, а знак « -- » - цифрой 1.
Положительные числа при прямом, обратном и дополнительном кодах имеют один и тот же вид, а отрицательные -- различный.
Прямой код (G)пр двоичного числа G = ± 0, г1, г2, … , гn (гi = 1 или 0) определяется условиями:
G при G ? 0
(G)пр =
(1 - G) при G ? 0
Положительное двоичное число с запятой, фиксированной перед старшим разрядом,
G+ = + 0, г1, г2, … , гn
в прямом коде представляется в виде:
(G+) пр = 0, г1, г2, … , гn (1)
Аналогично отрицательное двоичное число:
G- = - 0, г1, г2, … , гn (1a)
(G-) пр = 1, г1, г2, … , гn (2)
Способы представления чисел (1) и (2) называются прямым кодом соответственно положительных и отрицательных двоичных чисел.
Сложение и вычитание в прямом, обратном и дополнительном кодах
Сложение в прямом коде чисел, имеющих одинаковые знаки, выполняется достаточно просто. Мантиссы складываются и сумме присваивается код знака слагаемых. Значительно более сложной является операция алгебраического сложения в прямом коде чисел с раз-
личными знаками. В этом случае приходится определять большое по модулю число, производить вычитание мантисс и присваивать разности знак большего (по модулю) числа. Таким образом, если положительные и отрицательные числа представлены в прямом коде, операции над кодами знаков и мантиссами выполняются раздельно.
Операция вычитания (алгебраического сложения) сводится к операции простого арифметического сложения при помощи обратного и дополнительного кодов, используемых для представления отрицательных чисел в машине. При этом операция сложения распространяется и на разряды знаков, рассматриваемых как разряды целой части числа.
Чтобы представить двоичное отрицательное число (1а) в обратном коде, нужно поставить в знаковый разряд единицу, а во всех других разрядах заменить единицы нулями, а нули -- единицами:
(G-) обр = 1, у1, у 2, … , у n (3)
уi = 1 при гi = 0 и уi = 0 при гi = 1.
При записи отрицательного числа в дополнительном коде ставят единицу в разряд знака, а цифровую часть числа заменяют дополнением модуля числа до целой единицы.
Отрицательное число G- = - 0, г1, г2, … , гn в дополнительном коде имеет вид:
(G-) доп = 1, е1, е 2, … , е n (4)
где
0, е1, е 2, … , е n = 1 - 0, г1, г2, … , гn (4a)
Установим связь между самим отрицательным числом G- и числами (G-)обр и (G-)доп , представляющими его обратный и дополнительный коды.
Вычитая (1а) из (3), имеем:
(G-) обр - G- = 1, у1, у 2, … , у n - ( - 0, г1, г2, … , гn) = 1,11…1 = 2 - 2-n (так как уi + гi = 1)
Следовательно,
(G-) обр = G- + 2 - 2-n (4b)
Вычитая (1a) из (4), имеем:
(G-) доп - G- = 1, е1, е 2, … , е n - ( - 0, г1, г2, … , гn) (5)
Учитывая (4a), получаем:
(G-) доп = G- + 2 (5а)
Из (5) и (5а) следует:
(G-) доп = (G-) обр + 2-n
где n -- число разрядов в числе. Таким образом, дополнительный код может быть получен из обратного путем добавления к нему единицы младшего разряда.
Рассмотрим представление нуля. В процессе вычислений могут возникнуть «положительный» и «отрицательный» нули:
+ 0,00…0 ; - 0,00…0
Представление «положительного» нуля одинаково для прямого, обратного и дополнительного кодов:
(+ 0) пр = 0,00…0
Отрицательный нуль изображается: в прямом коде
(- 0) пр = 0,00…0
в обратном коде
(- 0) обр = 1,11…1
в дополнительном коде
(- 0) доп = 1,11…1 + 2-n = 0,00…0
так как перенос из разряда знака теряется.
Используя обратный или дополнительный код, можно операции вычитания и сложения чисел различных знаков свести к арифметическому сложению кодов чисел.
Рассмотрим использование обратного кода при алгебраическом сложении двух двоичных чисел G и Q, когда одно из них или оба числа отрицательны. Для этого случая может быть сформулировано следующее правило (предполагаем, что модуль алгебраической суммы меньше единицы).
При алгебраическом сложении двух двоичных чисел с использованием обратного кода положительные слагаемые представляются в прямом коде, а отрицательные - в обратном и производится арифметическое суммирование этих кодов, включая разряды знаков, которые при этом рассматриваются как разряды целых единиц. При возникновении переноса из разряда знака единица переноса прибавляется к младшему разряду суммы кодов (такой перенос называется круговым или циклическим). В результате получается алгебраическая сумма в прямом коде, если эта сумма положительна, и в обратном коде, если она отрицательна.
Рассмотрим теперь использование дополнительного кода для алгебраического сложения. Приведем соответствующее правило (полагаем, что модуль алгебраической суммы меньше единицы).
При алгебраическом сложении двух двоичных чисел с использованием дополнительного кода положительные слагаемые представляются в прямом коде, а отрицательные -- в дополнительном и производится арифметическое суммирование этих кодов, включая разряды знаков, которые при этом рассматриваются как разряды целых единиц. При возникновении переноса из разряда знака единица переноса отбрасывается. В результате получается алгебраическая сумма в прямом коде, если эта сумма положительна, и в дополнительном коде, если эта сумма отрицательна.
В самом деле, если G- < 0 и Q- < 0 , то согласно (4b):
(G-) доп + (Q-) доп = G- + 2 + G- + 2 = 2 + (G- + Q- + 2)
Так как -1 < G- + Q- < 0, то величина, стоящая в скобках, меньше двух, но больше единицы. Двойка, стоящая вне скобки, образует перенос из разряда знака, который будет отброшен. В результате получаем:
(G-) доп + (Q-) доп = (G- + Q-) + 2 = (G- + Q-) доп
G+ > 0, а Q- < 0, то
(G+) пр + (Q-) доп = (G+ + Q-) + 2
Если при этом 0 < G+ + Q- < 1, то стоящая вне скобки двойка дает единицу переноса из разряда знака, которая отбрасывается. При этом получаем:
(G+) пр + (Q-) доп = (G+ + Q-) пр
(G+ + Q- > 0)
Если же -1 < G+ + Q- < 0, то (G+ + Q- ) + 2 < 2 и переноса из разряда знака не возникает. В этом случае:
(G+) пр + (Q-) доп = (G+ + Q-) доп
(G+ + Q- < 0).
Применение дополнительного или обратного кода для представления отрицательных чисел упрощает операцию алгебраического сложения. Алгебраическое сложение чисел с разными знаками заменяется арифметическим сложением кодов, при этом автоматически получается код знака результата. Однако остается нерешенным вопрос о выработке признака переполнения разрядной сетки.
При сложении кодов теряется единица переноса из разряда целых единиц и результат ошибочно воспринимается как положительное число, меньшее единицы.
Отметим, что при алгебраическом сложении двух чисел G и Q, каждое из которых по модулю меньше единицы, может возникнуть переполнение разрядной сетки, но при этом модуль получаемой суммы всегда меньше двух. Это обстоятельство облегчает построение кодов, по виду которых можно судить о переполнении разрядной сетки.
Для получения признака переполнения разрядной сетки применяют модифицированные прямой, дополнительный и обратный коды. Эти коды отличаются от ранее рассмотренных кодов тем, что для представления знака используются два разряда.
При этом знак плюс обозначается 00, а знак минус -- 11. При алгебраическом сложении чисел знаковые разряды рассматриваются как разряды целой части числа.
При возникновении переноса единицы из старшего разряда знака эта единица отбрасывается, если отрицательные числа представляются модифицированным дополнительным кодом, или производится циклический перенос в младший разряд мантиссы, если отрицательные числа изображаются модифицированным обратным кодом.
При алгебраическом сложении на переполнение разрядной сетки (модуль алгебраической суммы больше единицы) указывает несовпадение цифр в знаковых разрядах. Комбинации 01 в знаковых разрядах соответствует положительное число, а комбинации 10 -- отрицательное число.
В этих случаях модуль суммы:
1 ? |x| < 2
Отметим также особенности нормализации и выполнения сдвига для отрицательных чисел, представленных в дополнительном (обратном) коде.
У нормализованного положительного или отрицательного числа с мантиссой, изображаемой в прямом коде, цифра в старшем S-ичном разряде мантиссы должна быть отлична от нуля. Для отрицательных мантисс, представленных в обратном или дополнительном коде, условие нормализации |q| ? 1/S выполняется, если цифра в старшем S-ичном разряде мантиссы есть нуль.
В случае чисел с плавающей запятой комбинации 01 и 10 в знаковых разрядах мантиссы указывают на нарушение нормализации влево, а комбинации цифр 00 и 1 уs1 (уs1 ? 0) в младшем знаковом разряде и старшем S-ичном цифровом разряде мантиссы сигнализируют о нарушении нормализации вправо. Для восстановления нормализации производится сдвиг мантиссы вправо (или влево) на нужное число разрядов, при этом порядок увеличивается (уменьшается) на соответствующее число единиц,
Если отрицательные числа представляются в дополнительном (обратном) коде, сдвиг производится по особым правилам («модифицированный сдвиг»), с тем чтобы в результате сдвига дополнительного (обратного) кода числа х на m S-ичных разрядов получился дополнительный (обратный) код числа Smx или S-mх соответственно для сдвига влево или вправо.
При модифицированном сдвиге дополнительного (обратного) кода вправо в освобождающиеся старшие разряды мантиссы записываются единицы, а при сдвиге влево единицы записываются в освобождающиеся младшие разряды.
Деление в прямом, обратном и дополнительном кодах
Деление в вычислительной машине обычно сводится к выполнению последовательности вычитаний делителя сначала из делимого, а затем из образующихся в процессе деления частичных остатков и сдвига частичных остатков на один разряд влево.
Необходимо отметить, что в машинах, оперирующих над числами с запятой, фиксированной перед старшим разрядом, деление возможно только в одном случае, если делимое по модулю меньше делителя. В противном случае частное превышает единицу и выходит за пределы разрядной сетки числа. Если в результате вычитания выясняется, что делимое или очередной частичный остаток больше или равны делителю, то в очередной разряд частного записывается единица и полученный в результате вычитания частичный остаток сдвигается влево на один разряд. Если в результате вычитания выясняется, что делимое или очередной частичный остаток меньше делителя, то в очередной разряд частного записывается нуль, к полученной разрядности добавляется делитель, чтобы восстановить предыдущий частичный остаток, и результат сдвигается влево на один разряд. Метод выполнения деления, когда в случае получения отрицательного остатка при вычитании (частичный остаток меньше делимого) к нему прибавляется делитель, называется методом деления с восстановлением остатка.
Рассмотрим пример деления с восстановлением остатка (см. таблицу). Для выполнения операции вычитания будем использовать дополнительный код. Деление с восстановлением остатка требует в наиболее неблагоприятном случае трёх тактов для формирования одного разряда частного: такта вычитания, такта сложения и такта сдвига.
Рассмотренный метод носит название деления с восстановлением остатка.
Недостатком этого метода является необходимость введения специального третьего такта для восстановления остатка, который значительно замедляет ход вычисления.
Обычно в вычислительных машинах для деления широко используется другой метод, называемый методом выполнения деления без восстановления остатка. Этот метод основан на прямом копировании действий при ручном делении («в столбик»).
При этом методе, если результат вычитания получился отрицательный, частичный остаток не восстанавливается путём прибавления делителя, а на следующем шаге деления вместо вычитания делимого производится его прибавление к частичному остатку. Если результат при этом остался отрицательным, то в очередную цифру частного записывается нуль и на следующем шаге также выполняется сложение. Если результат сложения получился положительным, то в очередной разряд частного записывается единица и на следующем шаге производится вычитание.
Можно показать, что частичные остатки при делении без восстановления остатка получаются такими же, как и остатки после сдвига восстановленного остатка при делении с восстановлением остатка.
Действительно, поскольку сдвиг частичного остатка на один разряд влево эквивалентен умножению его на два, получим:
2a - b = 2(a -b) + b
где a - частичный остаток; b - делитель.
Аналогично:
Деление без восстановления остатка всегда требует для получения одной цифры частного только двух тактов: такта сложения или вычитания и такта сдвига. Тем самым скорость вычисления этим методом оказывается выше чем в методе деления с восстановлением остатка.
Деление правильных дробей выполняется также, как деление целых чисел. Разница же заключается в том, что делимое имеет, как правило, такую же длину, как и делитель. Однако можно предположить, что делимое имеет ещё n младших разрядов, равных 0. Тогда становится ясно, что алгоритм деления дробей ничем не отличается от алгоритма деления целых чисел.
Исходя из рассмотренных методов деления в вычислительных машинах наиболее скоростной и простой метод является метод деления без восстановления остатка, так как при использовании данного метода для получения одной цифры частного необходимо выполнить всего лишь два такта, в то время как в методе с восстановлением частичного остатка для получения одной цифры частного требуется три такта.
Заключение
В данной курсовой работе были рассмотрены различные системы счисления (двоичная, восьмеричная, шестнадцатеричная), элементы двоичной «арифметики» а также реализация способов двоичной арифметики в цифровых вычислительных системах.
В частности были рассмотрены методы двоичного сложения (алгебраического сложения), умножения и деления. Метод двоичного деления был рассмотрен более близко.
Мы рассмотрели два основных метода реализации двоичного деления в цифровых вычислительных системах. Напрашивается вывод:
после глубокого рассмотрения двух методов реализации двоичного деления выяснилось, что метод с восстановлением частичного остатка является трудоёмким и неудобным, а также оказывается очень медленным в силу того, что для нахождения одного числа частного в этом методе требуется совершить три такта (такт вычитания, такт сложения и такт сдвига), в то время когда в методе без восстановления частичного остатка требуется всего лишь два такта (такт сложения(вычитания) и такт сдвига).
Становится ясно, что более эффективным и простым методом для деления двоичных чисел является метод без восстановления частичного остатка, основанный на делении двоичных чисел в прямом, обратном и дополнительном кодах.
Использованная литература
1) Каган Б. М., Каневский М. М. - «Цифровые вычислительные машины и системы» Под. ред. Б. М. Кагана. Изд. «Энергия», М. 1973г.
Страницы: 1, 2, 3
