Если задан ряд положительных целых чисел 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
Другие статьи по теме
Электропреобразовательные устройства РЭС Курс «Электропреобразовательные устройства РЭС» является одной из первых инженерных дисциплин специальности «Радиотехника», обеспечивающей подготовку радиоинженера в области силовых рад ...
Исследование биполярного транзистора в статическом режиме Биполярным транзистором называют трёхслойную полупроводниковую структуру с чередующимися типом проводимости областей, созданную в едином кристалле и образующую два встречно включённых вз ...
Интегрированные информационные технологии Использование принципа интеграции в компьютерных системах относится к различным аспектам организации технологий: интеграция информации в базах и банках данных; интеграция программ в еди ...