Полиадический код

Версия 09:08, 15 июля 2013

Полиадический код (или система счисления со смешанным основанием от англ. associated mixed radix system (AMRS))

Любое число $\{y_1,y_2,y_3,\ldots,y_n\}$ в системе остаточных классов может быть представленно в виде полиадического кода

$X=\sum_{i=1}^Nx_iM_{i-1}=x_1+m_1(x_2+m_2(\cdots+m_{N-1}x_{N})\cdots),$

где

$M_0=1,M_i=\prod_{j=1}^i m_j$ для $i>0$ и $0\leq x_i<m_i.$

Полиадический код используется для:

Сравнения чисел
Перевода чисел из системы остаточных классов в обычную позиционную систему счисления

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

Обратное преобразование на базе полиадического кода, базируется на идее, что любое число X может быть представлено в системе взаимно простых чисел $p_1,\ldots, p_n$ , как [1]:

$X = a_1 + a_2\cdot p_1 + a_3\cdot p_1\cdot p_2 + ... + a_{n-1}\cdot p_1\cdot p_2\cdot \ldots\cdot p_{n-2} + a_n\cdot p_1\cdot p_2\cdot \ldots\cdot p_{n-1}$ , где $0 < a_i < p_i$

$|X|_{p_1} = x_1 = a_1$
$|X - a_1|_{p_2} = |x_2 - a_1|_{p_2} = |a_2\cdot p_1|_{p_2}$ => a₂ = ((p₁^-1)%p₂*(x₂ - a₁))%p₂</li>

(X - a₁ - a₂*p₁)%p₃ = (a₃*p₁*p₂)%p₃ => a₃ = ((p₂^-1)%p₃*((p₁^-1)%p₃*(x₃ - a₁) - a₂))%p₃</li>

…</li> </ul> Для использования этого метода требуются константы вида (p_i^-1)%p_k^-1. Можно также заметить, что начинать вычисление a₃ можно, как только появилось значение a₁. На основе этого метода можно строить конвеерные преобразователи.

Ссылки

[1] M. A. Soderstrand, W. K. Jenkins, G. A. Jullien and F. J. Taylor. 1986. Residue Number System Arithmetic: Modern Applications in Digital Signal Processing, IEEE Press, New York.

@@ Строка 10: / Строка 10: @@
 * Сравнения чисел
 * Перевода чисел из системы остаточных классов в обычную позиционную систему счисления
+== Обратное преобразование ==
+Обратное преобразование на базе полиадического кода, базируется на идее, что любое число X может быть представлено в системе взаимно простых чисел <math>p_1,\ldots, p_n</math>, как [1]:
+:<math>X = a_1 + a_2\cdot p_1 + a_3\cdot p_1\cdot p_2 + ... + a_{n-1}\cdot p_1\cdot p_2\cdot \ldots\cdot p_{n-2} + a_n\cdot p_1\cdot p_2\cdot \ldots\cdot p_{n-1}</math>, где <math>0 < a_i < p_i</math>
+* <math>|X|_{p_1} = x_1 = a_1</math>
+* <math>|X - a_1|_{p_2} = |x_2 - a_1|_{p_2} = |a_2\cdot p_1|_{p_2}</math> => a<sub>2</sub> = ((p<sub>1</sub><sup>-1</sup>)%p<sub>2</sub>*(x<sub>2</sub> - a<sub>1</sub>))%p<sub>2</sub></li>
+<li>(X - a<sub>1</sub> - a<sub>2</sub>*p<sub>1</sub>)%p<sub>3</sub> = (a<sub>3</sub>*p<sub>1</sub>*p<sub>2</sub>)%p<sub>3</sub> => a<sub>3</sub> = ((p<sub>2</sub><sup>-1</sup>)%p<sub>3</sub>*((p<sub>1</sub><sup>-1</sup>)%p<sub>3</sub>*(x<sub>3</sub> - a<sub>1</sub>) - a<sub>2</sub>))%p<sub>3</sub></li>
+<li>…</li>
+</ul>
+Для использования этого метода требуются константы вида (p<sub>i</sub><sup>-1</sup>)%p<sub>k</sub><sup>-1</sup>. Можно также заметить, что начинать вычисление a<sub>3</sub> можно, как только появилось значение a<sub>1</sub>. На основе этого метода можно строить конвеерные преобразователи.
+== Ссылки ==
+[1] M. A. Soderstrand, W. K. Jenkins, G. A. Jullien and F. J. Taylor. 1986. Residue Number System Arithmetic: Modern Applications in Digital Signal Processing, IEEE Press, New York.

Полиадический код

Версия 09:08, 15 июля 2013

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

Ссылки

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

Пространства имён

Варианты

Просмотры

Действия

Поиск

Навигация