Формальные правила двоичной арифметики
Популярность двоичной системы счисления во многом определяется простотой выполнения арифметических действий:
В основу арифметико-логического устройства любой ЭВМ может быть положен либо сумматор, либо вычитатель. И в том и в другом случае могут быть разработаны алгоритмы выполнения арифметических операций. В выполнении арифметических действий всегда участвуют два числа или более. В результате арифметической операции появляется новое число
С=АВ, (3.1)
где – знак арифметического действия (сложение, вычитание, умножение, деление).
Операнд – число, участвующее в арифметической операции, выполняемой цифровым автоматом.
Так как цифровой автомат оперирует только автоматными изображениями чисел, то последние выступают в качестве операндов. Следовательно, для машинных операций более правильно выражение (3.1) написать в виде
где в квадратных скобках [ ] – обозначения автоматных изображений операндов.
Рассмотрим формальные правила выполнения арифметических операций сложения и вычитания на уровне разрядов операндов.
На основе правил двоичной арифметики можно записать правила сложения двоичных цифр так, как показано в таблице 3.1, где ai, bi– разряды операндов А и В соответственно; сi– разряд суммы; пi– перенос из данного разряда в соседний старший.
Двоичный полусумматор – устройство, выполняющее арифметические действия по правилам, указанным в таблице 3.1.
Таблица 3.1 Таблица 3.2
Появление единицы переноса при сложении двух разрядов несколько изменяет правила сложения двоичных цифр (табл. 3.2).
Обобщая вышеизложенное, можно сформулировать правила поразрядных действий при сложении операндов А и В:
где пi-1– перенос из (i-1)-го разряда; пi– перенос в (i+1)-й разряд (переносы принимают значения 0 или 1).
Двоичный сумматор – устройство, выполняющее арифметические действия по правилам, указанным в таблице 3.2. Условные обозначения двоичных полусумматоров и сумматоров показаны на рис. 7, а и б соответственно.
Рис. 7. Условное обозначение полусумматора и двоичного сумматора
На основе правил двоичной арифметики можно записать правила вычитания двоичных цифр так, как показано на таблице 3.3, где zi+1– заем в старшем разряде.
Таблица 3.3
Заем равносилен вычитанию единицы из старшего разряда. С учетом единицы заема из старшего соседнего разряда правила вычитания двоичных цифр можно записать так, как показано в таблице 3.4 (чтобы отличить заем от переноса, перед единицей поставлен знак минус).
Таблица 3.4
Если А – уменьшаемое (1-й операнд), В – вычитаемое (2-й операнд), то для поразрядных действий
Двоичный вычитатель – устройство, выполняющее арифметическое действие по правилам, указанным в таблице 3.4.
С точки зрения технической реализации всегда проще сложить два электрических сигнала, чем вычесть их друг из друга. В ЭВМ вместо сложения используется операция вычитания. В подавляющем большинстве ЭВМ основное устройство – двоичный сумматор.
Выполнение арифметических операций над числами с фиксированной и плавающей запятой
Сложение и вычитание
Сложение чисел в форме с фиксированной запятой
Рассмотрим несколько видов двоичных сумматоров.
Двоичный сумматор прямого кода (ДСПК) – сумматор, в котором отсутствует цепь поразрядного переноса между старшим цифровым и знаковым разрядами. На ДСПК можно складывать только числа, имеющие одинаковые знаки, т. е. такой сумматор не может выполнять операцию алгебраического сложения. В самом деле, пусть заданы операнды
где SgА, SgВ– соответственно содержимое знаковых разрядов изображений для А и В (символ происходит от английского слова sign – знак); аi, bi– цифровые разряды изображений.
Если SgА= SgВ, то сумма чисел будет иметь знак любого из слагаемых, а цифровая часть результата получится после сложения цифровых частей операндов.
Пример. Сложить числа А = 0,1011, В= 0,0100 на сумматоре прямого кода.
Решение.
Ответ: [С]пр= 0,1111.
Пример. Сложить числа А = –0,0101, В = –0,1001 на сумматоре прямого кода.
Решение.
Ответ: [С]пр=1,1110.
При сложении чисел на ДСПК возможен случай, когда абсолютное значение суммы операндов превышает единицу. Тогда имеет место переполнение разрядной сетки автомата. Признак переполнения – наличие единицы переноса из старшего разряда цифровой части сумматора. В этом случае должен вырабатываться сигнал переполнения =1, по которому происходит автоматический останов машины и корректировка масштабных коэффициентов с таким расчетом, чтобы избежать появления переполнения.
Двоичный сумматор дополнительного кода (ДСДК) – сумматор, оперирующий изображениями чисел в дополнительном коде. Характерная особенность ДСДК – наличие цепи поразрядного переноса из старшего разряда цифровой части в знаковый разряд. Определим правила сложения чисел на ДСДК.
Теорема 3.1. Сумма дополнительных кодов чисел есть дополнительный код результата.
Пример. Найти сумму чисел А =0,1010, В =0,0100, используя сумматор дополнительного кода.
Решение. Складываются машинные изображения этих чисел:
Ответ: С =0,1110.
Пример. Найти сумму чисел А = –0,1011, В = 0,0100 на сумматоре дополнительного кода.
Решение.
Ответ: С =–0,0111.
Пример. Найти сумму чисел А=0,1011, В =–0,0100 на сумматоре дополнительного кода.
Решение.
Ответ: С = 0,0111.
Двоичный сумматор обратного кода (ДСОК) – сумматор, оперирующий изображениями чисел в обратном коде. Характерная особенность ДСОК – наличие цепи кругового, или циклического, переноса из знакового разряда в младший разряд цифровой части. Определим правила сложения чисел на ДСОК.
Теорема 3.2. Сумма обратных кодов чисел есть обратный код результата.
Таким образом, на ДСОК машинные изображения чисел также складываются по правилам, приведенным в таблице 3.2.
Пример. Найти сумму чисел А=0,0101 и В =0,0111, используя сумматор обратного кода.
Решение.
Ответ: С =0,1100.
Пример. Найти сумму чисел А = –0,0101 и В = 0,0111, используя ДСОК
Решение.
Ответ: С =0,0010.
Пример. Найти сумму чисел А =0,0101 и В =–0,0111, используя ДСОК.
Решение.
Ответ: С =–0,0010.
Пример. Найти сумму чисел А =–0,0101 и В =–0,1000, используя ДСОК.
Решение.
Ответ: С =–0,1101.
В дальнейшем для упрощения записи передача циклического переноса будет осуществляться сразу при получении результата и отдельно фиксироваться не будет.
Переполнение разрядной сетки
При сложении чисел одинакового знака, представленных в форме с фиксированной запятой, может возникнуть переполнение разрядной сетки.
I. Признак переполнения разрядной сетки сумматора прямого кода – появление единицы переноса из старшего разряда цифровой части числа.
Пример.
II. Признак переполнения разрядной сетки сумматора дополнительного кода при сложении положительных чисел – отрицательный знак результата, а при сложении отрицательных чисел – положительный знак результата.
Пример.
III. Признак переполнения разрядной сетки сумматора обратного кода – знак результата, противоположный знакам операндов.
Пример.
Для обнаружения переполнения разрядной сетки в составе цифрового автомата должны быть предусмотрены аппаратные средства, автоматически вырабатывающие признак переполнения – сигнал .
Чтобы обнаружить переполнение разрядной сетки ДСОК и ДСДК, вводится вспомогательный разряд в знаковую часть изображения числа (рис. 8, а), который называют разрядом переполнения. На рис. 8, б,в соответственно представлены изображения положительного и отрицательного чисел. Такое представление числа называется модифицированным. Тогда в случае появления переполнения сигнал = 1:
в остальных случаях = 0.
Рис. 8. Представление чисел в модифицированном коде
Это подтверждается следующими примерами.
Особенности сложения чисел в форме с плавающей запятой
Числа, представленные в форме с плавающей запятой, изображаются двумя частями – мантиссой и порядком. При операции алгебраического сложения действия, выполняемые над мантиссами и порядками, различны. Следовательно, в цифровом автомате должны быть два раздельных устройства для обработки мантисс и для обработки порядков.
Так как для чисел с плавающей запятой справедливо условие
<1, (3.1)
где q – основание системы счисления, то всякий результат, не удовлетворяющий этому условию, должен быть приведен в соответствие с этой формулой. Такую операцию называют нормализацией числа. Операция нормализации числа состоит из проверки выполнимости условия (3.1) и сдвига изображения мантиссы в ту или иную сторону. Сдвиги могут осуществляться на один разряд и более в левую или правую сторону в пределах разрядной сетки машины.
Простой сдвиг – операция, выполняемая по следующим правилам:
Модифицированный сдвиг – операция над модифицированными изображениями, выполняемая следующим образом:
Нарушение нормализации числа – невыполнение условия (3.1). Так как условие (3.1) содержит два неравенства, то может быть нарушение справа и слева. Признак нарушения нормализации числа справа (когда величина результата равна или превышает единицу) – наличие разноименных комбинаций в знаковых разрядах сумматора, т. е.
(в остальных случаях =0), где – признак нарушения нормализации числа справа, указывающий на необходимость сдвига числа вправо на один разряд.
Признак нарушения нормализации числа слева (когда результат по собственной величине оказывается меньше 1/q) – наличие одинаковых комбинаций в разряде переполнения и старшем разряде цифровой части сумматора (p1):
(в остальных случаях =0), где – признак нарушения нормализации, указывающий на необходимость сдвига числа влево на один разряд.
Таким образом, операция нормализации числа состоит из совокупности сдвигов и проверки наличия признаков нарушения и .
Рассмотрим сложение чисел А =mApAи В =mBpB, имеющих одинаковый порядок рA= pB. Обе мантиссы удовлетворяют условию нормализации.
Сложение мантисс осуществляется на соответствующем сумматоре по правилам, изложенным ранее для чисел, представленных в форме с фиксированной запятой. Если после сложения мантисса результата удовлетворяет условию нормализации (т.е. =0, =0), то к этому результату приписывается порядок любого из операндов. В противном случае происходит нормализация числа.
Пример. Найти сумму чисел А=0,1000·2-3и В=–0,1011·2-3, если мантиссы и порядок обрабатываются на сумматорах дополнительного кода (шесть разрядов для мантиссы и четыре разряда для порядка).
Решение. Сначала записываются машинные изображения операндов:
а затем мантиссы складываются:
Здесь Sg2 p1= 1, т.е. =1, =0, значит необходим сдвиг мантиссы влево на разряд:
[m’c]мд=11,1010, (=1, =0).
Одновременно со сдвигом влево нужна коррекция порядка, т.е. уменьшение его величины на единицу (что равносильно прибавлению кода 1,111):
Так как после сдвига снова =1, то осуществляется еще раз сдвиг и коррекция порядка:
.
Так будет продолжаться до тех пор, пока величина не станет равной нулю. Следовательно, [m’’c]дудовлетворяет условию нормализации и результат равен [m’’c]мд=11,0100, [p’’c]д=1,011.
Ответ: С =–0,1100·2-5.
Пример. Найти сумму чисел А = –0,1100·24и В = –0,1000·24, если числа складываются на сумматоре обратного кода (шесть разрядов для мантиссы и четыре разряда для порядка).
Решение. Машинные изображения операндов записываются в следующем виде:
Затем складываются мантиссы:
Здесь произошло нарушение нормализации справа и требуется модифицированный сдвиг мантиссы результата вправо на один разряд:
Одновременно со сдвигом проводится коррекция порядка результата на величину +0,001, или [p’c]об= 0,100+0,001 = 0,101, в результате получается окончательный результат.
Ответ: С =–0,1010·25.
Рассмотрим наиболее общий случай сложения чисел, представленных в форме с плавающей запятой, когда их порядки не равны друг другу, т.е. pApB. Для операции сложения чисел необходимым условием является соответствие разрядов операндов друг другу. Значит, прежде всего нужно уравнять порядки, что, естественно, повлечет за собой временное нарушение нормализации одного из слагаемых. Выравнивание порядков означает, что порядок меньшего числа надо увеличить на величину р=|рА–рВ|, что означает сдвиг мантиссы меньшего числа вправо на количество разрядов, равное р.
Следовательно, цифровой автомат должен самостоятельно определять, какой из двух операндов меньший. На это укажет знак разности рА–рВ: положительный знак будет при рА = рВ, а отрицательный – при рА < рВ.
Операции сложения и вычитания чисел в форме с плавающей запятой осуществляются во всех современных машинах по изложенным выше правилам.
Пример. Сложить числа А=0,1011·2-2и В=–0,1001·2-3на сумматорах обратного кода (шесть двоичных разрядов для мантиссы и четыре двоичных разряда для порядка).
Решение. Прежде всего записываются машинные изображения чисел и определяется, какой из двух порядков больше:
Величину –[pВ]обобозначим [pВ]об, что означает изменение знака числа рВна обратный, т.е. [pВ]об=0,011. Тогда [p]об=[pА]об+[pВ]об=0,001.
Так как величина p положительна, то рА> рВ. Следовательно, надо сдвинуть мантиссу числа В вправо на количество разрядов, равное p, т. е. на один разряд [mВ]моб=11,1011 (сдвиг модифицированный). Теперь порядки операндов равны, и дальнейшие действия проводятся в последовательности, аналогичной последовательности, рассмотренной в предыдущем примере.
Складываются изображения мантисс
Осуществляется нормализация мантиссы (=1) и соответствующая коррекция порядка:
Так как нарушений нормализации нет, то получен окончательный результат.
Ответ: С =0,1110·2-3.
Пример. Сложить числа А и В, заданные в форме с фиксированной точкой:
mA=100110; ХA=101; mB=–111001; ХB=011.
Для выполнения операции сложения использовать сумматор дополнительного кода, имеющий семь битов для мантиссы со знаком, четыре бита для характеристики со знаком.
Решение. Запишем машинные изображения мантисс:
[mA]мд=00,100110, [mВ]мд=11,000111.
Исходные числа в памяти машины можно хранить либо в прямом, либо в обратном (дополнительном) кодах. Если числа хранятся в памяти машины в прямом коде, то при выполнении операции сложения (вычитания) на сумматорах обратного (дополнительного) кода необходимо провести преобразование из прямого кода в обратный (дополнительный) код. По окончании операции должно проводиться преобразование результата из обратного (дополнительного) кода в прямой.
При выполнении данного примера предполагается, что числа в памяти машины хранятся в дополнительном коде.
Прежде всего необходимо сравнить характеристики:
.
Разность характеристик – положительная: второй порядок меньше первого на 2. Следовательно, мантисса второго числа сдвигается на два разряда (сдвиг модифицированный) и после этого мантиссы складываются:
.
Так как =1, то проводится сдвиг влево на один разряд с коррекцией характеристики:
[m’С]д=00,101110 (=0, =0), [XС]д=0,101+1,111=0,100.
Таким образом, окончательный результат получен в нормализованном виде.
Ответ: С=+101110, ХС=100.
Последний пример приведен для случая, когда мантисса – целое число и представляется в форме с фиксированной точкой перед старшим разрядом. Сформулированные выше правила выполнения алгоритма алгебраического сложения действуют в данном случае без существенных изменений.
При реализации операций сложения (вычитания) чисел, представленных в форме с плавающей запятой, может возникнуть переполнение разрядной сетки сумматора порядков (характеристик): мантисса получается нормализованной и правильной, а порядок (характеристика) не соответствует. Следовательно, необходимо вырабатывать сигнал переполнения сумматора порядков.
Умножение двоичных чисел
Умножение чисел в форме с фиксированной запятой на сумматоре прямого кода
Пусть заданы машинные изображения двух чисел:
Тогда их произведение
где Sgc= SgA SgB; – знак сложения по модулю 2.
Применительно к двоичной системе счисления наиболее известны следующие основные способы выполнения операции умножения:
1) умножение, начиная с младших разрядов множителя:
2) умножение, начиная со старших разрядов множителя:
В обоих случаях операция умножения состоит из ряда последовательных операций сложения частных произведений. Операциями сложения управляют разряды множителя: если в каком-то разряде множителя находится единица, то к сумме частных произведений добавляется множимое с соответствующим сдвигом; если в разряде множителя – нуль, то множимое не прибавляется.
При точном умножении двух чисел количество цифр в произведении превышает количество цифр сомножителей не более чем в два раза. При умножении нескольких чисел количество цифр произведения может оказаться еще больше. Конечное число разрядов в устройствах цифрового автомата вынуждает ограничиваться максимально удвоенным количеством разрядов сумматоров.
При ограничении количества разрядов сумматора в произведение вносится погрешность. В случае большого объема вычислений погрешности одного знака накладываются друг на друга, в результате чего общая погрешность сильно возрастает. Поэтому существенное значение имеет округление результатов умножения, что дает возможность сделать погрешность произведения знакопеременной, а математическое ожидание погрешности округления при условии, что отброшенные младшие разряды могут с одинаковой вероятностью иметь любое из возможных значений, – равным нулю. При этом предельное по абсолютной величине значение погрешности будет наименьшим из возможных при заданном количестве значащих цифр, т. е. равным половине значения младшего разряда.
При выполнении операции умножения чисел возможен выход за пределы разрядной сетки только со стороны младших разрядов в силу ограничения, которое было наложено на числа, представленные в форме с фиксированной запятой.
Пример. Умножить числа [А]пр= 1,11010 и [В]пр= 0,11001.
Решение. Знак произведения определяем отдельно от цифровой части в соответствии с уравнением
Получение цифровой части можно показать в виде следующей записи:
11001
11010
1010001010.
Ответ: [С]пр= 1,1010001010.
Особенности умножения чисел, представленных в форме с плавающей запятой
Для чисел, представленных в форме с плавающей запятой, обязательным является представление в виде мантиссы и порядка (характеристики). При операции умножения действия, выполняемые над мантиссами и порядками, различны: мантиссы перемножаются, порядки складываются. Результат умножения может получиться ненормализованным, тогда потребуется нормализация с соответствующей коррекцией порядка результата.
Рассмотрим пример выполнения операций умножения чисел, заданных в прямом коде.
Пример. Перемножить числа А =–0,110012-3и В=0,100112+1.
Решение. Мантиссы перемножаются по правилам, рассмотренным для чисел, представленных в форме с фиксированной запятой. Для перемножения мантисс используется сумматор прямого кода, а для сложения порядков – сумматор обратного кода.
Сначала запишем машинные изображения чисел:
Выполняем операцию умножения мантисс:
10011
11001
111011011.
Знак произведения определяем отдельно от цифровой части в соответствии с уравнением
После выполнения указанных действий находим мантиссу произведения
[mc]пр=1,111011011.
Над порядками проводим операцию сложения
[pС]об=[pА]об+[pВ]об= 1,100+0,001 = 1,101.
Ответ: С =–0,1110110112-2.
Деление двоичных чисел
Деление чисел в форме с фиксированной запятой
Деление двоичных чисел во многом аналогично делению десятичных чисел. Процесс деления состоит в том, что последовательно разряд за разрядом отыскиваются цифры частного путем подбора с последующим умножением этой цифры на делитель и вычитанием этого произведения из делимого.
Из множества разных методов выполнения операции деления наиболее распространенным является “школьный” алгоритм деления, заключающийся в том, что делитель на каждом шаге вычитается столько раз из делимого (начиная со старших разрядов), сколько это возможно для получения наименьшего положительного остатка. Тогда в очередной разряд частного записывается цифра, равная числу делителей, содержащихся в делимом на данном шаге. Таким образом, весь процесс деления сводится к операциям вычитания и сдвига.
В универсальных вычислительных машинах, как правило, реализуется разновидность “школьного” алгоритма деления.
В общем случае “школьный” алгоритм деления на примере двоичных чисел выглядит следующим образом:
делимое – 1100100 |1010 – делитель
–1010 |1010 – частное
101
–1010
00 – остаток
Здесь цифры частного получаются последовательно, начиная со старшего разряда, путем вычитания делителя из полученного остатка. Если получен положительный остаток, то цифра частного равна единице; если остаток отрицательный, то цифра частного равна нулю, при этом восстанавливается предыдущий положительный остаток. Такой алгоритм деления получил название алгоритма деления с восстановлением остатка.
Особенности деления чисел, представленных в форме с плавающей запятой
Для получения частного от деления двух чисел, представленных в форме с плавающей запятой, необходимо определить mC= mA /mB, pC= pA–pB.
Так как мантиссы делимого и делителя – нормализованные числа, при делении возможны случаи, когда |mA||mВ|; |mA|<|mВ|.
Если мантисса делимого больше или равна мантиссе делителя, то в конце операции деления потребуется нормализация частного (нарушение правой границы). Таким образом, алгоритм деления начинается с операции вычитания делителя из делимого и записи единицы в целую часть частного. Все остальные действия над мантиссами аналогичны действиям над числами, представленными в форме с фиксированной запятой.
Если мантисса делимого меньше мантиссы делителя, то после операции вычитания на первом шаге получится отрицательный остаток, что означает нуль в целой части мантиссы частного и продолжение алгоритма деления по рассмотренным выше правилам для чисел, представленных в форме с фиксированной запятой. Таким образом, частное всегда получается в прямом коде.
Пример. Разделить число А=0,10001111·23на 5=0,1111·22.
Решение. Рассматривается случай, когда |mA|<|mВ|.
Выполняем операцию деления мантисс:
10001111 |1111
10001 |01001
– 1111
101
1011
– 1111
Одновременно вычислим порядок частного следующим образом:
pС=pА–pВ= 0,011–0,010=0,001
и определим знак частного SgС=0 0=0.
Ответ: С=0,1001·21.