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

Материал из Модулярная арифметики
(Различия между версиями)
Перейти к: навигация, поиск
(Новая страница: «Система {2<sup>n</sup>-1, 2<sup>n</sup>+1, 2<sup>n+1</sup>-1, 2<sup>n+1</sup>+1} - не является попарно взаимно простой, чт…»)
 
 
(не показаны 8 промежуточных версий 1 участника)
Строка 1: Строка 1:
−
Система {2<sup>n</sup>-1, 2<sup>n</sup>+1, 2<sup>n+1</sup>-1, 2<sup>n+1</sup>+1} - не является попарно взаимно простой, что несколько сокращает её динамический диапазон, но как будет показано не существенно.
+
Система модулей {2<sup>n</sup>-1, 2<sup>n</sup>+1, 2<sup>n+1</sup>-1, 2<sup>n+1</sup>+1} - не является попарно взаимно простой, что несколько сокращает её динамический диапазон, но как будет показано не существенно.
  
 
== Динамический диапазон ==
 
== Динамический диапазон ==
  
−
== Прямое преобразование ==
+
<math>M = HOK(2^n - 1, 2^n + 1, 2^{n+1} - 1, 2^{n+1}+1)</math>
 +
 
 +
где <math>HOK</math> - наименьшее общее кратное.
 +
 
 +
Что бы найти <math>M</math>, требуется определить наибольший общий делитель(<math>HOD</math>) для всех четырех модулей. Так как <math>2^n - 1</math> и <math>2^n + 1</math>, а также <math>2^{n+1} - 1</math> и <math>2^{n+1}+1</math> взаимнопросты, то необходимо найти наибольший общий делитель их попарного произведения.
 +
 
 +
<math>HOD(2^{2n} - 1, 2^{2n+2} - 1) = 3</math>
 +
 
 +
Отсюда по формуле для вычисления <math>HOK</math>:
 +
 
 +
<math>M = \frac{(2^{2n} - 1)\cdot(2^{2n+2} - 1)}{3}</math>
  
 
== Таблица покрытия ==
 
== Таблица покрытия ==
 +
 +
<table>
 +
<tr>
 +
<td style="text-align: center; border: 1px solid black; padding: 2px 5px;">
 +
n
 +
</td>
 +
<td style="text-align: center; border: 1px solid black; padding: 2px 5px;">
 +
Базис
 +
</td>
 +
<td style="text-align: center; border: 1px solid black; padding: 2px 5px;">
 +
Покрываемый интервал [0;M)
 +
</td>
 +
<td style="text-align: center; border: 1px solid black; padding: 2px 5px;">
 +
Бинарная битность
 +
</td>
 +
</tr>
 +
<tr>
 +
<td style="text-align: center; border: 1px solid black;">
 +
2
 +
</td>
 +
<td style="text-align: center; border: 1px solid black;">
 +
3, 5, 7, 9
 +
</td>
 +
<td style="text-align: center; border: 1px solid black;">
 +
[0; 315)
 +
</td>
 +
<td style="text-align: center; border: 1px solid black;">
 +
8
 +
</td>
 +
</tr>
 +
<tr>
 +
<td style="text-align: center; border: 1px solid black;">
 +
3
 +
</td>
 +
<td style="text-align: center; border: 1px solid black;">
 +
7, 9, 15, 17
 +
</td>
 +
<td style="text-align: center; border: 1px solid black;">
 +
[0; 5355)
 +
</td>
 +
<td style="text-align: center; border: 1px solid black;">
 +
12
 +
</td>
 +
</tr>
 +
 +
<tr>
 +
<td style="text-align: center; border: 1px solid black;">
 +
4
 +
</td>
 +
<td style="text-align: center; border: 1px solid black;">
 +
15, 17, 31, 33
 +
</td>
 +
<td style="text-align: center; border: 1px solid black;">
 +
[0; 86955)
 +
</td>
 +
<td style="text-align: center; border: 1px solid black;">
 +
16
 +
</td>
 +
</tr>
 +
 +
<tr>
 +
<td style="text-align: center; border: 1px solid black;">
 +
8
 +
</td>
 +
<td style="text-align: center; border: 1px solid black;">
 +
255, 257, 511, 513
 +
</td>
 +
<td style="text-align: center; border: 1px solid black;">
 +
[0; 5726513835)
 +
</td>
 +
<td style="text-align: center; border: 1px solid black;">
 +
32
 +
</td>
 +
</tr>
 +
 +
<tr>
 +
<td style="text-align: center; border: 1px solid black;">
 +
16
 +
</td>
 +
<td style="text-align: center; border: 1px solid black;">
 +
65535, 65537, 131071, 131073
 +
</td>
 +
<td style="text-align: center; border: 1px solid black;">
 +
[0; 24595658757787789995)
 +
</td>
 +
<td style="text-align: center; border: 1px solid black;">
 +
64
 +
</td>
 +
</tr>
 +
 +
</table>
 +
 +
 +
== Прямое преобразование ==
 +
 +
Для прямого преобразования используются следующие свойства:
 +
 +
<math>|2^{k}|_{2^{k}-1}=1</math> и <math>|2^{k}|_{2^{k}+1}=-1</math>
 +
 +
которое позволяет для преобразования целого числа <math>X</math> в модулярное представление <math>(x1, x2, y1, y2)</math> использовать следующие формулы:
 +
 +
<math>x1 = |X[{n-1}:{0}] + X[{2n-1}:{n}] + ... + X[{mn-1}:{(m-1)\cdot n}]|_{2^{n}-1}</math>
 +
 +
<math>x2 = |X[{n-1}:{0}] - X[{2n-1}:{n}] + ... - X[{mn-1}:{(m-1)\cdot n}]|_{2^{n}+1}</math>
 +
 +
<math>y1 = |X[{n}:{0}] + X[{2n}:{n+1}] + ... + X[{mn}:{(m-1)\cdot n+1}]|_{2^{n+1}-1}</math>
 +
 +
<math>y2 = |X[{n}:{0}] - X[{2n}:{n+1}] + ... - X[{mn}:{(m-1)\cdot n+1}]|_{2^{n+1}+1}</math>
 +
 +
* Количество слагаемых определяется размерностью входных данных.
 +
* Запись <math>X[a:b]</math> - означает взять биты из двоичной записи числа с позиции <math>b</math> до позиции <math>a</math>.
 +
 +
Так как значение внутри модуля незначительно превосходит сам модуль, то ответ можно получить по следующей схеме:
 +
 +
<math>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}</math>
 +
 +
 +
при условии что максимально возможное значение <math>K</math> менее чем <math>(t+1)\cdot(2^{n}-1)</math>
  
 
== Обратное преобразование ==
 
== Обратное преобразование ==
 +
 +
Обратное преобразование строится на базе CRT III (Китайская теорема об остатках ver.3) [1]. Если задана система из двух модулей <math>{m_1, m_2}</math> то значение <math>X</math> может быть найдено по следующей формуле:
 +
 +
<math>X = X_1+m_1\cdot|(\frac{m_1}{d})^{-1}\cdot\frac{X_2-X_1}{d}|_{\frac{m_2}{d}}</math>
 +
 +
где
 +
* <math>d</math> - НОД (наибольший общий делитель) <math>m_1, m_2</math>
 +
* <math>|a^{-1}|_b</math> - обратный элемент к <math>a</math> по модулю <math>b</math>
 +
* значение <math>m_1</math> должно быть больше <math>m_2</math>
 +
 +
Можно заметить что если <math>m_1, m_2</math> взаимно просты, то <math>d=1</math> и формула превращается в стандартную формулу полиадического кода (Mixed Radix System).
 +
 +
Обратный преобразователь для системы модулей из четырех элементов состоит из двух уровней. На первом уровне считаются промежуточные значения <math>A_1</math> и <math>A_2</math> (по формулам CRT III):
 +
 +
<math>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}</math>
 +
 +
<math>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}</math>
 +
 +
Как видно рассчет обоих коэфициентов легко реализуется на схемном уровне:
 +
* Умножение на <math>2^{n-1}</math> по сути сдвиг
 +
* Умножение <math>(2^{n}+1)\cdot T=T\cdot 2^{n}+T</math> - сдвиг и сложение
 +
* Вычет по модулю <math>{2^{n}-1}</math> - одно сложение, вычитание и мультиплексор.
 +
 +
На втором уровне преобразователя <math>d=3</math> и формула выглядит следующим образом:
 +
 +
<math>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}}</math>
 +
 +
Несложно показать что: <math>|(\frac{2^{2(n+1)}-1}{3})^{-1}|_{\frac{2^{2n}-1}{3}} = 1</math> [2]
 +
 +
Финальная формула в итоге будет:
 +
 +
<math>X = A2 + (2^{2(n+1)}-1)\cdot|\frac{A1-A2}{3}|_{\frac{2^{2n}-1}{3}}</math>
 +
 +
== Ссылки ==
 +
[1] http://etd.lsu.edu/docs/available/etd-11052010-141445/unrestricted/Report_Nov2.pdf
 +
 +
[2] http://www2.lirmm.fr/arith18/papers/Sousa-RNS.pdf

Текущая версия на 16:03, 20 мая 2013

Система модулей {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

Источник — «http://vscripts.ru/w/index.php?title=%D0%A1%D0%B8%D1%81%D1%82%D0%B5%D0%BC%D0%B0_%D0%B8%D0%B7_4_%D0%BC%D0%BE%D0%B4%D1%83%D0%BB%D0%B5%D0%B9_(2%5En-1,_2%5En%2B1,_2%5E(n%2B1)-1,_2%5E(n%2B1)%2B1)&oldid=405»
Персональные инструменты
Пространства имён

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