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

Материал из Модулярная арифметики
Перейти к: навигация, поиск
Строка 92: Строка 92:
 
<p>&nbsp;&nbsp;&nbsp;Ошибка более чем в 1 канале</p>
 
<p>&nbsp;&nbsp;&nbsp;Ошибка более чем в 1 канале</p>
 
<p><math>\}</math></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>k</math> - целое число, такое, что
 +
 +
:<math> k \leq \prod^{(N-2)}_{i=1} m_{i}</math>
 +
 +
Представление числа <math>k</math> в модулярном виде <math>N</math> цифрами остатков таково: <math>(k_1, k_2, k_3, ..., k_N)</math>, где <math>k_i</math> - значение остатка <math>k (mod  p_i)</math>. В этом случае 2 цифры остатков избыточны. Первые <math>(N-2)</math> цифр являются информационными, а последние две <math>(p_{N-1}, p_N)</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>. Количество уровней обоих методов совпадает и для реализации используются одинаковые элементы, поэтому тактовая частота работы после сокращения площади не изменится.
 
Простой метод основанный на репликации требует <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>. Количество уровней обоих методов совпадает и для реализации используются одинаковые элементы, поэтому тактовая частота работы после сокращения площади не изменится.
  

Версия 14:55, 30 октября 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):

  • 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}).

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

k \leq \prod^{(N-2)}_{i=1} m_{i}

Представление числа k в модулярном виде N цифрами остатков таково: (k_1, k_2, k_3, ..., k_N), где k_i - значение остатка k (mod p_i). В этом случае 2 цифры остатков избыточны. Первые (N-2) цифр являются информационными, а последние две (p_{N-1}, p_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

Ссылки

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