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

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

0 голосов
/ 29 октября 2018

Berlekamp-Massey algorithm

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

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

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

1 Ответ

0 голосов
/ 29 октября 2018

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

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

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

...