Algoritmo de Berlekamp-Welch

Algoritmo de corrección de errores

El algoritmo Berlekamp–Welch , también conocido como algoritmo Welch–Berlekamp , ​​debe su nombre a Elwyn R. Berlekamp y Lloyd R. Welch . Se trata de un algoritmo decodificador que corrige de forma eficiente los errores en los códigos Reed–Solomon para un código RS( n , k ), basado en la visión original de Reed Solomon, donde un mensaje se utiliza como coeficiente de un polinomio o se utiliza con interpolación de Lagrange para generar el polinomio de grado < k para las entradas y luego se aplica para crear una palabra de código codificada . ${\displaystyle m_{1},\cdots ,m_{k}}$ ${\displaystyle F(a_{i})}$ ${\displaystyle F(a_{i})}$ ${\displaystyle a_{1},\cdots ,a_{k}}$ ${\displaystyle F(a_{i})}$ ${\displaystyle a_{k+1},\cdots ,a_{n}}$ ${\displaystyle c_{1},\cdots ,c_{n}}$

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

Las 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 n - e casos sin error donde b _i = F( a _i ) . Estas ecuaciones no se pueden resolver directamente, pero definiendo Q() como el producto de E() y F():

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

y añadiendo 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 pueden resolverse 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. Como 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 pueden resolverse usando álgebra lineal, con complejidad temporal . ${\displaystyle O(n^{3})}$

El algoritmo comienza suponiendo que el número máximo de errores es 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 puedan resolver o e se reduzca a 0, lo que indica que no hay errores. Si Q()/E() tiene un resto = 0, entonces F() = Q()/E() y los valores de las palabras 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

Consideremos 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 va a codificar sistemáticamente es {1,6,3}. Utilizando la interpolación de Lagrange, F(a _i ) = 3 x ² + 2 x + 1, y aplicando F(a _i ) para a ₄ = 3 a a ₇ = 6, se obtiene la palabra de código {1,6,3,6,1,2,2}. Supongamos que se producen errores en c ₂ y c _5, lo que da como resultado la palabra de código recibida {1,5,3,6,3,2,2}. Empecemos con e = 2 y resolvamos 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 Calcule 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

• Corrección de errores de Reed-Solomon

Enlaces externos

• Notas de la conferencia del MIT sobre teoría de codificación esencial: Dra. Madhu Sudan
• Notas de la conferencia sobre teoría de la codificación de la Universidad de Buffalo: Dr. Atri Rudra
• Códigos algebraicos sobre líneas, planos y curvas: un enfoque de ingeniería – Richard E. Blahut
• Descodificación de códigos Reed-Solomon por Welch Berlekamp – LR Welch
• US 4,633,470, Welch, Lloyd R. & Berlekamp, ​​Elwyn R. , "Error Correction for Algebraic Block Codes", publicada el 27 de septiembre de 1983, emitida el 30 de diciembre de 1986  – La patente de Lloyd R. Welch y Elewyn R. Berlekamp