Горбатов В.А. - Фундаментальные основы дискретной математики. Информационная математика - 2000 (1019108), страница 13
Текст из файла (страница 13)
Для алгебраического сложения чисел х и у произвольного знака в системе счисления с натуральным основанием Я и естественным множеством цифр достаточна перевести запись этих чисел в обратный кад, просуммировать полученные коды ло правилам сложения чисел в системе с аснонанием Я и добавить единицу в младший разряд полученного выражения, если при суммировании паянляется единица переноса знакового разряда.
Полученный результат предстанляет собой обратный код истинной (алгебраической) суммы чисел х и у. Приме р 1.8. Вычислим алгебраическую сумму количественных эквивалентов 19.43 — 28.57 в троичной арифметике 3 = 3 и естественном алфавите дифр (О, 1, 21, ислольауя доволинтельиый код. Определим эвл»кь числа 19АЗ в агой арифметике с точностью до 3 э: целая часть— дробная часть— 19 [3 ОАЗ х 3 = Щ.29 18 6 [3 0.29 х 3 = ©.87 0.87 х 3 = ©.41 ф о 19.43 -+ [201.102]э -+ 3 х 0.201102. Аналогичгю одределяем вались числа 28.$7: делая часть— пробная часть— 28 [З 0.57 х 3 = 01.71 27 9 [3 0.71 х 3 = ©.13 0.13 х 3 = »$.39 Ф 28 57 -+ [1001 120]э -+ 3 х 0.1001120.
Выравниваем ворявки до большего: 19.43-+ 3» х 0.0201102, 28.$7 -+ 3» х 0.1001120. Заменяем вычитание слоиеинем в доволкнтельном коде: 0.0201102 2.1221102 [2.1221102] — доволнительиый вод суммы, 2.2122211], — обратный вод суьоеы, — 0.010001 1]э — мантисса суммы. В реэультате количественный эквивалент суммы равен -9.14.
Тот ие реэультат получаем, исвольэуя обратный код: 0.0201102 2.1221102 [2.1221102], -+ [-0.0100011], — мантисса суммы. з в я г,р» Гл, 1. Основы мноеосортныл множеств 66 $1.8. Компьютерные ориубметияи 0.13 х 4 = ©.52 0.52 х 4 = ф.08 ч © 0 0 12.31 -+ [30.02)» -+ 4 х 0.3002; дробная чвсть— лелея часть— 17 )4 0.21 х 4 = ($.81 0.84 х 4 = Е.З6 Ф 17.21 -ь [101.03)» -+ 4 к 0.1011. Порядок провэзедення равен 5: 2+ 3 м 5. Правила умнояею~я цифр окределекы а табл.
1.17, где а клетке [С А левая цифре соответствует переносу, правая — аначеиюо провваевення а этом разряде, Согласао табл. 1.17 аропвзедем умяонение Таблице 1.17 0.3002 Я,шов 3002 + 3002 3002 0.03101022 Посленормелнавлниполучим,что проваведениерааноА х0,3101; это определяет количественный эквивалент, разный 4 к(3 4 +1 4" +О 4 +1 4 )=3 4 +1 4 +О 4 ~+1 4 =209.
При делении из порядка делимого вычитают порядок делителя. Деление мантисс заменяют вычитанием делителя вз делимога да тех пор, пока в результате очередного вычитания не будет получена отрицательная разность. Затем прибавляют делитель к отрицательной разности (эта операция называется восстановлением При умножении необходимо просуммировать порядки сомножителей, произвести умножение мантисс по правилам умножения чисел, нормализовать результат и, если произошел сдвиг мантиссы произвеления, изменить соответственно порядок произведения. Знак произведения определяется отдельно естественным образом: если сомнажители имеют одинаковые знаки, то цроизведение — положительное число, в противном случае — отрицательное.
П риме р 1.9. Вьгчислве аровэзедение количественна»к эазивалентоа 12.13 х 17.21 в врифьытиае с основанием 4 и естественным алфавитом цифр (О,' 1, 2, 3). Пуведстааим эти колячестзенные эквиваленты з этой ерифмеюке с точностью до 4 целая часть— дробная чвсгь— 12 )4 12 3[4 дробная чвсть— 0.17 х 2 = 9.34 0.34 х 2 = ©.68 0.68 х 2»э ©.36 0.36 х 2 = ~9.72 11.1010 1101 Знак равности отрипателыовй, следозателив, целая часть чвстяого при деленны мантисс равна 0: Привзведем оаервдвю зосставвления: 11,1010 1101 [+~ ОО.НХВООО1 100. 1000 0001 Сумматор обрвтвпо вода является циклическим сумматора»с перенос на аяавоаого разряда суымируется с цифрой млвщпего раэрелв.
Сумматор дополнительного кода является епяклическиэс перввс на знакового разряда не суммируется с цифрой младшего разряда, перенос "проделает". остатков) и в качестве цифры частного записывают числа вычитаний лелителя без учета последнего вычитания. После этого роль делимога начинает играть остаток, а роль делителя — прежний делитель, сдвинутый на один разряд вправо, и т. д. Мантиссу частного нормализуют и соответственно изменяют порядок част- нога.
Знак частного определяют аналогично определению знака произведения. П р им е р 1.10. Вычислим частное, полученное в результате деления 8.17 на З.ЗЗ з двоичной врнфметяке Я = 2 с алфавитом цифр [О, 1). Определим закись чисел 8.17 и 3.33 э двоичной врифмепве, вычисляя дробную часть с точностью до 2»: целая часть— 8 [2 8.17 -+ [1000.0010)э -+ 2 х 0.10000010; делая честь— дробная часть— 3 [2 0.33 к 2 = ©.66 2 1[2 0.66 х г = Ср.зг Щ О 0 0.32 х 2 = ©.64 Ф 0.64 х г = ОУ.гз 3.33 -+ [11.0101)г -+ 2 х 0.11010100.
Порядок чэснюго ракен 2: 4 — 2 = 2. Вьгчяслим мантиссу частного, исвтьэуя обрвтвый аод; врн агом знак будеы кодировать двумя знфрами для того, чтобы правильно определять нарушение вврмвлиаэцзи мвпнссы: + поляруем 00, — кодируем 11. Первый цикл в»горвтма: 00.1000 0010 00.1000 0010 00.11010100 Е» 11.00101011 Гл. 1. Осиоем миогосортиык миолсесто 68 1 1.8. Компьютерные орир)метина 69 После восстановления калучям умеиьшвемое 00. 10000010. Второй цикл алгоритме. 00. 1000 0010 ОО.ОПО 1010 Знак ревности цаланительиый, следаввтельно, следующая цифра мантиссы част- нага — 1: 00.00011000 П+е 11.11001010 П.1110 0010 Знак равности отрицательный; следуюшвя цифре мвитяссы светлого — 0: Праяввадим восстановление остатке и леретадим к вычислению четвертой цифры честного. Четвертый цикл алгоритма: 00.0001 1000 00.0001 1010 00.0001 1000 П.П10 0101 П.ПП П01 Знак ревности отрицательный, следаввтельиа, четвертая цифра ментяссы част- иага — 0: После восстановления остатка вычисляем литую иерру мантиссы чвстяого: 00.0001 1000 00.0001 1000 оо.оооо по1 [+] пзптоо1о 100.0000 1010 00.0000 10П Знак ревности лоланительный, следовательно, пятая цифре — 1: Для лрввильного округления онвлап)чна вычисляем шестую цяфру; втой цифрой является 1.
Отсюда мантиссе чвспюга имеет вид Искомое честное есть 2 х 0.1010; аиа соатветствуег количественному эквиваленту 2.5) 2 и(1 2 +О 2 +1 2 е+О 2 )ю2+2 =2З. Как уже отмечалось, система счисления является весомозначной, если для каждого разряда с номером у можно указать такое Третий лика влгорнтме: 00.0001 1000 00,00 П 0101 00. 1000 0101 П+ ° П.1001 ОШ1 )а.паа ош ОО.ВВ) ) )Ю число р, что количественный эквивалент, который сопоставляется цифре а;, записанной в этом разряде, равен р.
[а;], где [о;]— количественйый эквивалент, сопостввляемый этой же цифре в нулевом разряде. Количественный эквивалент числа х определяется как я = ~~> р [о;]. В вычислительной технике представляет интерес двоична-десятичные системы счисления, в которых каждая десятичная цифра кодируется четырьмя двоичными цифрами и, следовательно, каждый разряд десятичной записи замещается четырьмя разрядами. Если этим четырем разрядам соответствуют некоторые веса, то имеет место весомозначная система для этих четырех двоичных разрядов. При использовании двоична-десятичных систем в ЭВМ желательно, чтобы копирование (оно неоднозначно, так как для кодирования десяти цифр можно использовать любые нз 16 тетрад— четверок из нулей и единиц) удовлетворяло некоторым ограничениям.
Приведем пять основных требований, которые сформулированы Рутисхаузером. Единственность. Необходимо однозначное соответствие цифр и тетрад, Если это требование не выполнено, то невозможно кодирование и декодирование чисел. Упорядоченность.
Большим десятичным цифрам должны соответствовать большие (по количественному эквиваленту) тетрады. Выполнение этого требования необходимо при сравнении кодированных чисел. гтеткосгнь. Четным десятичным цифрам должны соответствовать четные тетрады (тетрады, у которых в крайнем правом разряде стоит нуль), а нечетным цифрам — нечетные тетрады. Дополкипьелькоспть. Если цифры десятичной системы таковы, что сумма их равна девяти, то им должны сопоставляться тетрады, которые взаимно инвертированны, т. е.
получаются друг из друга заменой единиц на нули, а нулей на единицы. Выполнение этого требования необходимо для того, чтобы ввести в двоичнодесятичной системе дополнительный или обратный код. Весомозкочкоспгь. Должны существовать четыре веса р1, рт, рз, ре таких, что если десятичной цифре х сопоставлена тетрада сгтегтегзеге, то имеет место равенство ж = ег1 р1 +егт 'рт+сгз 'рз+сге'ре) сг)' се 0) 1. Кодирование, удовлетворяющее всем пяти требованиям, называется совершенным. Условимся через Т(х) обозначать тетраду, сопоставимую десятичной цифре з. Рассмотрим правила сложения для чисел, запи- 71 $1.8.
Компьютерные ориэ)мео)ики Гл. 1. Основы многосоро)ных мнохсесо)в 70 санных в двоична-десятичной системе. Пусть в десятичной системе взяты цифры х и у. Тогда либо х + у — некоторая новая цифра этой системы (если х + у < 10), либо результатом суммирования этих цифр является цифра, соответствующая х+ у — 10, и возникает единица переноса в следующий разряд.
Тогда правила сложения в двоична-десятичной системе имеют вид 1 Т(х+ у), х+у < 10, ( Т(х+ у — 10) + 16, х+ у > 10. Здесь прибавление 16 соответствуег переносу единицы в следующий разряд (перенос в правый разряд тетрады, стоящей слева от данной). Как следует из этого соотношения, при суммировании чисел в такой системе необходимо вносить поправки. Пусть, например, кодируется каждая десятичная цифра ее записью в двоичной системе с использованием четырех двоичных разрядов.
В этом случае цифра 5 будет закодирована тетрадой 0101. Такой способ кодирования называется кодом ярлмого замгщгнив (8421). В данном случае, учитывая, что для кода прямого замещения Т(х) = х, можно записать Т(х) + Т(у)— Таким образом, при суммировании в коде прямого замещения необходимо произвести суммирование в каждой паре тетрад по правилам двоичного сложения, учитывая перенос между тетрадами, если последний возникает. После этого в те разряды, где сумма кодированных цифр превысила 10, следует добавить поправку 0110. Проиллюстрируем это на следующем примере.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
