Полиадический код
Turbo (обсуждение | вклад) |
Turbo (обсуждение | вклад) |
||
| Строка 16: | Строка 16: | ||
:<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 = 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|_{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> => | + | * <math>|X - a_1|_{p_2} = |x_2 - a_1|_{p_2} = |a_2\cdot p_1|_{p_2}</math> => <math>a_2 = ||p_1^{-1}|_{p_2}\cdot (x_2 - a_1)|_{p_2}</math> |
| − | < | + | * <math>|X - a_1 - a_2\cdot p_1|_{p_3} = |a_3\cdot p_1 \cdot p_2|_{p_3}</math> => <math>a_3 = ||p_2^{-1}|_{p_3} \cdot (|p_1^{-1}|_{p_3} \cdot (x_3 - a_1) - a_2)|_{p_3}</math> |
| − | + | * ... | |
| − | + | ||
| − | Для использования этого метода требуются константы вида | + | Для использования этого метода требуются константы вида <math>|p_i^{-1}|%p_k</math>. Можно также заметить, что начинать вычисление <math>a_3</math> можно, как только появилось значение <math>a_1</math>. На основе этого метода можно строить конвеерные преобразователи. |
== Ссылки == | == Ссылки == | ||
[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. | [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:34, 15 июля 2013
Полиадический код (или система счисления со смешанным основанием от англ. associated mixed radix system (AMRS))
Любое число 
в системе остаточных классов может быть представленно в виде полиадического кода
где
для 
и 
Полиадический код используется для:
- Сравнения чисел
- Перевода чисел из системы остаточных классов в обычную позиционную систему счисления
Обратное преобразование
Обратное преобразование на базе полиадического кода, базируется на идее, что любое число X может быть представлено в системе взаимно простых чисел 
, как [1]:
, где 
-
-
=> 
-
=> 
- ...
Для использования этого метода требуются константы вида 
. Можно также заметить, что начинать вычисление 
можно, как только появилось значение 
. На основе этого метода можно строить конвеерные преобразователи.
Ссылки
[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.
