Система остаточных классов

Система остаточных классов (СОК) (англ. residue number system) — система счисления, основанная на модулярной арифметике.

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

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

Преимущества системы остаточных классовПравить

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

Формула для сложения:  , где

 
 
 
 

Аналогично выполняются вычитание, умножение и деление. Замечание: на деление накладываются дополнительные ограничения. Деление должно быть целочисленным, то есть делитель должен нацело делить делимое. Делитель должен быть взаимопростым со всеми модулями базиса.

Недостатки системы остаточных классовПравить

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

Применение системы остаточных классовПравить

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

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

Практическое применение: чехословацкая ламповая ЭВМ «EPOS», советская военная многопроцессорная суперЭВМ 5Э53, предназначенная для решения задач противоракетной обороны.

Специальные системы модулейПравить

В модулярной арифметике существуют специальные наборы модулей, которые позволяют частично нивелировать недостатки и для которых существуют эффективные алгоритмы сравнения чисел и для прямого и обратного перевода модулярных чисел в позиционную систему счисления. Одной из самых популярных систем модулей является набор из трех попарно взаимно простых чисел вида {2n−1, 2n, 2n+1}.

ПримерПравить

Рассмотрим СОК с базисом  . В этом базисе можно взаимооднозначно представить числа из промежутка от   до  , так как  . Таблица соответствия чисел из позиционной системы счисления и системы остаточных классов:

         
         
         
         
         
         

Пример сложенияПравить

Сложим два числа 9 и 14 в базисе  . Их представление в заданном базисе   и   (см. табличку выше). Воспользуемся формулой для сложения:  

 
 
 

  — по таблице убеждаемся, что результат равен 23.

Пример умноженияПравить

Умножим два числа 4 и 5 в базисе  . Их представление в заданном базисе   и   (см. табличку выше). Воспользуемся формулой для умножения:  

 
 
 

  — по таблице убеждаемся, что результат равен 20.

Замечание: если бы мы умножали или складывали числа, которые дали в результате умножения число больше или равное  , то полученный результат  , где   — результат операции в позиционной системе счисления.

Пример деления, при условии, что возможно деление нацелоПравить

Деление может быть выполнено аналогично умножению, но только если делитель делит делимое нацело, без остатка.
Для модулей   разделим число 1872 на 9.
Делим   на  .

Воспользуемся формулой
 

Здесь надо сказать, что  , что не то же самое, что просто разделить   на  .
По формуле   получаем:
 
 
 

 
 
 

Это и есть правильный результат — число 208. Однако такой результат можно получить, только если известно, что деление производится без остатка.

См. такжеПравить

ЛитератураПравить

СсылкиПравить