Главное


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

Если задан ряд положительных целых чисел 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 растет как сумма разрядностей тех же оснований.

Далее следует рассмотреть правила выполнения операций сложения и умножения в системе остаточных классов в случае, если оба числа и результат операции находятся в диапазоне [0, P). Пусть операнды А и В представлены соответственно остатками ai и bi по основаниям pi при i = 1, 2, . . ., 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)

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

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

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

Перейти на страницу: 1 2

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

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

Источник питания с микроконтроллером
Микроконтроллеры используются во всех сферах жизнедеятельности человека, устройствах, которые окружают его. Простота подключения и большие функциональные возможности делает его при ...

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

www.techspirit.ru © 2021