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

Версия 21:46, 5 ноября 2013

Содержание

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

Введение

Полиадический код (или система счисления со смешанным основанием от англ. 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$ и на основании сравнения выдать на выход правильное значение. Однако как будет показано ниже, корректирующий преобразователь можно значительно сократить по площади, объединив одинаковые части в каждом из обратных преобразователей и рассчитывая финальное позиционное значение только один раз для тройки с правильным значением.

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

$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$ . Из чего следует, что выражение ошибочно. Этот факт можно использовать для определения ошибки не восстанавливая значение целиком (нужен пруф). Тем самым можно сократить площадь преобразователя.

Схема сокращенного преобразователя в полиадический код для коррекции одиночной ошибки

Использовать несколько параллельных преобразователей оказывается неэффективным. Как показано в [2] для этой цели можно использовать сокращенную форму (см. рисунок ниже).

В этом случае на выходных узлах можно получить полиадическое представление для каждого из исключающих наборов $(P_1, P_2, P_3, P_4)$ :

$A_{P_1} = \{{a_1}_{P_1}, {a_2}_{P_1}, {a_3}_{P_1}\} = \{S_2(2), S_2(3), S_2(4)\}$
$A_{P_2} = \{{a_1}_{P_2}, {a_2}_{P_2}, {a_3}_{P_2}\} = \{S_1(1), S_3(3), S_3(4)\}$
$A_{P_3} = \{{a_1}_{P_3}, {a_2}_{P_3}, {a_3}_{P_3}\} = \{S_1(1), S_1(2), S_1(4)\}$
$A_{P_4} = \{{a_1}_{P_4}, {a_2}_{P_4}, {a_3}_{P_4}\} = \{S_1(1), S_1(2), S_1(3)\}$

Для последующего восстановления исходного числа с коррекцией возможной ошибки, можно воспользоваться следующим алгоритмом:

$if ({a_3}_{P_1} == 0) \{$

$X = {a_1}_{P_1} + {a_2}_{P_1}\cdot p_2$

$\} else if ({a_3}_{P_2} == 0) \{$

$X = {a_1}_{P_2} + {a_2}_{P_2}\cdot p_1$

$\} else if ({a_3}_{P_3} == 0) \{$

$X = {a_1}_{P_3} + {a_2}_{P_3}\cdot p_1$

$\} else if ({a_3}_{P_4} == 0) \{$

$X = {a_1}_{P_4} + {a_2}_{P_4}\cdot p_1$

$\} else \{$

Ошибка более чем в 1 канале

$\}$

Для произвольного значения $N$ схема сокращенного преобразователя в полиадический код строится следующим образом. Возьмем систему остатков для следующего набора $N$ взаимно простых целых модулей: $(p_1, p_2, p_3, ..., p_N)$ , где $(p_{i+1} < p_{i})$ .

Пусть $X$ - целое число, такое, что

$X \leq \prod^{(N-2)}_{i=1} p_{i}$

Представление числа $X$ в модулярном виде $N$ набором остатков таково: $(x_1, x_2, x_3, ..., x_N)$ , где $x_i$ - значение остатка $X (mod\ p_i)$ . В этом случае 2 цифры остатков избыточны. Данный набор позволяет найти и исправить одиночную ошибку в одном из модулярных каналов.

Для поиска и коррекции ошибок используется преобразование модулярного представления числа в полиадический код.

По набору $x_i$ создается полиадический код - набор $a_i$ . Ошибочные каналы модулярного представления определяются следующим образом.

Во-первых, из $N$ каналов модулярного представления числа $X$ , создаем $N$ наборов по $N-1$ каналов, причем последовательно исключается каждый канал, формируя так называемые проекции ("исключающие наборы"). Пусть $P_i$ - проекция, полученная исключением канала $x_i$ . Преобразуем в полиадический код каждую из проекций $P_i$ . Если для всех проекций старшие разряды полученного полиадического кода равны нулю, ни в одном канале $x_i$ ошибки нет. Если полученные старшие разряды ненулевые для всех проекций, кроме $P_j$ , то в канале $x_j$ присутствует ошибка, а $P_j$ - правильное представление числа $X$ .

Пусть ROMij - это любая схема или программа, получающая в момент времени 0 на вход целые $p$ и $q$ и в момент времени $T$ выдающая на выход $r$ , где $r = |(p - q) \cdot p_j^{-1}|_{p_i}$ .

Пусть LATCH - это любая схема или программа, получающая в момент времени 0 на вход целое число и выдающая это число на выход в момент времени $T$ .

Можно получить конвейерную схему, реализующую преобразование в полиадический код, разместив и соединив элементы ROMij и LATCH, определенные выше, как показано на следующем рисунке.

Назовем эту схему схемой преобразователя в полиадический код размера $D$ . На вход схемы поступают цифры остатков, обозначенные от $I1$ до $ID$ , а выходами являются цифры полиадического кода, обозначенные от $O1$ до $OD$ . Больший индекс соответствует старшему разряду. $D$ столбцов рассматриваются от $1$ до $D$ , причем столбец $1$ принимает младший вход. $D-1$ ступеней конвейера рассматриваются от $1$ до $D-1$ , причем входы схемы поступают на ступень $1$ . Каждая ступень конвейера срабатывает за время $T$ . Каждая ступень конвейера состоит из некоторого числа элементов ROMij и LATCH, на входы которых поступают выходы предыдущей ступени, а выходы передаются на входы следующей ступени. Элемент с индексами i.j - это ROMij, если $i>j$ , или LATCH, в противном случае. Левый вход элемента ROMij - $p$ , правый - $q$ .

Для произвольного значения $N$ схема сокращенного преобразователя в полиадический код - это конвейерная схема из $N-2$ ступеней, содержащая $(Y-1)$ элементов ROMij и $(Y-N+1)$ элементов LATCH, где $Y = (N \cdot (N-1) \cdot (N+1))/6$ . Входом схемы являются $N$ цифр модулярного представления, выходом - $(N+1) \cdot (N-1)/2$ цифр полиадического кода. Данная реализация преобразователя заключает в себе $N-1$ подсхем преобразователя в полиадический код, от $S_1$ до $S_{N-1}$ . Подсхема $S_z$ содержит $N-z+1$ элементов. Элемент ROMij, находящийся в столбце $u$ , ступени $v$ подсхемы $S_z$ определяется так:

$i=u+z-1;\ j=v+z-1$ .

Входами подсхемы $S_1$ являются цифры от $x_1$ до $x_N$ . Подсхема $S_1$ представляет собой особый случай, поскольку сокращена на одну ступень, ее выходы формируются после $N-2$ ступени: это цифры полиадического кода от $S_{1}(1)$ до $S_1(N)$ .

Входами подсхемы $S_i, i>1$ являются $N-i+1$ p-входов $i-1$ ступени подсхемы $S_1$ . Выходы подсхемы $S_i, i>1$ : от $S_{i}(i)$ до $S_i(N)$ .

Выходы рассмотренной схемы преобразователя необходимы и достаточны для полиадического представления всех проекций. Цифры полиадического кода проекции $P_{N}$ таковы: от $S_{1}(1)$ до $S_1(N-1)$ . Цифры полиадического кода проекции $P_{N-1}$ таковы: от $S_{1}(1)$ до $S_1(N-2)$ , и $S_1(N-1)$ .

Цифры полиадического кода проекции $P_{i}, i<N-1$ таковы: от $S_{1}(1)$ до $S_1(i-1)$ , если $i>1$ , и от $S_1(i+1)$ до $S_1(N)$ .

Простой метод основанный на репликации требует $X = (N \cdot (N-1) \cdot (N-2))/2$ LUT и ROM. Сокращенный метод требует $(Y-1)$ ROM и $(Y-N+1)$ LUT, где $Y = (N \cdot (N-1) \cdot (N+1))/6$ . Количество уровней обоих методов совпадает и для реализации используются одинаковые элементы, поэтому тактовая частота работы после сокращения площади не изменится.

N	4	5	6	7	10
Репликация (кол-во ROM/LUT)	12	30	60	105	360
Метод сокращения (кол-во ROM)	9	19	34	55	164
Метод сокращения (кол-во LUT)	7	16	30	50	156

Ссылки

[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"

@@ Строка 109: / Строка 109: @@
 Во-первых, из <math>N</math> каналов модулярного представления числа <math>X</math>, создаем <math>N</math> наборов по <math>N-1</math> каналов, причем последовательно исключается каждый канал, формируя так называемые проекции ("исключающие наборы"). Пусть <math>P_i</math> - проекция, полученная исключением канала <math>x_i</math>. Преобразуем в полиадический код каждую из проекций <math>P_i</math>. Если для всех проекций старшие разряды полученного полиадического кода равны нулю, ни в одном канале <math>x_i</math> ошибки нет. Если полученные старшие разряды ненулевые для всех проекций, кроме <math>P_j</math>, то в канале <math>x_j</math> присутствует ошибка, а <math>P_j</math> - правильное представление числа <math>X</math>.
+Пусть '''ROMij''' - это любая схема или программа, получающая в момент времени 0 на вход целые <math>p</math> и <math>q</math> и в момент времени <math>T</math> выдающая на выход  <math>r</math>, где <math>r = |(p - q) \cdot p_j^{-1}|_{p_i}</math>.
+Пусть '''LATCH''' - это любая схема или программа, получающая в момент времени 0 на вход целое число и выдающая это число на выход в момент времени <math>T</math>.
+Можно получить конвейерную схему, реализующую преобразование в полиадический код, разместив и соединив элементы '''ROMij''' и '''LATCH''', определенные выше, как показано на следующем рисунке.
 [[изображение:PoliadicCodeConvGeneralCase.PNG]]
+Назовем эту схему схемой преобразователя в полиадический код размера <math>D</math>. На вход схемы поступают цифры остатков, обозначенные от <math>I1</math> до <math>ID</math>, а выходами являются цифры полиадического кода, обозначенные от <math>O1</math> до <math>OD</math>. Больший индекс соответствует старшему разряду. <math>D</math> столбцов рассматриваются от <math>1</math> до <math>D</math>, причем столбец <math>1</math> принимает младший вход. <math>D-1</math> ступеней конвейера рассматриваются от <math>1</math> до <math>D-1</math>, причем входы схемы поступают на ступень <math>1</math>. Каждая ступень конвейера срабатывает за время <math>T</math>. Каждая ступень конвейера состоит из некоторого числа элементов '''ROMij''' и '''LATCH''', на входы которых поступают выходы предыдущей ступени, а выходы передаются на входы следующей ступени. Элемент с индексами '''i.j''' - это '''ROMij''', если <math>i>j</math>, или '''LATCH''', в противном случае. Левый вход элемента '''ROMij''' - <math>p</math>, правый - <math>q</math>.
+Для произвольного значения <math>N</math> схема сокращенного преобразователя в полиадический код - это конвейерная схема из <math>N-2</math> ступеней, содержащая <math>(Y-1)</math> элементов '''ROMij''' и <math>(Y-N+1)</math> элементов '''LATCH''', где <math>Y = (N \cdot (N-1) \cdot (N+1))/6</math>. Входом схемы являются <math>N</math> цифр модулярного представления, выходом - <math>(N+1) \cdot (N-1)/2</math> цифр полиадического кода. Данная реализация преобразователя заключает в себе <math>N-1</math> подсхем преобразователя в полиадический код, от <math>S_1</math> до <math>S_{N-1}</math>. Подсхема <math>S_z</math> содержит <math>N-z+1</math> элементов. Элемент '''ROMij''', находящийся в столбце <math>u</math>, ступени <math>v</math> подсхемы <math>S_z</math> определяется так:
+* <math>i=u+z-1;\ j=v+z-1</math>.
+Входами подсхемы <math>S_1</math> являются цифры от <math>x_1</math> до <math>x_N</math>. Подсхема <math>S_1</math> представляет собой особый случай, поскольку сокращена на одну ступень, ее выходы формируются после <math>N-2</math> ступени: это цифры полиадического кода от <math>S_{1}(1)</math> до <math>S_1(N)</math>.
+Входами подсхемы <math>S_i, i>1</math> являются <math>N-i+1</math> p-входов <math>i-1</math> ступени подсхемы <math>S_1</math>. Выходы подсхемы <math>S_i, i>1</math>: от <math>S_{i}(i)</math> до <math>S_i(N)</math>.
+Выходы рассмотренной схемы преобразователя необходимы и достаточны для полиадического представления всех проекций. Цифры полиадического кода проекции <math>P_{N}</math> таковы: от <math>S_{1}(1)</math> до <math>S_1(N-1)</math>. Цифры полиадического кода проекции <math>P_{N-1}</math> таковы: от <math>S_{1}(1)</math> до <math>S_1(N-2)</math>, и <math>S_1(N-1)</math>.
+Цифры полиадического кода проекции <math>P_{i}, i<N-1</math> таковы: от <math>S_{1}(1)</math> до <math>S_1(i-1)</math>, если <math>i>1</math>, и от <math>S_1(i+1)</math> до <math>S_1(N)</math>.

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

Версия 21:46, 5 ноября 2013

Содержание

Введение

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

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

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

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

Схема сокращенного преобразователя в полиадический код для коррекции одиночной ошибки

Ссылки

Навигация

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

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

Варианты

Просмотры

Действия

Поиск

Навигация

Инструменты