Algoritmo de Berlekamp-Massey

O algoritmo de Berlekamp-Massey é uma alternativa ao decodificador de Peterson para Reed-Solomon na resolução do sistema de equações lineares. Ele pode ser resumido como a busca pelos coeficientes Λ j {\displaystyle \Lambda _{j}} de um polinômio Λ ( x ) {\displaystyle \Lambda (x)} de modo que, para todas as posições i {\displaystyle i} em um fluxo de entrada S {\displaystyle S} : Nos exemplos de código abaixo, C ( x ) {\displaystyle C(x)} é uma instância potencial de Λ ( x ) {\displaystyle \Lambda (x)} . O polinômio localizador de erros C ( x ) {\displaystyle C(x)} para L {\displaystyle L} erros é definido como: O objetivo do algoritmo é determinar o grau mínimo L {\displaystyle L} e o polinômio C ( x ) {\displaystyle C(x)} que resultam em todas as síndromes Algoritmo: C ( x ) {\displaystyle C(x)} é inicializado com 1 {\displaystyle 1} , L {\displaystyle L} é o número atual de erros assumidos e é inicializado com zero. N {\displaystyle N} é o número total de síndromes. n {\displaystyle n} é usado como o iterador principal e para indexar as síndromes de 0 {\displaystyle 0} a N − 1 {\displaystyle N-1} . B ( x ) {\displaystyle B(x)} é uma cópia do último C ( x ) {\displaystyle C(x)} desde a última vez que L {\displaystyle L} foi atualizado, sendo inicializado com 1 {\displaystyle 1} . b {\displaystyle b} é uma cópia da última discrepância d {\displaystyle d} (explicada abaixo) desde a última vez que L {\displaystyle L} foi atualizado e inicializada com 1 {\displaystyle 1} . m {\displaystyle m} é o número de iterações desde que L {\displaystyle L} , B ( x ) {\displaystyle B(x)} e b {\displaystyle b} foram atualizados e é inicializado com 1 {\displaystyle 1} .

O algoritmo de Massey (1969, p. 124) para um corpo arbitrário: No caso de um código BCH binário em G F ( 2 ) {\displaystyle GF(2)} , a discrepância d {\displaystyle d} será zero em todos os passos ímpares, portanto uma verificação pode ser adicionada para evitar o seu cálculo.