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

Подождите немного. Документ загружается.

7.5. Умножение чисел в Д-кодах

Таблица 7.2

Су

0000

0001

(1000

0000

мматор

0000 0000

* ООП 1101

ООН 1101

* ООП П01

1101 0100

* ООП 1101

0001 0001

* ООП 1101

0100 1П0

0001 0100

* ООП 1101

1011 0001

* ООП 1101

0000 1110

Регистр в

0010 0100

0001

ООП

0001

0010

0001

0000

1П0 0010

0001

0000

П10 П10

Примечание

и, п. см - 0; РгВ :=

IS],,,,;

?гА := {А\^

Анализ тетрады й,

Конец анализа

Сдвиг на четыре разряда

Анализ тетрады

Ь-^

Конец анализа

Сдвиг на четыре разряда

Конец

В некоторых машинах единой системы при умножении десятичных чи-

сел в коде Д| используется метод ускорения операции, при котором вся

операция сводится к последовательному выполнению сложения или вычи-

тания на сумматоре дополнительного кода в зависимости от величины оче-

редной цифры множителя (табл. 7.3)

Таблица 7.3

Очередная [Еифра

миожигеля

Вид операции

*\А

+ 2Л

+ 2А + \А

+ 2А + 2А

Очередная цифра

множителя

Вил операции

+ 2А + 2А + )А

-2А-2А

-2А-\А

-2А

-и

Гаким образом, предварительно должны быть подготовлены множимое

и удвоенное множимое. При этом если предыдущая цифра была больше

пягн,

то действие на очередном шаге надо увеличить на +\А.

171

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

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

позволяющие ускорить эту операцию, например, по формулам

АВ

2А —

если Д

четное число,

R — 1

АВ = 2Л + Л, если В

нечетное число.

(7.7)

Действия в соответствии с (7.7) можно рассмотреть на примере деся-

тичных чисел: 35-42 = 2-35-(42/2) = 70-21 = 140-10 +70 = 280-5 + 70 =

= 560

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

При двоично-десятичном представлении чисел прием (7.7) может

быть упрощен, так как удвоение числа означает сдвиг влево, а деление

на 2 — сдвиг вправо. Так как сдвиги проводятся над двоичными кодами,

требуется коррекция тетрад на каждом шаге. Корректирующие поправки

определяются для каждого Д-кода. Коррекция выполняется тогда, когда

происходит сдвиг единицы из крайнего разряда данной тетрады в сосед-

нюю тетраду. Например, для кода Д, корректирующая поправка равна

-f ОНО для тетрад множимого и -ООП (или -f 1101) для тетрад множи-

теля.

Пример 7.17 (СМ-(19|). Умножить числа /(=00100100 и fl = 0100 00ll методом (7 7) в

коле Д,.

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

, . 0100 ООП

(-•) 0010 0001

(-*) 0001 0000

0000

0010

0100

1001

0100

1000

4.0000

^0110

It]

•) 0000 +1000

1101

0000

(-•) 0000

0101

0010

0001

0000

1010 Olio

4.0010 +1100 («-

^0110 ^0110

0011 +0010

оно

1001 0010

0100 (•

+0000

*0000

0000

0П01

0010

0100

оно

0111

1001

+0000

+0110

0100

1000

+1100

+0110

0010

0100

-) 0000 0010 0110 0100

ООН 1000

0111 ,0000

+0110

0100 ,

1000 («-

0111

1110

оно

1101

1000

0000

(«-)

0000

0111

1001

4т

оно

+ 1100

+0110

ООН

1000

+1100

+0110

ООН)

сдвиг

СДВИ!"

поправки

Сдвиг

поиpanки

СДВИ1

поправки

СДВИ!

поправки

сдвиг

поправки

Конец,

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

0001 0000 ООП 0010

172

7.6.

Деление чисел в

Д-кодах

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

Деление десятичных чисел в Д-кодах выполняется методом последова-

тельного вычитания делителя из делимого на первом шаге и из остатков —

на последующих шагах. Вычитание на каждом шаге проводится до тех пор,

пока не получится отрицательный остаток. Каждый раз при получении по-

ложительного остатка добавляется единица в специальный счетчик, где на-

капливается очередная цифра частного. Затем осуществляется сдвиг на че-

тыре двоичных разряда и прибавление делителя до тех пор, пока не

получится положительный остаток. Количество сложений (без последнего)

является дополнением соответствующей цифры частного до 9, что заносит-

ся в счетчик очередной цифры частного.

Таким образом, процесс деления состоит из ряда последовательно че-

редующихся циююв сложения и вычитания со сдвигами. Знак частного по-

лучается как логическая сумма по модулю 2 знаков чисел.

Все действия при выполнении операции деления должны осуществ-

ляться на сумматоре дополнительного (обратного) кода, работающего по

правилам сложения — вычитания соответствующего Д-кода.

Для просюты рассмотрим пример деления в десятичной системе счис-

ления, не прибегая к представлению чисел в виде тетрад.

Пример 7.18 I'auicJiMii. число Л = 0.154675 на й = 0,550 .

1'с

1м

е и и с yciiiiionKii исхолпого положения,

\\\\\\ \ Осуществляется пробное вычитание: если результат положительный или равен

n>.ii(),

1(1 [и.|р;|Г);||Ы!!ае^!ся сиишл прерывания, если отрицательный, то проводится сдвиг на

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

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

4i\L\\.

чисел)

Шаг 2

OciaroK <

Шаг 3:

154 675

55 000

99 675

55 000

675

55 000

89 675

5 500

95175

5 500

00 675

СЧ:=0

СЧ

1 +1

С,

СЧ:=9

СЧ:=9-|

Г,

173

7 Выполнение операций

над

десятичными числами

цифровых автоматах

Шаг

00 675

550

00125

550

99 575

СЧ:=0

СЧ-0+1

С,

т.

д.

Остаток

Ответ

С = 0,281

Алгоритм десятичного деления, подобный рассмотренному, использу-

ют в машинах ЕС ЭВМ.

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

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

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

удалось отыскать частное в виде С =

О,

с^С2

•. •

с„

. Тогда

^-5-(с,-2"'

+С2-2~' +... + с„-2") + Л„, (7.8)

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

Пусть R„ =0. Положим, что С| = I, Cj =

Сз

= ... =

. Тогда остаток на

первом шаге Л, =

А-Т^В.

Если Л( > О, то С| = 1; если Л, < О, то с, =

. В последнем случае вос-

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

что Cj ~ I, а остальные с, =0 и т. д.

Остаток на любом шаге

Л, ^A~BJ^C, -1" . (7.9)

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

зультат получается в двоичной системе счисления.

Пример

7J9.

Найти частное отделения

/i =

0,2425

на 5

= 0.5200.

Решение.

Для

наглядности выполним этот пример

десятичной системе счисле-

ния

записью результата

двоичном коде, предполагая,

что при

переходе

определен-

ному Д-коду

все

операции

над

десятичным числами будут выполняться

сю

правилам

этого Д-кода.

!ослеловательность выполнения операции деления дана

таблице

7-4,

Ответ.

С-0,011101,

Так как при сдвиге чисел, представленных в Д-коды, приходи1ся вво-

дить гюправки, то для хранения делителя цеяесообраз1ю имен, самостоя-

тельный сумматор, в котором при переносе единицы из одной тетрады в

другую автоматически вносится поправка.

174

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

Таблица 7.4

Делитель на /-м шаге

0.5200

0,2600

0,1300

0.0650

0.325

0.0162

0.0081

Сумматор

0,2425

0,2600

9,9825

*0,2600

0,2425

0,1300

0,1125

0,0650

0,0475

"0,0325

0,0150

"0,0162

9,9938

*0,0162

0,0150

"0,0081

0,0069

и т.д.

Примечания

И. П.

В2-'\ СМ:=|СМ1-в-2';

остаток отрицательный с, = 0 ;

восстановление й,;

fl-2 ^ CM-(CMl-fl 2-:

остаток положительный С2 =

S 2"'; CM:=(CMl-fl 2^';

остаток положительный с^ =\'.

В-2-';

СМ:=(СМ1-в 2 *;

остаток положительный с, =

;

В 2"'; СМ:=[СМ]-В-2-';

остаток отрицательный с, = 0 ;

восстановление й;;

В 2^; СМ:=(СМ1-В-2-';

остаток положительный с^ =

;

Конец

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

В основу алгоритмов извлечения квадратного корня в десятичной сис-

теме может быть с некоторыми уточнениями положена формула (6.8). Если

для двоичной системы счисления в качестве нулевого приближения берут

величину Уо

^2'*'"'

', где Е{т/2) — целая часть числа т/2, am — наи-

больший показатель степени основания системы, присутствующего в за-

данном числе, то для десятичной системы правильный выбор нулевого

приближения определяет число итераций, необходимых для получения за-

данной точности. Как известно, точность результата ограничивается чис-

лом разрядов сумматора, на котором проводится действие. Так, например,

если имеется шестиразрядный сумматор и на шаге / промежуточное значе-

ние резульгата у, имеет одну верную цифру, то можно предположить, что

у,^1 будет иметь по крайней мере две верных н одну сомнительную цифры,

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

верки и выявления правильных цифр необходимо получить их на (/ + 2)-м

шаге. Но из-за ограниченности разрядной сетки на этом шаге можно полу-

175

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

ЧИТЬ только три цифры. Таким образом, на шестиразрядном сумматоре в

результате можно получить две верных и одну сомнительную цифры. Из-за

этого обстоятельства итерационный метод нахождения корня является не-

целесообразным для двоично-десятичного представления чисел. Рассмот-

рим несколько иной подход.

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

де степенного полинома по основанию 10:

^ = а„10"+... + а|10' +а„10°.

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

л'

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

...

щ\й

а„)- =al •10-"+2а„(а„^1

-10""'

+...

+ Щ •

10 + а„) +a,^^i

•10-"'""

+ 2а„_| +IO""'lO"(a„_j-10"'- +,.. + «,• 10+ а„) +,.. +а?

•

Ю'+

+ 2а, Ю^а,-10'+ а, 10 +a„) + aj'lO'' + 2а,

•

Ю'Са,

•

10 +

а(,) + 0|- 10' -Ю' +2а, Ю-Оо +al,

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

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

щим степеням:

/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""'.

Обозначим скобку на каждом этапе через Ъ, и примем Л,,., -

^»i+i ~ ^ ' тогда

А'

=(Ь^^^^+

а„|

•

10"*' + а„

•

10")а„

•

10"

+ (*„ + а„

•

10" +

а„_|

10""'

)а„^|

10""'+ (*„,, + а„_|

•

10""' + a„^j

•

10""' )a„_j 10"'+...

... + (*2 +«2 ''0^ +"1

''О)"!

-Ю +

С*!

+«1 •10 + а„)а„.

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

виде степенного полинома предполагает, что число А не имеет степеней,

больших чем п.

176

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

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

-4^

(*,',*!

•

10 + а,*,

•

10 +а„)а„ -10^" + (ft,, • 10 + а„

•

10 +

+ а„^|)а„_|

•

10'""''

+... + (*;• 10 + а,

•

10 + а„)а„.

Окончательно получим

л'

=Х!(*,'*! -Ю + а,^,-10 +а,)а,-10^' , (7.10)

где ft,'^| — коэффициент при а,,^,

10^''*'',

т.е. полученный на предыдущем

этапе.

Алгоритм ручного вычисления квадратного корня по данной формуле

можно представить следующим образом:

Провести анализ двух старших разрядов числа А^, найти число а„,

квадрат которого наиболее близко подходит к двум старшим разрядам чис-

ла А^, оставаясь меньше последнего.

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

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

Сдвинуть остаток от вычитания на два разряда влево, а величину

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.8.

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

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

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

Пусть задано десятичное число A^a^a^Oia^, десятичная цифра, кото-

рая должна быть представлена в Д-коде в виде а, = {a^a^a'^a'^}^.

Используя равенство 10 = 8 + 2 = 2'+ 2', любое десятичное целое чис-

ло можно записать как

А,=(...

((аГоГ а7 а;" (2^ + 2') + а^аза'аГХг' + 2') +

+ а.',а.1а.\а\)(1^ + 2') + a^ajajaj).

Умножение на 2 означает сдвиг двоичного кода на к разрядов влево.

Следовательно, перевод сводится к сдвигу соответствующих тетрад и их

последующему суммированию. Это суммирование может быть выполнено

по следующей схеме (для четырехразрядного числа):

аХ

а','

а"

а.

оГ

а,

о"'

а"

о"

«Г

а"

^Г

«Г

СЕ"

а'"

о1

<•

«7

а"

а"*

«Г

а"

«•"

а'

а^

а'

а"

а"'

o-l

а]'

а"

а"'

а'"

а"

а*

a'l

а7

а"

а*

а4

а"

a'j

а\

«Г

а'

а',

а"

а\

12 II 10 98765432 I О

В схеме некоторые символы встречаются многократно. Так как при пе-

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

символов дадут единицы переноса в соседние разряды.

178

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

Таким обрадом, перевод числа в Д-коде осуществляетх;я путем сумми-

рования элементов тетрад по столбцам с передачей соответствующих пере-

носов.

Подобные способы перевода реализованы в машинах ЕС ЭВМ, маши-

нах фирмы «IBM» и т. д. При разработке схем перевода приходится решать

вопросы создания суммирующего устройства на много входов. При перево-

де,

например, восьмиразрядного десятичного числа количество слагаемых в

столбце оказывается равным 13. Значит, надо иметь сумматор на 13 входов.

Реализовать такую схему можно с помощью многоступенчатых схем. При

этом возникают дополнительные задержки сигнала, что снижает скорость

перевода чисел.

Перевод числа из двоичной системы счисления в Д-код может осуще-

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

тельных операций над двоичным изображением числа может быть исполь-

зована сама вычислительная машина (например, деление на число 1010

целых двоичных чисел; десятичные цифры получаются последовательно

одна за другой. При дробных числах эта операция видоизменяется таким

образом, чтобы при умножении на число 1010 можно было получить соот-

ве'гствующие цифры десятичных дробей).

Алгоритмы перевода чисел из двоичной системы счисления в Д-код

могут быть реализованы схемными или программными способами. Схем-

ные способы перевода десятичных чисел в Д-код или из Д-кода в двоичную

систему счисления и обратно весьма перспективны.

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

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

Преобразовать число /i =-0,6315 в дополнительный кол в кодах Д, н Д;-

Преобразовать число В = -0,1234 в обратный код в кодах Д; н Д^.

Сложигь числа Л

-0,6315 и

= 0,1234 на cyMMarqje дополнительного кода в коде Д,.

Сложить числа /4 = 0,6315 и В = -0,1234 на сумматоре обратного кода в коде Д^.

6. Сложи! ь числа Л

0,М45

и S=-0,1246 на сумматоре дополнительного кода в коде Д^.

Перемножить

чис па

А=0,\2 и В = 0,13 на сумматоре прямого кода в коде Д, -

8. Разделигь число А

0,1246 на S = 0,13 на сумматоре дополнительного кода в коде Д^.

9. Перемножить числа ^ = 0,146 и 5 = 0,178 ускоренным методом по (7.7) в коде Д,

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

10.

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

Д|

179

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

8.1.

Кодирование информации как средство обеспечения

контроля работы автомага

Коды как средство тайнописи появились в глубокой древности. Из-

вестно, что еще древнегреческий историк Геродот в V в. до н. э. приводил

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

Юлием Цезарем. Над созданием различных секретных шифров работали

такие известные ученые средневековья, как Ф. Бэкон, Д. Кардано и др. По-

являлись очень хитрые шифры и коды, которые, однако, с течением време-

ни расшифровывались и переставали быть секретом. Первым кодом, пред-

назначенным для передачи сообщений по каналам связи, был код С. Морзе,

содержащий разное количество символов для кодирования букв и цифр. За-

тем появился код Ж. Бодо, используемый в телеграфии, в котором все бук-

вы или цифры содержат одинаковое количество символов. В качестве сим-

волов может выступать наличие или отсутствие (пробел) импульса в

электрической цепи в Данный момент.

Коды, использующие два различных элементарных сигнала, называют-

ся двоичными. Эти сигналы удобно обозначать символами О и I. Тогда ко-

довое слово будет состоять из последовательностей нулей и единиц.

Двоичное кодирование тесно связано с принципом дихотомии, кото-

рый реализуется в графическом методе представления двоичной информа-

ции в виде графов.

В гл. 1 и 3 были рассмотрены общие и конкретные вопросы кодг!рова-

ния информации в цифровом автомате. Однако эти методы сами 1ш себе

еще не обеспечивают правильность выполнения того или иного алгоритма.

Рассмотренные ранее алгоритмы выполнения арифметических операций

обеспечат правильный результат только в случае, если машина работает без

нарушений. При возникновении какого-либо нарушения нормального

функционирования результат будет неверным, однако пользователь об этом

не узнает, если не будут предусмотрены меры, сигнализирующие о появле-

нии ошибки. Следовательно, с одной стороны, разработчиками машины

180