Полиадический код
Содержание
Введение
Полиадический код (или система счисления со смешанным основанием от англ. associated mixed radix system (AMRS))
Любое число в системе остаточных классов может быть представленно в виде полиадического кода
где
- для и
Полиадический код используется для:
- Сравнения чисел
- Перевода чисел из системы остаточных классов в обычную позиционную систему счисления
Обратное преобразование
Обратное преобразование на базе полиадического кода, базируется на идее, что любое число X может быть представлено в системе взаимно простых чисел , как [1]:
- , где
- =>
- =>
- ...
Для использования этого метода требуются константы вида . Можно также заметить, что начинать вычисление можно, как только появилось значение . На основе этого метода можно строить конвейерные преобразователи.
Конвейерный преобразователь в полиадический код
Используя формулы выше можно нарисовать схему конвейерного преобразователя. В данном случае мы используем модулярный базис из 4 элементов:
- ROMij - это таблица выполняющая следующее преобразование . Для больших значений модулей таблица может быть заменена на последовательный набор арифметических операций (вычитание, умножение на константу и взятие модуля)
- LATCH - элемент памяти сохраняющий значение до следующего такта
- На преобразование модулярного представления в полиадический код требуется N-1 ступеней конвейера.
Обратный конвейерный преобразователь на базе полиадического кода
Этот преобразователь используется для восстановления числа из модулярного кода, заданного набором остатков .
- ROMij - это таблица выполняющая следующее преобразование . Для больших значений модулей таблица может быть заменена на последовательный набор арифметических операций (вычитание, умножение на константу и взятие модуля)
- LATCH - элемент памяти сохраняющий значение до следующего такта
- SUM - обычный сумматор
- На преобразование модулярного представления в позиционный вид требуется N ступеней конвейера.
- В отличие от преобразования в полиадический код, данный преобразователь получается более громоздким из-за более сложной структуры ROMij и наличия сумматоров, битовый размер которых растет в нижней части конвейера.
Коррекция ошибок на базе полиадического кода
Пусть задан набор модулей , где . Из них первые два являются информационными, а последние два - проверочными. Данный набор позволяет корректировать одиночную ошибку в одном из модулярных каналов. Для коррекции можно использовать следующий наиболее простой подход на базе так называемой "репликации": из модулярного представления числа последовательно исключается каждый канал, формируя "исключающие наборы":
Динамический диапазон каждой из троек превышает заданный (можно убедиться для каждой тройки: ). В случае если ошибок не было, то при обратном преобразовании в позиционное представление значения всех троек должны лежать в диапазоне: и быть равными. В случае, если в одном из каналов произошла ошибка, то правильное значение даст только одна тройка, в которой исключено неверное значение, все остальные тройки будут лежать вне динамического диапазона (здесь нужна ссылка на пруФФФФФ или сам пруф).
В этом случае для восстановления числа требуется сделать 4 обратных преобразователя для каждой из троек. Сравнить полученные значения с и на основании сравнения выдать на выход правильное значение. Однако как будет показано ниже, корректирующий преобразователь можно значительно сократить по площади, объединив одинаковые части в каждом из обратных преобразователей и рассчитывая финальное позиционное значение только один раз для тройки с правильным значением.
Запишем, полиадическую формулу для каждой из троек:
Если посмотреть на самую правое слагаемое каждого из выражений можно заметить, что если любой из коэффициентов отличается от нуля, то всё выражение получается больше, чем . Из чего следует, что выражение ошибочно. Этот факт можно использовать для определения ошибки не восстанавливая значение целиком (нужен пруф). Тем самым можно сократить площадь преобразователя.
Схема сокращенного преобразователя в полиадический код для коррекции одиночной ошибки
Использовать несколько параллельных преобразователей оказывается неэффективным. Как показано в [2] для этой цели можно использовать сокращенную форму (см. рисунок ниже).
В этом случае на выходных узлах можно получить полиадическое представление для каждого из исключающих наборов :
Простой метод основанный на репликации требует 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"