Algoritmo de Berlekamp-Welch
# Algoritmo de Berlekamp-Welch

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 $m_{1},\cdots ,m_{k}$se utiliza como coeficientes de un polinomio $F(a_{i})$ o se utiliza con la interpolación de Lagrange para generar el polinomio $F(a_{i})$ de grado < k para entradas $a_{1},\cdots ,a_{k}$ y luego $F(a_{i})$ es aplicado a $a_{k+1},\cdots ,a_{n}$ para crear una palabra de código codificada $c_{1},\cdots ,c_{n}$.

El objetivo del decodificador es recuperar el polinomio de codificación original $F(a_{i})$, utilizando las entradas conocidas $a_{1},\cdots ,a_{n}$ y recibida la palabra en clave $b_{1},\cdots ,b_{n}$ con posibles errores. También calcula un error polinomial $E(a_{i})$ donde $E(a_{i})=0$ 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

    $b_{i}E(a_{i})=E(a_{i})F(a_{i})$

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:

    $Q(a_{i})=E(a_{i})F(a_{i})$

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.

    $b_{i}E(a_{i})=Q(a_{i})$
    $b_{i}E(a_{i})-Q(a_{i})=0$
    $b_{i}(e_{0}+e_{1}a_{i}+e_{2}a_{i}^{2}+\cdots +e_{e}a_{i}^{e})-(q_{0}+q_{1}a_{i}+q_{2}a_{i}^{2}+\cdots +q_{q}a_{i}^{q})=0$

donde q = n - e - 1. Dado que $e_e$ está restringido a ser 1, las ecuaciones se convierten en:

    $b_{i}(e_{0}+e_{1}a_{i}+e_{2}a_{i}^{2}+\cdots +e_{e-1}a_{i}^{e-1})-(q_{0}+q_{1}a_{i}+q_{2}a_{i}^{2}+\cdots +q_{q}a_{i}^{q})=-b_{i}a_{i}^{e}$

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.

## Ejemplo

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}. Comienza con e = 2 y resuelve las ecuaciones lineales:

    ${\begin{bmatrix}b_{1}&b_{1}a_{1}&-1&-a_{1}&-a_{1}^{2}&-a_{1}^{3}&-a_{1}^{4}\\b_{2}&b_{2}a_{2}&-1&-a_{2}&-a_{2}^{2}&-a_{2}^{3}&-a_{2}^{4}\\b_{3}&b_{3}a_{3}&-1&-a_{3}&-a_{3}^{2}&-a_{3}^{3}&-a_{3}^{4}\\b_{4}&b_{4}a_{4}&-1&-a_{4}&-a_{4}^{2}&-a_{4}^{3}&-a_{4}^{4}\\b_{5}&b_{5}a_{5}&-1&-a_{5}&-a_{5}^{2}&-a_{5}^{3}&-a_{5}^{4}\\b_{6}&b_{6}a_{6}&-1&-a_{6}&-a_{6}^{2}&-a_{6}^{3}&-a_{6}^{4}\\b_{7}&b_{7}a_{7}&-1&-a_{7}&-a_{7}^{2}&-a_{7}^{3}&-a_{7}^{4}\\\end{bmatrix}}{\begin{bmatrix}e_{0}\\e_{1}\\q0\\q1\\q2\\q3\\q4\\\end{bmatrix}}={\begin{bmatrix}-b_{1}a_{1}^{2}\\-b_{2}a_{2}^{2}\\-b_{3}a_{3}^{2}\\-b_{4}a_{4}^{2}\\-b_{5}a_{5}^{2}\\-b_{6}a_{6}^{2}\\-b_{7}a_{7}^{2}\\\end{bmatrix}}$
    ${\begin{bmatrix}1&0&6&0&0&0&0\\5&5&6&6&6&6&6\\3&6&6&5&3&6&5\\6&4&6&4&5&1&3\\3&5&6&3&5&6&3\\2&3&6&2&3&1&5\\2&5&6&1&6&1&6\\\end{bmatrix}}{\begin{bmatrix}e_{0}\\e_{1}\\q0\\q1\\q2\\q3\\q4\\\end{bmatrix}}={\begin{bmatrix}0\\2\\2\\2\\1\\6\\5\\\end{bmatrix}}$
    ${\begin{bmatrix}1&0&0&0&0&0&0\\0&1&0&0&0&0&0\\0&0&1&0&0&0&0\\0&0&0&1&0&0&0\\0&0&0&0&1&0&0\\0&0&0&0&0&1&0\\0&0&0&0&0&0&1\\\end{bmatrix}}{\begin{bmatrix}e_{0}\\e_{1}\\q0\\q1\\q2\\q3\\q4\\\end{bmatrix}}={\begin{bmatrix}4\\2\\4\\3\\3\\1\\3\\\end{bmatrix}}$

Comenzando desde la parte inferior de la matriz derecha, y la restricción $e_2$ = 1:

$Q(a_{i})=3x^{4}+1x^{3}+3x^{2}+3x+4$

$E(a_{i})=1x^{2}+2x+4$

$F(a_{i})=Q(a_{i})/E(a_{i})=3x^{2}+2x+1$ con resto = 0.

$E(a_i)$ = 0 en $a_2$ = 1 y $a_5$ = 4 Calcula $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}.

