Система из 4 модулей (2^n-1, 2^n+1, 2^(n+1)-1, 2^(n+1)+1)
Turbo (обсуждение | вклад) |
Turbo (обсуждение | вклад) |
||
(не показаны 3 промежуточные версии 1 участника) | |||
Строка 13: | Строка 13: | ||
Отсюда по формуле для вычисления <math>HOK</math>: | Отсюда по формуле для вычисления <math>HOK</math>: | ||
− | <math>M = | + | <math>M = \frac{(2^{2n} - 1)\cdot(2^{2n+2} - 1)}{3}</math> |
== Таблица покрытия == | == Таблица покрытия == | ||
Строка 117: | Строка 117: | ||
которое позволяет для преобразования целого числа <math>X</math> в модулярное представление <math>(x1, x2, y1, y2)</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) | + | <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) | + | <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) | + | <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) | + | <math>y2 = |X[{n}:{0}] - X[{2n}:{n+1}] + ... - X[{mn}:{(m-1)\cdot n+1}]|_{2^{n+1}+1}</math> |
* Количество слагаемых определяется размерностью входных данных. | * Количество слагаемых определяется размерностью входных данных. | ||
Строка 131: | Строка 131: | ||
<math>x1 = |K|_{2^{n}-1} = \begin{cases}K,&\text{if } K < 2^{n}-1\\ | <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 | + | K - (2^{n}-1),&\text{if } (2^{n}-1) \le K < 2\cdot(2^{n}-1)\\ |
...\\ | ...\\ | ||
− | K - t*(2^{n}-1),&\text{if } (t | + | K - t*(2^{n}-1),&\text{if } (t\cdot(2^{n}-1)) \le K < (t+1)\cdot(2^{n}-1)\\ |
\end{cases}</math> | \end{cases}</math> | ||
− | при условии что максимально возможное значение <math>K</math> менее чем <math>(t+1) | + | при условии что максимально возможное значение <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} - не является попарно взаимно простой, что несколько сокращает её динамический диапазон, но как будет показано не существенно.
Содержание |
[править] Динамический диапазон
где - наименьшее общее кратное.
Что бы найти , требуется определить наибольший общий делитель() для всех четырех модулей. Так как и , а также и взаимнопросты, то необходимо найти наибольший общий делитель их попарного произведения.
Отсюда по формуле для вычисления :
[править] Таблица покрытия
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 |
[править] Прямое преобразование
Для прямого преобразования используются следующие свойства:
и
которое позволяет для преобразования целого числа в модулярное представление использовать следующие формулы:
- Количество слагаемых определяется размерностью входных данных.
- Запись - означает взять биты из двоичной записи числа с позиции до позиции .
Так как значение внутри модуля незначительно превосходит сам модуль, то ответ можно получить по следующей схеме:
при условии что максимально возможное значение менее чем
[править] Обратное преобразование
Обратное преобразование строится на базе CRT III (Китайская теорема об остатках ver.3) [1]. Если задана система из двух модулей то значение может быть найдено по следующей формуле:
где
- - НОД (наибольший общий делитель)
- - обратный элемент к по модулю
- значение должно быть больше
Можно заметить что если взаимно просты, то и формула превращается в стандартную формулу полиадического кода (Mixed Radix System).
Обратный преобразователь для системы модулей из четырех элементов состоит из двух уровней. На первом уровне считаются промежуточные значения и (по формулам CRT III):
Как видно рассчет обоих коэфициентов легко реализуется на схемном уровне:
- Умножение на по сути сдвиг
- Умножение - сдвиг и сложение
- Вычет по модулю - одно сложение, вычитание и мультиплексор.
На втором уровне преобразователя и формула выглядит следующим образом:
Несложно показать что: [2]
Финальная формула в итоге будет:
[править] Ссылки
[1] http://etd.lsu.edu/docs/available/etd-11052010-141445/unrestricted/Report_Nov2.pdf