пример 6.7. Для системы модулей = 2, /?2 = 3, P?, - iPa - 7 найти значения Og, «з и 04 и с помощью найденных значений а, перевести код в остатках числа {х) = 0240 в десятичную запись.

Для данной системы коду 1000 соответствует число, которое делится без остатка на 3. 5, 7 и является нечетным. Единственным числом такого рода в М является число, равное произведению трех модулей, на которые оно делится без остатка. Таким образом, «1 = 105. Аналогично код 0100 означает число, делящееся без оетатка на 2, 5 и 7 и дающее остаток 1 при делении на 3. Число, равное произведению соответствующих модулей 70, удовлетворяет и тому условию, что при делении на 3 оно дает остаток единицу. В силу единственности кодирования в Ж ag = 70. С помощью подобных же рассуждений получаем, что аз = 126 и а4=120.

Отсюда

(л;),о==0 X 105 + 2 X 70 + 4 X 126 + О X 120 = 644.

Это значение лежит вне множества М. Поэтому его необходимо свести к элементу из Ж путем деления полученного числа на произведение модулей системы. Окончательно (x)io= 14. !

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

Т а б л и ц а 6.3

На первый взгляд может- показаться, что второй метод перевода существенно проще первого. Однако у этого метода имеется один недостаток, который зачастую заставляет предпочитать первый метод. Этот недостаток связан с тем, что кроме оборудования, работающего по модулям Pi в этом случае в машине

необходимо иметь оборудование, работающее по модулю р Рг-Pi-... • Рп, что усложняет и удорожает конструкцию машины.

Рассмотрим еще один способ перевода числа из кода в остатках в позиционную систему, определяемую соотношением (6.1), который в ряде случаев оказывается предпочтительнее описанных

• выше методов перевода *. ,

Для удобства записи через щ будем в дальнейшем обозначать цифру, стоящую в коде в остатках числа х в разряде, соответ-

ствующем модулю pi, т.- е. щ = rest -. Возьмем представление х

с помощью (6.1)

♦ X = Ь„ 1- Pi-Pi- .... • Pn i + •- + bi- pi + Ьо

и каждое слагаемое в этом представлении запишем в коде в остатках (слагаемые выписываем в обратном порядке)

Ьо. Ьо.-.. .bo(mod/;,), • • •

О, Ь,- pi (mod/>2). • • • . bipi (modP2), О, О..........b Pipz (mod Рз)

. . О, О, . . . . . . . . ,b„ iPi-P2-- •P„ ,(modp„).

Из этих соотношений вытекает, что

й, = Ьо (mod pi), " • •

. a2 = b„+Pi Pi (той Pi).

«3 = bo + bi pi (mod Ps) + b2Pi- P2 (mod p)

y. «n = be + b,/;,(modp„)-f-...+b„ j./;,-/;2. ... .p j(modp„).

Перепишем полученные соотношения в следующем виде

I bQ = ai (mod pi),

bf Pi (mod P2) = «2 - bo (mod pg), bi- Pi-P2 (mod ps) = «3 - bo - 61 (modp)

b„ r PiPi - • P„ i (mod>„) = a„ - b„ - (modp„) -- • • • - b„ 2-A-• • • • P„ 2 p„).

Общий член в этих соотношениях имеет вид

i-i 1-2 ki

b, ,IIPft(modp,) = «i -Ьо- S hU Pi (той Pi). ft=i ft=i 1=1

* Этот способ предложен М. Н. Андреевым.

Подберем множитель Ц так, чтобы выполнялось сравнение г-а

Li П Рк (mod Pi) = 1 (mod pi).

Тогда

bi . = (ai - bo)Li - biLiPi-...-

- fi-2 iPi- P2......Pj 2 P

или г • "

= («г - bo) Ц - LibkYipi (mod pi). *=i г=1 .

Для каждого коэффициента Li\pi -можно подобрать такой

множитель TVi = 1 (modр/), чтобы выполнялось сравнение к-1

kijl Pi qtk (той Pi), qik<Pi-1=1 -

Тогда общий член соотношений запишется как

bi i = qtoh + qiibi +...+ qi i ц a. . • (б.з)

Соотношения (6.3) являются рекуррентными. Например, для системы модулей 2, 3, 5, 7, Н, 13} эти соотношения имеют вид

Ьо-= й1 (mod-2), • Ь, = Ьо + 2й2 (mod 3),

b2 = 4bo + 3bi +«3(m6d5). . . •

- b3 = 3bo + 6bi + 4&2 + 4«4(mod7), bi = lObo + Щ + 5&2 + ЗЬз + «5 (mod 11), 655= lObo + 7&, + 8.&2 + 63 + Ibi + Зйб (mod 13).

Заметим, что перевод числа из кода в остатках в какую-либо позиционную систему решает проблему сравнения двух чисел. Если оба числа находятся в одном множестве М или М", то при попарном сравнении цифр bi или десятичных цифр, начиная со старшего разряда, можно получить ответ на вопрос: какое число больше. Отметим, что при использовании для сравнения представления чисел в виде (6.1) для сравнения двух и-разрядных чисел вкоде в остатках*тре-буется 4и + 2 такта работы машины.

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