Siguiente: Codificación y decodificación Arriba: Códigos cíclicos Anterior: Códigos cíclicos

Polinomios generadores y revisores de paridad

Definición 8.1   Sea $\mathbb{K}$ un campo finito. En el espacio $\mathbb{K}^n$, la transformación lineal que sobre la base canónica actúa como $\rho_n:{\bf e}_j\mapsto {\bf e}_{(j+1)\mbox{\scriptsize\rm\ mod }n}$ se dice ser la rotación de componentes. Un código lineal-$(n,k)$ $C<\mathbb{K}^n$ es cíclico si $\rho_n(C)\subset C$.

Sea $\mathbb{K}[X]$ el anillo de polinomios sobre $\mathbb{K}$ y sea $\iota_n: \mathbb{K}^n\to\mathbb{K}[X]$, $(a_0,\ldots,a_{n-1})\mapsto \sum_{i=0}^{n-1} a_i X^i$ la transformación que a cada vector de $n$ coeficientes lo convierte en el polinomio correspondiente. $\iota_n$ es, naturalmente, un monomorfismo lineal de espacios vectoriales sobre $\mathbb{K}$. Consideremos el polinomio $c_n(X)=X^n-1$ y al cociente $\mathbb{K}[X]/(c_n(X)) = \mathbb{K}[X]/(X^n-1)$ el cual, visto como un espacio vectorial de dimensión $n$, hace que $\pi\circ\iota_n:{\bf a}\mapsto\iota_n({\bf a})+(X^n-1)$ sea un isomorfismo lineal que aplica la base canónica de $\mathbb{K}^n$ sobre la base polinomial $\left(X^j+(X^n-1)\right)_{j=0}^{n-1}$, donde $\pi:\mathbb{K}[X]\to\mathbb{K}[X]/(X^n-1)$ es la proyección canónica $\pi:f(X)\mapsto f(X)+(X^n-1)$. Se tiene el diagrama:

$$\xymatrix{ \mathbb{K}^n\ar[dr]_{\pi_n\circ\iota_n} \ar[r]^{\... ... & \mathbb{K}[X] \ar[d]^{\pi_n} \\ & \mathbb{K}[X]/(X^n-1) }$$ (19)

Si $C<\mathbb{K}^n$ es un código cíclico entonces vale la implicación:

$${\bf a}\in C\ \ \Longrightarrow\ \ X\cdot\left(\pi\circ\iota_n({\bf a})\right)\in\pi\circ\iota_n(C),$$

por tanto, la imagen $\pi\circ\iota_n(C)$ es un ideal en el anillo $\mathbb{K}[X]/(X^n-1)$.

Como $\mathbb{K}[X]$ es un anillo de ideales principales, necesariamente existe un polinomio $g(X)\in\mathbb{K}[X]$ tal que $(g(X)+(X^n-1))=\pi\circ\iota_n(C)$. Un tal polinomio con grado mínimo se dice ser generador del código $C$. De hecho el grado mínimo ha de ser $n-k$ y en $\mathbb{K}[X]$ se ha de tener $g(X)\vert(X^n-1)$.

Recíprocamente, si $g(X)\in\mathbb{K}[X]$ es tal que $g(X)\vert(X^n-1)$, el ideal generado por él, reducido módulo $(X^n-1)$, consta de polinomios cuyos vectores de coeficientes forman un código cíclico $C$.

Observación 8.1   Así para cada $n$ por cada divisor del polinomio $X^n-1$ en $\mathbb{K}[X]$ se tendrá un código cíclico.

Hagamos aquí una breve disgresión sobre divisores del polinomio $X^n-1$ en campos finitos $\mathbb{K}=\mathbb{F}_{q}$, donde $q$ es la potencia de un primo. El orden de un polinomio no-nulo $p(X)\in\mathbb{F}_{q}[X]$ es el mínimo $n$ tal que $p(X)\vert(X^n-1)$ en $\mathbb{F}_{q}[X]$. Un polinomio $p(X)\in\mathbb{F}_{q}[X]$ de grado $m\in\mathbb{N}$ es primitivo si es el polinomio mínimo de un elemento primitivo, es decir, de un generador del grupo multiplicativo $\mathbb{F}_{q^m}^*$. Pues bien, se tiene que un polinomio de grado $m$ es primitivo cuando y sólo cuando su orden es $q^m-1$. Además, para cada $m$ el número de polinomios primitivos de grado $m$ en $\mathbb{F}_{q}[X]$ es $\phi(q^m-1)/m$ donde $\phi$ es la función tociente de Euler.

Así para un polinomio primitivo $g(X)\in\mathbb{F}_{2}[X]$ de grado $m$, de acuerdo con la observación 8.1, el tamaño de bloque para que $g(X)$ sea el generador de un código cíclico debe ser $n=2^m-1$.

Sigamos con nuestra exposición. Si el polinomio generador de un código cíclico es $g(X) = \sum_{i=0}^{n-k} g_i X^i$ entonces

$$G_{nk} = \left(\begin{array}{ccccccc} g_0 & 0 & 0 & \cdots &... ... & 0 & g_{n-k} \end{array}\right) \in \mathbb{K}^{n\times k}$$ (20)

es una generatriz del código $C$. El polinomio generador $g(X)$, que es único si se le supone mónico, es decir con coeficiente principal 1, determina pues por completo al código cíclico $C$. Es convencional identificar a cada palabra de código ${\bf a}\in C$ tanto con el polinomio $\iota_n({\bf a})$ como con la clase $\iota_n({\bf a}) + (X^n-1)$ de ese polinomio y por tanto en el contexto de códigos cíclicos se dice que las palabras de código son polinomios.

Ejemplo 8.1 (Palabras de peso par)   Sea $\mathbb{K}=\mathbb{F}_2$ el campo primo de característica $2$ y sea $C\subset\mathbb{F}_2^n$ el espacio de palabras en $\mathbb{F}_2^n$ con peso de Hamming par.

Este es un subespacio lineal y una matriz revisora de paridad es ${\bf 1}^T$:

$$\forall \mbox{\boldmath $\varepsilon$}\in\mathbb{F}_2^n:\ \mb... ...n$} = \langle{\bf 1}\vert\mbox{\boldmath $\varepsilon$}\rangle.$$

Por tanto $n-k=1$ y consecuentemente $C$ posee $k=n-1$ bits de información.

Claramente $C$ es cíclico. Como la palabra $110^{n-2}$ está en $C$, el polinomio generador ha de ser $g(X)=X+1$ el cual evidentemente divide a $c_n(X) = X^n-1 = X^n+1$ en $\mathbb{F}_2[X]$. Algunos ejemplos de generatrices son

$$G_{3} = \left(\begin{array}{cc} 1 & 0 \\ 1 & 1 \\ 0 & 1 %\\... ... & 1 \\ 0 & 0 & 0 & 0 & 1 %\\ \end{array}\right) %\ \ , \ \$$

Así el código de palabras con peso par en $\mathbb{F}_2^n$ puede representarse de manera precisa con el solo polinomio $g(X)=X+1$. $\Box$

Sea $C\subset\mathbb{K}^n$ un código cíclico y sea $g(X) = \sum_{i=0}^{n-k-1} g_i X^i + X^{n-k}$ su polinomio generador. Como $g(X)\vert(X^n-1)$, el cociente $h(X) =\frac{X^n-1}{g(X)}$ es un polinomio, de grado $k$. Escribamos $h(X) = \sum_{i=0}^{k} h_i X^i$. Entonces,

$$X^n-1 = g(X)h(X) = \left(\sum_{i=0}^{n-k} g_i X^i\right) \lef... ...\sum_{\ell=0}^{n}\left( \sum_{i+j=\ell} g_i h_j \right)X^{\ell}$$

por lo cual en el campo $\mathbb{K}$ se ha de tener

$$g_{0} h_0 = 1\ \ \&\ \ \left[\ell\in[\![1,n-1]\!]\ \Rightarr... ...\ell,k\}} g_i h_{\ell-i} = 0\right]\ \ \&\ \ g_{n-k} h_k = 1.$$ (21)

Al considerar un polinomio $f(X)\in(g(X))$, necesariamente

$$h(X)\,f(X) = \frac{X^n-1}{g(X)}\, e(X)\, g(X) = e(X)\,(X^n-1)$$

para algún $e(X)\in\mathbb{K}[X]$, o sea $h(X)\,f(X) \equiv 0 \,\mbox{\rm mod}\,(X^n-1)$. Es debido a esto último que el polinomio $h(X)$ se dice ser el polinomio revisor de paridad del código cíclico $C$. De hecho la matriz

$$H_{nk} = \left(\begin{array}{cccccccccccc} 0 & 0 & 0 & \cdot... ... 0 & 0 & 0 \end{array}\right) \in \mathbb{K}^{(n-k)\times n}$$ (22)

es revisora de paridad del código $C$, pues por las relaciones (21) se ve que $H_{nk} G_{nk} = 0 \in \mathbb{K}^{(n-k)\times k}$, es decir cada rengón de $H_{nk}$ es ortogonal a todas las columnas de $G_{nk}$. Es importante remarcar que en la ec. (20) los índices son crecientes en cada columna, en tanto que en la ec. (22) son decrecientes en cada renglón. Se tiene pues:

$$\forall{\bf u}\in \mathbb{K}^n:\ \left[{\bf u}\in C\ \Longrightarrow\ H_{nk}{\bf u} = {\bf0}\right],$$

y en consecuencia

$$\forall{\bf u},{\bf v}\in \mathbb{K}^n:\ \left[{\bf u}-{\bf v}\in C\ \Longrightarrow\ H_{nk}{\bf u} = H_{nk}{\bf v}\right] .$$ (23)

Ejemplo 8.2 (Códigos cíclicos binarios de longitud $n=7$)   En $\mathbb{K}=\mathbb{F}_2$, el polinomio $X^7-1 = X^7+1$ se factoriza como $X^7+1 = (X+1) (X^3+X+1) (X^3+X^2+1),$ así posee tres divisores irreducibles

$$\gamma_{70}(X) =X+1\hspace{2em},\hspace{2em}\gamma_{71}(X) =X^3+X+1\hspace{2em},\hspace{2em}\gamma_{72}(X) =X^3+X^2+1.$$

Cualquier producto de éstos dividirá a $X^7+1$, por lo que existen $2^3=8$ divisores de él, de los cuales dos son triviales: $g_{70}(X)=\gamma_{70}(X)\gamma_{71}(X)\gamma_{72}(X)=X^7+1$ y $g_{77}(X)=1$.

Hay pues $6= 2^3-2$ códigos cíclicos binarios de longitud $n=7$. En particular, para el polinomio $g_{73}(X) = \gamma_{70}(X)\gamma_{71}(X) = X^4 + X^3 + X^2 +1$ se tiene $h_{73}(X) = \frac{X^7+1}{g_{73}(X)} = \gamma_{72}(X) = X^3+X^2+1$ y las matrices generatriz y revisora de paridad siguientes:

$$G_{73} = \left[\begin{array}{ccc} 1 & 0 & 0 \\ 0 & 1 & 0 \\ ... ...0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 \end{array}\right].$$

La función de codificación es pues

$$(u_0,u_1,u_2)\mapsto (u_0\,,\,u_1\,,\,u_0+u_2\,,\,u_0+u_1\,,\,u_0+u_1+u_2\,,\,u_1+u_2\,,\,u_2).$$

Este se dice ser el código ``símplex''. En los $7=2^3-1$ renglones de la matriz generatriz $G_{73}$ aparecen las representaciones en binario de los números en el intervalo $[\![1,2^3-1]\!]$, por tanto su código dual es uno de Hamming. $\Box$

Ejemplo 8.3 (Códigos cíclicos terciarios de longitud $n=8$)   En $\mathbb{K}=\mathbb{F}_3$, el polinomio $X^8-1 = X^8+2$ (pues $2=-1$) se factoriza como $X^8-1 = (X+1) (X+2) (X^2+1) (X^2+X+2) (X^2+2X+2) ,$ así posee cinco divisores irreducibles

$$\begin{array}{c} \gamma_{80}(X) =X+1 \hspace{1em},\hspace{1em... ... \hspace{1em},\hspace{1em}\gamma_{84}(X) =X^2+2X+2. \end{array}$$

Cualquier producto de éstos dividirá a $X^8-1$, por lo que existen $2^5=32$ divisores de él, de los cuales dos son triviales: $g_{80}(X)=X^8-1$ y $g_{88}(X)=1$.

Hay pues $30= 2^5-2$ códigos cíclicos terciarios de longitud $n=8$. En particular, para el polinomio $g_{85}(X) = \gamma_{81}(X)\gamma_{82}(X) = X^3 + 2X^2 + X + 2$ se tiene $h_{85}(X) = \frac{X^8-1}{g_{85}(X)} = \gamma_{80}(X) \gamma_{83}(X) \gamma_{84}(X) = X^5+X^4+X+1$ y las matrices generatriz y revisora de paridad siguientes:

$$G_{85} = \left[\begin{array}{ccccc} 2 & 0 & 0 & 0 & 0 \\ 1 &... ... & 0 \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 & 0 %\\ \end{array}\right].$$

$\Box$

Siguiente: Codificación y decodificación Arriba: Códigos cíclicos Anterior: Códigos cíclicos