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 polinomio de grado < k para entradas y luego 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 recibida la palabra en clave con posibles errores. También calcula un error polinomial donde corresponde a errores en la palabra de código recibida.

Ecuaciones clave

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.

Ejemplo

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:

con resto = 0.

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}.

Véase también Reed–Solomon

Referencias

Enlaces externos MIT Lecture Notes on Essential Coding Theory – Dr. Madhu Sudan University at Buffalo Lecture Notes on Coding Theory – Dr. Atri Rudra

Categoría:Teoría de códigos Categoría:Teoría de la información Categoría:Detección y corrección de errores