Основы информатики_Савельев А.Я_Учебник_2001

В некоторых машинах единой системы при умножении десятичных чи­ сел в коде Д | используется метод ускорения операции, при котором вся операция сводится к последовательному выполнению сложения или вычи­ тания на сумматоре дополнительного кода в зависимости от величины оче­ редной цифры множителя (табл. 7.3)

Гаким образом, предварительно должны быть подготовлены множимое и удвоенное множимое. При этом если предыдущая цифра была больше пягн, то действие на очередном шаге надо увеличить на +\А.

171

7 Выполнение операций над десятичными числами в цифровых автоматах

При умножении десятичных чисел часто используют другие приемы, позволяющие ускорить эту операцию, например, по формулам

= 560 - 2 + 280 -f 70 = 1120 - U 280 -f 70 = 1470 .

При двоично-десятичном представлении чисел прием (7.7) может быть упрощен, так как удвоение числа означает сдвиг влево, а деление на 2 — сдвиг вправо. Так как сдвиги проводятся над двоичными кодами, требуется коррекция тетрад на каждом шаге. Корректирующие поправки определяются для каждого Д-кода. Коррекция выполняется тогда, когда происходит сдвиг единицы из крайнего разряда данной тетрады в сосед­

Р е ш е н и е - Схема умножения выглядит следующим образом:

Ответ: .^5=00010000 00110010,

172

7.6.Деление чисел в Д-кодах

7.6.Деление чисел в Д-кодах

Деление десятичных чисел в Д-кодах выполняется методом последова­ тельного вычитания делителя из делимого на первом шаге и из остатков — на последующих шагах. Вычитание на каждом шаге проводится до тех пор, пока не получится отрицательный остаток. Каждый раз при получении по­ ложительного остатка добавляется единица в специальный счетчик, где на­ капливается очередная цифра частного. Затем осуществляется сдвиг на че­ тыре двоичных разряда и прибавление делителя до тех пор, пока не получится положительный остаток. Количество сложений (без последнего) является дополнением соответствующей цифры частного до 9, что заносит­ ся в счетчик очередной цифры частного.

Таким образом, процесс деления состоит из ряда последовательно че­ редующихся циююв сложения и вычитания со сдвигами. Знак частного по­ лучается как логическая сумма по модулю 2 знаков чисел.

Все действия при выполнении операции деления должны осуществ­ ляться на сумматоре дополнительного (обратного) кода, работающего по правилам сложения — вычитания соответствующего Д-кода.

Для просюты рассмотрим пример деления в десятичной системе счис­ ления, не прибегая к представлению чисел в виде тетрад.

\\\\\\ \ Осуществляется пробное вычитание: если результат положительный или равен n>.ii(), 1(1 [и.|р;|Г);||Ы!!ае^!ся сиишл прерывания, если отрицательный, то проводится сдвиг на

(),'П!у K-[p;i;sy

В ,'iinmoM случае иолушстся отрицшельный остаток (рассматривается только цифровая

173

7 Выполнение операций над десятичными числами в цифровых автоматах

Ответ С = 0,281

Алгоритм десятичного деления, подобный рассмотренному, использу­ ют в машинах ЕС ЭВМ.

Для ускорения операции деления применяют приемы, ана;югичнь1е приемам, употребляемым для ускорения выполнения операции умножения.

Пусть А — делимое, В — делитель, С —частное. Предположим, что

где Л„ —остаток от деления.

станавливается предыдущий положительный остаток, Затем принимаем,

Таким образом, при делении десятичных чисел, заданных в Д-коде, ре­ зультат получается в двоичной системе счисления.

Пример 7J9. Найти частное отделения /i = 0,2425 на 5 = 0.5200.

Р е ш е н и е . Для наглядности выполним этот пример в десятичной системе счисле­ ния с записью результата в двоичном коде, предполагая, что при переходе к определен­ ному Д-коду все операции над десятичным числами будут выполняться сю правилам этого Д-кода.

I !ослеловательность выполнения операции деления дана в таблице 7-4, Ответ. С-0,011101,

Так как при сдвиге чисел, представленных в Д-коды, приходи1ся вво­ дить гюправки, то для хранения делителя цеяесообраз1ю имен, самостоя­ тельный сумматор, в котором при переносе единицы из одной тетрады в другую автоматически вносится поправка.

174

7 7 Извлечение квадратного корня вД-кодах

ит.д. Конец

7.7.Извлечение квадратного корня в Д-кодах

Воснову алгоритмов извлечения квадратного корня в десятичной сис­ теме может быть с некоторыми уточнениями положена формула (6.8). Если для двоичной системы счисления в качестве нулевого приближения берут

величину Уо ^2'*'"' ', где Е{т/2) — целая часть числа т/2, am — наи­ больший показатель степени основания системы, присутствующего в за­ данном числе, то для десятичной системы правильный выбор нулевого приближения определяет число итераций, необходимых для получения за­ данной точности. Как известно, точность результата ограничивается чис­ лом разрядов сумматора, на котором проводится действие. Так, например, если имеется шестиразрядный сумматор и на шаге / промежуточное значе­ ние резульгата у, имеет одну верную цифру, то можно предположить, что у,^1 будет иметь по крайней мере две верных н одну сомнительную цифры, для получения которых используе-гся пять разрядов сумматора. Для про­ верки и выявления правильных цифр необходимо получить их на (/ + 2)-м шаге. Но из-за ограниченности разрядной сетки на этом шаге можно полу-

175

". Выполнение операний над десятичными числами в цифровых автоматах

ЧИТЬ только три цифры. Таким образом, на шестиразрядном сумматоре в результате можно получить две верных и одну сомнительную цифры. Из-за этого обстоятельства итерационный метод нахождения корня является не­ целесообразным для двоично-десятичного представления чисел. Рассмот­ рим несколько иной подход.

В десятичной системе счисления целое число можно представигь в ви­ де степенного полинома по основанию 10:

^ = а „ 1 0 " + . . . + а | 1 0 ' + а „ 1 0 ° .

Квадрат числа А можно записать так:

л' =а;10'"+2а„10"(Ч . - г10""' +... + 0,-10 +«„) + («„_,• 10""' +...

... + щ\й + а„)- =al •10-"+2а„(а„^1 -10""' +... + Щ • 10 + а„) +a,^^i •10-"'"" + + 2а„_| +IO""'lO"(a„_j-10"'- +,.. + «,• 10+ а„) +,.. +а? • Ю'+

где и — любое целое число.

Раскроем в этом выражении скобки и сгруппирует члены по убываю­ щим степеням:

/4' = а,; • 1 о'" + а„_| • 10""' (2а„ -10"+ «„_, • 10""') + a„_j • I О"' (2а„ 10" + + 2а„_| 10""' + а„_2 • 10""') + а„_, • 10"~'(2а„ • 10" + ... + a„j • 10""') + ,..

... + ао(2ч,-iC' + Za,,-! -Ю""' + ... + 2а, • 10 +а„).

Здесь на каждом последующем этапе содержимое в /-Й скобке огличается от содержимого скобки иа предыдущем этапе тем, что имеет дополни­ тельные слагаемые а,,^,^, • 10""'" и а„_, -10""'.

+ а„_| 10""' )а„^| 10""'+ (*„,, + а„_| • 10""' + a„^j • 10""' )a„_j 1 0 " ' + . . .

... + (*2 +«2 ''0^ +"1 ''О)"! -Ю + С*! +«1 •10 + а„)а„.

Данное допущение возможно, так как первоначальная запись числа А в виде степенного полинома предполагает, что число А не имеет степеней, больших чем п.

176

7.7- Извлечение квадратного корня вД-кодах

Вынося из скобок Ь, общие для скобки множители, получим

-4^ = (*,',*! • 10 + а,*, • 10 + а „ ) а „ -10^" + (ft,, • 10 + а„ • 10 + + а„^|)а„_| • 10'""'' +... + (*;• 10 + а, • 10 + а„)а„.

этапе.

Алгоритм ручного вычисления квадратного корня по данной формуле можно представить следующим образом:

1. Провести анализ двух старших разрядов числа А^, найти число а „ , квадрат которого наиболее близко подходит к двум старшим разрядам чис­ ла А^, оставаясь меньше последнего.

2. Провести вычитание из старших разрядов А^ квадрата числа а „ .

3.Удвой гь число а„ .

4.Сдвинуть остаток от вычитания на два разряда влево, а величину 2с/„ — на один разряд влево.

5.Приписать справа от остатка вычитания два следующих старших разряда числа А'^.

6.Провести анализ полученного числа на равенство нулю.

7.Если полученное число не равно нулю, то, анализируя его, найти та­ кое а„ I, которое, будучи умноженным на (2а„ • 10 + о,,^,), даст в результате Mncjro, меньшее 1юлученпого на пятом шаге, но наиболее близкое к нему по значению. Перейти к п. 3.

8.Если при анализе в п. 6 получено равенство, то перейти к п. 4, предвартельпо приписав справа от а„ нуль.

Ч, После получения количества цифр, равного и/2, прекратить вычис­ ление.

При анализе в пп. 1, 7 можно использовать следующее соображение: ес­ ли последова1ельпо рассматривать квадраты чисел от О до 9, то переход от квадрата од|ю1 о числа можно представить как прибавление к уже известному квалра1у определенного числа, которое можно определить из формулы

с = а' - ft' = (и - ft)(o + ft); если а = ft - 1 , то а' =Ь' +{а- Ь)(а + b) = b' + + (а + ft), где а — предыдущее число, возведенное в квадрат.

177

7.Выполнение операций над десятичными числами в цифровых автоматах

Данный метод позволяет повысить точность результата. На шестираз­ рядном сумматоре можно получить в результате пять точных цифр, так как не все число во время выполнения над ним действий располагается на сум­ маторе.

Кнедостаткам метода относят довольно длительное время, необходи­ мое для получения результата.

7.8. Перевод чисел в Д-код

Рассмотрим некоторые вопросы перевода десятичных чисел, представ­ ленных в Д-коде, в двоичную систему счисления.

Следовательно, перевод сводится к сдвигу соответствующих тетрад и их последующему суммированию. Это суммирование может быть выполнено по следующей схеме (для четырехразрядного числа):

реводе осуществляется суммирование по столбцам, то пары одинаковых символов дадут единицы переноса в соседние разряды.

178

7 8. Перевод чисел вД-код

Таким обрадом, перевод числа в Д-коде осуществляетх;я путем сумми­ рования элементов тетрад по столбцам с передачей соответствующих пере­ носов.

Подобные способы перевода реализованы в машинах ЕС ЭВМ, маши­ нах фирмы «IBM» и т. д. При разработке схем перевода приходится решать вопросы создания суммирующего устройства на много входов. При перево­ де, например, восьмиразрядного десятичного числа количество слагаемых в столбце оказывается равным 13. Значит, надо иметь сумматор на 13 входов. Реализовать такую схему можно с помощью многоступенчатых схем. При этом возникают дополнительные задержки сигнала, что снижает скорость перевода чисел.

Перевод числа из двоичной системы счисления в Д-код может осуще­ ствляться разными способами. В некоторых случаях для ряда последова­ тельных операций над двоичным изображением числа может быть исполь­ зована сама вычислительная машина (например, деление на число 1010 целых двоичных чисел; десятичные цифры получаются последовательно одна за другой. При дробных числах эта операция видоизменяется таким образом, чтобы при умножении на число 1010 можно было получить соотве'гствующие цифры десятичных дробей).

Алгоритмы перевода чисел из двоичной системы счисления в Д-код могут быть реализованы схемными или программными способами. Схем­ ные способы перевода десятичных чисел в Д-код или из Д-кода в двоичную систему счисления и обратно весьма перспективны.

Задание для самоконтроля

1. Какие комбинации являются запрещенными для кодов Дь Дг^ As ?

(Сумматор обратного кода).

10. Извлечь квадратный корень из числа /i =0,14412 на сумматоре обратного кода в коде

Д|

179

8. КОНТРОЛЬ РАБОТЫ ЦИФРОВОГО АВТОМАТА

8.1. Кодирование информации как средство обеспечения контроля работы автомага

Коды как средство тайнописи появились в глубокой древности. Из­ вестно, что еще древнегреческий историк Геродот в V в. до н. э. приводил примеры писем, понятных лишь адресату. Секретная азбука использовалась Юлием Цезарем. Над созданием различных секретных шифров работали такие известные ученые средневековья, как Ф. Бэкон, Д. Кардано и др. По­ являлись очень хитрые шифры и коды, которые, однако, с течением време­ ни расшифровывались и переставали быть секретом. Первым кодом, пред­ назначенным для передачи сообщений по каналам связи, был код С. Морзе, содержащий разное количество символов для кодирования букв и цифр. За­ тем появился код Ж. Бодо, используемый в телеграфии, в котором все бук­ вы или цифры содержат одинаковое количество символов. В качестве сим­ волов может выступать наличие или отсутствие (пробел) импульса в электрической цепи в Данный момент.

Коды, использующие два различных элементарных сигнала, называют­ ся двоичными. Эти сигналы удобно обозначать символами О и I. Тогда ко­ довое слово будет состоять из последовательностей нулей и единиц.

Двоичное кодирование тесно связано с принципом дихотомии, кото­ рый реализуется в графическом методе представления двоичной информа­ ции в виде графов.

В гл. 1 и 3 были рассмотрены общие и конкретные вопросы кодг!рования информации в цифровом автомате. Однако эти методы сами 1ш себе еще не обеспечивают правильность выполнения того или иного алгоритма. Рассмотренные ранее алгоритмы выполнения арифметических операций обеспечат правильный результат только в случае, если машина работает без нарушений. При возникновении какого-либо нарушения нормального функционирования результат будет неверным, однако пользователь об этом не узнает, если не будут предусмотрены меры, сигнализирующие о появле­ нии ошибки. Следовательно, с одной стороны, разработчиками машины

180