Если задан ряд положительных целых чисел p1, p2, . . ., рn, называемых в дальнейшем основаниями системы, то под системой счисления в остаточных классах принято понимать такую систему, в которой целое положительное число представляется в виде набора остатков (вычетов) по выбранным основаниям N = (a1, a2, ., an), причем образование цифр ai осуществляется следующим процессом

ai = N - pi , (1.1)

где i = 1, 2, ., n.

Т.е. цифра i-го разряда ai числа N есть наименьший положительный остаток от деления N на pi.

Здесь в отличие от обобщенной позиционной системы образование цифры каждого разряда проводится независимо друг от друга. Цифра i-го разряда ai представляет собой наименьший положительный остаток от деления самого числа N, а не предыдущего частного, как это имело место в позиционной системе, на i-e основание pi. Очевидно, что ai < pi.

В теории чисел доказано, что если числа pi взаимно простые между собой, то описанное цифрами a1, a2, ., an представление числа N является единственным.

Объем диапазона представимых чисел в этом случае как легко видеть, равен

P = p1 p2 . pn.

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

Далее следует рассмотреть правила выполнения операций сложения и умножения в системе остаточных классов в случае, если оба числа и результат операции находятся в диапазоне Результаты операций сложения и умножения А + В и АВ представлены соответственно остатками di и gi по тем же основаниям рi т. е.

А = (а1, а2, ., аn), (1.2)

B = (b1, b2, ., bn ), (1.3)

A + B = (g1, g2, ., g n), (1.4)

AB = (d1, d2, ., d n), (1.5)

и при этом имеют место соотношения

A < P, B < P, A + B < P, AB < P. (1.6)

Утверждается, что gi сравнимо с аi + b i по модулю рi, а d i сравнимо с аib i по тому же модулю, т. е.

gi ≡ аi + b i (mod рi ), (1.7)

di ≡ аib i (mod рi ), (2.8)

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

gi = аi + b i - рi, (1.9)

di = аi b i - рi. (1.10)

Необходимо охарактеризовать в общих чертах достоинства и недостатки введенной системы счисления в остаточных классах.

К достоинствам следует отнести :

· независимость образования разрядов числа, в силу чего каждый разряд несет информацию обо всем исходном числе, а не о промежуточном числе, получающемся в результате образования более младших разрядов. Отсюда вытекает независимость разрядов числа друг от друга и возможность их независимой параллельной обработки. При введении дополнительного контрольного основания остаток, взятый по этому основанию, несет избыточную информацию об исходном числе, что позволяет обнаруживать и исправлять ошибки в цифрах по рабочим основаниям системы; Перейти на страницу: 1 2

Другие статьи по теме

Электропреобразовательные устройства РЭС Курс «Электропреобразовательные устройства РЭС» является одной из первых инженерных дисциплин специальности «Радиотехника», обеспечивающей подготовку радиоинженера в области силовых рад ...

Исследование биполярного транзистора в статическом режиме Биполярным транзистором называют трёхслойную полупроводниковую структуру с чередующимися типом проводимости областей, созданную в едином кристалле и образующую два встречно включённых вз ...

Интегрированные информационные технологии Использование принципа интеграции в компьютерных системах относится к различным аспектам организации технологий: интеграция информации в базах и банках данных; интеграция программ в еди ...