Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Арифметические операции
В настоящем разделе рассмотрим некоторые правила выполнения основных арифметических операций над числами в системах счисления с основанием 2, 8, 10 и 16 представленных в прямом, обратном или дополнительном коде.
Операция изменения знака
Выполнение операции изменения знака числа сводится:
• в прямом коде – к инвертированию знакового разряда кода;
• в обратном коде – к инвертированию знакового разряда и замене цифр всех значащих разрядов кода обратными;
• в дополнительном коде – к инвертированию знакового разряда и к вычислению дополнения значащих разрядов кода до веса знакового разряда.
Правило изменения знака в прямом коде очевидно. Правила изменения знака в обратном и дополнительном кодах следуют из правил преобразования прямого кода в обратный или в дополнительный код и наоборот, но не совпадают с последними. При преобразовании кодов знак сохраняется, а при изменении знака он инвертируется. В остальном правила аналогичны.
Внимание. В дополнительном коде нельзя изменить знак минимального числа (отрицательного максимального по модулю) при сохранении формата. Это следует из асимметрии представления чисел в дополнительных кодах. Если формат расширять нельзя, то изменению знака должна предшествовать проверка кода операнда на значение 1⎢00…0доп с последующим блокированием выполнения операции либо приняты меры для исключения образования этого значения на предшествующих этапах вычислений.
Следующие примеры пар кодов иллюстрируют результаты изменения знака операнда в различных кодах и системах счисления:
|
0⎢1011 1002п |
0⎢7657 1008д |
0⎢1011 1002о |
0⎢9AF0 3616о |
0⎢3764 4308о |
|
1⎢1011 1002п |
1⎢0120 7008д |
1⎢0100 0112о |
1⎢650F C916о |
1⎢4013 3478о |
|
1⎢F876 AB016д |
0⎢1011 1002д |
1⎢4019 34710о |
0⎢7345 4268п |
1⎢9876 20010д |
|
0⎢0789 55016д |
1⎢0100 1002д |
0⎢5980 65210о |
1⎢7345 4268п |
0⎢0123 80010д |
Сложение и вычитание чисел без знака
Сложение и вычитание беззнаковых чисел происходит по обычным для
позиционных систем счисления алгоритмам. Примеры (для n =3):
|
0012 +1002 = 1012 |
1012 – 0102 = 0112 |
Ситуации, когда уменьшаемое меньше вычитаемого или когда результат суммы не умещается в n разрядов, считаются ошибочными и должны отслеживаться устройством компьютера. Реакция на такие ошибки может быть различной в разных типах компьютеров.
Сложение
Операция алгебраического сложения в дополнительном коде
Как было отмечено ранее, алгоритмы выполнения операции алгебраического сложения в прямых кодах относительно сложны. В обратном и дополнительном кодах сложение выполняется проще, поскольку не возникает необходимость в анализе знаков операндов, в сравнении их модулей и т.п.
Сложение в дополнительном коде сводится к сложению одноименных разрядов чисел, начиная с младшего разряда включая знаковый разряд, с учетом переноса из предыдущего разряда. Знаковые разряды складываются по правилам сложения двоичных цифр с учетом переноса из предшествующего разряда. Перенос из знакового разряда отбрасывается. Полученный результат представлен в дополнительном коде.
Рассмотрим примеры сложения чисел в дополнительном коде. При их анализе обратите внимание на то, как складываются знаковые разряды.
Пусть операнды – десятичные числа –231,15 и +215,04. Их сумма равна –016,11.
Дополнительные коды операндов и суммы соответственно равны 1⎜768.85 0⎜215.04 и 1⎜983.89. Выполним сложение операндов в дополнительном коде:
Пусть десятичные операнды равны –231,15 и –215,04. Их сумма равна
–446,19.
Дополнительные коды операндов и суммы: 1⎜768.85, 1⎜784.96 и 1⎜553.81. Выполним сложение дополнительных кодов слагаемых:
Примеры сложения двоичных чисел в дополнительном коде:
При сложении одноразрядных двоичных, восьмеричных или шестнадцатеричных чисел следует пользоваться таблицами сложения цифр в этих системах счисления или следующим правилом. Если количественному эквиваленту суммы цифр соответствует цифра из алфавита системы счисления, то перенос в следующий разряд равен нулю, а сумма равна цифре
соответствующей количественному эквиваленту суммы. Если количественный эквивалент суммы цифр больше количественного эквивалента максимальной цифры алфавита, то перенос в следующий разряд равен единице, а цифра суммы имеет количественный эквивалент суммы уменьшенный на основание системы счисления.
Например, в восьмеричной системе счисления 3+2=5 и перенос равен 0. Сумма 4+6=2 и перенос равен 1, так как количественный эквивалент суммы 4+6>7 (4+6=1010), а количественный эквивалент единицы переноса в восьмеричной системе счисления равен 8.
В шестнадцатеричной системе счисления 4+6=А (А имеет количественный эквивалент 1010) и перенос равен 0. Сумма 4+А=Е (Е=1410) и перенос равен 0. Сумма А+А=4 и перенос равен 1 так как вес переноса равен 1610, а А+А=2010.
Примеры сложения шестнадцатеричных чисел в дополнительных кодах.
Операция алгебраического сложения в обратном коде
Сложение в обратном коде выполняется также как и в дополнительном коде, но с той разницей, что перенос из знакового разряда не отбрасывается, а прибавляется к младшему разряду промежуточной суммы. Этот перенос называют циклическим. Результат сложения будет получен в обратном коде.
Примеры сложения двоичных чисел в обратном коде:
Примеры сложения восьмеричных чисел в обратном коде:
Сложение в обратном коде можно начинать с любого, необязательно с младшего разряда, что в некоторых случаях может быть полезно при реализации устройств.
Циклическое распространение переноса при сложении является серьезным недостатком обратного кода по сравнению с дополнительным кодом. Поэтому, несмотря на простоту преобразования прямого кода в обратный код и наоборот, и на простоту изменения знака числа в обратном коде, обратный код сравнительно редко применяют в устройствах вычислительной техники и автоматики.
Переполнение разрядной сетки при сложении
При ограниченной разрядной сетке диапазон представления чисел ограничен. Поэтому сумма двух операндов принадлежащих диапазону может оказаться за его пределами, что приведет к существенной ошибке в вычисленной сумме. Например, пусть в двоичном дополнительном пятиразрядном коде представлены целые положительные операнды со знаком 0⎢0111 (+7) и 0⎢1100 (+12). Сложим их по правилу сложения в дополнительном коде. Величина ошибки недопустимо велика и вызвана выходом правильного значения суммы 0⎢10011 (+19) за пределы диапазона (+15; –16) представления целых со знаком в двоичном дополнительном коде в выбранной пятиразрядной сетке. Такое явление называют переполнением разрядной сетки.
В ЭВМ применяют аппаратуру контроля переполнения разрядной сетки, назначение которой состоит в формировании сигнала R=1 при переполнении. В основу функционирования аппаратуры контроля могут быть положены различные алгоритмы.
Очевидно, что при сложении операндов с разными знаками модуль суммы меньше модуля любого из операндов. Поэтому при разных знаках операндов результат не может выйти за пределы диапазона представления чисел и, следовательно, R=0.
Переполнение разрядной сетки суммы может возникнуть только при одинаковых знаках операндов.
Если операнды положительны и их сумма не укладывается в диапазон представимых чисел, то при их сложении в дополнительном коде образуется перенос из старшего значащего разряда в разряд знака, который приводит к формированию ошибочного отрицательного результата. Поэтому признак переполнения при положительных операндах an⎢an–1…a1a0a–1a–2…am и
bn⎢ bn–1…b1b0b–1b–2…bm можно описать двумя вариантами булевого выражения:
где Sn – знаковый разряд суммы; pn – перенос в знаковый разряд.
Если оба операнда отрицательны и сумма выходит за пределы диапазона представляемых чисел, то отсутствие переноса в знаковый разряд приводит к ошибочному положительному результату. Поэтому признаки переполнения при отрицательных операндах – положительный знак результата или отсутствие переноса в знаковый разряд:
Сказанное позволяет определить булевы уравнения, описывающие варианты комбинационных схем вычисляющих признак переполнения разрядной сетки суммы:
Если R=1, то код суммы содержит ошибку.
Существует простой способ ее устранить. Для этого достаточно
• в двоичной системе счисления приписать к ошибочному результату слева знаковый разряд любого из операндов;
• в восьмеричной, десятичной и шестнадцатеричной системах счисления приписать к ошибочному результату слева знаковый разряд любого из операндов и, если знаковый разряд ошибочного результата равен нулю, заменить его на 6, 8 или E соответственно.
Например,
Вычитание
Вычитание в дополнительном коде сводится к вычитанию одноименных разрядов чисел, начиная с младшего разряда и включая знаковый разряд, с учетом заёма из предыдущего разряда. Знаковые разряды вычитаются по правилам вычитания двоичных цифр с учетом заёма из предшествующего разряда. Заём из знакового разряда отбрасывается. Полученный результат представлен в дополнительном коде.
Примеры вычитания двоичных чисел в дополнительном коде:
Примеры вычитания шестнадцатеричных чисел в дополнительном коде:
Вычитание в обратном коде отличается от вычитания в дополнительном коде тем, что заём из знакового разряда не отбрасывается, а вычитается из младшего разряда промежуточной разности. Этот заём называют циклическим. Результат вычитания будет получен в обратном коде. Вычитание можно выполнять, начиная с любого разряда.
Примеры вычитания двоичных чисел в обратном коде:
Переполнение разрядной сетки при вычитании
Переполнение разрядной сетки при вычитании может произойти только при разных знаках операндов. Если знак уменьшаемого 0, а вычитаемого 1, то знак разности должен быть 0. При переполнении разрядной сетки знак разности будет 1 из-за отсутствия заёма.
Поэтому признак переполнения можно описать выражениями:
где dn – знаковый разряд разности; un – заём из знакового разряда.
Если знак уменьшаемого 1, а вычитаемого 0, то знак разности должен быть 1. В этом случае признак переполнения описывается выражениями:
Признак переполнения при вычитании описывается уравнениями:
При R=1 дополнительный код правильного значения разности можно получить, приписав к результату слева знак уменьшаемого и считать, что все остальные разряды являются значащими. Например:
Замена операции вычитания сложением и наоборот
Можно вычислить разность Z=X–Y не путем вычитания Y из значения X, а посредством сложения X с (–Y). Действительно:
Это позволяет строить устройство для вычитания (вычитатель) из устройства изменения знака и сумматора.
Напротив, можно исключить выполнение операции сложения, заменив ее операциями изменения знака второго операнда с последующим вычитанием его из первого операнда. Действительно:
Эта возможность никак не зависит от системы счисления и от того, в каких кодах выполняется сложение или вычитание.
Операция алгебраического умножения
Умножение в прямом коде
Результат умножения в прямом коде двух операндов без знака содержащих n и m значащих разрядов имеет n+m значащих разрядов. В частном случае, если n=m разрядность результата вдвое превышает разрядность операндов.
При умножении операндов со знаком и n значащими разрядами образуется произведение, содержащее 2n+1 разряд. Поэтому при записи произведения в формате, вдвое превышающем формат операндов, существует слева один избыточный значащий разряд, в который следует записывать 0. Например, если операнды со знаком представлены в прямом коде в шестнадцатиразрядном формате, то значащих разрядов 15, а разрядность произведения, включая его знак, 2×15+1=31. Поэтому в 32 разрядный формат придется записывать 0 в разряд, следующий за разрядом знака.
Знак произведения вычисляют путем сложения по модулю 2 знаковых разрядов операндов. Значащие разряды произведения вычисляют, перемножая операнды как числа без знака. Результат умножения XY целых без знака должен быть равен результату Y-кратного сложения X с самим собой. Дробные числа перемножают как целые, а положение запятой в произведении определяют, отсчитывая, справа налево столько разрядов, сколько дробных разрядов в операндах вместе.
При умножении вычисляют частные произведения множимого X на каждый разряд множителя Y. Суммируют частные произведения с учетом веса каждого из них равного весу разряда множителя. Вес частного произведения учитывают сдвигом его влево на необходимое число разрядов относительно частного произведения X на младший разряд Y.
При вычислении частных произведений в системе счисления с основанием P>2 необходимо учитывать переносы в старшие разряды, возникающие при умножении цифры X на цифру Y. В двоичной системе такие переносы отсутствуют, что существенно упрощает процесс умножения в двоичной системе счисления.
Таблицы умножения цифр системы счисления можно получить, перемножив количественные эквиваленты ее цифр и представив результаты в этой системе счисления. Например, произведение цифр 9×F шестнадцатеричной системы счисления имеет количественный эквивалент 910×1510=13510, или 8716. Следовательно, результат в данном разряде равен 716, и перенос в следующий разряд равен 816.
В двоичной системе счисления частное произведение X на цифру Y равно 0, если цифра Y равна 0, или оно равно X, если цифра Y равна 1. Это существенно упрощает вычисление частных произведений в двоичной системе.
Например, пусть необходимо перемножить прямые двоичные коды чисел 0⎢1101.01 и 1⎢1011.10. Определим знак результата: 0⊕1=1 – знак произведения минус. Найдем матрицу частных произведений значащих разрядов:
первая и предпоследняя строки матрицы нулевые, так как они содержат частные произведения X на младший и предпоследний разряды Y равные нулю. Остальные строки содержат X, так как соответствующие им разряды Y содержат 1. Каждое последующее частное произведение сдвинуто на разряд влево относительно предыдущего, чтобы учесть его вес;
произведение можно вычислять путем суммирования частных произведений так, как это обычно делают в десятичной системе счисления. Причем порядок суммирования цифр столбца и переносов в столбец не играет роли.
Умножение в дополнительном коде.
Если операнды представлены в дополнительном коде и содержат по n значащих разрядов, то количество значащих разрядов в их произведении равно 2n+1. Это на один разряд больше, чем при умножении в прямом коде. Поэтому, например, при умножении двоичных дополнительных кодов операндов представленных в 16 разрядном формате необходимо для хранения произведения использовать все разряды 32 разрядного формата.
Старший дополнительный значащий 2n+1 разряд дополнительного кода положительного произведения принимает значение 1 только в том случае, когда оба операнда отрицательны и все их значащие разряды равны 0. Это вызвано асимметрией представления чисел в дополнительном коде. Дополнительный значащий 2n+1 разряд отрицательного произведения всегда содержит цифру обратную нулю: 1 в двоичной, 9 в десятичной, F в шестнадцатеричной системах счисления.
Например. Пусть в десятичной системе счисления X=Y=1|00доп (–10010). Тогда произведение XY = 0|10000 (+1000010) и содержит 5, а не 4, как можно было бы ожидать, значащих разрядов.
Знак произведения равен сумме по модулю 2 знаковых разрядов операндов.
Таким образом, по крайней мере, два разряда произведения – знаковый и дополнительный можно вычислять, не выполняя собственно умножения.
Остальные разряды дополнительного кода произведения можно вычислять разными способами. Рассмотрим некоторые из них.
Умножение в дополнительном коде выполняется с промежуточным преобразованием операндов в прямой код и результата – в дополнительный. Очевидно, что изложенный способ умножения дополнительных кодов операндов значительно сложнее способа умножения в прямом коде, что усложняет аппаратуру и замедляет процесс вычислений.
Умножение без преобразования в прямой код с введением корректирующих поправок в результат
Если перемножать значащие разряды дополнительных кодов операндов так, как это делали в прямом коде, то результат получится верным, если знаки операндов положительные. Это следует из того, что дополнительные коды положительных операндов и положительного результата совпадают с их прямыми кодами. При отрицательных знаках операндов результат умножения ошибочен.
Выполним анализ ошибки. Найдем значение результата умножения отрицательных чисел и сравним его с правильным значением.
Пусть операнды X<0, а Y≥0. Так как операнды представлены в дополнительном коде, то количественные эквиваленты значащих разрядов их кодов будут равны Pn−|X| и |Y|. Здесь Pn – вес знакового разряда (n≥0), а
Pn−|X| – дополнение значения |X| до Pn. Количественный эквивалент кода значащих разрядов произведения, полученного по правилу умножения в прямом коде, будет равен
Так как правильное значение результата должно быть представлено в дополнительном коде, то его значащие разряды должны содержать код дополнения |XY| до веса знакового разряда произведения. Знаковый разряд произведения должен иметь вес P2n+1, так как количество разрядов в целой части произведения при умножении удваивается и образуется один дополнительный значащий разряд. Следовательно, количественный эквивалент значащих разрядов дополнительного кода произведения должен быть равен
Очевидно, что код результата содержит ошибку, и ее количественный эквивалент
Аналогично, при X≥0 и Y<0 код результата содержит ошибку
Если оба операнда отрицательны X<0, Y<0, то количественный эквивалент кода значащих разрядов произведения получится равным
Так как произведение положительно, правильный код значащих разрядов произведения должен иметь количественный эквивалент |X||Y|.
Ошибка составит величину
Что следует сделать для ликвидации ошибок?
Очевиден первый вариант ответа на этот вопрос – устранять последствия неправильных действий – устранять ошибку путем ее компенсации. В данном случае этот путь поиска вполне реален, так как ошибка детерминирована. Ее можно устранять путем прибавления той или иной корректирующей поправки к результату умножения. Величина корректирующей поправки зависит от знаков операндов.
При несовпадении знаков операндов достаточно прибавить к коду результата умножения сдвинутый влево на n разрядов код дополнения положительного операнда до Pn+1 для того, чтобы количественный эквивалент (1) кода результата умножения стал равным количественному эквиваленту правильного результата (2). Действительно, если, например X<0, а Y≥0, то ошибочный результат (1) увеличенный на (3) будет равен
что и требуется.
Если знаки обоих операндов отрицательны, то к результату умножения достаточно прибавить сдвинутые на n разрядов влево значащие разряды прямых кодов операндов и уменьшить результат на единицу в разряде 2n. Это приведет к тому, что количественный эквивалент результата станет равным требуемому. Действительно, прибавив к ошибочному произведению (4) ошибку (5) получим:
Пример. Пусть десятичные операнды X=±910,24; Y=±800,13. Правильные значения произведений XY=±728310,3312. Дополнительные коды операндов 0⎢910.24; 1⎢089.76 и 0⎢800.13; 1⎢199.87 соответственно. Дополнительные коды произведений 0⎢0728310,3312 и 1⎢9271689.6688.
Перемножим дополнительные коды операндов по правилу умножения в прямых кодах и введем корректирующие поправки.
В исходных данных отсутствуют значения поправок. Поэтому их приходится вычислять путем взятия дополнений операндов, что сильно осложняет процесс умножения.
Операция алгебраического деления
В отличие от умножения, сложения и вычитания результат операции деления в общем случае не может быть представлен точно в формате конечной длины. Поэтому различают:
• деление целых с вычислением целого частного и/или остатка;
• деление целых и действительных чисел с вычислением частного в заданном формате с фиксированной точкой;
• деление целых и действительных чисел с вычислением заданного количества значащих разрядов частного;
• деление целых и действительных чисел с вычислением заданного количества значащих разрядов частного с округлением результата.
Знак частного равен сумме по модулю 2 знаковых разрядов операндов.
Операнды могут быть числами со знаком или без знака. При делении целых без знака принимают, что знак операндов положителен, а знаки частного и остатка отбрасывают.
Особые случаи. При делении возникают особые случаи, когда оба или один из операндов равны нулю. Пусть X – делимое, Y – делитель, Z – частное, R – остаток.
1. X=0; Y≠0. Результат Z=0 и R=0. Вопрос состоит в знаках результата
2. X ≠0; Y=0. Частное Z=∞ и не является конкретной числовой величиной. Открыт вопрос об остатке R и о знаках частного и остатка.
3. X=0; Y=0. Частное Z и остаток R не являются числовыми величинами.
Поэтому при делении обязательно проверяют операнды на нуль. При обнаружении особого случая процесс деления прерывают и формируют признак особого случая. Принимают решение о том, что делать дальше. Обычно частному и остатку присваивают нулевые значения. Знак частного определяют как сумму по модулю 2 знаковых разрядов операндов, а знак остатка принимают равным знаку делимого. В случаях 2 и 3 процесс вычислений прерывают.
Рассмотрим результаты различных операций деления при отсутствии особых случаев.
Деление целых с вычислением целого частного Z и целого остатка R
При любом способе деления целых с вычислением целого частного и остатка в любой системе счисления результаты должны быть точными и удовлетворять отношению:
причем
Формат частного должен быть равен формату делимого, так как при
Y = 1, частное Z = X.
Формат остатка должен быть равен формату делителя, так как модуль остатка может быть меньше модуля делителя всего лишь на 1.
Знак остатка совпадает со знаком делимого. Действительно, из (1) следует, что при X<0, произведение YZ<0. Поэтому для вычисления делимого по (1) нужно к отрицательной величине YZ прибавлять отрицательный остаток.
Например, 16:3=+5 и R=+1; 16:(–3)=–5 и R=+1; (–16):3=–5 и R=–1;
(–16):(–3)=+5 и R=–1.
Деление целых и действительных чисел с вычислением частного в формате с фиксированной точкой
Частное Z вычисляют с абсолютной погрешностью Δ=X/Y–Z, величина которой неизвестна, а ее значение принадлежит некоторому заданному интервалу [Δмакс, Δмин], причем знак Δ может любым, если Δмакс≥0, а Δмин<0. Так, что
Формат частного выбирают исходя из границ интервалов, которым могут принадлежать абсолютные значения операндов. Очевидно, что формат частного должен позволять сохранять значение старшего значащего разряда частного.
Так как
то, зная |X|макс и |Y|мин, не трудно найти вес старшего значащего разряда в формате Z.
Количество значащих разрядов в формате выбирают исходя из заданной точности представления и выбранного способа округления Z.
Деление целых и действительных чисел с вычислением заданного количества значащих разрядов частного
Результатами являются точные значения заданного количества l старших значащих разрядов частного, начиная с первого разряда слева не равного нулю, и индекс i младшего значащего разряда. Например, при l=5 результат деления 15,3:(–17,1)=–0,89473684… должен быть (Z=–89473; i=–5).
В особом случае при X=0 и Y≠0 следует всем значащим разрядам частного присвоить значение 0, принять i=0 и сформировать признак особого случая.
Формат частного включает разряд знака и l значащих разрядов. Формат i целого со знаком выбирают исходя из значений индекса младшего разряда минимально возможного значения частного при заданных форматах операндов и значения l.
Так как младшие разряды частного отбрасываются (их количество в общем случае бесконечно велико), то образуется ошибка в его представлении. Абсолютная погрешность частного Δ=X/Y–Z при таком его вычислении в точности равна количественному эквиваленту не вычисленных младших разрядов или, это то же самое, количественному эквиваленту R/Y
где R – последний остаток от деления.
Справедливы отношения:
Знак абсолютной погрешности Δ не является случайным, а совпадает со знаком частного, так как знак R совпадает со знаком делимого.
Модуль абсолютной погрешности частного случаен и его величина
где P – основание системы счисления;
i≠const – индекс младшего разряда частного, который определяется вычисляемым в процессе деления положением запятой в частном.
Максимальное значение модуля погрешности можно принять
Относительная погрешность, приведенная к величине частного
всегда положительна, так как знак погрешности Δ совпадает со знаком частного.
Максимальное значение относительной погрешности зависит только от основания системы счисления и от количества вычисляемых разрядов в частном
так как |Z|мин содержит только одну 1 в старшем значащем разряде с индексом i+l–1.
Деление целых и действительных чисел с вычислением заданного количества значащих разрядов частного с округлением результата
Отличается от предыдущего случая тем, что с целью уменьшения погрешности результат округляется до ближайшего к точному значению частного.
Рассмотрим некоторые способы вычисления разрядов частного и остатка.
Деление действительных чисел можно свести к делению целых. Для этого следует в дробных частях операндов уровнять количество разрядов, приписав, справа к одному из них недостающие нули, и интерпретировать полученные коды как целые. Например, 53,253:2,4=53,253:2,400=
=53 253:2 400. Поэтому в дальнейшем будем рассматривать способы деления целых.
Деление прямых двоичных кодов операндов с вычислением прямых кодов частного и остатка
Знаки частного и остатка определяют по приведенным выше правилам и сводят деление к вычислению значащих разрядов частного и остатка по значащим разрядам операндов.
В основу способов деления могут быть положены следующие результаты.
Пусть делимое X>0 и делитель Y>0 двоичные n разрядные целые. Справедливо отношение
где Z – частное, индекс старшего значащего разряда которого не может превышать n–1;
Rm – остаток от деления X на Y;
m – индекс младшего разряда частного (m ≤ n–1).
Остаток должен удовлетворять условию 2m(Y–1) ≥ Rm ≥ 0.
Поскольку частное
где zi – цифры частного Z и zi∈{0,1}, то
Из (1) следует
где Ri – промежуточный остаток (i=n–1, n–2, … , m), причем 2i(Y–1) ≥ Ri ≥ 0.
Из (2) получим
Так как члены выражения (4) не меньше нуля и zi∈{0,1}, то из (4) следуют правила для вычисления остатков и значений разрядов частного, начиная со старшего разряда zn-1:
На основании полученных правил могут быть разработаны различные способы их реализации.
Деление чисел с просмотром разрядов делимого слева направо
Пусть делимое X>0 и делитель Y>0 двоичные целые без знака в форматах включающих n и k разрядов соответственно. Индекс старшего значащего разряда частного должен совпадать с индексом старшего разряда делимого и быть равным n–1. Индекс младшего разряда частного m определяется требуемым числом разрядов в частном и может быть m≤n.
Разряды частного, начиная с zn–1 до zm включительно, вычисляют, придерживаясь выражений (5) – (7), но для упрощения и/или ускорения вычислений вводят различные модификации не влияющие на результат.
Деление с записью очередного сдвинутого влево остатка на место предыдущего и вычислением разряда частного в соответствии с (7)
Рассмотрим способ деления на примере.
Пусть X=110112=2710; Y=1012=510. Количество разрядов в делимом n=5; в делителе – k=3. Индексы старших разрядов частного и делимого равны
n–1=4, так как при Y=1 Z=X. Вычислим разряды частного от z4 до z–3. Тогда m=–3; i =4,3, ... ,–3.
Из (7) следует, что о значении разряда zi (i=n–1, n–2, … ,m) можно судить, сравнивая предыдущий остаток Ri+1 с делителем, сдвинутым при i >0 на i разрядов влево, а при i<0 на |i| разрядов вправо. При i=n–1 остаток Ri+1=Rn=X, а делитель сдвинут на n–1 разрядов влево так, что младший значащий разряд делителя совмещен со старшим разрядом делимого в одной позиции.
Из (8) следует, что при zi=0 очередной остаток Ri равен предыдущему, а при zi=1 очередной остаток равен Ri+1–2iY.
Исходя из сказанного, выполним следующие действия.
Расширим формат делимого, приписав к нему слева k нулей.
Разобьем формат расширенного делимого на две группы разрядов, старшую и младшую. К старшей группе (обозначим ее X1) отнесем k+1 разрядов.
Деление будем выполнять по шагам.
1. Сравнивать количественные эквиваленты X1 и Y, вычисляя значение отношения X1≥Y. Сравниваются (k+1)-разрядный код X1 с k-разрядным кодом Y.
2. Вычислять значение разности X1–Y.
В каждом шаге результат сравнения является очередной цифрой частного, начиная со старшей.
Результат вычисления разности X1–Y служит для определения очередного остатка и используется только в том случае, когда отношение (X1≥Y)=1, т.е. при X1–Y≥0. Поэтому можно разрешить: выполнять вычитание с ошибкой при X1<Y; вычислять только k младших разрядов разности X1–Y. Это позволит упростить и ускорить выполнение операции вычитания.
В шаге образуем новое делимое по следующему правилу. Если цифра частного 0, сдвинем делимое влево на один разряд с занесением нуля справа и потерей старшего разряда. Сдвиг сводится к чтению делимого и последующей записи его значения на прежнее место со смещением влево. Если цифра частного 1, выполним ту же работу, но при записи подменим старшие k разряды вычисленной разностью.
Действительно. При zi=0 очередной остаток Ri равен предыдущему (7). Из (5) – (7) следует, что в очередном шаге следует повторить вычисления, сдвинув делитель на один разряд вправо по отношению к его положению в предыдущем шаге или, это то же самое, сдвинув делимое на разряд влево. При zi=1 младшие разряды очередного остатка совпадают с младшими разрядами предыдущего остатка не участвовавшими в вычислениях, а старшие равны вычисленной разности. Поэтому при zi=1 для получения очередного делимого нужно сдвинуть старое делимое на разряд влево с одновременной заменой старших разрядов вычисленной разностью. Поскольку при сдвиге старший разряд разности будет потерян, то нет смысла его вычислять, что учтено при вычислении X1–Y.
В аппаратуре можно новое делимое записывать на место старого. Это позволяет использовать в очередном шаге оборудование, использовавшееся для сравнения и вычисления нового делимого в предыдущем шаге.
В примере в первом шаге вычисляем (X1≥Y)=0 – старшую цифру частного. Одновременно с записью цифры частного 0, сдвинем делимое влево. Получим новое делимое X=00110110 и X1=0011. Во втором шаге результат сравнения 0. Очередное делимое X=01101100 и X1=0110. В третьем шаге цифра частного 1, так как (X1≥Y)=1. Разность X1–Y=001. Заменив, старшие три разряда в сдвигаемом делимом на разность получим очередное делимое 00111000.
Процесс деления может продолжаться до бесконечности. Для прекращения процесса используют следующие правила:
− При делении целых с вычислением целого частного и остатка выполняют n шагов. Искомый остаток имеет формат делителя и размещен в старших разрядах делимого вычисленного в последнем шаге. В примере он выделен жирным шрифтом и равен 010.
− При делении целых и действительных чисел с вычислением частного в заданном формате с фиксированной точкой шаги выполняют до заполнения всех разрядов формата частного.
− При делении целых и действительных чисел с вычислением заданного количества значащих разрядов частного выполняют отсчет числа выполненных шагов, начиная с шага результатом которого является первая единица в частном, и продолжают выполнять шаги до тех пор, пока количество отсчитанных шагов не станет равным заданному количеству значащих разрядов.
Операцию вычитания можно заменить сложением X1 с дополнением Y. Например, в примере дополнение 101 будет равно 011. Значения суммы будут использоваться только при (X1≥Y)=1 и только k ее младших разрядов, что позволит упростить выполнение операции сложения.
Деление в дополнительных кодах с получением частного в дополнительном коде
Если операнды представлены в дополнительном коде, можно преобразовать их в прямой код, затем выполнить деление в прямом коде и, если частное должно быть представлено в дополнительном коде, преобразовать прямой код частного в дополнительный. Процедуры преобразования кодов замедляют процесс деления. Поэтому применяют способы деления без промежуточного преобразования операндов в прямой код.
При конструировании способов деления в дополнительных кодах можно в их основу положить рассмотренные способы деления в прямых кодах. Очевидно, что знак дополнительного кода частного можно вычислять так же как в прямом коде сложением по модулю 2 знаковых разрядов операндов. Следовательно, задача сводится к поиску способа деления значащих разрядов операндов представленных в дополнительном коде.
При расширении формата делимого влево следует копировать в дополнительные разряды знаковый разряд делимого, чтобы не изменить его количественный эквивалент. Например, делимое x=1|00101=–27. После расширения формата делимого на два разряда влево x=1|1100101=–27.
Сконструируем способ деления в дополнительных кодах, положив в его основу способ деления в прямых кодах использованный в предыдущем примере, допуская его модификацию. Заметим, что многие из рассматриваемых в конструируемом способе решений могут быть применены при конструировании иных способов деления в дополнительном коде.
При делении в прямых кодах для нахождения очередной цифры частного определяли: укладывается ли делитель в коде X1 старших разрядов делимого, относя к ним столько разрядов делимого, какова длина делителя. При делении в дополнительном коде можно поступать аналогично. Остается лишь открытым вопрос о том, как выполнять сравнение модулей чисел со знаком, если они представлены в дополнительном коде.
Если знаки операндов совпадают, то судить о том, укладывается ли в X1 делитель можно по знаку их разности. Например, +7–(+5)=+2 (укладывается); –7–(–5)=–2 (укладывается). Если знаки операндов не совпадают, то соответствующим признаком является знак суммы. Например, +7+(–5)=+2 (укладывается); –7+(+5)=–2 (укладывается).
Следовательно, если знаки операндов совпадают, для сравнения следует вычислять разность X1–Y; если знаки операндов не совпадают, следует выполнять сложение X1+Y. Признаком укладывания в обоих случаях является совпадение знака результата сложения или вычитания со знаком делимого.
Заметим, что можно предложить иные способы сравнения.
Из приведенных примеров сравнения видно, что признаком 1 в прямом коде частного будет совпадение знака делимого со знаком разности или суммы. Для получения обратного кода частного можно использовать признак совпадения знака делителя со знаком разности (суммы) как признак 1 в разряде частного. Дополнительный код частного можно получить преобразованием его обратного кода в дополнительный.
Если делитель не укладывается в X1, для получения очередного значения X1 следует сдвинуть делимое на один разряд влево с потерей разряда слева и занесением нуля справа (удвоить). В противном случае, нужно при сдвиге делимого на разряд влево заместить его старшие разряды вычисленной разностью (суммой). Рассмотрим применение этого правила на примере.
Операция округления действительных чисел
При выполнении операций над действительными числами может быть получен результат, не умещающийся в разрядную сетку, отведенную для хранения результата. Так как операнды действительные числа и, следовательно, представлены с некоторой погрешностью, результат не может быть точным. Поэтому с целью размещения результата в разрядной сетке он может быть округлен.
Округление до нуля. Это простейший способ округления не требующий никаких затрат на реализацию. Он состоит в отбрасывании младших разрядов результата не умещающихся в разрядной сетке.
Рассмотрим особенности этого способа при кодировании чисел в прямом, обратном и дополнительном коде.
Количественный эквивалент прямого кода числа до округления можно представить как сумму количественных эквивалентов сохраняемых старших разрядов от n до k и отбрасываемых младших разрядов от k-1 до m
Результат округления будет иметь количественный эквивалент
а абсолютная погрешность округления
имеет знак, совпадающий со знаком результата. Модуль абсолютной погрешности 0≤|Δпро|<Pk меньше веса младшего разряда сохраняемого результата.
Если данное представлено в обратном коде, то до округления его количественный эквивалент
После округления до k>m разряда путем отбрасывания k–m младших разрядов
Тогда ошибка округления обратного кода путем отбрасыванием младших разрядов составит
Знак ошибки, так же как при округлении до нуля в прямом коде, совпадает со знаком числа, и ее модуль 0≤|Δобро|<Pk меньше веса младшего разряда сохраняемого результата.
Округление до нуля дополнительного кода числа приводит к иным результатам.
До округления количественный эквивалент дополнительного кода
После округления до k>m разряда путем отбрасывания k–m младших разрядов
Ошибка округления до нуля дополнительного кода составит
Следовательно, знак ошибки не зависит от знака числа, а ее модуль меньше веса младшего разряда сохраняемого результата.
Чтобы получать после округления дополнительного кода отрицательного числа результат с количественным эквивалентом таким же, как и при округлении этого числа в прямом коде, необходимо увеличить результат усечения на 1 его младшего разряда кроме случая, когда отбрасываемые разряды равны нулю.
В примерах A, B, C выполнено округление до нуля отрицательного десятичного числа в прямом, обратном и дополнительном коде.
В примере C результат усечения дополнительного кода 1|756доп является ближайшим меньшим приближением к исходному числу. Чтобы получить дополнительный код ближайшего большего приближения выполнено прибавление 1 к младшему разряду.
Примеры D и E иллюстрируют тот факт, что при равенстве нулю отбрасываемых разрядов дополнительного кода отрицательного числа не следует прибавлять 1 к младшему разряду усеченного кода.
В примерах F, G, H, I выполнено округление до нуля двоичных кодов.
Систематическое одностороннее смещение промежуточных результатов вычислений влечет накопление ошибок и снижает достоверность конечного результата, что является существенным недостатком этого способа округления.
Округление до нуля с увеличением на 1 цифры в младшем сохраняемом разряде, если ее количественный эквивалент меньше половины количественного эквивалента основания системы счисления. Например, при P=10 цифра в сохраняемом разряде k остается без изменения, если ak∈{5,6,7,8,9}, и заменяется на большую, если ak∈{0,1,2,3,4}. Разряды от m до k–1 отбрасываются. В двоичной системе цифра ak=1 сохраняется, а цифра ak=0 заменяется на ak=1.
Если при округлении ak сохранит значение, то погрешность округления будет такой же, как и при округлении до нуля. Если ak возрастет на 1, то погрешность изменит свой знак, а ее модуль не превысит веса сохраняемого разряда. Поскольку до округления значения ak равновероятны, знак погрешности равновероятен. Равновероятно ее значение в интервале Pk>Δ01>–Pk.
Рассматриваемый способ округления не намного сложнее предыдущего, так как прибавление 1 не может вызвать распространения переноса. Равно вероятность погрешности на интервале Pk>Δ01>–Pk препятствует накоплению погрешности округления. Недостатки этого способа в том, что интервал, в котором лежит погрешность, вдвое больше, чем при способе округления до нуля, и, кроме того, результат после округления не может содержать 0 в младшем разряде. Последнее может приводить к существенным ошибкам в вычислениях. Например, многократное деление переменной на основание системы счисления с округлением никогда не приведет к результату равному нулю.
Округление до ближайшего числа, которое можно представить в сокращенной разрядной сетке.
Исходный код заменяется укороченным кодом, количественный эквивалент которого является ближайшим к количественному эквиваленту исходного кода. Если существуют два равноценных ближайших укороченных кода, то возникает особый случай. В особом случае, если цифра младшего разряда кода полученного округлением до нуля ak<P/2, то для замены выбирают результат округления до нуля. В противном случае к младшему разряду результата округления до нуля прибавляют 1 и тем самым заменяют исходный код другим ближайшим значением.
Арифметические действия в ДДК
Сложение в двоично-десятичном коде
В процессе сложения вырабатывается сумма по модулю 16 и 16-ричный выходной перенос. Но в итоге необходимо получить число по модулю 10 и 10-тичный перенос, поэтому в некоторых случаях полученный результат следует скорректировать на 6.
Введем обозначения: Хi – цифра i-го разряда 1-го слагаемого, Yi – цифра
i-го разряда 2-го слагаемого, Pi – перенос из (i – 1)-го разряда в i-ый разряд.
Тогда рассмотрим возможные случаи:
1. Если Хi + Yi + Pi < 10, то суммы по модулю 10 и 16 совпадают и коррекция результата не нужна.
2. Если Хi + Yi + Pi ≥ 16, то при первом сложении сумму необходимо скорректировать на +6, т.к. перенос передан в старший разряд весом 16 вместо 10. Признаком коррекции при этом служит выходной тетрадный перенос.
3. Если 10 ≤ Хi + Yi + Pi < 16, то необходима коррекция на +6 из-за превышения допустимого значения суммы.
Например, сложить 18410 и 29810:
В результате сложения в младшем разряде (тетраде) мы получили результат, превышающий 9 (правило 3). Следовательно, необходима коррекция на +6 из-за превышения допустимого значения суммы. Во втором разряде (тетраде) имеет место правило 2, т.е. имеется выходной тетрадный перенос. Следовательно, также необходима коррекция на +6.
Сложить 47510 и 82910:
После выполнения коррекции результата мы вновь получили во втором разряде результат, превышающий 9. Следовательно, необходимо этот разряд (тетраду) откорректировать. В этом случае нас не интересует наличие выходных тетрадных переносов.
Другой алгоритм сложения использует избыточные на +6 значения разрядов одного из слагаемых, т.е. выполняется предварительная коррекция всех разрядов одного из слагаемых на +6.
При этом, если в разряде суммы возникает тетрадный перенос, то значение суммы правильное, т.к. оно как бы заранее было скорректировано.
Если переноса нет, то предварительная коррекция была не нужна, и избыток на +6 необходимо компенсировать вычитанием 6, или сложением с 10 и игнорированием при этом выходного переноса.
Например, выполнить сложение 18410 и 29810 с предварительной коррекцией:
В первом примере в первом и во втором разрядах (тетрадах) суммы возникал тетрадный перенос, поэтому предварительная коррекция была выполнена верно. В третьем разряде (тетраде) не было тетрадного переноса, следовательно, предварительная коррекция была не нужна, и избыток на +6 необходимо компенсировать вычитанием 6 (случай а), или сложением с 10 и игнорированием при этом выходного переноса (случай б).
Еще один способ решения:
Вычитание в двоично-десятичном коде
Результат вычитания всегда меньше 10, поэтому разность необходимо корректировать на –6 только при возникновении 16-ричного займа, т.к. десятичный разряд в этом случае приобретает лишних 6 единиц.
Например, выполнить вычитание 61510 и 39610:
В 1-ом и 2-ом разрядах (тетрадах) имеет место займ из более старшего разряда, поэтому данные разряды необходимо скорректировать на –6.
В вышеописанных примерах мы рассматривали только информационные
разряды, считая, что знаковый разряд во всех случаях «+» (1100). В некоторых случаях знаковый разряд результата может иметь знак «–» (1101).
Поэтому при выполнении операции вычитания числа предварительно анализируются. Если уменьшаемое при этом окажется меньше вычитаемого, выполняется операция вычитания уменьшаемого из вычитаемого, а результату присваивается знак «–».
Например, выполнить вычитание 12410 и 38110.
Алгебраическое сложение в ДДК с использованием дополнительного кода
При алгебраическом сложении многоразрядных десятичных двоично-кодированных чисел, отрицательные числа можно предварительно представить в дополнительном коде. Дополнительный код образуется из обратного кода прибавлением единицы в младший разряд. Формирование обратного кода для двоично-кодированных десятичных чисел производится путем замены цифр в тетрадах числа (кроме знакового разряда) их дополнениями до 9. Операцию определения дополнений до 9 к цифрам числа в тетрадах можно провести согласно выражения:
где Di – дополнение до 9 к цифре i-й тетрады числа; Xi – цифра i-й тетрады числа.
В этом случае, после прибавления корректирующей поправки к тетрадам числа, вычитание полученных сумм из 15 равнозначно простому инвертированию тетрад. В результате получим обратный код путем прибавления единицы к младшему разряду.
Формирование дополнительного кода двоично-кодированных десятичных чисел рассмотрим на примере отрицательного числа:
Прибавим во все тетрады прямого кода корректирующую поправку:
После инвертирования разрядов числа (кроме знакового) получим обратный код:
Каждая тетрада обратного кода является дополнением до 9 к тетрадам прямого кода. Прибавляя к младшему разряду обратного кода единицу получаем дополнительный код исходного отрицательного числа:
Принцип алгебраического сложения многоразрядных двоично-кодированных десятичных чисел рассмотрим при сложении полученного отрицательного числа с положительным числом:
При суммировании рассматриваемых кодов чисел получен результат в виде дополнительного кода. Для преобразования полученного результата в прямой код необходимо в каждую тетраду прибавить корректирующую поправку, затем произвести инвертирование цифр в тетрадах и прибавить единицу в младший разряд:
Рассмотренная методика проведения операции алгебраического сложения применима в основном при представлении десятичных чисел в коде 8-4-2-1. Если для представления десятичных цифр используются другие двоичные коды, то указанная операция производится несколько по иным правилам. Например, при использовании кода с избытком 3 или кода 2-4-2-1, дополнительный код отрицательного числа получается простым инвертированием цифр двоичных тетрад прямого кода без дополнительного прибавления корректирующей поправки.
Эти коды отличаются от прямого, обратного и дополнительного кодов тем, что на изображение знака отводится два разряда: если число положительное – 00, если число отрицательное – 11. Такие коды оказались удобны (с точки зрения построения АЛУ) для выявления переполнения разрядной сетки. Если знаковые разряды результата принимают значение 00 и 11, то переполнения разрядной сетки не было, а если 01 или 10 – то было переполнение. Например,
Проблема точности возникает, как правило, при работе с микро- и миниЭВМ, имеющих небольшую длину машинного слова (1 – 2 байта). Рассмотрим микропроцессор, работающий со словами длины 1 байт. Этот формат позволяет представить целые числа в диапазоне от –128 до 127. Очевидно, что для решения большинства задач такого диапазона чисел недостаточно. Использование двух однобайтовых слов (16 бит) позволяет представить уже числа в диапазоне от –32768 до 32767. Это так называемые числа с двойной точностью. Иногда используются числа тройной точности (1 бит – знак и 23 бита для модуля числа). Это обеспечивает диапазон уже от –8388608 до 8388607, т.е. точность существенно повышается.
Однако при работе с арифметикой повышенной точности требуется больший объем памяти для хранения того же объема данных и более интенсивная работа процессора. Увеличение объема требуемой памяти достаточно очевидно. Рассмотрим очень коротко последовательность операций при сложении чисел с тройной точностью. Здесь уже недостаточно извлечь два слова из памяти, сформировать сумму в аккумуляторе и переслать результат в однобайтовую ячейку памяти. Сначала необходимо произвести обращение к младшему значащему байту каждого числа. После сложения результат записывается в память, а возможные при этом переносы подлежат временному хранению. Затем извлекаются средние по значимости байты, их складывают и к сумме добавляют биты переноса, полученные в результате предыдущей операции. Результат записывается в память на место, специально зарезервированное для среднего байта суммы. Со старшим байтом поступают аналогично.
Таким образом, при использовании арифметики тройной точности требуются в три раза большие объем памяти и время на операции сложения по сравнению с арифметикой одинарной точности. Кроме того, в случае возникновения прерываний необходимо временно хранить содержимое регистра переносов (то же самое для вычитания, умножения и деления).