Файл: Самохин А.Ф. Эксплуатация цифровых вычислительных машин [учеб. пособие].pdf

Скачать файл
Заказать решение

ВУЗ: Не указан

Категория: Не указан

Дисциплина: Не указана

Добавлен: 19.06.2024

Просмотров: 139

Скачиваний: 0

ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.

- £3-

Дополнение

т -значного

числа А равно

2

- / - А .

Неоо'ходшо

выбрать

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

 

 

был равен

дополнению кода 2 " -

1-(АЛ+М ) ,

где

П -

число

знаков

в коде.

Таким образом,

должно выпол­

няться

равенство

 

 

 

 

 

 

 

2 П-

 

=

 

 

откуда

 

 

 

 

 

 

 

м ={[гп-/-А/(2т-/)].

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

§ 4 .3 . Коды с использованием наименьших вычетов

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

Из теории чисел известно, что для любого числа можно за­ писать тождество

А - R (A)mod^ ,

(4 .1 )

которое читается следующим образом: число А тождественно о остатком R f A ) от деления А на модуль .

Это тождество устанавливает следующее соответствие;

A = C j t +В(А),

- 64-

где А

Ч • 1 ■R -

целы е

ч и с л а ;

 

А -

лю сю е

п - р а з р я д н о е ч и с л о ;

I

-

м о д у л ь ,

и л и д е л и т е л ь ;

 

 

-

ч а с т н о е о т

д е л е н и я н а

Q -

о с т а т о к

о т

д е л е н и я А н а Cj .

Под остатком мы обычно будем понимать наименьший положитель­

ный остаток

(наименьший вычет числа

А по модулю Q

) .

Если два целых числа А и В при

делении на натуральное

число ^

дают одинаковые остатки,

то они называются

сравни­

мыми по модулю

.

Сравнимость чисел

записывается так;

 

А =

3

mod^

(4 ,2 )

 

или

 

 

 

Р (А )

=

U (B)m od^

(4 .

3 )

Перечислим некоторые свойства сравнений.

I . Если А и В сравнимы по mod(J, , то их разность де­ лится на этот модуль без остатка,

т ,е .

если

A=Bmod^, ,

то R (

^ j modLj, -О

2 . Сравнения обладают свойством симметричности,

т .е .

если

А-Ьтос/д, ,

то £> =Ато

 

3 . Сравнения обладают свойством транзитивности,

т .е .

если

А-ВтоцО,

и B -C nod(j,

то А = С m od LL

4.

Сравнения по одному и тому же модулю можно почленно

складывать и вычитать,

 

 

 

т .е .

из

и

0 = /1modQ-

следует, что

 

 

А ± С = (' В 1 Л ) mod а

 

 

65-

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

т.е. если A + B = C f n o d ^ , то А = ( С - В ) mod

6. К любой части сравнения можно прибавить число, кратное модулю, т.е. если

A = B m o d C J,

, то

А + KCj. =

 

7. Обе части сравнения можно умножить на одно и то же

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

 

, то

 

 

 

A = B m od(f,

А К = В К т о о

1 д ,

8. Обе части сравнения можно возвести в одну и ту же сте­

пень, т.е. если A

= bm od ^ .

г то А

= В

m odcj,

9. Сравнения по одному и тому же модулюможно почленно

перемножить, т.е. если

 

 

 

 

А = В m od^

и

С = Д т о с ( д .

, то

А С = В Д m odcj,

10. Обе части сравнения можно разделить на их общий дели­ тель, если последний взаимно прост с модулем (имеет с нимоб­ щийнаибольший делитель, равный единице),

т.е. если А С =BCm dcf к

( С ,р ) =

/

, то

A

^ B r n d ty

11. Обе части сравнения и модуль можно разделить на любой

их общий делитель, т.е.

если

 

 

 

 

А = Bmodcj и А - К А

, В = К В '

и

C j,= K (j\

то A '- B 'm o d ^ .

12. Если сравнение имеет место по модулю

Q

, то оно

имеет место и по модулю,

равному любому делителюмодуля g ,

т.е. если A = B m o d g и

= o #То А ^ В fHod К

5.3т..0-7.

- 6 6 -

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

Пусть

,A=R(A2)mod^

............. An*R(An)ntodfy ,

тогда на основании свойства(4)

 

 

t ^ r t u M m o d q ,

 

<4' 4)

Но, согласно выражению (4 .1 ),

 

 

Ел, =

<W

 

< 4 ' 5 )

/*/

можно

записать:

Следовательно, на основании свойства 3

£ R M , ) = R ( | a i ) m d $

(4 .6 )

 

Аналогично можно получить тождество

 

 

f l R ^ i )

= k (U A i)m o d g ,

(4 .7 )

ы

14

 

 

Тождества (4 .6 ) и (4 .7 ) позволяют использовать наименьшие вычеты для контроля арифметических операций. Например, душ конт­ роле правильности сложения чисел А и В необходимо до выполнения операции над числами получить вычеты этих чисел Р (А ) и R ( Б ) ,

одновременно с выполнением сложения чисел сложить на отдельном суъвШоре эти вычеты, получить вычет суммы чисел и сравнить вычет cJ'MMbi чисел с суммой вычетов слагаемых. Несовпадение ука-

хе$ йа наличие ошибки.

Аналогично выполняется, с использованием тождества (4 .7 ),

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

- 6 7 -

Тахт образом, при контроле по наименьшим вычетам имеет­

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

Каждая кодовая комбинация в этом случае, очевидно, должна

состоять из кода числа и контрольной части, представляющей наименьший вычет кода числа.

Контрольную часть в дальнейшем мы будем называть контроль­ ным кодом, а контроль по наименьшим вычетам - контролем по мо­ дулю .

В практике используют два вица контроля по модулю: число­

вой контроль и цифровой контроль. В первом случае контрольным

кодом является

остаток Я (А ) от деления самого числа А на

модуль ^ .

В этом случае при контроле арифметических опера­

ций нет необходимости учитывать переносы. Во втором случае кон­

трольным кодом является остаток

/ ? ( £ ai )

от деления

 

1=0

 

суш и цифр числа А на мод

. Ь частности, цифровой конт­

роль двоичных чисел по

сводится, по

существу, к конт-

ролю на четность.

 

 

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

вычет же суммы цифр числа можно получить более простыми спосо­ бами.

Ниже будет показано, что при определенном выборе модуля можно, сохранив преимущество числового контроля (Отсутствие необходимости учитывать переносы) свести задачу получения вы­ чета к нахождению вычета суммы цифр числа как при цифровом контроле.

-68-

§4 .4 . Нахождение вычетов и выбор модуля

Для нахождения вычета числа по mod (J, в общем олучае

необходимо выполнить деление числа на этот модуль. Однако, так как операция деления занимает достаточно большое время, целе сообразно найти способ получения вычетов без выполнения деле­ ния. Покажем, что это возможно.

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

Р

А = ап-хрП 1+ °п-грп V . . + a / + o / = Z a , / >

(4-8)

Рассмотрим три случая: модуль больше основания системы,

модуль меньше основания

системы

и модуль равен основанию.

 

I .

Пусть

Q >р .

 

 

 

 

 

 

 

Тогда можно записать P ~ $ ~ f

»

где

-

положительное

число,

определяемое величиной

.

Подставив

значение

 

в выражение (4 .8 ), получим

 

 

 

 

 

 

 

 

А =

 

 

 

 

 

 

(4-9)

Запишем бином

С

в ввде

РОД8

 

 

 

 

Из рассмотрения разложения бинома видно, что в образовании

остатка

от деления этого

бинома на модуль

^

принимает учас­

тие только последний член ряда,

у которого

i= j

. Остальные

члены ряда остаток не образуют,

так как в

них

^

входит

со­

множителем. Следовательно, вычет числа А можно определить по тождеству:

Смотрите также файлы