Математические основы системы остаточных классов (стр. 7 из 19)
К любой кодовой системе применимы следующие требования:
- возможность представления в данной системе любой величины в рассматриваемом, заранее назначенном диапазоне;
- единственность представления – любая кодовая комбинация соответствует одному и только одному числу в заданном диапазоне;
- простота оперирования с числами в данной системе счисления.
Таким образом, коды чисел являются именами числовых объектов, составляющих числовой диапазон. Диапазоны как модели вещественных чисел должны с максимально доступной полнотой и простотой отражать свойства числового множества.
Всякое представление чисел рабочего диапазона является лишь составным элементом соответствующей машинной арифметики и не может рассматриваться отдельно от неё. Арифметические свойства той или иной системы счисления прежде всего определяются характером межразрядных связей, появляющихся в ходе выполнения операций над кодовыми словами. Исследования показали, что в рамках обычной позиционной системы счисления (ПСС) значительного ускорения выполнения операций добиться невозможно. Это объясняется тем, что в ПСС значение разряда любого числа, кроме младшего, являющегося результатом двухместной арифметической операции, зависит не только от значения одноимённых операндов, но и от всех младших разрядов, т. е. ПСС обладает строго последовательной структурой. Сегодня, предпочтение отдаётся вычислительным структурам, обладающими способностями к параллельной обработке информации. Этими особенностями обладают непозиционные коды с параллельной структурой, которые позволяют реализовать идею распараллеливания операций на уровне выполнения элементарных арифметических действий. Эта мысль зародилась в середине 50-х годов прошлого века, когда чешские учёные М. Валах и Л. Свобода в своих исследованиях в области непозиционных систем счисления рассматривают представление чисел в виде набора остатков от деления на выбранные натуральные модули – основания системы. Подобную систему счисления стали называть системой остаточных классов (СОК) или модулярной системой счисления (МСС). Вслед за чешскими учёными возможность применения этой системы в ЭВМ рассмотрена в исследованиях американских учёных Айкена, Семона и Гарнера.
Пусть заданы положительные числа
, которые называют основаниями или модулями системы. Обозначим 
. Эта величина характеризует объём диапазона системы. Под системой остаточных классов понимают такую непозиционную систему счисления, в которой целое неотрицательное число А можно представить в виде набора остатков от деления этого числа на выбранные основания системы, т. е. 
, 
. (1.1´)Возможность такого представления числа определяется теоремой о делении с остатком в кольце целых чисел.
Теорема. Если
, то существуют единственные 
, такие, что 
(1.2´)Несложно заметить, что каждый остаток
получается независимо от других и содержит информацию обо всём числе.Установить взаимно-однозначное соответствие между целыми числами из диапазона [0, P) и их остатками позволяет китайская теорема об остатках.
Возможность применения СОК в вычислительных алгоритмах обуславливается наличием определённого изоморфизма между математическими операциями над целыми числами и соответствующими операциями над системой целых неотрицательных остатков по отдельным модулям. Причём сложение, умножение, возведение в целую положительную степень любых целых положительных чисел совершенно идентичны соответствующим операциям, выполняемым над системой остатков.
Пусть операнды А и В, а также результаты операций сложения и умножения А + В и А·В представлены соответственно остатками
, 
, 
по основаниям 
, причём оба числа и результаты находятся в диапазоне [0, P), то есть , 
, 
, (1.3´) 
,и
, 
, 
, 
.Выражения (1.3) можно переписать в виде
(1.4´) 
. (1.5´)Справедливость этих правил выполнения арифметических действий в СОК непосредственно вытекает из свойств сравнения.
Действительно, на основании (1.1´) можно переписать в виде
Из представления А и В по теореме о делении с остатком (1. 2´) следует, что
, 
, 
, 
.Тогда
.Откуда,
.В случае умножения
.Тогда
.Следовательно,
.Примеры.
Даны: р1 = 2, р2 = 3, р3 = 5, р4 = 7. А = (0, 0, 3, 4), В = (1, 1, 2, 0).
Найти: А+В, А – В, АВ.
Решение.
А+В = (0, 0, 3, 4) + (1, 1, 2, 0) = (1, 1, 0, 4).
АВ = (0, 0, 3, 4)· (1, 1, 2, 0) = (0, 0, 1, 0).
А – В = (0, 0, 3, 4) – (1, 1, 2, 0) = (1, 2, 1, 4).
В отличие от позиционной системы счисления (ПСС), в которой число А представляется в виде
, (1.6´)где N – основание ПСС , значение числа в модулярном коде не зависит от местоположения каждого разряда в его представлении, а зависит от значения основания соответствующего разряда. Поэтому модулярный код является непозиционным.
Таким образом, выполнение арифметических операций в модулярном коде производится независимо по каждому из модулей, что и указывает на параллелизм данной системы. Это обстоятельство определяет поразрядное выполнение операций. Это свойство избавит от необходимости «занимать» или «переносить» единицу старшего разряда, что приводит к появлению кодов с параллельной структурой. Это позволяет распараллелить алгоритмы при выполнении арифметических операций.
Перевод чисел из ПСС в СОК при помощи выражения (1.1´) связан с реализацией операции деления, поэтому использование данного метода неэффективно.
Итак, операции сложения и умножения над числами, представленными в СОК, сводятся к соответствующим операциям над цифрами этого представления. Это относится и к возведению в степень, к вычислению значений многочлена и т. п. Операция вычитания в СОК заменяется сложением с аддитивной инверсией отрицательного числа. Все эти операции модульные, т. е. не требуют позиционных характеристик обрабатываемых чисел.
Исследования СОК выявили целый ряд её преимуществ.
1) Максимальный параллелизм. Для оценки уровня параллелизма системы счисления вводится специальный показатель
, (1.7´)где k– длина кода системы, n(v) – количество поразрядных показателей параллелизма
, не меньших заданного порога 
, причём 
, где ni – максимально возможное число пар цифр 
оказывающих влияние на значение суммы 
в ходе её формирования на языке данного кода. Для СОК показатель параллелизма принимает максимально возможное значение 
. Это говорит об отсутствии межразрядных связей в числе, записанном в СОК.