direita|miniaturadaimagem|Algoritmo de Berlekamp-Massey O algoritmo de Berlekamp-Massey é um algoritmo que encontra o menor registrador de deslocamento com retroalimentação linear (LFSR, do inglês *Linear-Feedback Shift Register*) para uma dada sequência binária de saída. O algoritmo também encontra o polinômio mínimo de uma sequência linearmente recorrente em um corpo arbitrário. O requisito de ser um corpo significa que o algoritmo de Berlekamp-Massey exige que todos os elementos não nulos possuam um inverso multiplicativo. Reeds e Sloane oferecem uma extensão para lidar com um anel.

Elwyn Berlekamp inventou um algoritmo para decodificar códigos Bose-Chaudhuri-Hocquenghem (BCH).. Editora anterior McGraw-Hill, Nova York, NY. James Massey reconheceu sua aplicação em registradores de deslocamento com retroalimentação linear e simplificou o algoritmo. Massey denominou o algoritmo de Algoritmo de Síntese LFSR (Algoritmo Iterativo de Berlekamp), mas atualmente ele é conhecido como algoritmo de Berlekamp-Massey.

Descrição do algoritmo 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 de um polinômio de modo que, para todas as posições em um fluxo de entrada :

Nos exemplos de código abaixo, é uma instância potencial de . O polinômio localizador de erros para erros é definido como:

ou invertido:

O objetivo do algoritmo é determinar o grau mínimo e o polinômio que resultam em todas as síndromes

sendo iguais a :

Algoritmo: é inicializado com , é o número atual de erros assumidos e é inicializado com zero. é o número total de síndromes. é usado como o iterador principal e para indexar as síndromes de a . é uma cópia do último desde a última vez que foi atualizado, sendo inicializado com . é uma cópia da última discrepância (explicada abaixo) desde a última vez que foi atualizado e inicializada com . é o número de iterações desde que , e foram atualizados e é inicializado com .

Cada iteração do algoritmo calcula uma discrepância . Na iteração isso seria:

Se for zero, o algoritmo assume que e estão corretos para o momento, incrementa e continua.

Se não for zero, o algoritmo ajusta de modo que um recálculo de resulte em zero:

O termo *desloca* para que ele siga as síndromes correspondentes a . Se a atualização anterior de ocorreu na iteração , então , e uma discrepância recalculada seria:

Isso mudaria a discrepância recalculada para:

O algoritmo também precisa aumentar (número de erros) conforme a necessidade. Se for igual ao número real de erros, então durante o processo de iteração, as discrepâncias se tornarão zero antes que se torne maior ou igual a . Caso contrário, é atualizado e o algoritmo atualizará , , aumentará e redefinirá . A fórmula limita ao número de síndromes disponíveis utilizadas para calcular as discrepâncias, e também lida com o caso em que aumenta em mais de .

Pseudocódigo O algoritmo de para um corpo arbitrário: polinomio(corpo K) s(x) = ... /* coeficientes sao s_j; sequencia de saida como um polinomio de grau N-1 */ /* polinomio de conexao */ polinomio(corpo K) C(x) = 1; /* coeficientes sao c_j */ polinomio(corpo K) B(x) = 1; int L = 0; int m = 1; corpo K b = 1; int n;

/* passos 2 e 6 */ for (n = 0; n < N; n++) { /* passo 2. calcular discrepancia */ corpo K d = s_n + \sum_{i=1}^L c_i s_{n - i}; // Representação teórica do somatório

if (d == 0) { /* passo 3. discrepancia eh zero; a anulacao continua */ m = m + 1; } else if (2 * L <= n) { /* passo 5. */ /* copia temporaria de C(x) */ polinomio(corpo K) T(x) = C(x);

C(x) = C(x) - d * b^-1 * x^m * B(x); L = n + 1 - L; B(x) = T(x); b = d; m = 1; } else { /* passo 4. */ C(x) = C(x) - d * b^-1 * x^m * B(x); m = m + 1;

return L;No caso de um código BCH binário em , a discrepância será zero em todos os passos ímpares, portanto uma verificação pode ser adicionada para evitar o seu cálculo. /* ... */ for (n = 0; n < N; n++) { /* se o passo for impar, discrepancia == 0, sem necessidade de calcular */ if ((n & 1) != 0) { m = m + 1; continue;

/* ... */

Ver também

Correção de erros Reed-Solomon Algoritmo de Reeds-Sloane, uma extensão para sequências sobre inteiros mod Registrador de deslocamento com retroalimentação não-linear (NLFSR)

Ligações externas

Implementação de GF(2) em Mathematica Applet do Algoritmo de Berlekamp-Massey Calculadora Online de Berlekamp-Massey para GF(2)