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

Материал из Модулярная арифметики
Перейти к: навигация, поиск
 
(не показано 11 промежуточных версии 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>
  
Строка 58: Строка 64:
 
Динамический диапазон каждой из троек превышает заданный (можно убедиться для каждой тройки: <math>p_1 \cdot p_2 \cdot p_3 > p_1 \cdot p_2</math>). В случае если ошибок не было, то при обратном преобразовании в позиционное представление значения всех троек должны лежать в диапазоне: <math>[0 <= X < p_1 \cdot p_2]</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> и на основании сравнения выдать на выход правильное значение. Однако как будет показано ниже, корректирующий преобразователь можно значительно сократить по площади, объединив одинаковые части в каждом из обратных преобразователей и рассчитывая финальное позиционное значение только один раз для тройки с правильным значением.
+
В этом случае для восстановления числа требуется сделать 4 обратных преобразователя для каждой из троек. Сравнить полученные значения с <math>p_1 \cdot p_2</math> и на основании сравнения выдать на выход правильное значение. Однако, как будет показано ниже, корректирующий преобразователь можно значительно сократить по площади, объединив одинаковые части в каждом из обратных преобразователей и рассчитывая финальное позиционное значение только один раз для тройки с правильным значением.
  
 
Запишем, полиадическую формулу для каждой из троек:
 
Запишем, полиадическую формулу для каждой из троек:
Строка 66: Строка 72:
 
* <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>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>. Из чего следует, что выражение ошибочно. Этот факт можно использовать для определения ошибки не восстанавливая значение целиком ('''нужен пруф'''). Тем самым можно сократить площадь преобразователя.
+
Если посмотреть на самую правое слагаемое каждого из выражений, можно заметить, что если любой из коэффициентов <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] для этой цели можно использовать сокращенную форму (см. рисунок ниже).
+
Использовать несколько параллельных преобразователей оказывается неэффективным. Как показано в [2], для этой цели можно использовать сокращенную форму (см. рисунок ниже).
  
 
[[Изображение:Конвейерный преобразователь в полиадический код с коррекцией ошибок.png]]
 
[[Изображение:Конвейерный преобразователь в полиадический код с коррекцией ошибок.png]]
Строка 79: Строка 85:
 
* <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>
 
* <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>
  
−
Простой метод основанный на репликации требует <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>
+
Для последующего восстановления исходного числа с коррекцией возможной ошибки можно воспользоваться следующим алгоритмом:
 +
 
 +
<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;">
 
<table style="border: 1px solid black; padding: 3px;">
Строка 116: Строка 190:
  
 
</table>
 
</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»