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

Система модулей {2ⁿ-1, 2ⁿ+1, 2ⁿ⁺¹-1, 2ⁿ⁺¹+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