Алгоритм Берлекампа-Мэсси не работает для наименее значимого символа синдрома 0

Алгоритм Берлекампа-Месси

Я пытаюсь реализовать этот алгоритм на картинке выше. Алгоритм Берлекампа-Масси решает следующую задачу в RS(n,k) Система: с учетом синдрома полинома

S(z) = {S(nk-1),........S(2),S(1),S(0)}

Находит наименьшую степень Погрешность полинома. Этот алгоритм работает хорошо для всех синдромов, но когда S (0) становится 0, многочлен ошибки является неправильным. Что-то не хватает в упомянутом алгоритме??

Источник

1 ответ

Решение

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

Я не уверен, что вы действительно имеете в виду S(0) в своем вопросе. В большинстве статей S(j) определяется как сумма элементов, умноженных на последующие степени (местоположения) (alpha^j). Важно, чтобы синдромы, используемые декодером, основывались на корнях полинома генератора, если первый последовательный корень = FCR = альфа ^0 = 1 (г (х) = (х-1)(х-альфа) (х -альфа ^2)...), используйте S(0) - S (nk-1), или если FCR = альфа (г (х) = (х-альфа) (х-альфа ^ 2)...) используйте S(1) - S (nk).

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

Статья в вики имеет более простое описание алгоритма с примером кода. Обратите внимание, что для представления полинома локатора ошибок используется лямбда (Λ) вместо сигмы (σ). Описание приведено для примера кода, и в этом случае S[0] может означать S(0) или S(1), в зависимости от FCR (который не упоминается).

https://en.wikipedia.org/wiki/Berlekamp%E2%80%93Massey_algorithm

Я также написал интерактивные программы RS для 4-битных и 8-битных полей, которые включают Berlekamp Massey в качестве одного из трех декодеров, реализованных в программах. Программы позволяют пользователю указывать FCR как 1 или 2, если не выбран самовзаимный полином (непопулярная опция, используемая для упрощения аппаратных кодеров). В этих примерах программ полиномы обычно хранятся вначале наиболее значимым термином (устаревшая проблема), поэтому код сдвигает массивы, чтобы справиться с этим.

http://rcgldr.net/misc/eccdemo4.zip

http://rcgldr.net/misc/eccdemo8.zip

Я модифицировал одну из моих демонстрационных программ ecc для работы с GF(2^10). Я провел ваш тестовый пример:

S[...] = {0000 0596 0302 0897}   (S[0] = 0)

Это итерации и полиномы, которые я получаю для декодера BM:

k      d    σ

0   0000    0001
1   0596    0596 x^2 + 0000 x + 0001
2   0302    0596 x^2 + 1006 x + 0001
3   0147    0585 x^2 + 1006 x + 0001

корни это:

383 = 1/(2^526) and 699 = 1/(2^527)

Мелочи, изменяя коэффициенты, вы получаете локаторы вместо их обратных:

 0001 x^2 + 1006 x + 0585 : roots are 346 = 2^256 and 692 = 2^257

Обратите внимание, что Forney нужен необратимый многочлен, если для расчета значений ошибок используется Forney.

Источник
Другие вопросы по тегам