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

Материал из Модулярная арифметики
Перейти к: навигация, поиск
Строка 68: Строка 68:
 
Если посмотреть на самую правое слагаемое каждого из выражений можно заметить, что если любой из коэффициентов <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]]
Строка 78: Строка 78:
 
* <math>P_3 = \{S_1(4), S_1(2), S_1(1)\}</math>
 
* <math>P_3 = \{S_1(4), S_1(2), S_1(1)\}</math>
 
* <math>P_4 = \{S_1(3), S_1(2), S_1(1)\}</math>
 
* <math>P_4 = \{S_1(3), S_1(2), S_1(1)\}</math>
 +
 +
Простой метод основанный на репликации требует <math>A = (N \cdot (N-1) \cdot (N-2))/2</math> LUT и ROM. Сокращенный метод требует <math>(B-1)</math> ROM и <math>(B-N+1)</math> LUT, где <math>B = (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>
  
  

Версия 11:42, 7 октября 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 - элемент памяти сохраняющий значение до следующего такта
  • 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):

  • P_1 = \{S_2(4), S_2(3), S_2(2)\}
  • P_2 = \{S_3(4), S_3(3), S_1(1)\}
  • P_3 = \{S_1(4), S_1(2), S_1(1)\}
  • P_4 = \{S_1(3), S_1(2), S_1(1)\}

Простой метод основанный на репликации требует A = (N \cdot (N-1) \cdot (N-2))/2 LUT и ROM. Сокращенный метод требует (B-1) ROM и (B-N+1) LUT, где B = (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=619»