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

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

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

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

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

==========

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


embedded reed-solomon
person Alma Rahat    schedule 06.12.2012    source источник
comment
Я полагаю, вы хотите выполнить прямое исправление ошибок (а не просто обнаруживать ошибки)? Вы должны сказать это прямо.   -  person starblue    schedule 06.12.2012

Ответы (1)


arrow_upward
1
arrow_downward

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

person Aki Suihkonen    schedule 07.12.2012
comment
Существуют и другие методы, которые можно использовать в случае пакетных ошибок. Я получил кое-что из здесь. Ваша ссылка была полезной. Спасибо за ваш ответ. - person Alma Rahat; 07.12.2012