Какой самый быстрый алгоритм с точки зрения времени вычислений для пакетных ошибок (блочный код) во встроенной среде?

Question

Я рассматриваю реализацию кодирования и декодирования для устройств, работающих в шумном канале с пакетными ошибками. Я обнаружил, что наиболее распространенными методами для устранения ошибок являются следующие:

1. Коды Рида-Соломона (РС)
2. Пожарные коды
3. Чередование
4. конкатенация
5. Каскадный

Я предполагаю, что во встроенных системах наиболее эффективный способ реализации полиномиальных методов для хранения соответствующих полиномов в таблицах поиска. Тем не менее, кодирование и декодирование требует значительного количества вычислений и просто интересно, сколько времени это может занять.

Любая помощь будет оценена.

==========

PS: Обнаружение и исправление оба необходимы.

Answer 1

Я не думаю, что есть RS для исправления ошибок блока. Сверточные коды довольно быстрые (~15 амортизированных инструкций на декодированный бит для Витерби), но подходят только для спорадических битовых изменений. Синдром для BCH (двоичного) кода (31,5) может быть вычислен еще быстрее, но он имеет возможность только восстановить 2 бита.

На этой странице обсуждается сложность полных программных реализаций длинного RS-декодирования:

 RS(255,251) - 12 Mbps
 RS(255,239) - 2.7 Mbps
 RS(255,223) - 1.1 Mbps

Преобразование синдрома 2-х ошибок в местоположения ошибок достигло скорости 12 Мбит / с на 166 МГц Pentium (используя, вероятно, справочную таблицу), которая, как можно сказать, на 5-10% эффективнее, чем современные типичные встроенные процессоры. Сложность больших полиномов составляет около O(M*N), где M = длина блока, N= длина кода для вычисления синдрома и алгоритм Берлекампа-Масси. Похоже, что поиск по Чину часто выполняется путем перебора всех возможных (255) корней и подстановки их один за другим в полином ошибки, что также имеет сложность около O(M*N), так как M = размер блока = 255 примерно равно количеству кодовых слов (256).