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

El objetivo del decodificador es recuperar el polinomio de codificación original ${\displaystyle F(a_{i})}$, utilizando las entradas conocidas ${\displaystyle a_{1},\cdots ,a_{n}}$ y recibida la palabra en clave ${\displaystyle b_{1},\cdots ,b_{n}}$ con posibles errores. También calcula un error polinomial ${\displaystyle E(a_{i})}$ donde ${\displaystyle E(a_{i})=0}$ corresponde a errores en la palabra de código recibida.^[5]​^[6]​

Ecuaciones clave

Definiendo e = número de errores, el conjunto clave de n ecuaciones es

${\displaystyle 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 ():

${\displaystyle 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.

${\displaystyle b_{i}E(a_{i})=Q(a_{i})}$ 

${\displaystyle b_{i}E(a_{i})-Q(a_{i})=0}$ 

${\displaystyle 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:

${\displaystyle 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 x + 1, y aplicando F (a _i ) para un ₄ = 3 a un ₇ = 6, da como resultado la palabra de código {1,6,3,6, 1,2,2}. Suponga que ocurren errores en c ₂ y c ₅ 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:

${\displaystyle {\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}}}$ 

${\displaystyle {\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}}}$ 

${\displaystyle {\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₂ = 1:

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

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

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

E(a_i) = 0 en a₂ = 1 y a₅ = 4 Calcula F(a₂ = 1) = 6 y F(a₅ = 4) = 1 para producir la palabra de código corregida {1,6,3,6,1,2,2}.

Véase también

• Reed–Solomon

Referencias

1. Error correction for algebraic block codes (en inglés), 27 de septiembre de 1983, consultado el 28 de marzo de 2021 .
2. «Algebraic Codes on Lines, Planes, and Curves | Communications, information theory and signal processing». Cambridge University Press (en inglés). Consultado el 28 de marzo de 2021. 
3. «US4633470A - Error correction for algebraic block codes». worldwide.espacenet.com. Consultado el 28 de marzo de 2021. 
4. Berlekamp, Elwyn R. (1984). Algebraic coding theory (Rev. ed edición). Aegean Park Press. ISBN 0-89412-063-8. OCLC 10787423. Consultado el 28 de marzo de 2021. 
5. «A simple algorithm for decoding Reed-Solomon codes and its relation to the Welch-Berlekamp algorithm». 
6. Koetter, R.; Vardy, A. (2003-11). «Algebraic soft-decision decoding of Reed-Solomon codes». IEEE Transactions on Information Theory 49 (11): 2809-2825. ISSN 1557-9654. doi:10.1109/TIT.2003.819332. Consultado el 28 de marzo de 2021. 

Enlaces externos

• MIT Lecture Notes on Essential Coding Theory – Dr. Madhu Sudan