Siguiente: Decodificación de Reed-Solomon Arriba: Códigos de Reed-Solomon Anterior: Códigos RS: Como códigos

Códigos RS: Como códigos cíclicos

Si en el campo $\mathbb{F}_{q}$ consideramos $n=q-1$, entonces las raíces $(q-1)$-ésimas de la unidad en $\mathbb{F}_{q}$ son todos sus elementos no-nulos, es decir, los elementos del grupo mutiplicativo, y el código de Reed-Solomon será cíclico. Veamos esto con detalle. Seguiremos aquí la presentación hecha en [4].

Sea $q\in\mathbb{N}$ la potencia de un número primo $p$ y sea $\mathbb{K}=\mathbb{F}_q$ el campo de Galois de $q$ elementos, de característica $p$. Sea $a\in\mathbb{F}_q$ un elemento primitivo, vale decir, un generador del grupo cíclico multiplicativo $\mathbb{F}_q^*$. Para $k\leq q-1$, sea $g_{q-1,k}(X)$ el polinomio

$$g_{q-1,k}(X)=\prod_{\kappa=1}^{q-1-k}\left(X-a^{\kappa}\right).$$

Como $\forall \kappa\in[\![1,q-1-k]\!]$, $\left(a^{\kappa}\right)^{q-1} = \left(a^{q-1}\right)^{\kappa} = 1^{\kappa} = 1$, se tiene $\left(X-a^{\kappa}\right)\vert\left(X^{q-1}-1\right)$, y por tanto $g_{q-1,k}(X)\vert\left(X^{q-1}-1\right)$.

El código de Reed-Solomon $\mbox{\rm RS}(q-1,k)$ de longitud $q-1$ y dimensión $k$ es el código cíclico generado por el polinomio $g_{q-1,k}(X)$. Por tanto:

$$\forall f(X)\in\mathbb{F}_q[X]:\left[ f(X)\in\mbox{\rm RS}(q-... ...,\&\,\forall \kappa\in[\![1,q-1-k]\!]:\,f(a^{\kappa})=0\right].$$

Observamos aquí que la última subcondición puede sustituirse por la que impone que $q-1-k$ potencias consecutivas de $a$ son raíces de $f$ (esto porque el código es cíclico). Observamos también que si $a$ no fuese primitivo, entonces ha de generar un subgrupo de $\mathbb{F}_q^*$, por tanto el orden ha de ser un divisor de $q-1$. Se tendría entonces un código de menor tamaño, pero también cíclico.

Al escribir a un elemento $f(X)\in\mbox{\rm RS}(q-1,k)$ como $f(X) = \sum_{\lambda=0}^{q-2} f_{\lambda} X^{\lambda}$, se tiene $\forall \kappa\in[\![1,q-1-k]\!]$

$$0 = f(a^{\kappa}) = \sum_{\lambda=0}^{q-2} f_{\lambda} a^{\kappa\lambda} = {\bf a}_{\kappa}^T {\bf f}$$

donde

$${\bf a}_{\kappa} = \left[\begin{array}{c} 1 \\ a^{\kappa} \\ ... ...n{array}{c} f_0 \\ f_1 \\ \vdots \\ f_{q-2} \end{array}\right].$$

Por tanto una matriz revisora de paridad del código $\mbox{\rm RS}(q-1,k)$ es:

$$\mbox{\rm RS}_{q-1,k}^{\perp} = \left[a^{\kappa\lambda}\righ... ... %\\ \end{array}\right]\in\mathbb{F}_q^{(q-1-k)\times(q-1)}.$$ (26)

Observación 8.5   Cualesquiera $q-1-k$ columnas de la matriz $\mbox{\rm RS}_{q-1,k}^{\perp}$, dada por (26), son linealmente independientes en $\mathbb{F}_q^{q-1-k}$. En otras palabras, al tomar cualesquiera $q-1-k$ columnas de la matriz $\mbox{\rm RS}_{q-1,k}^{\perp}$, la submatriz resultante es no-singular.

Observación 8.6   El código $\mbox{\rm RS}(q-1,k)$ tiene distancia mínima $d=q-k$.

En efecto, por la observación anterior $d\geq q-k$. Por la desigualdad de Singleton $d\leq q-k$. $\Box$

Ejemplo 8.4   Sean $q=2^3=8$ y $k=3$. Entonces $q-1-k=4$. Al tomar como elemento primitivo $a=\mbox{\tt010}$, se tiene que el grupo multiplicativo $\mathbb{F}_8^*$ queda representado como sigue:

$$\begin{array}{c\vert ccccccc} \kappa & 0 & 1 & 2 & 3 & 4 & 5 ... ...mbox{\tt011} & \mbox{\tt 111} & \mbox{\tt 101} %\\ \end{array}$$

Por otro lado, $g_{73}(X) = (X-a) (X-a^2) (X-a^3) (X-a^4) = a^3 + aX + X^2 + a^3 X^3 + X^4$, y el código $\mbox{\rm RS}(7,3)$ es el generado por el polinomio $g_{73}(X)$.

Dada una palabra $\sigma\in\mathbb{F}_8^3$, digamos $\sigma = \mbox{\tt 101}\ \mbox{\tt001}\ \mbox{\tt 111}$, ésta puede identificarse con el polinomio $\sigma(X) = a^6 + a^2 X + a^5 X^2$. Al codificarlo, se obtiene el polinomio

$$\sigma(X)\, g_{73}(X) = a^2 + a^4 X + a^2 X^2 + a^6 X^3 + a^6 X^4 + a^4 X^5 + a^5 X^6,$$

el cual polinomio representa a la 7-palabra $\tau=\mbox{\tt001}\ \mbox{\tt011}\ \mbox{\tt001}\ \mbox{\tt 101}\ \mbox{\tt 101}\ \mbox{\tt011}\ \mbox{\tt 111}.$ Así pues, el código $\mbox{\rm RS}(7,3)$ establece la correspondencia $\sigma\mapsto \tau$. $\Box$

Siguiente: Decodificación de Reed-Solomon Arriba: Códigos de Reed-Solomon Anterior: Códigos RS: Como códigos