El algoritmo de Berlekamp-Welch, también conocido como el algoritmo de Welch-Berlekamp, lleva el nombre de Elwyn R. Berlekamp y Lloyd R.
[1][2] Este es un algoritmo decodificador que corrige de manera eficiente los errores en los códigos Reed-Solomon para un código RS (n, k), basado en la vista original de Reed Solomon donde un mensaje
se utiliza como coeficientes de un polinomio
o se utiliza con la interpolación de Lagrange para generar el polinomio
de grado < k para entradas
para crear una palabra de código codificada
[3][4] El objetivo del decodificador es recuperar el polinomio de codificación original
, utilizando las entradas conocidas
y recibida la palabra en clave
con posibles errores.
También calcula un error polinomial
corresponde a errores en la palabra de código recibida.
[5][6] Definiendo e = número de errores, el conjunto clave de n ecuaciones es Donde E(ai) = 0 para los casos e cuando bi ≠ F (ai), y E (ai) ≠ 0 para los casos n-e sin error donde bi = F(ai).
Estas ecuaciones no se pueden resolver directamente, sino definiendo Q () como el producto de E () y F (): y agregando la restricción de que el coeficiente más significativo de E (ai) = ee = 1, el resultado conducirá a un conjunto de ecuaciones que se pueden resolver con álgebra lineal.
donde q = n - e - 1.
Dado que ee está restringido a ser 1, las ecuaciones se convierten en: resultando en un conjunto de ecuaciones que se pueden resolver usando álgebra lineal, con complejidad de tiempo O (n ^ 3).
El algoritmo comienza asumiendo el número máximo de errores e = ⌊(n-k)/2⌋.
Si las ecuaciones no se pueden resolver (debido a la redundancia), e se reduce en 1 y el proceso se repite, hasta que las ecuaciones se pueden resolver o e se reduce a 0, lo que indica que no hay errores.
Si Q () / E () tiene resto = 0, entonces F() = Q()/E() y los valores de la palabra de código F (ai) se calculan para las ubicaciones donde E(ai) = 0 para recuperar la palabra de código original.
Si el resto ≠ 0, entonces se ha detectado un error incorregible.
Considere RS (7,3) (n=7 k=3) definido en GF (7) con α = 3 y valores de entrada: ai = i-1: {0,1,2,3,4,5, 6}.
El mensaje que se codificará sistemáticamente es {1,6,3}.
Usando la interpolación de Lagrange, F (a i ) = 3 x 2 + 2 x + 1, y aplicando F (a i ) para un 4 = 3 a un 7 = 6, da como resultado la palabra de código {1,6,3,6, 1,2,2}.
Suponga que ocurren errores en c 2 y c 5 que dan como resultado la palabra de código recibida {1,5,3,6,3,2,2}.
Comienza con e = 2 y resuelve las ecuaciones lineales:
Comenzando desde la parte inferior de la matriz derecha, y la restricción e2 = 1:
E(ai) = 0 en a2 = 1 y a5 = 4 Calcula F(a2 = 1) = 6 y F(a5 = 4) = 1 para producir la palabra de código corregida {1,6,3,6,1,2,2}.