Система из 4 модулей (2^n-1, 2^n+1, 2^(n+1)-1, 2^(n+1)+1)
Turbo (обсуждение | вклад) |
Turbo (обсуждение | вклад) |
||
Строка 110: | Строка 110: | ||
== Прямое преобразование == | == Прямое преобразование == | ||
+ | |||
+ | Для прямого преобразования используются следующие свойства: | ||
+ | |||
+ | <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)*n}]|_{2^{n}-1}</math> | ||
+ | |||
+ | <math>x2 = |X[{n-1}:{0}] - X[{2n-1}:{n}] + ... - X[{mn-1}:{(m-1)*n}]|_{2^{n}+1}</math> | ||
+ | |||
+ | <math>y1 = |X[{n}:{0}] + X[{2n}:{n+1}] + ... + X[{mn}:{(m-1)*n+1}]|_{2^{n+1}-1}</math> | ||
+ | |||
+ | <math>y2 = |X[{n}:{0}] - X[{2n}:{n+1}] + ... - X[{mn}:{(m-1)*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*(2^{n}-1)\\ | ||
+ | ...\\ | ||
+ | K - t*(2^{n}-1), \text{ if } t*(2^{n}-1) \le K < (t+1)*(2^{n}-1)\\ | ||
+ | \end{cases}</math> | ||
== Обратное преобразование == | == Обратное преобразование == |
Версия 13:14, 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 |
Прямое преобразование
Для прямого преобразования используются следующие свойства:
и
которое позволяет для преобразования целого числа в модулярное представление использовать следующие формулы:
- Количество слагаемых определяется размерностью входных данных.
- Запись - означает взять биты из двоичной записи числа с позиции до позиции .
Так как значение внутри модуля незначительно превосходит сам модуль, то ответ можно получить по следующей схеме: