Система из 4 модулей (2^n-1, 2^n+1, 2^(n+1)-1, 2^(n+1)+1)

Материал из Модулярная арифметики
Перейти к: навигация, поиск

Система модулей {2n-1, 2n+1, 2n+1-1, 2n+1+1} - не является попарно взаимно простой, что несколько сокращает её динамический диапазон, но как будет показано не существенно.

Содержание

Динамический диапазон

M = HOK(2^n - 1, 2^n + 1, 2^{n+1} - 1, 2^{n+1}+1)

где HOK - наименьшее общее кратное.

Что бы найти M, требуется определить наибольший общий делитель(HOD) для всех четырех модулей. Так как 2^n - 1 и 2^n + 1, а также 2^{n+1} - 1 и 2^{n+1}+1 взаимнопросты, то необходимо найти наибольший общий делитель их попарного произведения.

HOD(2^{2n} - 1, 2^{2n+2} - 1) = 3

Отсюда по формуле для вычисления HOK:

M = \frac{(2^{2n} - 1)\cdot(2^{2n+2} - 1)}{3}

Таблица покрытия

n

Базис

Покрываемый интервал [0;M)

Бинарная битность

2

3, 5, 7, 9

[0; 315)

8

3

7, 9, 15, 17

[0; 5355)

12

4

15, 17, 31, 33

[0; 86955)

16

8

255, 257, 511, 513

[0; 5726513835)

32

16

65535, 65537, 131071, 131073

[0; 24595658757787789995)

64


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

Для прямого преобразования используются следующие свойства:

|2^{k}|_{2^{k}-1}=1 и |2^{k}|_{2^{k}+1}=-1

которое позволяет для преобразования целого числа X в модулярное представление (x1, x2, y1, y2) использовать следующие формулы:

x1 = |X[{n-1}:{0}] + X[{2n-1}:{n}] + ... + X[{mn-1}:{(m-1)\cdot n}]|_{2^{n}-1}

x2 = |X[{n-1}:{0}] - X[{2n-1}:{n}] + ... - X[{mn-1}:{(m-1)\cdot n}]|_{2^{n}+1}

y1 = |X[{n}:{0}] + X[{2n}:{n+1}] + ... + X[{mn}:{(m-1)\cdot n+1}]|_{2^{n+1}-1}

y2 = |X[{n}:{0}] - X[{2n}:{n+1}] + ... - X[{mn}:{(m-1)\cdot n+1}]|_{2^{n+1}+1}

  • Количество слагаемых определяется размерностью входных данных.
  • Запись X[a:b] - означает взять биты из двоичной записи числа с позиции b до позиции a.

Так как значение внутри модуля незначительно превосходит сам модуль, то ответ можно получить по следующей схеме:

x1 = |K|_{2^{n}-1} = \begin{cases}K,&\text{if  } K < 2^{n}-1\\
K - (2^{n}-1),&\text{if  } (2^{n}-1) \le K < 2\cdot(2^{n}-1)\\
...\\
K - t*(2^{n}-1),&\text{if  } (t\cdot(2^{n}-1)) \le K < (t+1)\cdot(2^{n}-1)\\
\end{cases}


при условии что максимально возможное значение K менее чем (t+1)\cdot(2^{n}-1)

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

Обратное преобразование строится на базе CRT III (Китайская теорема об остатках ver.3) [1]. Если задана система из двух модулей {m_1, m_2} то значение X может быть найдено по следующей формуле:

X = X_1+m_1\cdot|(\frac{m_1}{d})^{-1}\cdot\frac{X_2-X_1}{d}|_{\frac{m_2}{d}}

где

  • d - НОД (наибольший общий делитель) m_1, m_2
  • |a^{-1}|_b - обратный элемент к a по модулю b
  • значение m_1 должно быть больше m_2

Можно заметить что если m_1, m_2 взаимно просты, то d=1 и формула превращается в стандартную формулу полиадического кода (Mixed Radix System).

Обратный преобразователь для системы модулей из четырех элементов состоит из двух уровней. На первом уровне считаются промежуточные значения A_1 и A_2 (по формулам CRT III):

A1 = x2+(2^{n}+1)\cdot|(2^n+1)^{-1}\cdot(x1-x2)|_{2^{n}-1} = x2+(2^{n}+1)\cdot|2^{n-1}\cdot(x1-x2)|_{2^{n}-1}

A2 = y2+(2^{n+1}+1)\cdot|(2^{n+1}+1)^{-1}\cdot(y1-y2)|_{2^{n+1}-1} = y2+(2^{n+1}+1)\cdot|(2^{n}\cdot(y1-y2)|_{2^{n+1}-1}

Как видно рассчет обоих коэфициентов легко реализуется на схемном уровне:

  • Умножение на 2^{n-1} по сути сдвиг
  • Умножение (2^{n}+1)\cdot T=T\cdot 2^{n}+T - сдвиг и сложение
  • Вычет по модулю {2^{n}-1} - одно сложение, вычитание и мультиплексор.

На втором уровне преобразователя d=3 и формула выглядит следующим образом:

X = A2 + (2^{2(n+1)}-1)\cdot|(\frac{2^{2(n+1)}-1}{3})^{-1}\cdot\frac{A1-A2}{3}|_{\frac{2^{2n}-1}{3}}

Несложно показать что: |(\frac{2^{2(n+1)}-1}{3})^{-1}|_{\frac{2^{2n}-1}{3}} = 1 [2]

Финальная формула в итоге будет:

X = A2 + (2^{2(n+1)}-1)\cdot|\frac{A1-A2}{3}|_{\frac{2^{2n}-1}{3}}

Ссылки

[1] http://etd.lsu.edu/docs/available/etd-11052010-141445/unrestricted/Report_Nov2.pdf

[2] http://www2.lirmm.fr/arith18/papers/Sousa-RNS.pdf


Персональные инструменты
Пространства имён

Варианты
Действия
Навигация