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

Материал из Модулярная арифметики
Перейти к: навигация, поиск
 
(не показаны 24 промежуточные версии 2 участников)
Строка 3: Строка 3:
 
'''Полиадический код''' (или система счисления со смешанным основанием от англ. [http://en.wikipedia.org/wiki/Residue_number_system#Associated_mixed_radix_system associated mixed radix system (AMRS)])
 
'''Полиадический код''' (или система счисления со смешанным основанием от англ. [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>\{b_k\}_{k=0}^{\infty}</math>, и каждое число <math>X</math> в ней представляется как линейная комбинация:
 +
<math>X = \sum_{k=0}^{n-1} a_{k}b_k</math>, где на коэффициенты <math>a_{k}</math>, называемые как и прежде цифрами, накладываются некоторые ограничения.
 +
Записью числа <math>x</math> в смешанной системе счисления называется перечисление его цифр в порядке уменьшения индекса <math>k</math>, начиная с первого ненулевого.
 +
 
 +
 
 +
Любое число <math>\{x_1,x_2,x_3,\ldots,x_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>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>x_k</math> - цифры кода, числа <math>M_k</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>
 
:<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>
  
Строка 28: Строка 34:
  
 
== Конвейерный преобразователь в полиадический код ==
 
== Конвейерный преобразователь в полиадический код ==
 +
 +
Используя формулы выше можно нарисовать схему конвейерного преобразователя. В данном случае мы используем модулярный базис из 4 элементов:
  
 
[[изображение:Конвейерный преобразователь в полиадический код.png]]
 
[[изображение:Конвейерный преобразователь в полиадический код.png]]
 +
 +
* '''ROMij''' - это таблица выполняющая следующее преобразование <math>r = |(p - q) \cdot p_j^{-1}|_{p_i}</math>. Для больших значений модулей таблица может быть заменена на последовательный набор арифметических операций (вычитание, умножение на константу и взятие модуля)
 +
* '''LATCH''' - элемент памяти сохраняющий значение до следующего такта
 +
* На преобразование модулярного представления в полиадический код требуется 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''' - элемент памяти сохраняющий значение до следующего такта
 +
* '''SUM''' - обычный сумматор
 +
* На преобразование модулярного представления в позиционный вид требуется N ступеней конвейера.
 +
* В отличие от преобразования в полиадический код, данный преобразователь получается более громоздким из-за более сложной структуры '''ROMij''' и наличия сумматоров, битовый размер которых растет в нижней части конвейера.
 +
 +
== Коррекция ошибок на базе полиадического кода ==
 +
 +
Пусть задан набор модулей <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>P_1 = (x_2, x_3, x_4)</math>
 +
* <math>P_2 = (x_1, x_3, x_4)</math>
 +
* <math>P_3 = (x_1, x_2, x_4)</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> и быть равными. В случае, если в одном из каналов произошла ошибка, то правильное значение даст только одна тройка, в которой исключено неверное значение, все остальные тройки будут лежать вне динамического диапазона ('''здесь нужна ссылка на пруФФФФФ или сам пруф''').
 +
 +
В этом случае для восстановления числа требуется сделать 4 обратных преобразователя для каждой из троек. Сравнить полученные значения с <math>p_1 \cdot p_2</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_{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_{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_{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}_{P_1}, {a_3}_{P_2}, {a_3}_{P_3}, {a_3}_{P_4}</math> отличается от нуля, то всё выражение получается больше, чем <math>p_1 \cdot p_2</math>. Из чего следует, что выражение ошибочно. Этот факт можно использовать для определения ошибки, не восстанавливая значение целиком ('''нужен пруф'''). Тем самым можно сократить площадь преобразователя.
 +
 +
== Схема сокращенного преобразователя в полиадический код для коррекции одиночной ошибки ==
 +
Использовать несколько параллельных преобразователей оказывается неэффективным. Как показано в [2], для этой цели можно использовать сокращенную форму (см. рисунок ниже).
 +
 +
[[Изображение:Конвейерный преобразователь в полиадический код с коррекцией ошибок.png]]
 +
 +
В этом случае на выходных узлах можно получить полиадическое представление для каждого из исключающих наборов <math>(P_1, P_2, P_3, P_4)</math>:
 +
* <math>A_{P_1} = \{{a_1}_{P_1}, {a_2}_{P_1}, {a_3}_{P_1}\} = \{S_2(2), S_2(3), S_2(4)\}</math>
 +
* <math>A_{P_2} = \{{a_1}_{P_2}, {a_2}_{P_2}, {a_3}_{P_2}\} = \{S_1(1), S_3(3), S_3(4)\}</math>
 +
* <math>A_{P_3} = \{{a_1}_{P_3}, {a_2}_{P_3}, {a_3}_{P_3}\} = \{S_1(1), S_1(2), S_1(4)\}</math>
 +
* <math>A_{P_4} = \{{a_1}_{P_4}, {a_2}_{P_4}, {a_3}_{P_4}\} = \{S_1(1), S_1(2), S_1(3)\}</math>
 +
 +
Для последующего восстановления исходного числа с коррекцией возможной ошибки можно воспользоваться следующим алгоритмом:
 +
 +
<p><math>if ({a_3}_{P_1} == 0) \{</math></p>
 +
<p>&nbsp;&nbsp;&nbsp;<math>X = {a_1}_{P_1} + {a_2}_{P_1}\cdot p_2</math></p>
 +
<p><math>\} else if ({a_3}_{P_2} == 0) \{</math></p>
 +
<p>&nbsp;&nbsp;&nbsp;<math>X = {a_1}_{P_2} + {a_2}_{P_2}\cdot p_1</math></p>
 +
<p><math>\} else if ({a_3}_{P_3} == 0) \{</math></p>
 +
<p>&nbsp;&nbsp;&nbsp;<math>X = {a_1}_{P_3} + {a_2}_{P_3}\cdot p_1</math></p>
 +
<p><math>\} else if ({a_3}_{P_4} == 0) \{</math></p>
 +
<p>&nbsp;&nbsp;&nbsp;<math>X = {a_1}_{P_4} + {a_2}_{P_4}\cdot p_1</math></p>
 +
<p><math>\} else \{</math></p>
 +
<p>&nbsp;&nbsp;&nbsp;Ошибка более чем в 1 канале</p>
 +
<p><math>\}</math></p>
 +
 +
 +
Для произвольного значения <math>N</math> схема сокращенного преобразователя в полиадический код строится следующим образом.
 +
Возьмем систему остатков для следующего набора <math>N</math> взаимно простых целых модулей: <math>(p_1, p_2, p_3, ..., p_N)</math>, где <math>(p_{i+1} < p_{i})</math>.
 +
 +
Пусть <math>X</math> - целое число, такое, что
 +
 +
:<math> X \leq \prod^{(N-2)}_{i=1} p_{i}</math>
 +
 +
Представление числа <math>X</math> в модулярном виде <math>N</math> набором остатков таково: <math>(x_1, x_2, x_3, ..., x_N)</math>, где <math>x_i</math> - значение остатка <math>X (mod\  p_i)</math>. В этом случае 2 цифры остатков избыточны. Данный набор позволяет найти и исправить одиночную ошибку в одном из модулярных каналов.
 +
 +
Для поиска и коррекции ошибок используется преобразование модулярного представления числа в полиадический код.
 +
 +
По набору <math>x_i</math> создается полиадический код - набор <math>a_i</math>. Ошибочные каналы модулярного представления определяются следующим образом.
 +
 +
Во-первых, из <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>.
 +
 +
Данный преобразователь может быть реализован следующим образом:
 +
 +
Во-первых, при помощи преобразования в полиадический код определяются <math>N-1</math> цифр полиадического кода, которые должны быть вычислены для каждой из <math>N</math> проекций. Затем каждая из цифр выражается через элементы, необходимые для ее вычисления.
 +
 +
Во-вторых, выявляются уникальные подформулы.
 +
 +
В-третьих, первая ступень преобразователя строится размещением и соединением элементов, соответствующих уникальным подформулам первого порядка (наибольшей вложенности).
 +
 +
В-четвертых, вторая ступень преобразователя строится размещением и соединением элементов, соответствующих уникальным подформулам второго порядка.
 +
 +
Процесс продолжается до тех пор, пока не будут построены все <math>N-1</math> ступеней. Затем там, где необходимо, добавляются элементы '''LATCH''', чтобы передать все цифры полиадического кода до конца конвейера.
 +
  
  
−
== Обратный преобразователь на базе полиадического кода ==
+
Простой метод, основанный на репликации, требует <math>X = (N \cdot (N-1) \cdot (N-2))/2</math> LUT и ROM. Сокращенный метод требует <math>(Y-1)</math> ROM и <math>(Y-N+1)</math> LUT, где <math>Y = (N \cdot (N-1) \cdot (N+1))/6</math>. Количество уровней обоих методов совпадает, и для реализации используются одинаковые элементы, поэтому тактовая частота работы после сокращения площади не изменится.
  
 +
<table style="border: 1px solid black; padding: 3px;">
 +
<tr>
 +
<td style="border: 1px solid black; padding: 3px;">N</td>
 +
<td style="border: 1px solid black; padding: 3px;">4</td>
 +
<td style="border: 1px solid black; padding: 3px;">5</td>
 +
<td style="border: 1px solid black; padding: 3px;">6</td>
 +
<td style="border: 1px solid black; padding: 3px;">7</td>
 +
<td style="border: 1px solid black; padding: 3px;">10</td>
 +
</tr>
 +
<tr>
 +
<td style="border: 1px solid black; padding: 3px;">Репликация (кол-во ROM/LUT)</td>
 +
<td style="border: 1px solid black; padding: 3px;">12</td>
 +
<td style="border: 1px solid black; padding: 3px;">30</td>
 +
<td style="border: 1px solid black; padding: 3px;">60</td>
 +
<td style="border: 1px solid black; padding: 3px;">105</td>
 +
<td style="border: 1px solid black; padding: 3px;">360</td>
 +
</tr>
 +
<tr>
 +
<td style="border: 1px solid black; padding: 3px;">Метод сокращения (кол-во ROM)</td>
 +
<td style="border: 1px solid black; padding: 3px;">9</td>
 +
<td style="border: 1px solid black; padding: 3px;">19</td>
 +
<td style="border: 1px solid black; padding: 3px;">34</td>
 +
<td style="border: 1px solid black; padding: 3px;">55</td>
 +
<td style="border: 1px solid black; padding: 3px;">164</td>
 +
</tr>
 +
<tr>
 +
<td style="border: 1px solid black; padding: 3px;">Метод сокращения (кол-во LUT)</td>
 +
<td style="border: 1px solid black; padding: 3px;">7</td>
 +
<td style="border: 1px solid black; padding: 3px;">16</td>
 +
<td style="border: 1px solid black; padding: 3px;">30</td>
 +
<td style="border: 1px solid black; padding: 3px;">50</td>
 +
<td style="border: 1px solid black; padding: 3px;">156</td>
 +
</tr>
  
 +
</table>
  
 
== Ссылки ==
 
== Ссылки ==
 
* [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"]

Текущая версия на 09:24, 12 февраля 2015

Введение

Полиадический код (или система счисления со смешанным основанием от англ. associated mixed radix system (AMRS))


Основанием смешанной системы счисления является возрастающая последовательность чисел \{b_k\}_{k=0}^{\infty}, и каждое число X в ней представляется как линейная комбинация: X = \sum_{k=0}^{n-1} a_{k}b_k, где на коэффициенты a_{k}, называемые как и прежде цифрами, накладываются некоторые ограничения. Записью числа x в смешанной системе счисления называется перечисление его цифр в порядке уменьшения индекса k, начиная с первого ненулевого.


Любое число \{x_1,x_2,x_3,\ldots,x_n\} в системе остаточных классов может быть представлено в виде полиадического кода

X=\sum_{i=1}^Nx_iM_{i-1}=x_1+m_1(x_2+m_2(\cdots+m_{N-1}x_{N})\cdots),

где x_k - цифры кода, числа M_k - основание смешанной системы счисления:

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 - элемент памяти сохраняющий значение до следующего такта
  • 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], для этой цели можно использовать сокращенную форму (см. рисунок ниже).

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

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

PoliadicCodeConvGeneralCase.PNG


Назовем эту схему схемой преобразователя в полиадический код размера 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).

Данный преобразователь может быть реализован следующим образом:

Во-первых, при помощи преобразования в полиадический код определяются N-1 цифр полиадического кода, которые должны быть вычислены для каждой из N проекций. Затем каждая из цифр выражается через элементы, необходимые для ее вычисления.

Во-вторых, выявляются уникальные подформулы.

В-третьих, первая ступень преобразователя строится размещением и соединением элементов, соответствующих уникальным подформулам первого порядка (наибольшей вложенности).

В-четвертых, вторая ступень преобразователя строится размещением и соединением элементов, соответствующих уникальным подформулам второго порядка.

Процесс продолжается до тех пор, пока не будут построены все N-1 ступеней. Затем там, где необходимо, добавляются элементы LATCH, чтобы передать все цифры полиадического кода до конца конвейера.


Простой метод, основанный на репликации, требует 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

Ссылки

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