Просмотр исходного текста страницы Полиадический код

'''Полиадический код''' (или система счисления со смешанным основанием от англ. [http://en.wikipedia.org/wiki/Residue_number_system#Associated_mixed_radix_system associated mixed radix system (AMRS)])

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

:<math>X=\sum_{i=1}^Nx_iM_{i-1}=x_1+m_1(x_2+m_2(\cdots+m_{N-1}x_{N})\cdots),</math>
где
:<math>M_0=1,M_i=\prod_{j=1}^i m_j</math> для <math>i>0</math> и <math>0\leq x_i<m_i.</math>

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

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

Обратное преобразование на базе полиадического кода, базируется на идее, что любое число 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> => <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>a_4 = ||p_3^{-1}|_{p_4} \cdot (|p_2^{-1}|_{p_4} \cdot (|p_1^{-1}|_{p_4} \cdot (x_3 - a_1) - a_2) - a_3)|_{p_4}</math>
* ...
* <math>a_n = ||p_{n-1}^{-1}|_{p_n} \cdot (|p_{n-2}^{-1}|_{p_n} \cdot ( ... |p_2^{-1}|_{p_n} \cdot (|p_1^{-1}|_{p_n} \cdot (x_n - a_1) - a_2) - ...) - a_{n-1}|_{p_n}</math>


Для использования этого метода требуются константы вида <math>|p_i^{-1}|_{p_k}</math>. Можно также заметить, что начинать вычисление <math>a_3</math> можно, как только появилось значение <math>a_1</math>. На основе этого метода можно строить конвейерные преобразователи.

== Конвейерный преобразователь в полиадический код ==

[[изображение:Конвейерный преобразователь в полиадический код.png]]


== Обратный преобразователь на базе полиадического кода ==



== Ссылки ==
* [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.
* [2] [https://docs.google.com/viewer?url=patentimages.storage.googleapis.com/pdfs/US4752904.pdf Патент "Efficient structure for computing mixed-radix projections from residue number systems"]