Джон Ф.Уэйкерли Проектирование цифровых устройств. Том I (2002) (1095889), страница 17
Текст из файла (страница 17)
Комбинации битов расположены в тех же местах по окружности, а прибавление и отнимание того или иного числа, как и ранее, достигается поворотом указателя на соответствующее число позиций по часовой стрелке или против нее. 2.7. Сложение и вычитание двоичных чисел в обратном коде 69 *2.7. Сложение и вычитание двоичных чисел в обратном коде Взглянем еше рвз на табл.2.6; это поможет нам объяснить правило сложения двоичных чисел, представленных в обратном юде.
Если начать с числа 1000 (-7 ) и счиг ~в тать в прямом направлении, то каждое следующее число будет получаться нз предыдущего в результате добавления 1, за исключением перехода от 1111 (отрицательный 0) к 0001, (+1, ). При достижении числа 1111 мы должны для продолжения правильного счета прибавить 2, а не 1. Из этого следует алгоритм сложения двоичных чисел в обратном юде: следует выполнять стандартное двоичное сложение, но добавлять еще одну 1 при переходе через! 111 . Достижение значения 1111 при сложении можно обнаружить, следя за переносом нз знакового разряда. Таким образом, правило свохсвния двоичных чисел в обратном коде (опез *-сотр!етвп! айй!оп) можно сформулировать совсем просто; Выполняется стандартное двоичное сложение; если возникает перенос из зна- кового разряда,то к результату прибавляется 1.
Это правило часто называю г пикническим переносом (впс(агоипг(сапу). Ниже приведены примеры сложения в обратном коде; в последних трех примерах производится циклический перенос; +5 О! 01 + -5 + 1010 +4 0100 + -7 + 1000 +3 0011 + +4 + 0100 +7 0111 -0 1111 -3 1!00 -О 1111 + -0 + 1111 +б 0110 + -3 + 1100 1101 + 1010 11!!О , 1 1111 !0111 е 1 1000 +3 10010 1 0011 Если следовать сформулированному алгоритму, осуществляемому в два шага„ то в результате сложения числа с его обратным кодом получается отрицательный через этот разрыв. В этом случае говорят, что в старшем разряде возникает потребность заема (Ьокган ).
Из рис. 2.4 следует также, что вычитание числа без знака, равного п, можно осуществить, повернув указатель па часовой стрелке на 16 — п позиций. Это экв ивалентно сложению с точным дополнением числа п. При вычитании заем возникает, если соответствуюшее сложение с точным дополнением нв приводит к переносу. Таким образом, перенос или заем, возникающие при сложении чисел без знака, указывают на то, что результат не укладывается в диапазон представимых чисел. При сложении чисел со знаком в дополнительном коде на тот же факт указывает обсуждавшееся нами выше переполнение. Думать о переносе при сложении чисел со знаком излишне в том смысле, что переполнение может наступать или не наступать независимо от того, происходит перенос илн нет. О.
Действительно, процедура сложения, предусматриваемая этим правилом, никогда не может привести к положительному О, если только оба слагаемых не равны положительному О. Как и в случае с числами, представленными в дополнительном коле, простейший способ реализации вычитания чисач в обратном коде (опезьсотр!степ! зибггасбоп) состоит в том, чтобы взять дополнение вычитаемого числа н сложить его с уменьшаемым. Правила переполнения для сложения и вычитания в обратном коде — те же самые, что и в случае дополнительного кода, Все правила преобразования двоичных чисел в числа с обратным знаком, их сложенияя и вычитания, представленные в атом разделе и ранее, сведены в табл. 2.7. Табл. 2.7.
Сводка правил сложения и вычитания двоичных чисел Правила преоб- Правила вычитания раэовенин чисел в числа с обретным знаком Представление чисел Правиле сложения Сложить числа. Результат оказывается вне диапазона предсгавимых чисел, если возникает перенос нз старшего разряда. Без знака Нс применяется. При одинаковых знаках: сложить величины; при появлении переноса из старшего разряда происходит переполнение; результат имеет тот же знак. Изменитьзнаковый бит числа В прямом кодс со знаком вычнтаемою н произве- сти сложение.
При разных знаках: вычесть меньшую величину из большей; переполнения быть не может; результат имеет знак большего по величине числа. Все биты числа изменить на противоположные; к результату прибавить !. В дополнитель- ном коде Все биты числа изменить на противоположные. В обратном коде 70 Глава 2. Числовые системы и коды Сложить. игнорируя возможный перенос из старшего разряда. Переполнение наступает атом случае, когда переносы в старший разряд и из него различны. Сложить; если возникает перенос из старшего разряда, то к результату добавить !.
Переполнение наступаег атом случае, когда переносы а старшиН разряд н из него различны. Отнять вычитаемое от умснылаемого. Результат оказывается вне диапазона представимых чисел, если в старшем разряде возни каст заем. Изменить знаковый бит Изменить на противоположные асс биты аычизаемого н сложить с умсньшаемым, полагая перенос в млашлий разряд равным ! Все биты вычитасмого изменить на противоположные и осуществить сложение.
*2.8. Двоичное умножение В начальной школе учат перемножать путем сдвига множимого, умножения его на значение соответствующего разряда множителя и сложения (зй!уГ-апг)-асИ ти!пр!!саггоп) всех полученных таким образом чисел. Тот же принцип можно применить для нахождения произведения двух двоичных чисел бвз знака !ипяяпег! Ьгпагу ти!пр!!со!!оп).
Прн двоичном умножении образование подлежащих сложению сдвинутых чисел тривиально„так как в каждом из разрядов множителя возможны только два значения: 0 нли 1. Приведем примеры: !(ц ! х 1101 множимое множитель !О!1 ОООО !О!! 10!1 сдвинутые множимые !000!111 произведение В цифровой системе удобнее не формировать вначале все сдвинутые копии множнмого и затем их складывать, а при каждом шаге прибавлять очередное сдвинутое множимое к частичному произведению (раж!а! ргог)ис!). При реализации этого метода в предыдущем примере перемножения 4-разрядных двоичных чисел понадобятся четыре сложения и возникнут четыре частичных произведения: 1011 х 1101 11 х 13 множимое множитель 0000 1011 частичное произведение сдвинутоемножимое 01011 00004 001011 10!1!.1 0110111 1011441 10001111 В общем случае умножения п-разрядного двоичного числа на т-разрядное двоичное число для представления произведения необходимы самое большее лет битов.
В алгоритме с ланга н сложения для получения резул ьтата требуется выч ислитыл частичных произведений и выполнить т сложений, но первое сложение тривиально„поскольку начальное частичное произведение равно нулю. Хотя это первое частичное произведение состоит всего лишь из л значащих битов„после каждого шага сложения длина частичного произведения увеличивается на один значащий бит, так как при каждом сложении может возникнуть перенос. В то же время на каждом шаге еще один бит частичного произведения, начиная с крайнего !! х 13 33 1! 143 2.2.
Восьмерычныемшестнадцатеричныечисла 71 частичноепроизведение сдвинутое множимое частичное произведение сдвинутое множимое частичное произведение сдвинутое множимое произведение гж глава 2. Числовые системы и коды 1011 х 1101 множимое множитель х -3 00000 11011 частичное произведение сдвинутое множимое с обратным знаком частичное произведение сдвинутое множимое частичноепроизведение сдвинутоемножимое частичное произведение сдвинутое множимое произведение !11011 000001 1111011 1101111 1!100!1! 0010!И~1 00001111 Обработка старшего разряда производится несколько хитрее, так как на каждом шаге мы получаем еще один значащий бит и имеем дело с числами со знаком. Поэтому перед сложением каждого сдвинутого множимого с А-разрядным частичным произведением мы увеличиваем число значащих битов в кажлом из слагаемых до /г+! по правилу знакового расширения.
В результате каждая сумма состоит из /с+1 битов; перенос из старшего разряда ~Я+1)-разрядной суммы игнорируется. правого бита и двигаясь влево, будет оставаться неизменным. В разделе 8.7.2 показано, что алгоритм сдвига и сложения можно реализовать в цифровой схеме, состоящей из регистра сдвига, сумматора и управляющей логики. Умножение чисел со знаком (л/8пед ти/Пр//сабоп) можно осуществить с помощью умножения чисел без знака, применяя арифметические правила: выполняется умножение без знака величин и произведению присваивается знак «плюс»„ если сомножители одного знака, и знак «минус», если их знаки различны. Это очень удобно делать при представлении чисел в прямом коде со знаком, поскольку знак и величина при этом разделены.
При представлении чисел в дополнительном коде выделение величины отрицательного числа и изменение знака у произведения, полученного по правилам перемножения чисел без знака, являются не совсем простыми операциями. Это подталкивает нас к поиску более эффективного способа умрноисения чис«л в дополнительном коде (п«о усотр/етет ти/г/р//са//оп), о чем сейчас и пойдет речь. В принципе, перемножение чисел без знака сводится к последовательности сложений сдвинутых множимых по правилам сложения чисел без знака; иа каждом шаге сдвиг миожимого соответствует весу бита множителя. У чисел в дополнительном коде биты имеют те же самые веса, что и у чисел без знака, за исключением старшего бита, вес которого отрицателен (см. раздел 2.5.4). Таким образом, умножение чисел в дополнительном коде можно выполнить как последовательность сложений сдвинутых множимых по правилам сложения чисел в дополнительном коде, Исключение составляет последний шаг, на котором сдвинутое множимое, соответствующее старшему разряду множителя, должно быть взято с обратным знаком, прежде чем оно будет добавлено к частичному произведению.
Ниже повторен наш предыдущий пример, только теперь множимое и множитель интерпретируются как числа в дополнительном коде: 2.9.Двоичноеделение ТЗ *2.9. Двоичное деление Простейший алгоритм двоичного деления основан на методе деления «р тем сдвига и вычитания (з)«ф-апг(-зид«гас«г((гм(оп), которому учат в начальной школе. В табл.2.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
