Коды БЧХ, Вопросы по алгоритмам декодирования Опции

[des00]

Гуру кодирования, просвятите по теме

Потребовалось мне для проекта сделать БЧХ декодер работающий в поле GF(2), реализовал его по алгоритму Берлекэмпа-Месси приведенному на рисунке. Мне интересно, чем определяется необходимость последней проверки алгоритма перед процедурой Ченя(на рисунке выделено)? Ведь для бинарных БЧХ кодов четные невязки всегда будут равны нулю, а на нечетных проходах, по блок-схеме алгоритма, мы всегда попадаем на изменение длинны и степени полинома локатора ошибок. Т.е. эта проверка ничего не определяет. Тогда зачем она нужна? Или такая ситуация возможна только для не бинарных кодов?

И вопрос по алгоритму Евклида. Во всех книгах написано что он лучше подходит для аппаратной реализации, чем алгоритм Берлекэмпа-Месси, из-за своей регулярной структуры. Но один из шагов алгоритма деление полинома на полином. В железе же это делается с помощью регистров с линейными обратными связями, что приводит к многотактному делению и появлению лишних задержек, что ИМХО не айс. Так в чем же его преимущество перед алгоритмом Берлекэмпа-Месси ?

Спасибо.

Эскизы прикрепленных изображений

 

[Denisnovel]

Можно ли определить невозможность исправления ошибок до вычисления всех локаторов ошибок(в поиске Ченя)? Проблема в том, что декодер пытается исправить ошибки и вносит новые.

[petrov]

Можно ли определить невозможность исправления ошибок до вычисления всех локаторов ошибок(в поиске Ченя)? Проблема в том, что декодер пытается исправить ошибки и вносит новые.

Уже обсуждалось в этом топике...

[Denisnovel]

Из обсуждения выше я понял, что достоверно невозможно определить количество ошибок, если ошибок слишком много. Но меня интересует случай, когда ошибок меньше граници детектирования. Можно ли в этом случае определить возможность исправления ошибок до поиска ченя?

[petrov]

Но меня интересует случай, когда ошибок меньше граници детектирования. Можно ли в этом случае определить возможность исправления ошибок до поиска ченя?

Вопрос дурацкий, если ошибки можно исправить то их можно исправить и ничего определять не надо.

[Gold777]

Из обсуждения выше я понял, что достоверно невозможно определить количество ошибок, если ошибок слишком много. Но меня интересует случай, когда ошибок меньше граници детектирования. Можно ли в этом случае определить возможность исправления ошибок до поиска ченя?

Если количество ошибок превышает исправляющую способность кода , то нет смысла определять сколько было ошибок. Если как Вы говорите ошибок точно меньше исправляющей способности, то вы с высокой степенью вероятности можете предположить, что возможность исправления есть. А вот местоположения этих ошибок Вы сможете определить только после процедуры Ченя. Хотя мне непонятно зачем Вам определять возможность исправления.

[Denisnovel]

Может я не правильно выразился. Можно ли вычислить сигнал "decoding failure" до поиска Ченя?

[Gold777]

Может я не правильно выразился. Можно ли вычислить сигнал "decoding failure" до поиска Ченя?

нельзя

[Denisnovel]

Ясно. Спасибо.

[des00]

нельзя

Ясно. Спасибо.

можно, но не в реализации алгоритма берлекампа с фиксированным количеством шагов. В частности, если мне не изменяет память, в книге "Кодирование с исправлением ошибок в системах связи" есть классическая реализация алгоритма берлекампа с делением, там есть анализ степени полинома, которая получилась.

ну и еще, если степень полинома локаторов меньше t, то гарантировано все будет ок.
это не к месту %)

[des00]

можно, но не в реализации алгоритма берлекампа с фиксированным количеством шагов. В частности, если мне не изменяет память, в книге "Кодирование с исправлением ошибок в системах связи" есть классическая реализация алгоритма берлекампа с делением, там есть анализ степени полинома, которая получилась.

а вот и тот алгоритм и статья . Кстати есть такая занятная вещь как "декодирование за границей БЧХ" никто не сталкивался ?

[SKov]

а вот и тот алгоритм и статья . Кстати есть такая занятная вещь как "декодирование за границей БЧХ" никто не сталкивался ?

Обычно рассматривается случай одной-двух дополнительных ошибок, не больше. Есть куча работ.

[des00]

Обычно рассматривается случай одной-двух дополнительных ошибок, не больше. Есть куча работ.

как раз такой случай мне и попался на глаза. код дополняется двумя символами которые декодируются за счет изменения берлекампа. сегодня еще рыл сеть, нашел пару статей об арифметическом декодировании кодов РС с мягким решением. Подробно не смотрел, отметил только что в них, РС указан как класс арифметических кодов.

[Denisnovel]

Делаю паралельную реализация поиска Ченя согласно прикрепленному файлу. Считает правильно, но результат сдвунут на 1. Т.е. 0 появляется раньше на одну позицию.
При начале поиска происходит инициализация. Если написать "start_root_index(i)-1" то с одной ошибкой работает, с двумя не работает совсем.

Код

loc_mult_par[i] <= gf_mult_a_by_b_const(iloc_poly[i], ALPHA_TO[start_root_index(i)-1]);

Что это может быть?

Эскизы прикрепленных изображений

 

[Mikhalych]

Делаю паралельную реализация поиска Ченя согласно прикрепленному файлу. Считает правильно, но результат сдвунут на 1.
Что это может быть?

Код неукороченный случаем?

[Denisnovel]

Код укороченный. Проблема где-то в инициализации