Siguiente: Códigos de Golay Arriba: Códigos cíclicos Anterior: Polinomios generadores y revisores

Codificación y decodificación

Sea $C\subset\mathbb{K}^n$ un código-$[n,k]$ cíclico, sea $g(X)\in\mathbb{K}[X]$ su polinomio generador y sea $G_{nk}$ su matriz generatriz. Naturalmente, dada una palabra ${\bf a}\in\mathbb{K}^k$, ella ha de quedar codificada por la palabra ${\bf c} = G_{nk}{\bf a}\in\mathbb{K}^n$. Ya que la $j$-ésima columna $g_j$ de la matriz generatriz $G_{nk}$ corresponde bajo la función $\iota_n$ al polinomio $X^jg(X)$, se tiene $\iota_n({\bf c}) = \iota_n(G_{nk}{\bf a}) = g(X)\iota_k({\bf a})$. En otras palabras, la manera de codificar a cada palabra es viéndola como un polinomio y multiplicando por éste al polinomio generador. Esta codificación mediante códigos cíclicos se dice ser no-sistemática.

Definición 8.2   Sea $C<\mathbb{K}^n$ un código cíclico con polinomio generador $g(X)$. Para cada ${\bf u}\in \mathbb{K}^n$, sea $\iota_n({\bf u})$ el polinomio con vector de coeficientes ${\bf u}$. El síndrome polinomial de ${\bf u}$ es el polinomio $\iota_n({\bf u})\,\mbox{\rm mod}\,g(X)$ (o si se quiere, su vector de coeficientes).

Esta definición concuerda con la 5.5. En efecto, para cada ${\bf u}\in \mathbb{K}^n$, al escribir $r(X)=\iota_n({\bf u})\,\mbox{\rm mod}\,g(X)$, entonces $\iota_n({\bf u})=q(X)\,g(X) + r(X)$, con $\mbox{grado}(r(X))<n-k$, para algún polinomio $q(X)$. Así, sea ${\bf r}\in\mathbb{K}^n$ tal que $\iota_n({\bf r})=r(X)$ (como $\mbox{grado}(r(X))<n-k$, las últimas $k$ entradas de ${\bf r}$ son 0). Por la relación (23),

$$H_{nk}{\bf u} = H_{nk}{\bf r} = \left[\, H_{nk}^{(n-k)}\ \ H... ... r}^{(k)} \end{array}\right] = H_{nk}^{(n-k)}{\bf r}^{(n-k)},$$ (24)

donde $H_{nk}^{(n-k)}\in\mathbb{K}^{(n-k)\times(n-k)}$ es la matriz formada por las primeras $(n-k)$ columnas de $H_{nk}$, $H_{nk}^{(k)}\in\mathbb{K}^{(n-k)\times k}$ es la matriz formada por las últimas $k$ columnas de $H_{nk}$, ${\bf r}^{(n-k)}\in\mathbb{K}^{n-k}$ consta de las primeras $(n-k)$ entradas de ${\bf r}$ y ${\bf r}^{(k)}={\bf0}\in\mathbb{K}^{k}$ consta de las últimas $k$ entradas de ${\bf r}$. El síndrome de ${\bf u}$, en el sentido de la definición 5.5, es $H_{nk}{\bf u}$ y, según la relación (24), éste es $H_{nk}^{(n-k)}{\bf r}^{(n-k)}$. Ya que $H_{nk}^{(n-k)}$ posee una forma triangular su determinante es $(-1)^{\left\lfloor\frac{n-k}{2}\right\rfloor}h_k^{n-k}$ y es, por tanto, una matriz no singular. Esta determina un automorfismo lineal en $\mathbb{K}^{n-k}$ y la correspondencia entre los síndromes de la definición 5.5 y los de la 8.2.

Procedimiento de decodificación.

Supóngase que al transmitir una palabra ${\bf a}\in C$ se recibiera la palabra ${\bf b}\in\mathbb{K}^n$. El error cometido sería pues ${\bf e}={\bf a}-{\bf b}$. Vistas las palabras como polinomios, al calcular el síndrome polinomial $r(X)\in\mathbb{K}[X]$ de ${\bf b}$ se tendrá que existe un polinomio $q(X)\in\mathbb{K}[X]$ tal que $\iota_n({\bf b}) = q(X)\,g(X) + r(X)$. Si la distancia mínima del código $C$ fuese $d$ entonces habría que localizar una palabra ${\bf e}_s$ de peso de Hamming a lo sumo $\left\lfloor\frac{d}{2}\right\rfloor$ tal que $\iota_n({\bf e}_s) = r(X)\,\mbox{mod}\,g(X)$. Entonces necesariamente ${\bf e}_s={\bf e}$ y en tal caso se corrige ${\bf b}$ cambiándolo por ${\bf a}={\bf e}_s+{\bf b}$. $\Box$

El problema de cálculo de distancias mínimos de códigos cíclicos se ha tratado con diversos enfoques y el artículo de van Lint y Wilson [14] se ha convertido en una referencia clásica.

El proceso de decodificación descrito requiere pues calcular a los elementos con menor peso de Hamming en clases de congruencia módulo el polinomio generador.

Observación 8.2   Para un polinomio $f(X)\in\mathbb{K}[X]$ cualquiera, si $\overline{f}(X)$ es el polinomio que se obtiene al rotar los coeficientes de $f(X)$, entonces

$$\overline{f}(X)\,\mbox{\rm mod}\,g(X) = (X\cdot f(X))\,\mbox{\rm mod}\,g(X).$$

Así pues, si $\iota_n({\bf f})=f(X)$, el síndrome polinomial del ``polinomio rotado'' $\iota_n(\rho_n({\bf f}))$ coincide con el de $X\,r(X)$, donde $r(X)$ es el síndrome de $f(X)$.

Observamos que si $f(X) = q(X)\,g(X) + r(X)$, con $f(X) = \iota_n({\bf f})$, al rotar ${\bf f}$, valen:

$$\begin{eqnarray*} \iota_n(\rho_n({\bf f})) &=& X\,f(X) - f_{n-1}X^n + f_{n-1} \\... ..._{n-1}\,g(X)h(X) \\ &=& X\,r(X) + g(X)(X\,q(X) - f_{n-1}h(X)) \end{eqnarray*}$$

$\Box$

De esta manera, se puede calcular representantes principales para síndromes obtenidos de rotaciones de otros síndromes.

Por ejemplo, para el código-$[7,3]$ símplex tratado en el ejemplo 8.2, el polinomio generador es $g_{73}(X) = X^4 + X^3 + X^2 +1$. Por tanto, módulo $g_{73}(X)$, se tiene $X^4 = X^3 + X^2 +1$, y en consecuencia

$$\begin{eqnarray*} X^5 &=& X\cdot X^4 = X^4 + X^3 + X = \left(X^3 + X^2 +1\right)... ...6 = X^4 + X^3 + X^2 = \left(X^3 + X^2 +1\right) + X^3 + X^2 = 1 \end{eqnarray*}$$

Así pues, en la base polinomial se tiene la correspondencia siguiente:

$$\begin{array}{\vert\vert r\vert\vert c\vert c\vert c\vert c\v... ...^2 +1 & X^2 + X +1 & X^3 + X^2 + X \\ \hline \hline \end{array}$$

Dada una palabra ${\bf b}$, se calcula su síndrome, $r(X)$. Si éste aparece en el segundo renglón de la tabla anterior, entonces la correspondiente posición en el primero indicará cuál es el bit que hay que corregir. Si acaso el síndrome no apareciese, entonces, por tratarse de un código cíclico, la palabra puede rotarse y su síndrome multiplicarse por $X$ y reducirlo módulo $g(X)$ para volver a realizar la prueba. $\Box$

Otra manera de codificación, llamada ésta sistemática, utilizando códigos cíclicos es la siguiente. Dada una palabra ${\bf a}\in\mathbb{K}^k$ sea $\eta_{nk}({\bf a}) = \sum_{\kappa=0}^{k-1} a_{\kappa} X^{n-k+\kappa}$ el polinomio de grado $n-1$ cuyos coeficientes ``más altos'' están dados por la palabra ${\bf a}$. Entonces ésta queda codificada por la palabra ${\bf c}\in\mathbb{K}^n$ tal que

$$\iota_n({\bf c}) = \eta_{nk}({\bf a})-\left[\eta_{nk}({\bf a})\,\mbox{mod}\,g(X)\right]$$

o puesto equivalentemente,

$$c(X) = -\left[\left(X^{n-k}\,a(X)\right)\,\mbox{mod}\,g(X)\right] + X^{n-k}\,a(X)$$

el cual polinomio, en efecto, está en el código cíclico $C$ pues es un múltiplo del polinomio generador $g(X)$ de $C$. La palabra ${\bf c}\in\mathbb{K}^n$ de código, se descompone naturalmente en dos tramos: ${\bf c}={\bf c}_r{\bf c}_i\in\mathbb{K}^{n-k}\times\mathbb{K}^k$, tales que la parte ``alta'' ${\bf c}_i\in\mathbb{K}^k$ coincide con la palabra de información ${\bf a}$ y la parte ``baja'' ${\bf c}_r\in\mathbb{K}^{n-k}$ tiene fines de revisión de paridad.

Ahora, si Alicia envíase una palabra de código ${\bf c}={\bf c}_r{\bf c}_i\in\mathbb{K}^{n-k}\times\mathbb{K}^k$ y Beto recibiese la palabra ${\bf c}'={\bf c}'_r{\bf c}'_i\in\mathbb{K}^{n-k}\times\mathbb{K}^k$ entonces Beto calcula el síndrome $s'(X)=c'(X)\,\mbox{mod}\,g(X)$. Si acaso $s'(X)=0$ entonces Beto acepta a ${\bf c}'$ como ${\bf c}$ y no reconoce que hubiera habido errores. Si, en cambio, $s'(X)\not=0$ entonces reconoce que hubo errores y ha de proceder a corregirlos. Se ha de tener una tabla estándar de errores, de distancia de Hamming mínima, para algunos síndromes de manera que cuando se tenga un síndrome particular se lo localice en esa tabla para identificar el error del que proviene, y si no apareciese entonces se procede a rotar la palabra recibida y a multiplicar su síndrome por $X$, reducirlo módulo $g(X)$, y volver a realizar la prueba.

Siguiente: Códigos de Golay Arriba: Códigos cíclicos Anterior: Polinomios generadores y revisores