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

[des00]

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

если код укороченный и начинаете перебор с элемента a^n, то нужно скорректировать инициализацию на a^(gf_n_max - n) нулей.

[Denisnovel]

Сейчас сделал так. Вроде работает. Буду тестировать.

Код

  function automatic data_t start_root_index(input int step);
    start_root_index = (step*(gf_n_max - n /*+ 1*/)) % gf_n_max;
  endfunction

[Denisnovel]

,,

Сообщение отредактировал Denisnovel - Mar 14 2012, 09:33

[mad_physicist]

Господа, просвятите начинающего!
Задача стоит реализовать на языке MATLAB алгоритм Берлекемпа-Месси в декодере БЧХ. Алгоритм предусматривает использование компонент (элементов) синдрома, которые определяются как значения принятого слова (полинома) в нулях кода (в корнях порождающего многочлена). Мне непонятно, в какой форме должны находиться и использоваться в этой ситуации корни порождающего многочлена. Буду особенно благодарен за комментарии с примерами.

[des00]

Буду особенно благодарен за комментарии с примерами.

что мешает найти в матлабе файлик rsdec.m или bchdec.m и посмотреть ?

[mad_physicist]

что мешает найти в матлабе файлик rsdec.m или bchdec.m и посмотреть ?

отсутствие уверенности в том, что там именно нужный мне алгоритм

[Gold777]

Господа, просвятите начинающего!
Задача стоит реализовать на языке MATLAB алгоритм Берлекемпа-Месси в декодере БЧХ. Алгоритм предусматривает использование компонент (элементов) синдрома, которые определяются как значения принятого слова (полинома) в нулях кода (в корнях порождающего многочлена). Мне непонятно, в какой форме должны находиться и использоваться в этой ситуации корни порождающего многочлена. Буду особенно благодарен за комментарии с примерами.

Если хотите разобраться в алгоритме БМ, почитайте Морелос-Сарагоса - Искусство помехоустойчивого кодирования. Для алгоритма БМ нужны только компоненты синдромов. Компоненты синдромов рассчитываются с помощью элементов поля Галуа.
О чем вы спрашиваете мне не очень понятно ( Что значит в какой форме должны находиться и использоваться в этой ситуации корни порождающего многочлена?).

Сообщение отредактировал Gold777 - Mar 28 2012, 11:26

[mad_physicist]

Если хотите разобраться в алгоритме БМ, почитайте Морелос-Сарагоса - Искусство помехоустойчивого кодирования. Для алгоритма БМ нужны только компоненты синдромов. Компоненты синдромов рассчитываются с помощью элементов поля Галуа.
О чем вы спрашиваете мне не очень понятно ( Что значит в какой форме должны находиться и использоваться в этой ситуации корни порождающего многочлена?).

То, что я написал, основано именно на книге Морелоса-Сарагосы и статье С.В. Фёдорова о реализации БМ-алгоритма для РС-кодов на ПЛИС. Компоненты синдромов вычисляются путём подстановки корней порождающего полинома в полином принятого сообщения. Я пока не понимаю, как именно это должно происходить. То есть у меня имеется порождающий полином 14-й степени, нахождение его корней "в лоб", обычной арифметикой, даёт мне 14 комплексных корней. Я подозреваю, что такое решение не есть правильное, и необходимо использовать полиноминальную арифметику. Но каким образом это сделать я пока не знаю.
Попутно задам ещё один вопрос: подскажите, как связаны между собой компоненты синдрома, о которых говорилось выше, и синдромный полином?

[des00]

отсутствие уверенности в том, что там именно нужный мне алгоритм

угу, а если учесть что обе эти функции ссылаются на функцию из файла berlekamp.m, то да, действительно никакой уверенности нет %)))

[des00]

Уважаемые гуру, подскажите что не так делаю.

Решил проверить работу декодера БЧХ со стираниям. Взял алгоритм из Скляра :
1. заместить стирания нулями
2. заместить стирания единицам
3. декодировать оба и выбрать то слово, которое соответствует наименьшему числу ошибок, исправленных вне позиций стирания.

Кол-во исправляемых стираний определяется по формуле p <= d-1. Набросал в матлабе простой пример. взял код {255, 131, 18}, с dmin = 37. Но не вижу исправления 36 стираний %(

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

Спасибо.

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

 

Прикрепленные файлы

 bch_era.zip ( 4.57 килобайт ) Кол-во скачиваний: 27

 

[Gold777]

То, что я написал, основано именно на книге Морелоса-Сарагосы и статье С.В. Фёдорова о реализации БМ-алгоритма для РС-кодов на ПЛИС. Компоненты синдромов вычисляются путём подстановки корней порождающего полинома в полином принятого сообщения. Я пока не понимаю, как именно это должно происходить. То есть у меня имеется порождающий полином 14-й степени, нахождение его корней "в лоб", обычной арифметикой, даёт мне 14 комплексных корней. Я подозреваю, что такое решение не есть правильное, и необходимо использовать полиноминальную арифметику. Но каким образом это сделать я пока не знаю.
Попутно задам ещё один вопрос: подскажите, как связаны между собой компоненты синдрома, о которых говорилось выше, и синдромный полином?

Необходимо использовать арифметику в поле Галуа. Для реализации в ПЛИС вам синдромный полином не нужен, нужны компоненты синдрома, которые потом используются в алгоритме для нахождения коэффициентов полинома локаторов ошибок. Разберитесь для начала как находятся компоненты синдрома и с арифметикой в поле Галуа, а потом уже к алгоритму переходите. Хорошо написано это в статье Рахман П.А. Основы защиты данных от разрушения. Коды Рида-Соломона.

[mad_physicist]

Необходимо использовать арифметику в поле Галуа. Для реализации в ПЛИС вам синдромный полином не нужен, нужны компоненты синдрома, которые потом используются в алгоритме для нахождения коэффициентов полинома локаторов ошибок. Разберитесь для начала как находятся компоненты синдрома и с арифметикой в поле Галуа, а потом уже к алгоритму переходите. Хорошо написано это в статье Рахман П.А. Основы защиты данных от разрушения. Коды Рида-Соломона.

Спасибо, обязательно воспользуюсь Вашими рекомендациями

[x736C]

Кол-во исправляемых стираний определяется по формуле p <= d-1. Набросал в матлабе простой пример. взял код {255, 131, 18}, с dmin = 37. Но не вижу исправления 36 стираний %(

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

Не смог разобраться с системой накопления статистики. Смысл графика также не очень ясен. И к своему стыду не понял, что имеется в виду под spike.
У меня была более простая моделька (так сказать, показательно-учебная), но идентичная по сути. Ваш пример «хавает», исправляя 36 стираний при нуле ошибок.
Кол-во исправляемых стираний + ошибок, действительно, по формуле 2b + u < d, где b — кол. битовых ошибок, u — количество стираний.

 bch_with_erasures.zip ( 1.39 килобайт ) Кол-во скачиваний: 101

Если, конечно, актуально.

[des00]

Не смог разобраться с системой накопления статистики. Смысл графика также не очень ясен. И к своему стыду не понял, что имеется в виду под spike.

spike - импульсная ошибка, моделирую канал с импульсными ошибками, при наличии 100% ой схемы их обнаружений. статистика - кол-во выбитых бит на блок и итоговый бер

У меня была более простая моделька (так сказать, показательно-учебная), но идентичная по сути. Ваш пример «хавает», исправляя 36 стираний при нуле ошибок.
Кол-во исправляемых стираний + ошибок, действительно, по формуле 2b + u < d, где b — кол. битовых ошибок, u — количество стираний.

 bch_with_erasures.zip ( 1.39 килобайт ) Кол-во скачиваний: 101

Если, конечно, актуально.

конечно актуально, а то судя по молчанию гуру, у меня появилось подозрение что вопрос мега ламерский и я туплю сильно %)

правда тему я пока немного оставил, другим занялся. Спасибо что ответили, скоро обновлю выложенный бчх декодер версией со стираниями %) и в турбокоды нырну

[SKov]

в турбокоды нырну

Лучше ныряйте в LDPC.