Полиадический код — различия между версиями
Isaeva (обсуждение | вклад) |
Isaeva (обсуждение | вклад) |
||
Строка 139: | Строка 139: | ||
Во-вторых, выявляются уникальные подформулы. | Во-вторых, выявляются уникальные подформулы. | ||
− | В-третьих, первая ступень преобразователя строится размещением и соединением элементов, соответствующих подформулам первого порядка (наибольшей вложенности). | + | В-третьих, первая ступень преобразователя строится размещением и соединением элементов, соответствующих уникальным подформулам первого порядка (наибольшей вложенности). |
+ | |||
+ | В-четвертых, вторая ступень преобразователя строится размещением и соединением элементов, соответствующих уникальным подформулам второго порядка. | ||
+ | |||
+ | Процесс продолжается до тех пор, пока не будут построены все <math>N-1</math> ступеней. Затем там, где необходимо, добавляются элементы '''LATCH''', чтобы провести все цифры полиадического кода до конца конвейера. | ||
Версия 14:31, 6 ноября 2013
Содержание
Введение
Полиадический код (или система счисления со смешанным основанием от англ. 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"