Система счисления в остаточных классах(СОК)

Главное отличие системы остаточных классов заключается в том, что у нее имеется не одно, а несколько оснований: b_i=(b₁,b₂,...,b_n), причем i-я цифра x_i любого числа Х представляет собой остаток от деления исходного числа на i-е основание b_i:

Единственное ограничение, налагаемое на величины основания b_i, заключается в том, что все b_i должны быть взаимно-простыми числами.

 

Если b₁=3 b₂=5, то

 

 0 0 0

 1 1 1

 2 2 2

 3 0 3

 4 1 4

 5 2 0

 6 0 1

 7 1 2

 8 2 3

 9 0 4

10 1 0

11 2 1

12 0 2

13 1 3

14 2 4

15 0 0

 

Полученное сочетание остатков можно принять для изображения (кодирования) чисел в разрешенном диапазоне.

Диапазон представления ^>_<0]

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

 Остаток от деления А на число N: A(mod N)=R

Пусть b=7, рассмотрим A=15 B=21

Остаток по модулю 7 А(mod 7)=15(mod 7)=1

                        B(mod 7)=21(mod 7)=0

Если C=A+B=15+21=36, то C(mod 7)=36(mod 7)=1

(1). т.е. C(mod 7)=(A+B)(mod 7)=A(mod 7)+B(mod 7)

Это можно доказать: A+B=C ; Но

Аналогично

(2). Если C=A*B, то C(mod 7)=(A*B)(mod 7)=A(mod 7)*B(mod 7)

     15=3*5 15(mod 3)=15(mod 5)=0

При этом если сумма (если произведение) остатков превышает модуль dm, то она (или оно) тоже берется по модулю dm (делится на dm).

 

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

 

Пример:

1.Сложить числа в двоично-кодированной СОК с основаниями b ₁ =3 b ₂ =5 b ₃ =7

38+47

38(mod 3)=2 38(mod 5)=3 38(mod 7)=3

X₁ =38₁₀=233(10/COK)=(10; 011; 011) (2/COK)

47(mod 3)=2 47(mod 5)=2 47(mod 7)=5

X₂=47₁₀=255(10/COK)=(10; 010; 101)(2/COK)

 

X₁ (10; 011; 011)

+

X₂ (10; 010; 101)

X₃ (01; 000; 001) (2/COK)

 

Проверка: 38₁₀+47₁₀=85₁₀

85(mod 3)=1   85(mod 5)=0   85(mod 7)=1

 

 

В СОК наиболее просто и экономично строятся реверсные счетчики, т.к. при увеличении или уменьшении некоторого числа на 1 все остатки от деления также соответственно увеличатся на 1. Если при увеличении числа некоторый остаток имеет величину bi-1, то он заменяется в следующем шаге на 0. При уменьшении числа остаток, равный 0 заменяется на b_i-1.

 

Недостатки СОК

 

1. Относительная сложность операции деления. Обычно деление сводится к определению обратной величины делителя Х по итеративной формуле  с последующим умножением найденного значения на делимое.

2. Значительная сложность перевода чисел из принятой позиционной системы в СОК и обратно. Прямое деление на все основания для получения цифр практически не используется (не эффективно и долго). На практике, т.к. в машине уже есть арифметическое устройство, работающее в СОК, для перевода чисел пользуются наборами всех цифр и нужных степеней основания исходной (например, десятичной) систем, представляемых в СОК. Так для перевода числа 14₁₀ в СОК с основанием b_i=3;5 нужны такие константы: 10⁰=1=(1;1) 4=(1;4) 10¹=10=(1;0) Тогда 14₁₀=1*10¹+4*10⁰=(1;1)*(1;0)+(1;4)(1;1)=(1;0)+(1;4)=(2;4) Обратное преобразование еще более сложно

3. Относительная сложность сравнения чисел в СОК, поскольку их поразрядное сравнение ничего не дает.

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

 

В следствии этого СОК получил применение в основном в специализированном ЭИВМ, в которых необходимо высокое быстродействие, диапазон изменения чисел фиксирован, а операция деления встречается редко.

 

 

Контроль по модулю.

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

 

1. A₁=B₁(mod p) A₂=B₂(mod p)

(A₁+A₂)mod p=B₁(mod p)+B₁(mod p)

2. A=B(mod p) C=B(mod p) A=C(mod p)

3. A₁=B₁(mod p) C=B₂(mod p) (AC)mod p=B₁B₂(mod p)

4. A=B(mod p) Am=Bm(mod mp)

5. A=B(mod p) Aⁿ=Bⁿ(mod p)

6. (mod p)

 

Существуют два метода получения контрольного кода: числовой и цифровой

 

Числовой метод контроля

 

Код числа определяется в ССОК с mod P              

 r_A=A-[ ]

Если p=q (основанию СС), то контролируется только младший разряд (плохо).

Аналогично для m<n p=q^m контролируется m младших разрядов

Контроль на основании выполнения операций в ССОК

Неудобство: получение r_A

 

Цифровой метод контроля

При цифровом методе:

 

или  , где a_i-цифра числа

 

Контрольный код получают:

1)  непосредственным делением  на mod p

2)  суммированием цифр по mod p

(Второй способ легче)

 

Однако при цифровом методе свойства сравнений не всегда справедливы из-за наличия переносов (заемов) при арифметических действиях. Поэтому контрольный код результата операции находят с коррекцией.

Но можно выбрать такой модуль, что коррекция не нужна. Очевидно, это будет если:

 

r_A=A mod p

 

т.е. , но A=

т.е

Это возможно, если a_iqⁱ=a_i(mod p)

т.е. qⁱ=1(mod p) q=1(mod p)

т.е. q=mp+1, где m-целое число

 

Но тогда

 

Анализ показывает, что для двоичной СС (q=2) целого p нет. Это значит, что контролируемую информацию надо представлять в некоторой промежуточной СС.

 

К модулю p представляют требования:

1)  величина mod p должна быть такой, чтобы возникновение ошибки нарушало сравнимость кодов.

2)  образование контрольного кода должно осуществляться простыми средствами

3)  величена mod p должна быть по возможности небольшой, чтобы не возрастал объем вспомогательного оборудования.

 

Т.к. в ЭВМ информация представляется символами двоичного алфавита, то для контроля целесообразно перейти к системам с основанием q=2^S (S 2): 4,8,16

Переход от двоичного представления исходной информации к новому представлению с основанием q=2^S осуществляется разбиением информации на группы по S разрезов с последующим суммированием этих групп по модулю p=(2^S-1)/m или при m=1 p=2^S-1

Модули для контроля p=3 (m=2, s=2, p=3)

                        p=7 (m=1, s=3, p=7)

 

Пример: контроль по mod 3

Контролируемая информация представляется символами 4-й системы с последующим суммированием по mod 3 диад (свертывание). Требуется двухразрядный двоичный сумматор с цепью циклического переноса из старшего разряда в младший.

A=46=101110₂ B=29=011101₂