next up previous contents
Siguiente: Método PGZ Arriba: Códigos cíclicos Anterior: Códigos RS: Como códigos

Decodificación de Reed-Solomon

Sea $q$ una potencia de un número primo y sea $k\leq q-1$. Supongamos que para una palabra $\sigma\in\mathbb{F}_q^k$, su código correspondiente a $\mbox{\rm RS}(q-1,k)$ es $f(X) = \sum_{\lambda=0}^{q-2} f_{\lambda} X^{\lambda}\in\mathbb{F}_q[X]$, pero que, al ser transmitido, el destinatario hubiera recibido $h(X) = \sum_{\lambda=0}^{q-2} h_{\lambda} X^{\lambda}$. El propósito de la decodificación es recuperar $f(X)$ a partir de $h(X)$ o, en otras palabras, calcular el error $e(X)=h(X)-f(X)$. Naturalmente, la recuperación de $\sigma$ a partir de $f(X)$ se hace dividiendo a este último entre el polinomio $g_{q-1,k}(X)$.

Para cada $\kappa\in[\![1,q-1-k]\!]$ denotemos por $s_{\kappa}$ al síndrome $s_{\kappa} = e(a^{\kappa}) = h(a^{\kappa})$ (pues $f(a^{\kappa})=0$).

Inicialmente, consideremos el caso $k=1$.

Supongamos que el error entre $h(X)$ y $f(X)$ ocurre solamente en un ``byte'', es decir, en un solo coeficiente, digamos $h_{\lambda}$. Entonces los síndromes han de satisfacer $s_1=e_{\lambda}a^{\lambda}$ y $s_2=e_{\lambda}a^{2\lambda}$. Por tanto $a^{\lambda} = \frac{s_2}{s_1}$ y, en consecuencia, $e_{\lambda} = \frac{s_1^2}{s_2}$. Así pues:

Decodificación de Reed-Solomon para $k=1$. Si sólo hay un error en un solo coeficiente, la posición en la que ocurre es $\lambda = \log_a\left(\frac{s_2}{s_1}\right)$ y el coeficiente del error ahí es $e_{\lambda} = \frac{s_1^2}{s_2}$.

Para $k>1$, sea $E\subset[\![0,q-2]\!]$ el conjunto de índices $\lambda$ tales que $e_{\lambda} \not= 0$. Entonces se tiene el sistema de ecuaciones lineales:

\begin{displaymath}
\forall\kappa\in[\![0,q-1-k]\!]:\ \ s_{\kappa} = \sum_{\lambda\in E} e_{\lambda}a^{\kappa\lambda}
\end{displaymath} (27)

con soluciones únicas siempre que $2\,\mbox{\rm card}\,(E)\leq q-1-k$. Sin embargo éste no determina al conjunto de índices $E$.

Para determinarlo es necesaria una labor suplementaria. Se define el polinomio localizador de errores como

\begin{displaymath}
\rho(X) = \prod_{\lambda\in E} (X-a^{-\lambda}).
\end{displaymath} (28)

el cual es un polinomio mónico. Entonces las raíces de $\rho(X)$ son precisamente las potencias $a^{-\lambda}$ con $\lambda\in E$. También se define el polinomio evaluador de errores como
\begin{displaymath}
\omega(X) = \sum_{\lambda\in E} e_{\lambda} \prod_{\ell\in E-\{\lambda\}} (X-a^{-\ell}).
\end{displaymath} (29)

Se tiene $\mbox{\rm grd}\,(\rho(X)) = \mbox{\rm card}\,(E)$ y $\mbox{\rm grd}\,(\omega(X)) = \mbox{\rm card}\,(E)-1$. Se supondrá $2\,\mbox{\rm card}\,(E)\leq q-1-k$.

Proposición 8.4   Los polinomios $\rho(X)$ y $\omega(X)$ son primos relativos y
\begin{displaymath}
\forall\lambda\in E:\ e_{\lambda} = \frac{\omega(a^{-\lambda})}{\rho'(a^{-\lambda})},
\end{displaymath} (30)

donde $\rho'(X)$ es la derivada formal del polinomio $\rho(X)$.

En efecto, para lo primero observamos que $\rho(X)$ y $\omega(X)$ no pueden tener raíces comunes:

\begin{eqnarray*}
\rho(x) = 0 &\Longrightarrow& x = a^{-\lambda}\ \mbox{ para al...
... a^{-\ell}) \\
&\Longrightarrow& \omega(a^{-\lambda}) \not= 0.
\end{eqnarray*}

Para lo segundo, por la fórmula de Leibniz, la derivada formal de $\rho(X)$ es

\begin{displaymath}\rho'(X) = \sum_{\lambda\in E} \prod_{\ell\in E-\{\lambda\}} (X-a^{-\ell})\end{displaymath}

y por tanto $\rho'(a^{-\lambda}) = \prod_{\ell\in E-\{\lambda\}} (a^{-\lambda} - a^{-\ell})$. Así resulta la expresión (30). $\Box$


Si se determinara el polinomio localizador de errores $\rho(X)$ entonces sus raíces determinan a su vez el conjunto $E$. Consideremos un tercer polinomio, llamado de síndromes, pues éstos son sus coeficientes:

\begin{displaymath}\sigma(X) = s_1 + s_2X + \cdots + s_{q-1-k}X^{q-2-k} = \sum_{\kappa=0}^{q-2-k}s_{\kappa+1}X^{\kappa}.\end{displaymath}

Proposición 8.5   Existe un polinomio $\mu(X)\in\mathbb{F}_q[X]$ tal que se cumple la ecuación clave:
\begin{displaymath}
\rho(X) \sigma(X) = \mu(X)\,X^{q-1-k} - \omega(X).
\end{displaymath} (31)

O equivalentemente:

\begin{displaymath}\rho(X) \sigma(X) = - \omega(X) \bmod X^{q-1-k}. \end{displaymath}

En efecto, un cálculo directo da:

$\displaystyle \sigma(X)$ $\textstyle =$ $\displaystyle \sum_{\kappa=0}^{q-2-k}\,e(a^{\kappa+1})\,X^{\kappa}$  
  $\textstyle =$ $\displaystyle \sum_{\kappa=0}^{q-2-k}\left[\sum_{\lambda\in E}e_{\lambda}a^{(\kappa+1)\lambda}\right]X^{\kappa}$  
  $\textstyle =$ $\displaystyle \sum_{\lambda\in E}e_{\lambda}a^{\lambda}\left[\sum_{\kappa=0}^{q-2-k}\left(a^{\lambda}X\right)^{\kappa}\right]$  
  $\textstyle =$ $\displaystyle \sum_{\lambda\in E}e_{\lambda}\left[\frac{\left(a^{\lambda}X\right)^{q-1-k}-1}{X-a^{-\lambda}}\right] ,%\\
$ (32)

de donde

\begin{eqnarray*}
\rho(X) \sigma(X) &=& \sum_{\lambda\in E} e_{\lambda}\left[\le...
...l}) \right] - \omega(X) \\
&=& X^{q-1-k}\,\mu(X) - \omega(X) .
\end{eqnarray*}

$\Box$


Así pues, para decodificar, habiendo calculado el polinomio de síndromes $\sigma(X)$, se ha de determinar a los polinomios localizador y evaluador de errores $\rho(X)$ y $\omega(X)$ de manera que se cumpla la ecuación clave (31).



Subsections
next up previous contents
Siguiente: Método PGZ Arriba: Códigos cíclicos Anterior: Códigos RS: Como códigos
Guillermo M. Luna
2010-05-09