Siguiente: Método de Euclides Arriba: Decodificación de Reed-Solomon Anterior: Decodificación de Reed-Solomon

Método PGZ

Veamos una primera forma de resolver la ecuación clave, mediante el llamado decodificador de Peterson-Gorenstein-Zierler (PGZ).

Supongamos que hubieran ocurrido $m$ errores, con $2m\leq q-1-k$. Escribamos a los polinomios localizador y evaluador de errores como:

$$\begin{eqnarray*} \rho(X) &=& r_0 + r_1 X + \cdots + r_{m-1} X^{m-1} + X^m \\ \omega(X) &=& u_0 + u_1 X + \cdots + u_{m-1} X^{m-1} \end{eqnarray*}$$

El producto $\rho(X) \sigma(X)$ es de grado a lo sumo $m+q-2-k$, pero para $j\in[\![m,q-2-k]\!]$ la ecuación clave implica que el coeficiente correspondiente en ese producto es nulo. Por la manera en la que se multiplica a los polinomios, se ha de tener pues:

$$j\in[\![m,q-2-k]\!]\ \Rightarrow\ \sum_{\ell=0}^mr_{\ell}s_{j+1-\ell} = 0.$$

Puesto que $r_m=1$, se tiene:

$$j\in[\![m,q-2-k]\!]\ \Rightarrow\ \sum_{\ell=0}^{m-1}r_{\ell}s_{j+1-\ell} = -s_{j+1-m}.$$

Estas condiciones plantean, de forma matricial, el sistema de ecuaciones:

$$\left[\begin{array}{lllcl} s_{m+1} & s_{m} & s_{m-1} & \cdot... ...1 \\ s_2 \\ s_3 \\ \vdots \\ s_{q-k-(1+m)} \end{array}\right]$$ (33)

o sea ${\bf S}\cdot{\bf r} = {\bf s}$, donde ${\bf S}\in\mathbb{F}_q^{(q-k-(1+m))\times m}$, ${\bf s}\in\mathbb{F}_q^{q-k-(1+m)}$ y ${\bf r}\in\mathbb{F}_q^m$ es el vector de coeficientes de $\rho(X)$ y hace aquí el papel de incógnita. El sistema (33) está sobredimensionado (hay más condiciones que incógnitas), puede pues resolverse tomando solamente sus primeros $m$ renglones. Queda el sistema:

$$\left[\begin{array}{lllcl} s_{m+1} & s_{m} & s_{m-1} & \cdots & s... ...[\begin{array}{l} r_0 \\ r_1 \\ r_2 \\ \vdots \\ r_{m-1} \end{array}\right] = -\left[\begin{array}{l} s_1 \\ s_2 \\ s_3 \\ \vdots \\ s_{m} \end{array}\right]$$ (34)

$${\bf S}_m\cdot{\bf r} = - {\bf s}_m$$

Como los síndromes son no nulos, y ${\bf S}_m$ es una matriz definida por diagonales, se tiene que es no-singular. Por tanto el polinomio localizador de errores se obtiene como ${\bf r} =- {\bf S}_m^{-1}{\bf s}_m$.

Habiendo así localizado el conjunto $E$, el sistema (27) permite entonces calcular el error $e(X)$, con lo cual se ha de completar el proceso de decodificación.

También puede verse que si $m'\in[\![m+1,q-1-k]\!]$ entonces ${\bf S}_{m'}$ es singular. Así pues, si se desconociera cuál es el valor de $m$, entonces éste se obtendría como el máximo $m'$ tal que ${\bf S}_{m'}$ es no-singular.

Siguiente: Método de Euclides Arriba: Decodificación de Reed-Solomon Anterior: Decodificación de Reed-Solomon