Полиадический код — различия между версиями
Turbo (обсуждение | вклад) (Новая страница: «'''Полиадический код''' (или система счисления со смешанным основанием от англ. [http://en.wikipedia…») |
Isaeva (обсуждение | вклад) |
||
(не показаны 33 промежуточные версии 2 участников) | |||
Строка 1: | Строка 1: | ||
+ | == Введение == | ||
+ | |||
'''Полиадический код''' (или система счисления со смешанным основанием от англ. [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>\{ | + | |
+ | Основанием смешанной системы счисления является возрастающая последовательность чисел <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> | ||
Строка 10: | Строка 18: | ||
* Сравнения чисел | * Сравнения чисел | ||
* Перевода чисел из системы остаточных классов в обычную позиционную систему счисления | * Перевода чисел из системы остаточных классов в обычную позиционную систему счисления | ||
+ | |||
+ | == Обратное преобразование == | ||
+ | |||
+ | Обратное преобразование на базе полиадического кода, базируется на идее, что любое число X может быть представлено в системе взаимно простых чисел <math>p_1,\ldots, p_n</math>, как [1]: | ||
+ | :<math>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}</math>, где <math>0 < a_i < p_i</math> | ||
+ | * <math>|X|_{p_1} = x_1 = a_1</math> | ||
+ | * <math>|X - a_1|_{p_2} = |x_2 - a_1|_{p_2} = |a_2\cdot p_1|_{p_2}</math> => <math>a_2 = ||p_1^{-1}|_{p_2}\cdot (x_2 - a_1)|_{p_2}</math> | ||
+ | * <math>|X - a_1 - a_2\cdot p_1|_{p_3} = |a_3\cdot p_1 \cdot p_2|_{p_3}</math> => <math>a_3 = ||p_2^{-1}|_{p_3} \cdot (|p_1^{-1}|_{p_3} \cdot (x_3 - a_1) - a_2)|_{p_3}</math> | ||
+ | * <math>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}</math> | ||
+ | * ... | ||
+ | * <math>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}</math> | ||
+ | |||
+ | |||
+ | Для использования этого метода требуются константы вида <math>|p_i^{-1}|_{p_k}</math>. Можно также заметить, что начинать вычисление <math>a_3</math> можно, как только появилось значение <math>a_1</math>. На основе этого метода можно строить конвейерные преобразователи. | ||
+ | |||
+ | == Конвейерный преобразователь в полиадический код == | ||
+ | |||
+ | Используя формулы выше можно нарисовать схему конвейерного преобразователя. В данном случае мы используем модулярный базис из 4 элементов: | ||
+ | |||
+ | [[изображение:Конвейерный преобразователь в полиадический код.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> <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> <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> <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> <math>X = {a_1}_{P_4} + {a_2}_{P_4}\cdot p_1</math></p> | ||
+ | <p><math>\} else \{</math></p> | ||
+ | <p> Ошибка более чем в 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. | ||
+ | * [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))
Основанием смешанной системы счисления является возрастающая последовательность чисел , и каждое число в ней представляется как линейная комбинация:
, где на коэффициенты , называемые как и прежде цифрами, накладываются некоторые ограничения.
Записью числа в смешанной системе счисления называется перечисление его цифр в порядке уменьшения индекса , начиная с первого ненулевого.
Любое число в системе остаточных классов может быть представлено в виде полиадического кода
где - цифры кода, числа - основание смешанной системы счисления:
- для и
Полиадический код используется для:
- Сравнения чисел
- Перевода чисел из системы остаточных классов в обычную позиционную систему счисления
Обратное преобразование
Обратное преобразование на базе полиадического кода, базируется на идее, что любое число X может быть представлено в системе взаимно простых чисел , как [1]:
- , где
- =>
- =>
- ...
Для использования этого метода требуются константы вида . Можно также заметить, что начинать вычисление можно, как только появилось значение . На основе этого метода можно строить конвейерные преобразователи.
Конвейерный преобразователь в полиадический код
Используя формулы выше можно нарисовать схему конвейерного преобразователя. В данном случае мы используем модулярный базис из 4 элементов:
- ROMij - это таблица выполняющая следующее преобразование . Для больших значений модулей таблица может быть заменена на последовательный набор арифметических операций (вычитание, умножение на константу и взятие модуля)
- LATCH - элемент памяти сохраняющий значение до следующего такта
- На преобразование модулярного представления в полиадический код требуется N-1 ступеней конвейера.
Обратный конвейерный преобразователь на базе полиадического кода
Этот преобразователь используется для восстановления числа из модулярного кода, заданного набором остатков .
- ROMij - это таблица выполняющая следующее преобразование . Для больших значений модулей таблица может быть заменена на последовательный набор арифметических операций (вычитание, умножение на константу и взятие модуля)
- LATCH - элемент памяти сохраняющий значение до следующего такта
- SUM - обычный сумматор
- На преобразование модулярного представления в позиционный вид требуется N ступеней конвейера.
- В отличие от преобразования в полиадический код, данный преобразователь получается более громоздким из-за более сложной структуры ROMij и наличия сумматоров, битовый размер которых растет в нижней части конвейера.
Коррекция ошибок на базе полиадического кода
Пусть задан набор модулей , где . Из них первые два являются информационными, а последние два - проверочными. Данный набор позволяет корректировать одиночную ошибку в одном из модулярных каналов. Для коррекции можно использовать следующий наиболее простой подход на базе так называемой "репликации": из модулярного представления числа последовательно исключается каждый канал, формируя "исключающие наборы":
Динамический диапазон каждой из троек превышает заданный (можно убедиться для каждой тройки: ). В случае если ошибок не было, то при обратном преобразовании в позиционное представление значения всех троек должны лежать в диапазоне: и быть равными. В случае, если в одном из каналов произошла ошибка, то правильное значение даст только одна тройка, в которой исключено неверное значение, все остальные тройки будут лежать вне динамического диапазона (здесь нужна ссылка на пруФФФФФ или сам пруф).
В этом случае для восстановления числа требуется сделать 4 обратных преобразователя для каждой из троек. Сравнить полученные значения с и на основании сравнения выдать на выход правильное значение. Однако, как будет показано ниже, корректирующий преобразователь можно значительно сократить по площади, объединив одинаковые части в каждом из обратных преобразователей и рассчитывая финальное позиционное значение только один раз для тройки с правильным значением.
Запишем, полиадическую формулу для каждой из троек:
Если посмотреть на самую правое слагаемое каждого из выражений, можно заметить, что если любой из коэффициентов отличается от нуля, то всё выражение получается больше, чем . Из чего следует, что выражение ошибочно. Этот факт можно использовать для определения ошибки, не восстанавливая значение целиком (нужен пруф). Тем самым можно сократить площадь преобразователя.
Схема сокращенного преобразователя в полиадический код для коррекции одиночной ошибки
Использовать несколько параллельных преобразователей оказывается неэффективным. Как показано в [2], для этой цели можно использовать сокращенную форму (см. рисунок ниже).
В этом случае на выходных узлах можно получить полиадическое представление для каждого из исключающих наборов :
Для последующего восстановления исходного числа с коррекцией возможной ошибки можно воспользоваться следующим алгоритмом:
Ошибка более чем в 1 канале
Для произвольного значения схема сокращенного преобразователя в полиадический код строится следующим образом.
Возьмем систему остатков для следующего набора взаимно простых целых модулей: , где .
Пусть - целое число, такое, что
Представление числа в модулярном виде набором остатков таково: , где - значение остатка . В этом случае 2 цифры остатков избыточны. Данный набор позволяет найти и исправить одиночную ошибку в одном из модулярных каналов.
Для поиска и коррекции ошибок используется преобразование модулярного представления числа в полиадический код.
По набору создается полиадический код - набор . Ошибочные каналы модулярного представления определяются следующим образом.
Во-первых, из каналов модулярного представления числа , создаем наборов по каналов, причем последовательно исключается каждый канал, формируя так называемые проекции ("исключающие наборы"). Пусть - проекция, полученная исключением канала . Преобразуем в полиадический код каждую из проекций . Если для всех проекций старшие разряды полученного полиадического кода равны нулю, ни в одном канале ошибки нет. Если полученные старшие разряды ненулевые для всех проекций, кроме , то в канале присутствует ошибка, а - правильное представление числа .
Пусть ROMij - это любая схема или программа, получающая в момент времени 0 на вход целые и и в момент времени выдающая на выход , где .
Пусть LATCH - это любая схема или программа, получающая в момент времени 0 на вход целое число и выдающая это число на выход в момент времени .
Можно получить конвейерную схему, реализующую преобразование в полиадический код, разместив и соединив элементы ROMij и LATCH, определенные выше, как показано на следующем рисунке.
Назовем эту схему схемой преобразователя в полиадический код размера . На вход схемы поступают цифры остатков, обозначенные от до , а выходами являются цифры полиадического кода, обозначенные от до . Больший индекс соответствует старшему разряду. столбцов рассматриваются от до , причем столбец принимает младший вход. ступеней конвейера рассматриваются от до , причем входы схемы поступают на ступень . Каждая ступень конвейера срабатывает за время . Каждая ступень конвейера состоит из некоторого числа элементов ROMij и LATCH, на входы которых поступают выходы предыдущей ступени, а выходы передаются на входы следующей ступени. Элемент с индексами i.j - это ROMij, если , или LATCH, в противном случае. Левый вход элемента ROMij - , правый - .
Для произвольного значения схема сокращенного преобразователя в полиадический код - это конвейерная схема из ступеней, содержащая элементов ROMij и элементов LATCH, где . Входом схемы являются цифр модулярного представления, выходом - цифр полиадического кода. Данная реализация преобразователя заключает в себе подсхем преобразователя в полиадический код, от до . Подсхема содержит элементов. Элемент ROMij, находящийся в столбце , ступени подсхемы определяется так:
- .
Входами подсхемы являются цифры от до . Подсхема представляет собой особый случай, поскольку сокращена на одну ступень, ее выходы формируются после ступени: это цифры полиадического кода от до .
Входами подсхемы являются p-входов ступени подсхемы . Выходы подсхемы : от до .
Выходы рассмотренной схемы преобразователя необходимы и достаточны для того, чтобы получить полиадическое представление всех проекций. Цифры полиадического кода проекции таковы: от до . Цифры полиадического кода проекции таковы: от до , и .
Цифры полиадического кода проекции таковы: от до , если , и от до .
Данный преобразователь может быть реализован следующим образом:
Во-первых, при помощи преобразования в полиадический код определяются цифр полиадического кода, которые должны быть вычислены для каждой из проекций. Затем каждая из цифр выражается через элементы, необходимые для ее вычисления.
Во-вторых, выявляются уникальные подформулы.
В-третьих, первая ступень преобразователя строится размещением и соединением элементов, соответствующих уникальным подформулам первого порядка (наибольшей вложенности).
В-четвертых, вторая ступень преобразователя строится размещением и соединением элементов, соответствующих уникальным подформулам второго порядка.
Процесс продолжается до тех пор, пока не будут построены все ступеней. Затем там, где необходимо, добавляются элементы LATCH, чтобы передать все цифры полиадического кода до конца конвейера.
Простой метод, основанный на репликации, требует LUT и ROM. Сокращенный метод требует ROM и LUT, где . Количество уровней обоих методов совпадает, и для реализации используются одинаковые элементы, поэтому тактовая частота работы после сокращения площади не изменится.
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"