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

Версия 10:56, 7 октября 2013

Содержание

1 Введение
2 Обратное преобразование
3 Конвейерный преобразователь в полиадический код
4 Обратный конвейерный преобразователь на базе полиадического кода
5 Коррекция ошибок на базе полиадического кода
6 Ссылки

Введение

Полиадический код (или система счисления со смешанным основанием от англ. 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 элементов:

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

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

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

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

Коррекция ошибок на базе полиадического кода

Пусть задан набор модулей $(p_1, p_2, p_3, p_4)$ , где $(p_1 < p_2 < p_3 < p_4)$ . Из них первые два $(p_1, p_2)$ являются информационными, а последние два $(p_3, p_4)$ - проверочными. Данный набор позволяет корректировать одиночную ошибку в одном из модулярных каналов. Для коррекции можно использовать следующий наиболее простой подход: из модулярного представления числа $(x_1, x_2, x_3, x_4)$ последовательно исключается каждый канал, формируя наборы:

$P_1 = (x_2, x_3, x_4)$
$P_2 = (x_1, x_3, x_4)$
$P_3 = (x_1, x_2, x_4)$
$P_4 = (x_1, x_2, x_3)$

Динамический диапазон каждой из троек превышает заданный (можно убедиться для каждой тройки: $p_1 \cdot p_2 \cdot p_3 > p_1 \cdot p_2$ ). В случае если ошибок не было, то при обратном преобразовании в позиционное представление значения всех троек должны лежать в диапазоне: $[0 <= X < p_1 \cdot p_2]$ и быть равными. В случае, если в одном из каналов произошла ошибка, то правильное значение даст только одна тройка, в которой исключено неверное значение, все остальные тройки будут лежать вне динамического диапазона (здесь нужна ссылка на пруФФФФФ или сам пруф).

В этом случае для восстановления числа требуется сделать 4 обратных преобразователя для каждой из троек. Сравнить полученные значения с $p_1 \cdot p_2$ и на основании сравнения выдать на выход правильное значение. Однако как будет показано ниже, корректирующий преобразователь можно значительно сократить по площади, объединив одинаковые части в каждом из обратных преобразователей и рассчитывая финальное позиционное значение только один раз для тройки с правильным значением [2].

Запишем, полиадическую формулу для каждой из троек:

$X_{P_1} = {a_1}_{P_1} + {a_2}_{P_1}\cdot p_2 + {a_3}_{P_1}\cdot p_2\cdot p_3$
$X_{P_2} = {a_1}_{P_2} + {a_2}_{P_2}\cdot p_1 + {a_3}_{P_2}\cdot p_1\cdot p_3$
$X_{P_3} = {a_1}_{P_3} + {a_2}_{P_3}\cdot p_1 + {a_3}_{P_3}\cdot p_1\cdot p_2$
$X_{P_4} = {a_1}_{P_4} + {a_2}_{P_4}\cdot p_1 + {a_3}_{P_4}\cdot p_1\cdot p_2$

Если посмотреть на самую правое слагаемое каждого из выражений можно заметить, что если любой из коэффициентов ${a_3}_{P_1}, {a_3}_{P_2}, {a_3}_{P_3}, {a_3}_{P_4}$ отличается от нуля, то всё выражение получается больше, чем $p_1 \cdot p_2$ . Из чего следует, что выражение ошибочно. Этот факт можно использовать для определения ошибки не восстанавливая значение целиком (нужен пруф). Тем самым можно сократить площадь преобразователя.

Ссылки

[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] Патент "Efficient structure for computing mixed-radix projections from residue number systems"

@@ Строка 51: / Строка 51: @@
 Пусть задан набор модулей <math>(p_1, p_2, p_3, p_4)</math>, где <math>(p_1 < p_2 < p_3 < p_4)</math>. Из них первые два <math>(p_1, p_2)</math> являются информационными, а последние два <math>(p_3, p_4)</math> - проверочными. Данный набор позволяет корректировать одиночную ошибку в одном из модулярных каналов. Для коррекции можно использовать следующий наиболее простой подход: из модулярного представления числа <math>(x_1, x_2, x_3, x_4)</math> последовательно исключается каждый канал, формируя наборы:
-* <math>S_1 = (x_2, x_3, x_4)</math>
+* <math>P_1 = (x_2, x_3, x_4)</math>
-* <math>S_2 = (x_1, x_3, x_4)</math>
+* <math>P_2 = (x_1, x_3, x_4)</math>
-* <math>S_3 = (x_1, x_2, x_4)</math>
+* <math>P_3 = (x_1, x_2, x_4)</math>
-* <math>S_4 = (x_1, x_2, x_3)</math>
+* <math>P_4 = (x_1, x_2, x_3)</math>
 Динамический диапазон каждой из троек превышает заданный (можно убедиться для каждой тройки: <math>p_1 \cdot p_2 \cdot p_3 > p_1 \cdot p_2</math>). В случае если ошибок не было, то при обратном преобразовании в позиционное представление значения всех троек должны лежать в диапазоне: <math>[0 <= X < p_1 \cdot p_2]</math> и быть равными. В случае, если в одном из каналов произошла ошибка, то правильное значение даст только одна тройка, в которой исключено неверное значение, все остальные тройки будут лежать вне динамического диапазона ('''здесь нужна ссылка на пруФФФФФ или сам пруф''').
@@ Строка 61: / Строка 61: @@
 Запишем, полиадическую формулу для каждой из троек:
-* <math>X_{S_1} = {a_1}_{S_1} + {a_2}_{S_1}\cdot p_2 + {a_3}_{S_1}\cdot p_2\cdot p_3</math>
+* <math>X_{P_1} = {a_1}_{P_1} + {a_2}_{P_1}\cdot p_2 + {a_3}_{P_1}\cdot p_2\cdot p_3</math>
-* <math>X_{S_2} = {a_1}_{S_2} + {a_2}_{S_2}\cdot p_1 + {a_3}_{S_2}\cdot p_1\cdot p_3</math>
+* <math>X_{P_2} = {a_1}_{P_2} + {a_2}_{P_2}\cdot p_1 + {a_3}_{P_2}\cdot p_1\cdot p_3</math>
-* <math>X_{S_3} = {a_1}_{S_3} + {a_2}_{S_3}\cdot p_1 + {a_3}_{S_3}\cdot p_1\cdot p_2</math>
+* <math>X_{P_3} = {a_1}_{P_3} + {a_2}_{P_3}\cdot p_1 + {a_3}_{P_3}\cdot p_1\cdot p_2</math>
-* <math>X_{S_4} = {a_1}_{S_4} + {a_2}_{S_4}\cdot p_1 + {a_3}_{S_4}\cdot p_1\cdot p_2</math>
+* <math>X_{P_4} = {a_1}_{P_4} + {a_2}_{P_4}\cdot p_1 + {a_3}_{P_4}\cdot p_1\cdot p_2</math>
-Если посмотреть на самую правое слагаемое каждого из выражений можно заметить, что если любой из коэффициентов <math>{a_3}_{S_1}, {a_3}_{S_2}, {a_3}_{S_3}, {a_3}_{S_4}</math> отличается от нуля, то всё выражение получается больше, чем <math>p_1 \cdot p_2</math>. Из чего следует, что выражение ошибочно. Этот факт можно использовать для определения ошибки не восстанавливая значение целиком ('''нужен пруф'''). Тем самым можно сократить площадь преобразователя.
+Если посмотреть на самую правое слагаемое каждого из выражений можно заметить, что если любой из коэффициентов <math>{a_3}_{P_1}, {a_3}_{P_2}, {a_3}_{P_3}, {a_3}_{P_4}</math> отличается от нуля, то всё выражение получается больше, чем <math>p_1 \cdot p_2</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.
 * [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"]

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

Версия 10:56, 7 октября 2013

Содержание

Введение

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

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

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

Коррекция ошибок на базе полиадического кода

Ссылки

Навигация

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

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

Варианты

Просмотры

Действия

Поиск

Навигация

Инструменты