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.^[1] Reeds e Sloane oferecem uma extensão para lidar com um anel.^[2]

Elwyn Berlekamp inventou um algoritmo para decodificar códigos Bose-Chaudhuri-Hocquenghem (BCH).^[3][4] James Massey reconheceu sua aplicação em registradores de deslocamento com retroalimentação linear e simplificou o algoritmo.^[5][6] Massey denominou o algoritmo de Algoritmo de Síntese LFSR (Algoritmo Iterativo de Berlekamp),^[7] mas atualmente ele é conhecido como 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 ${\displaystyle \Lambda _{j}}$ de um polinômio ${\displaystyle \Lambda (x)}$ de modo que, para todas as posições ${\displaystyle i}$ em um fluxo de entrada ${\displaystyle S}$:

${\displaystyle S_{i+\nu }+\Lambda _{1}S_{i+\nu -1}+\cdots +\Lambda _{\nu -1}S_{i+1}+\Lambda _{\nu }S_{i}=0.}$

Nos exemplos de código abaixo, ${\displaystyle C(x)}$ é uma instância potencial de ${\displaystyle \Lambda (x)}$. O polinômio localizador de erros ${\displaystyle C(x)}$ para ${\displaystyle L}$ erros é definido como:

${\displaystyle C(x)=C_{L}x^{L}+C_{L-1}x^{L-1}+\cdots +C_{2}x^{2}+C_{1}x+1}$

ou invertido:

${\displaystyle C(x)=1+C_{1}x+C_{2}x^{2}+\cdots +C_{L-1}x^{L-1}+C_{L}x^{L}.}$

O objetivo do algoritmo é determinar o grau mínimo ${\displaystyle L}$ e o polinômio ${\displaystyle C(x)}$ que resultam em todas as síndromes

${\displaystyle S_{n}+C_{1}S_{n-1}+\cdots +C_{L}S_{n-L}}$

sendo iguais a ${\displaystyle 0}$:

${\displaystyle S_{n}+C_{1}S_{n-1}+\cdots +C_{L}S_{n-L}=0,\qquad L\leq n\leq N-1.}$

Algoritmo: ${\displaystyle C(x)}$ é inicializado com ${\displaystyle 1}$, ${\displaystyle L}$ é o número atual de erros assumidos e é inicializado com zero. ${\displaystyle N}$ é o número total de síndromes. ${\displaystyle n}$ é usado como o iterador principal e para indexar as síndromes de ${\displaystyle 0}$ a ${\displaystyle N-1}$. ${\displaystyle B(x)}$ é uma cópia do último ${\displaystyle C(x)}$ desde a última vez que ${\displaystyle L}$ foi atualizado, sendo inicializado com ${\displaystyle 1}$. ${\displaystyle b}$ é uma cópia da última discrepância ${\displaystyle d}$ (explicada abaixo) desde a última vez que ${\displaystyle L}$ foi atualizado e inicializada com ${\displaystyle 1}$. ${\displaystyle m}$ é o número de iterações desde que ${\displaystyle L}$, ${\displaystyle B(x)}$ e ${\displaystyle b}$ foram atualizados e é inicializado com ${\displaystyle 1}$.

Cada iteração do algoritmo calcula uma discrepância ${\displaystyle d}$. Na iteração ${\displaystyle k}$ isso seria:

${\displaystyle d\gets S_{k}+C_{1}S_{k-1}+\cdots +C_{L}S_{k-L}.}$

Se ${\displaystyle d}$ for zero, o algoritmo assume que ${\displaystyle C(x)}$ e ${\displaystyle L}$ estão corretos para o momento, incrementa ${\displaystyle m}$ e continua.

Se ${\displaystyle d}$ não for zero, o algoritmo ajusta ${\displaystyle C(x)}$ de modo que um recálculo de ${\displaystyle d}$ resulte em zero:

${\displaystyle C(x)\gets C(x)-(d/b)x^{m}B(x).}$

O termo ${\displaystyle x^{m}}$ *desloca* ${\displaystyle B(x)}$ para que ele siga as síndromes correspondentes a ${\displaystyle b}$. Se a atualização anterior de ${\displaystyle L}$ ocorreu na iteração ${\displaystyle j}$, então ${\displaystyle m=k-j}$, e uma discrepância recalculada seria:

${\displaystyle d\gets S_{k}+C_{1}S_{k-1}+\cdots -(d/b)(S_{j}+B_{1}S_{j-1}+\cdots ).}$

Isso mudaria a discrepância recalculada para:

${\displaystyle d=d-(d/b)b=d-d=0.}$

O algoritmo também precisa aumentar ${\displaystyle L}$ (número de erros) conforme a necessidade. Se ${\displaystyle L}$ 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 ${\displaystyle n}$ se torne maior ou igual a ${\displaystyle 2L}$. Caso contrário, ${\displaystyle L}$ é atualizado e o algoritmo atualizará ${\displaystyle B(x)}$, ${\displaystyle b}$, aumentará ${\displaystyle L}$ e redefinirá ${\displaystyle m=1}$. A fórmula ${\displaystyle L=(n+1-L)}$ limita ${\displaystyle L}$ ao número de síndromes disponíveis utilizadas para calcular as discrepâncias, e também lida com o caso em que ${\displaystyle L}$ aumenta em mais de ${\displaystyle 1}$.

O algoritmo de Massey (1969, p. 124) 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 ${\displaystyle GF(2)}$, a discrepância ${\displaystyle d}$ 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;
        }
    /* ... */

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

• Hazewinkel, Michiel, ed. (2001), «Berlekamp-Massey algorithm», Enciclopédia de Matemática, ISBN 978-1-55608-010-4 (em inglês), Springer 
• Predefinição:PlanetMath
• Weisstein, Eric W. «Algoritmo de Berlekamp-Massey». MathWorld (em inglês) 
• Implementação de GF(2) em Mathematica
• (em alemão) Applet do Algoritmo de Berlekamp-Massey
• Calculadora Online de Berlekamp-Massey para GF(2)