Введение в модулярную арифметику

в 11:19, , рубрики: Алгоритмы, Электроника для начинающих

В обычной жизни мы обычно пользуемся позиционной системой счисления. В позиционной системе счисления значение каждого числового знака (цифры) в записи числа зависит от его позиции (разряда) [1]. Однако существуют и так называемые «непозиционные системы счисления», к одной из которых относится «система счисления в остатках» (или в оригинале Residue Number System (RNS)), являющаяся основой модулярной арифметики. Модулярная арифметика базируется на «Китайской теореме об остатках» [2], которая для нашего случая звучит следующим образом:

Для любой системы взаимно простых чисел p1, … pn, любое число X из диапазона [0; M), где M = p1*p2*…*pn взаимооднозначно представимо в виде вектора (a1, a2, …, an), где ai = X%pi (здесь и далее «%» — операция взятия остатка от целочисленного деления X на pi).
p1, … pn – модули системы
a1, a2, …, an – остатки (вычеты) числа по заданной системе модулей

На первый взгляд непонятно какое преимущество может дать такая система, однако существует 2 свойства, которые позволяют эффективно использовать модулярную арифметику в некоторых областях микроэлектроники:

  1. Отсутствие переноса разрядов в сложении и умножении. Пусть нам дано два числа X1 и X2, представленные в виде системы остатков (x11, x12, …, x1n) и (x21, x22, …, x2n) по системе взаимнопростых чисел (p1, p2, …, pn). В этом случае:
    X3 = X1 + X2 = ((x11+x21)%p1, (x12+x22)%p2, …, (x1n+x2n)%pn)
    X4 = X1 * X2 = ((x11*x21)%p1, (x12*x22)%p2, …, (x1n*x2n)%pn)
    То есть что бы сложить или умножить два числа, достаточно сложить или умножить соответствующие элементы вектора, что для микроэлектроники означает, что это можно сделать параллельно и из-за малых размерностей p1, p2, …, pn сделать очень быстро.
  2. Ошибка в одной позиции вектора не влияет на расчеты в других позициях вектора. В отличие от позиционной системы счисления все элементы вектора равнозначны и ошибка в одном из них ведет всего лишь к сокращению динамического диапазона. Этот факт позволяет проектировать устройства с повышенной отказоустойчивостью и коррекцией ошибок.

Обычное умножение Модулярное умножение
Введение в модулярную арифметику Введение в модулярную арифметику

Но не всё так гладко, как хотелось бы. В отличие от позиционной системы счисления, следующие операции (называемые «немодульными») выполняются сложнее, чем в позиционной системе счисления: сравнение чисел, контроль переполнения, деление, квадратный корень и.т.д. Первые успешные попытки применения модулярной арифметики в микроэлектронике были предприняты ещё в 1950-х годах, но из-за сложностей с немодульными операциями интерес несколько утих. Однако в настоящее время модулярная арифметика снова возвращается в микроэлектронику по следующим причинам:

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

В данный момент модулярная арифметика применяется в следующих областях: цифровая обработка сигналов, криптография, обработка изображений/аудио/видео и.т.д.

Прямое преобразование

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

Пример: Пусть требуется найти представление числа X = 25 по системе модулей (3, 5, 7). X = (25%3, 25%5, 25%7) = (1, 0, 4).

Реализация нахождения вычета в микроэлектронике по заданному модулю строится на следующих свойствах вычетов:
(a+b) % p = (a%p + b%p)%p
(a*b) % p = (a%p * b%p)%p

Любое число X можно записать в виде X%p = (xn-1*2n-1 + xn-2*2n-2 + x0*20)%p = ((xn-1)%p*2n-1%p) + ((xn-2)%p*2n-2%p) + … + x0%p)%p. Поскольку в данном случае xn-1, … x0 равны 0 или 1, то фактически нам требуется сложить вычеты вида (2i%p).

Пример: пусть задано число 25 или в двоичной системе счисления 11001 и требуется найти остаток по модулю 7.
25%7 = (1*24 + 1*23 + 0*22 + 0*1 + 1*20)%7 = (24%7 + 23%7 + 1%7)%7 = (2 + 1 + 1)%7 = 4

Систему используемых модулей подбирают под конкретную задачу. Например, для представления 32-х битных чисел достаточно следующей системы модулей: (7, 11, 13, 17, 19, 23 , 29, 31) – все они взаимнопросты друг с другом, их произведение равно 6685349671 > 4294967296. Каждый из модулей не превышает 5 бит, то есть операции сложения и умножения будут производиться над 5-битными числами.
Особое значение так же имеет система модулей вида: (2n-1, 2n, 2n+1) в связи с тем, что прямое и обратное преобразование для них выполняется простейшим образом. Что бы получить остаток от деления на 2n достаточно взять последние n цифр двоичного представления числа.

Арифметические операции

Пример: пусть задана система модулей (3, 5, 7), то есть мы можем выполнять операции, результат которых не превышает 3*5*7 = 105. Умножим два числа 8 и 10.
8 = (8%3, 8%5, 8%7) = (2, 3, 1)
10 = (10%3, 10%5, 10%7) = (1, 0, 3)
8*10 = ((2*1)%3, (3*0)%5, (1*3)%7) = (2, 0, 3)

Проверяем
80 = (80%3, 80%5, 80%7) = (2, 0, 3)

Обратное преобразование

Обратное преобразование из системы счисления в остаточных классах в позиционную систему счисления производится одним из двух способов:

  1. На базе Китайской теоремы об остатках или системы ортогональных базисов
  2. На базе полиадического кода (другие названия mixed-radix system, система, со смешанным основанием)

Остальные предложенные в различной литературе способы, по сути, являются смесью этих двух.

Способ, основанный на Китайской теореме об остатках, базируется на следующей идее:
X = (x1, x2, … xn) = (x1, 0, …, 0) + (0, x2, …, 0) + … + (0, 0, …., xn) = x1*(1, 0, …, 0) + x2*(0, 1, …, 0) + … + xn*(0, 0, …, 1).
То есть для обратного преобразования требуется найти систему ортогональных базисов B1 = (1, 0, …, 0), B2 = (0, 1, …, 0), …, BN = (0, 0, …, 1). Эти вектора находятся один раз для заданного базиса, а для их поиска требуется решить уравнение вида: (Mi*bi)%pi = 1, где Mi = M/pi, а bi – искомое число. В этом случае позиционное представление Bi = Mi*bi и
X = (x1*(M1*b1) + x2*(M2*b2) + … + xn*(Mn*bn))%M

Пример: пусть задана система модулей (3, 5, 7), найдем значения Mi и bi (0 < i <= 3)
M = 3*5*7 = 105
M1 = 105/3 = 35
M2 = 105/5 = 21
M3 = 105/7 = 15
(35*b1)%3 = 1 => b1 = 2
(21*b2)%5 = 1 => b2 = 1
(15*b3)%7 = 1 => b3 = 1

Теперь преобразуем какое-нибудь число в системе остаточных классов. Положим
X = (2, 3, 1) = (2*35*2 + 3*21*1 + 1*15*1)%105 = (140 + 63 + 15)%105 = 218%105 = 8

Минус этого метода заключается в том, что для обратного преобразования требуется умножение и сложение больших чисел (M1, …, Mn), а так же операция взятия остатка по модулю большого числа M.

Способ на базе полиадического кода, базируется на идее, что любое число X может быть представлено в системе взаимно простых чисел p1, … pn, как [4]:
X = a1 + a2*p1 + a3*p1*p1 + an-1*p1*p2*…*pn-2 + an*p1*p2*…*pn-1, где 0 < ai < pi

  • X%p1 = x1 = a1
  • (X – a1)%p2 = (x2-a1)%p2 = a2*p1
  • (X - (a1 + a2*p1))%p3 = (x3 – (a1 + a2*p1))%p3 = a3*p1*p2

Отсюда вытекает следующий итеративный процесс поиска исходного числа:

  • SUM = x1
  • SUM = SUM + (x2-SUM)%p2
  • SUM = SUM + (x3-SUM)%p3
  • SUM = SUM + (xn-SUM)%pn

Пример: Рассмотрим тот же пример — найдем позиционное представление числа X = (2, 3, 1) в системе модулей (3, 5, 7)

  1. SUM = 2
  2. SUM = SUM + (x2-SUM)%p2 = 2 + (3-2)%5 = 3
  3. SUM = SUM + (x3-SUM)%p3 = 3 + (1 - 3)%7 = 3 + (-2)%7 = 3 + (7-2)%7 = 3 + 5 = 8

Замечание: в данном случае в процессе вычитания у нас получилось отрицательное число, которое мы как бы скомпенсировали, добавив 7%7 = 0.

P.S.

Статья написана несколько сумбурно, потому что тема достаточно большая и в одну статью вместить все не представляется возможным. В следующих статьях я попробую расписать более подробно различные аспекты модулярной арифметики. На Хабре же я не нашел вообще ничего что относится к этой теме, только краткие упоминания в других статьях, поэтому и было решено написать небольшой обзор с простенькими примерами. Для тех, кого тема заинтересовала, рекомендую прочитать книгу номер [3] из списка литературы (на английском языке), она написана доступным языком с большим количеством примеров.

Литература

[1] ru.wikipedia.org/wiki/%D0%9F%D0%BE%D0%B7%D0%B8%D1%86%D0%B8%D0%BE%D0%BD%D0%BD%D0%B0%D1%8F_%D1%81%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D1%81%D1%87%D0%B8%D1%81%D0%BB%D0%B5%D0%BD%D0%B8%D1%8F
[2] ru.wikipedia.org/wiki/%D0%9A%D0%B8%D1%82%D0%B0%D0%B9%D1%81%D0%BA%D0%B0%D1%8F_%D1%82%D0%B5%D0%BE%D1%80%D0%B5%D0%BC%D0%B0_%D0%BE%D0%B1_%D0%BE%D1%81%D1%82%D0%B0%D1%82%D0%BA%D0%B0%D1%85
[3] Amos Omondi, Benjamin Premkumar, Residue Number Systems: Theory and Implementation, 2007.
[4] M. A. Soderstrand, W. K. Jenkins, G. A. Jullien and F. J. Taylor. 1986. Residue Number System Arithmetic: Modern Applications in Digital Signal Processing, IEEE Press, New York.

Автор: Turbo


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js