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 $m_{1}, \dots, 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}, \dots, a_{k}$ y luego $F (a_{i})$ es aplicado a $a_{k + 1}, \dots, a_{n}$ para crear una palabra de código codificada $c_{1}, \dots, c_{n}$ .^[3]^[4]

El objetivo del decodificador es recuperar el polinomio de codificación original $F (a_{i})$ , utilizando las entradas conocidas $a_{1}, \dots, a_{n}$ y recibida la palabra en clave $b_{1}, \dots, 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.^[5]^[6]

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} + \dots + e_{e} a_{i}^{e}) - (q_{0} + q_{1} a_{i} + q_{2} a_{i}^{2} + \dots + 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} + \dots + e_{e - 1} a_{i}^{e - 1}) - (q_{0} + q_{1} a_{i} + q_{2} a_{i}^{2} + \dots + 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:

[\begin{matrix} 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{matrix}] [\begin{matrix} e_{0} \\ e_{1} \\ q 0 \\ q 1 \\ q 2 \\ q 3 \\ q 4 \end{matrix}] = [\begin{matrix} - 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{matrix}]

[\begin{matrix} 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{matrix}] [\begin{matrix} e_{0} \\ e_{1} \\ q 0 \\ q 1 \\ q 2 \\ q 3 \\ q 4 \end{matrix}] = [\begin{matrix} 0 \\ 2 \\ 2 \\ 2 \\ 1 \\ 6 \\ 5 \end{matrix}]

[\begin{matrix} 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{matrix}] [\begin{matrix} e_{0} \\ e_{1} \\ q 0 \\ q 1 \\ q 2 \\ q 3 \\ q 4 \end{matrix}] = [\begin{matrix} 4 \\ 2 \\ 4 \\ 3 \\ 3 \\ 1 \\ 3 \end{matrix}]

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

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

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

$F (a_{i}) = Q (a_{i}) / E (a_{i}) = 3 x^{2} + 2 x + 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

Plantilla:Listaref

Enlaces externos

Plantilla:Control de autoridades

[1] Plantilla:Obra citada

[2] Plantilla:Cita web

[3] Plantilla:Cita web

[4] Plantilla:Cita libro

[5] Plantilla:Cita web

[6] Plantilla:Cita publicación

[1]

[2]

[3]

[4]

[5]

[6]

Algoritmo de Berlekamp-Welch

Sumario

Ecuaciones clave

Ejemplo

Véase también

Referencias

Enlaces externos

Menú de navegación

Algoritmo de Berlekamp-Welch

Ecuaciones clave

Ejemplo

Véase también

Referencias

Enlaces externos

Menú de navegación

Buscar