El algoritmo de Berlekamp-Welch , también conocido como el algoritmo de Welch-Berlekamp , lleva el nombre de Elwyn R. Berlekamp y Lloyd R. Welch . 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 polinomiode grado < k para entradas y entonces es aplicado a para crear una palabra de código codificada .
El objetivo del decodificador es recuperar el polinomio de codificación original , utilizando las entradas conocidas y recibió la palabra en clave con posibles errores. También calcula un polinomio de error dónde correspondiente a errores en la palabra de código recibida.
Definiendo e = número de errores, el conjunto clave de n ecuaciones es
Donde E ( a i ) = 0 para los casos e cuando b i ≠ F (a i ), y E (a i ) ≠ 0 para los casos n - e sin error donde b i = F ( a i ). 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 (a i ) = e e = 1, el resultado conducirá a un conjunto de ecuaciones que se pueden resolver con álgebra lineal.
donde q = n - e - 1. Dado que e e 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 ( a i ) se calculan para las ubicaciones donde E ( a i ) = 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: a i = 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}. Comience con e = 2 y resuelva las ecuaciones lineales:
Comenzando desde la parte inferior de la matriz derecha, y la restricción e 2 = 1:
con resto = 0.
E ( a i ) = 0 en a 2 = 1 y a 5 = 4 Calcule F ( a 2 = 1) = 6 y F ( a 5 = 4) = 1 para producir la palabra de código corregida {1,6,3,6 , 1,2,2}.