Полиадический код — различия между версиями

Материал из Модулярная арифметики
Перейти к: навигация, поиск
Строка 29: Строка 29:
 
== Конвейерный преобразователь в полиадический код ==
 
== Конвейерный преобразователь в полиадический код ==
  
−
Используя формулы выше можно нарисовать схему конвейерного преобразователя
+
Используя формулы выше можно нарисовать схему конвейерного преобразователя. В данном случае мы используем модулярный базис из 4 элементов:
  
 
[[изображение:Конвейерный преобразователь в полиадический код.png]]
 
[[изображение:Конвейерный преобразователь в полиадический код.png]]
  
−
* '''ROMij''' - это таблица выполняющая следующее преобразование <math>r = |(p - q) \cdot p_j^{-1}|_{p_i}</math>
+
* '''ROMij''' - это таблица выполняющая следующее преобразование <math>r = |(p - q) \cdot p_j^{-1}|_{p_i}</math>. Для больших значений модулей таблица может быть заменена на последовательный набор арифметических операций (вычитание, умножение на константу и взятие модуля)
 
* '''LATCH''' - элемент памяти сохраняющий значение до следующего такта
 
* '''LATCH''' - элемент памяти сохраняющий значение до следующего такта
 
* На преобразование модулярного представления в полиадический код требуется N-1 ступеней конвейера.
 
* На преобразование модулярного представления в полиадический код требуется N-1 ступеней конвейера.
  
−
== Обратный преобразователь на базе полиадического кода ==
+
== Обратный конвейерный преобразователь на базе полиадического кода ==
  
 +
Этот преобразователь используется для восстановления числа <math>X</math> из модулярного кода, заданного набором остатков <math>(x1, x2, x3, x4)</math>.
 +
 +
[[изображение:Обратный конвейерный преобразователь на базе полиадического кода.png]]
 +
* '''ROMij''' - это таблица выполняющая следующее преобразование <math>r = |(p - q) \cdot p_j^{-1}|_{p_i} \cdot (p_1\cdot p_2 \cdot ... \cdot p_{i-1})</math>. Для больших значений модулей таблица может быть заменена на последовательный набор арифметических операций (вычитание, умножение на константу и взятие модуля)
 +
* '''LATCH''' - элемент памяти сохраняющий значение до следующего такта
 +
* На преобразование модулярного представления в позиционный вид требуется N ступеней конвейера.
 +
* В отличие от преобразования в полиадический код, данный преобразователь получается более громоздким из-за более сложной структуры '''ROMij''' и наличия сумматоров, битовый размер которых растет в нижней части конвейера.
  
 
== Ссылки ==
 
== Ссылки ==
 
* [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.
 
* [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"]
 
* [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"]

Версия 12:22, 25 сентября 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_2 = ||p_1^{-1}|_{p_2}\cdot (x_2 - a_1)|_{p_2}
  • |X - a_1 - a_2\cdot p_1|_{p_3} = |a_3\cdot p_1 \cdot p_2|_{p_3} => a_3 = ||p_2^{-1}|_{p_3} \cdot (|p_1^{-1}|_{p_3} \cdot (x_3 - a_1) - a_2)|_{p_3}
  • 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}
  • ...
  • 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}


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

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

Используя формулы выше можно нарисовать схему конвейерного преобразователя. В данном случае мы используем модулярный базис из 4 элементов:

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

  • ROMij - это таблица выполняющая следующее преобразование r = |(p - q) \cdot p_j^{-1}|_{p_i}. Для больших значений модулей таблица может быть заменена на последовательный набор арифметических операций (вычитание, умножение на константу и взятие модуля)
  • LATCH - элемент памяти сохраняющий значение до следующего такта
  • На преобразование модулярного представления в полиадический код требуется N-1 ступеней конвейера.

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

Этот преобразователь используется для восстановления числа X из модулярного кода, заданного набором остатков (x1, x2, x3, x4).

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

  • ROMij - это таблица выполняющая следующее преобразование r = |(p - q) \cdot p_j^{-1}|_{p_i} \cdot (p_1\cdot p_2 \cdot ... \cdot p_{i-1}). Для больших значений модулей таблица может быть заменена на последовательный набор арифметических операций (вычитание, умножение на константу и взятие модуля)
  • LATCH - элемент памяти сохраняющий значение до следующего такта
  • На преобразование модулярного представления в позиционный вид требуется N ступеней конвейера.
  • В отличие от преобразования в полиадический код, данный преобразователь получается более громоздким из-за более сложной структуры ROMij и наличия сумматоров, битовый размер которых растет в нижней части конвейера.

Ссылки

Источник — «https://vscripts.ru/w/index.php?title=Полиадический_код&oldid=580»