[skip-to-content]
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \renewcommand{\gcd}{\operatorname{mcd}} \renewcommand{\lcm}{\operatorname{mcm}} \renewcommand{\deg}{\operatorname{gr}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

Sección22.2Códigos Polinomiales

Sabiendo sobre anillos de polinomios y cuerpos finitos, es posible derivar códigos más sofisticados que los del Capítulo 8. En primer lugar recordemos que un código de bloques \((n, k)\) consiste de una función codificadora inyectiva \(E:{\mathbb Z}^{k}_{2} \rightarrow {\mathbb Z}^{n}_{2}\) y una función decodificadora \(D:{\mathbb Z}^{n}_{2} \rightarrow {\mathbb Z}^{k}_{2}\text{.}\) El código es corrector de errores si \(D\) es sobreyectivo. Un código es lineal si es el espacio nulo de una matriz \(H \in {\mathbb M}_{k \times n}({\mathbb Z}_2)\text{.}\)

Estamos interesados en una clase de códigos conocidos como códigos cíclicos. Sea \(\phi : {\mathbb Z}_2^k \rightarrow {\mathbb Z}_2^n\) un código de bloques \((n,k)\) binario. Entonces \(\phi\) es un código cíclico si para cada palabra \((a_1, a_2, \ldots, a_n )\) en el código, la palabra formada por desplazamiento cíclico, la \(n\)-tupla \((a_n, a_1, a_2, \ldots, a_{n - 1} )\) también está en el código. Los códigos cíclicos son fáciles de implementar en un computador usando registro de shift [2, 3].

Ejemplo22.14

Considere los código lineales \((6,3)\)generados por las dos matrices

\begin{equation*} G_1 = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} \quad \text{y} \quad G_2 = \begin{pmatrix} 1 & 0 & 0 \\ 1 & 1 & 0 \\ 1 & 1 & 1 \\ 1 & 1 & 1 \\ 0 & 1 & 1 \\ 0 & 0 & 1 \end{pmatrix}. \end{equation*}

Los mensajes del primero se codifican como sigue:

\begin{equation*} \begin{array}{rclccrcl} (000) & \mapsto & (000000) & & & (100) & \mapsto & (100100) \\ (001) & \mapsto & (001001) & & & (101) & \mapsto & (101101) \\ (010) & \mapsto & (010010) & & & (110) & \mapsto & (110110) \\ (011) & \mapsto & (011011) & & & (111) & \mapsto & (111111). \end{array} \end{equation*}

Es fácil ver que las palabras del código forman un código cíclico. En el segundo, las 3-tuplas se codifican de la siguiente manera:

\begin{equation*} \begin{array}{rclccrcl} (000) & \mapsto & (000000) & & & (100) & \mapsto & (111100) \\ (001) & \mapsto & (001111) & & & (101) & \mapsto & (110011) \\ (010) & \mapsto & (011110) & & & (110) & \mapsto & (100010) \\ (011) & \mapsto & (010001) & & & (111) & \mapsto & (101101). \end{array} \end{equation*}

Este código no es cíclico, pues \((101101)\) es una palabra del código pero \((011011)\) no lo es.

SubsecciónCódigos Polinomiales

Nos gustaría encontrar un método fácil para obtener códigos cíclicos lineales. Para lograr esto, podemos usar lo que sabemos de cuerpos finitos y anillos de polinomios sobre \({\mathbb Z}_2\text{.}\) Cualquier \(n\)-tupla binaria se puede interpretar como un polinomio en \({\mathbb Z}_2[x]\text{.}\) Dicho de otra forma, la \(n\)-tupla \((a_0, a_1, \ldots, a_{n - 1} )\) corresponde al polinomio

\begin{equation*} f(x) = a_0 + a_1 x + \cdots + a_{n-1} x^{n - 1}, \end{equation*}

donde el grado de \(f(x)\) es a lo más \(n - 1\text{.}\) Por ejemplo, el polinomio correspondiente a la 5-tupla \((10011)\) es

\begin{equation*} 1 + 0 x + 0 x^2 + 1 x^3 + 1 x^4 = 1 + x^3 + x^4. \end{equation*}

Recíprocamente, dado cualquier polinomio \(f(x) \in {\mathbb Z}_2[x]\) con \(\deg f(x) \lt n\) le podemos asociar una \(n\)-tupla binaria. El polinomio \(x + x^2 + x^4\) corresponde a la 5-tupla \((01101)\text{.}\)

Fijemos un polinomio no constante \(g(x)\) en \({\mathbb Z}_2[x]\) de grado \(n - k\text{.}\) Podemos definir un \((n,k)\)-código \(C\) de la siguiente manera. Si \((a_0, \ldots, a_{k - 1})\) es una \(k\)-tupla a codificar, entonces \(f(x) = a_0 + a_1 x + \cdots + a_{k - 1} x^{k - 1}\) es el correspondiente polinomio en \({\mathbb Z}_2[x]\text{.}\) Para codificar \(f(x)\text{,}\) lo multiplicamos por \(g(x)\text{.}\) Las palabras en \(C\) son todos aquellos polinomios en \({\mathbb Z}_2[x]\) de grado menor a \(n\) que son divisibles por \(g(x)\text{.}\) Los Códigos obtenidos de esta manera se llaman códigos polinomiales.

Ejemplo22.15

Si \(g(x)= 1 + x^3\text{,}\) podemos definir un \((6,3)\)-código \(C\) como sigue. Para codificar una 3-tupla \(( a_0, a_1, a_2 )\text{,}\) multiplicamos el correspondiente polinomio \(f(x) = a_0 + a_1 x + a_2 x^2\) por \(1 + x^3\text{.}\) Estamos definiendo una función \(\phi : {\mathbb Z}_2^3 \rightarrow {\mathbb Z}_2^6\) como \(\phi : f(x) \mapsto g(x) f(x)\text{.}\) Es fácil verificar que esta función es un homomorfismo de grupos. De hecho, si consideramos \({\mathbb Z}_2^n\) como un espacio vectorial sobre \({\mathbb Z}_2\text{,}\) \(\phi\) es una transformación lineal de espacios vectoriales (vea el Ejercicio 20.4.15, Capítulo 20). Calculemos el núcleo de \(\phi\text{.}\) Observe que \(\phi ( a_0, a_1, a_2 ) = (000000)\) exactamente cuando

\begin{align*} 0 + 0x + 0x^2 + 0x^3 + 0x^4 + 0 x^5 & = (1 + x^3) ( a_0 + a_1 x + a_2 x^2 )\\ & = a_0 + a_1 x + a_2 x^2 + a_0 x^3 + a_1 x^4 + a_2 x^5. \end{align*}

Como los polinomios sobre un cuerpo forman un dominio integral, \(a_0 + a_1 x + a_2 x^2\) debe ser el polinomio cero. Por lo tanto, \(\ker \phi = \{ (000) \}\) y \(\phi\) es 1-1.

Para calcular una matriz generadora para \(C\text{,}\) solo debemos examinar cómo se codifican los polinomios \(1\text{,}\) \(x\text{,}\) y \(x^2\text{:}\)

\begin{align*} (1 + x^3) \cdot 1 & = 1 + x^3\\ (1 + x^3)x & = x + x^4\\ (1 + x^3)x^2 & = x^2 + x^5. \end{align*}

Obtenemos el código correspondiente a la matriz generadora \(G_1\) en el Ejemplo 22.14. la matriz de verificación de paridad para este código es

\begin{equation*} H = \begin{pmatrix} 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 \end{pmatrix}. \end{equation*}

Como el menor peso de cualquier palabra no nula del código es 2, este código es capaz de detectar cualquier error único.

Los anillos de Polinomios tienen una estructura muy rica; por lo tanto, nuestro objetivo inmediato es establecer una relación entre los códigos polinomiales y la teoría de anillos. Recuerde que \(x^n - 1 = (x - 1)( x^{n-1} + \cdots + x + 1)\text{.}\) El anillo cociente

\begin{equation*} R_n = {\mathbb Z}_2[x]/ \langle x^n - 1 \rangle \end{equation*}

puede ser considerado como el anillo de polinomios de la forma

\begin{equation*} f(t) = a_0 + a_1 t + \cdots + a_{n-1} t^{n-1} \end{equation*}

que satisfacen la condición \(t^n = 1\text{.}\) Es un ejercicio sencillo mostrar que \({\mathbb Z}_2^n\) y \(R_n\) son isomorfos como espacios vectoriales. Frecuentemente interpretaremos los elementos en \({\mathbb Z}_2^n\) con elementos en \({\mathbb Z}[x] / \langle x^n - 1 \rangle\text{.}\) De esta forma podemos interpretar un código lineal como un subconjunto de \({\mathbb Z}[x] / \langle x^n - 1 \rangle\text{.}\)

La estructura adicional de anillo en los códigos polinomiales es muy poderosa para describir códigos cíclicos. Un shift cíclico de una \(n\)-tupla puede ser descrito por una multiplicación polinomial. Si \(f(t) = a_0 + a_1 t + \cdots + a_{n-1} t^{n-1}\) es un código polinomial en \(R_n\text{,}\) entonces

\begin{equation*} tf(t) = a_{n-1} + a_0 t + \cdots + a_{n-2} t^{n-1} \end{equation*}

es la palabra desplazada cíclicamente obtenida de multiplicar \(f(t)\) por \(t\text{.}\) El siguiente teorema entrega una hermosa clasificación de los códigos cíclicos en términos de los ideales de \(R_n\text{.}\)

Sea \(C\) un código cíclico lineal y supongamos que \(f(t)\) está en \(C\text{.}\) Entonces \(t f(t)\) también está en \(C\text{.}\) Así, \(t^k f(t)\) está en \(C\) para todo \(k \in {\mathbb N}\text{.}\) Como \(C\) es un código lineal, cualquier combinación lineal de las palabras \(f(t), tf(t), t^2f(t), \ldots, t^{n-1}f(t)\) también es una palabra del código; por lo tanto, para cada polinomio therefore \(p(t)\text{,}\) \(p(t)f(t)\) está en \(C\text{.}\) Luego, \(C\) es un ideal.

Recíprocamente, sea \(C\) un ideal en \({\mathbb Z}_2[x]/\langle x^n + 1\rangle\text{.}\) Supongamos que \(f(t) = a_0 + a_1 t + \cdots + a_{n - 1} t^{n - 1}\) es una palabra en \(C\text{.}\) Entonces \(t f(t)\) es una palabra en \(C\text{;}\) es decir, \((a_1, \ldots, a_{n-1}, a_0)\) está en \(C\text{.}\)

El Teorema 22.16 nos dice que conocer los ideales de \(R_n\) es equivalente a conocer los códigos cíclicos en \({\mathbb Z}_2^n\text{.}\) Afortunadamente es fácil describir los ideales en \(R_n\text{.}\) El homomorfismo natural \(\phi : {\mathbb Z}_2[x] \rightarrow R_n\) definido por \(\phi[f(x)] = f(t)\) es un homomorfismo epiyectivo. El núcleo de \(\phi\) es el ideal generado por \(x^n - 1\text{.}\) Por el Teorema 16.34, todo ideal \(C\) en \(R_n\) es de la forma \(\phi(I)\text{,}\) donde \(I\) es un ideal en \({\mathbb Z}_2[x]\) que contiene al ideal \(\langle x^n - 1 \rangle\text{.}\) Por el Teorema 17.20, sabemos que todo ideal en \({\mathbb Z}_2[x]\) es un ideal principal, pues \({\mathbb Z}_2\) es un cuerpo. Por lo tanto, \(I = \langle g(x) \rangle\) para algún polinomio mónico en \({\mathbb Z}_2[x]\text{.}\) Como \(\langle x^n - 1 \rangle\) está contenido en \(I\text{,}\) se debe tener que \(g(x)\) divide a \(x^n - 1\text{.}\) Así, todo ideal \(C\) en \(R_n\) es de la forma

\begin{equation*} C = \langle g(t) \rangle = \{ f(t)g(t) : f(t) \in R_n \text{ y } g(x) \mid (x^n - 1) \text{ en } {\mathbb Z}_2[x] \}. \end{equation*}

El polinomio único de grado mínimo que genera \(C\) se llama polinomio generador minimal de \(C\text{.}\)

Ejemplo22.17

Si factorizamos \(x^7 - 1\) en sus componentes irreducibles, tenemos

\begin{equation*} x^7 - 1 = (1 + x)(1 + x + x^3)(1+ x^2 + x^3). \end{equation*}

Vemos que \(g(t) = (1 + t + t^3)\) genera un ideal \(C\) en \(R_7\text{.}\) Este es un código de bloque \((7, 4)\text{.}\) Como en el Ejemplo 22.15, es fácil calcular una matriz generadora examinando qué le hace \(g(t)\) a los polinomios 1, \(t\text{,}\) \(t^2\text{,}\) y \(t^3\text{.}\) Una matriz generadora para \(C\) es

\begin{equation*} G = \begin{pmatrix} 1 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 \\ 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}. \end{equation*}

En general, podemos determinar una matriz generadora para un código \((n, k)\) \(C\) por la forma en que se codifican los elementos \(t^k\text{.}\) Sea \(x^n - 1 = g(x) h(x)\) en \({\mathbb Z}_2[x]\text{.}\) Si \(g(x) = g_0 + g_1 x + \cdots + g_{n-k} x^{n-k}\) and \(h(x) = h_0 + h_1 x + \cdots + h_k x^k\text{,}\) entonces la matriz de \(n \times k\)

\begin{equation*} G = \begin{pmatrix} g_0 & 0 & \cdots & 0 \\ g_1 & g_0 & \cdots & 0 \\ \vdots & \vdots &\ddots & \vdots \\ g_{n-k} & g_{n-k-1} & \cdots & g_0 \\ 0 & g_{n-k} & \cdots & g_{1} \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & g_{n-k} \end{pmatrix} \end{equation*}

es una matriz generadora para el código \(C\) con generador polinomial \(g(t)\text{.}\) La matriz de verificación de paridad para \(C\) es la matriz de \((n-k) \times n\)

\begin{equation*} H = \begin{pmatrix} 0 & \cdots & 0 & 0 & h_k & \cdots & h_0 \\ 0 & \cdots & 0 & h_k & \cdots & h_0 & 0 \\ \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\ h_k & \cdots & h_0 & 0 & 0 & \cdots & 0 \end{pmatrix}. \end{equation*}

Dejaremos los detalles de la demostreción de la siguiente proposición como un ejercicio.

Ejemplo22.19

En el Ejemplo 22.17,

\begin{equation*} x^7 - 1 = g(x) h(x) = (1 + x + x^3)(1 + x + x^2 + x^4). \end{equation*}

Por lo tanto, una matriz verificadora para este código es

\begin{equation*} H = \begin{pmatrix} 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 1 & 0 \\ 1 & 0 & 1 & 1 & 1 & 0 & 0 \end{pmatrix}. \end{equation*}

Para determinanr las capacidades de detección y corrección de errores de un código cíclico, necesitamos saber algo sobre determinantes. Si \(\alpha_1, \ldots, \alpha_n\) son elementos en un cuerpo \(F\text{,}\) entonces la matriz de \(n \times n\)

\begin{equation*} \begin{pmatrix} 1 & 1 & \cdots & 1 \\ \alpha_1 & \alpha_2 & \cdots & \alpha_n \\ \alpha_1^2 & \alpha_2^2 & \cdots & \alpha_n^2 \\ \vdots & \vdots & \ddots & \vdots \\ \alpha_1^{n-1} & \alpha_2^{n-1} & \cdots & \alpha_n^{n-1} \end{pmatrix} \end{equation*}

se llama matriz de Vandermonde. El determinante de esta matriz se llama determinante de Vandermonde. Necesitaremos el siguiente lema en nuestro estudio de los códigos cíclicos.

Procederemos por inducción en \(n\text{.}\) Si \(n = 2\text{,}\) entonces el determinante es \(\alpha_2 - \alpha_1\text{.}\) Supongamos demostrado el resultado para \(n - 1\) y consideremos el polinomio \(p(x)\) definido por

\begin{equation*} p(x) = \det \begin{pmatrix} 1 & 1 & \cdots & 1 & 1 \\ \alpha_1 & \alpha_2 & \cdots & \alpha_{n-1} & x \\ \alpha_1^2 & \alpha_2^2 & \cdots & \alpha_{n-1}^2 & x^2 \\ \vdots & \vdots & \ddots & \vdots & \vdots \\ \alpha_1^{n-1} & \alpha_2^{n-1} & \cdots & \alpha_{n-1}^{n-1} & x^{n-1} \end{pmatrix}. \end{equation*}

Expandiendo este determinante por cofactores en la última columna, vemos que \(p(x)\) es un polinomio de grado a lo más \(n-1\text{.}\) Además, las raíces de \(p(x)\) son \(\alpha_1, \ldots, \alpha_{n-1}\text{,}\) pues la sustitución de cualquiera de esos elementos en la última columna producirá una columna idéntica a otra columna de la matriz. Recuerde que el determinante de una matriz es cero si esta tiene dos columnas idénticas. Por lo tanto,

\begin{equation*} p(x) = (x - \alpha_1)(x - \alpha_2) \cdots (x - \alpha_{n-1}) \beta, \end{equation*}

donde

\begin{equation*} \beta = (-1)^{n + n} \det \begin{pmatrix} 1 & 1 & \cdots & 1 \\ \alpha_1 & \alpha_2 & \cdots & \alpha_{n-1} \\ \alpha_1^2 & \alpha_2^2 & \cdots & \alpha_{n-1}^2 \\ \vdots & \vdots & \ddots & \vdots \\ \alpha_1^{n-2} & \alpha_2^{n-2} & \cdots & \alpha_{n-1}^{n-2} \end{pmatrix}. \end{equation*}

Por nuestra hipótesis de inducción,

\begin{equation*} \beta = (-1)^{n+n} \prod_{1 \leq j \lt i \leq n-1} (\alpha_i - \alpha_j). \end{equation*}

Si evaluamos en \(x = \alpha_n\text{,}\) el resultados es una consecuencia inmediata.

El siguiente teorema nos entrega una estimación de las capacidades de detección y corrección de errores para un polinomio generador en particular.

Supongamos que

\begin{equation*} g( \omega^r) = g(\omega^{r + 1}) = \cdots = g( \omega^{r + s - 1}) = 0. \end{equation*}

Sea \(f(x)\) algún polinomio en \(C\) con \(s\) o menos coeficientes distintos de cero. Podemos suponer que

\begin{equation*} f(x) = a_{i_0} x^{i_0} + a_{i_1} x^{i_1} + \cdots + a_{i_{s - 1}} x^{i_{s - 1}} \end{equation*}

es algún polinomio en \(C\text{.}\) Es suficiente con demostrar que todos los \(a_i\) tienen que ser cero. Como

\begin{equation*} g( \omega^r) = g(\omega^{r + 1}) = \cdots = g( \omega^{r + s - 1}) = 0 \end{equation*}

y \(g(x)\) divide a \(f(x)\text{,}\)

\begin{equation*} f( \omega^r) = f(\omega^{r + 1}) = \cdots = f( \omega^{r + s - 1}) = 0. \end{equation*}

Equivalentemente, tenemos el siguiente sistema de ecuaciones:

\begin{align*} a_{i_0} (\omega^r)^{i_0} + a_{i_1} (\omega^r)^{i_1} + \cdots + a_{i_{s - 1}} (\omega^r)^{i_{s - 1}} & = 0\\ a_{i_0} (\omega^{r + 1})^{i_0} + a_{i_1} (\omega^{r + 1})^{i_2} + \cdots + a_{i_{s-1}} (\omega^{r+1})^{i_{s-1}} & = 0\\ & \vdots \\ a_{i_0} (\omega^{r + s - 1})^{i_0} + a_{i_1} (\omega^{r + s - 1})^{i_1} + \cdots + a_{i_{s - 1}} (\omega^{r + s - 1})^{i_{s - 1}} & = 0. \end{align*}

Por lo tanto, \((a_{i_0}, a_{i_1}, \ldots, a_{i_{s - 1}})\) es una solución del sistema de ecuaciones lineales homogéneo

\begin{align*} (\omega^{i_0})^r x_0 + (\omega^{i_1})^r x_1 + \cdots + (\omega^{i_{s - 1}})^r x_{n - 1} & = 0\\ (\omega^{i_0})^{r + 1} x_0 + (\omega^{i_1})^{r + 1} x_1 + \cdots + (\omega^{i_{s - 1}})^{r + 1} x_{n - 1} & = 0\\ & \vdots \\ (\omega^{i_0})^{r + s - 1} x_0 + (\omega^{i_1})^{r + s - 1} x_1 + \cdots + (\omega^{i_{s - 1}})^{r + s - 1} x_{n - 1} & = 0. \end{align*}

Pero este sistema tiene solución única, pues el determinante de la matriz

\begin{equation*} \begin{pmatrix} (\omega^{i_0})^r & (\omega^{i_1})^r & \cdots & (\omega^{i_{s-1}})^r \\ (\omega^{i_0})^{r+1} & (\omega^{i_1})^{r+1} & \cdots & (\omega^{i_{s-1}})^{r+1} \\ \vdots & \vdots & \ddots & \vdots \\ (\omega^{i_0})^{r+s-1} & (\omega^{i_1})^{r+s-1} & \cdots & (\omega^{i_{s-1}})^{r+s-1} \end{pmatrix} \end{equation*}

no es cero por el Lema 22.20 y las propiedades básicas de los determinantes (Ejercicio). Por lo tanto, esta solución es \(a_{i_0} = a_{i_1} = \cdots = a_{i_{s - 1}} = 0\text{.}\)

SubsecciónCódigos BCH

Entre los códigos más importantes, descubiertos independientemente por A. Hocquenghem en 1959 y por R. C. Bose y D. V. Ray-Chaudhuri en 1960, están los códigos BCH. Los sistemas de comunicación Europeo y Trasantlántico, ambos usan códigos BCH. Las palabras a codificar son de largo 231, y se usa un polinomio de grado 24 para generar el código. Como \(231 + 24 = 255 = 2^8-1\text{,}\) tenemos un código de bloque \((255, 231)\text{.}\) Este código BCH es capaz de detectar seis errores y tiene una razón de falla de 1 en 16 millones. Una ventaja de los códigos BCH es que existen algoritmos eficientes de corrección de errores para ellos.

La idea detrás de los códigos BCH es elegir un polinomio generador de grado minimal que tenga la mayor capacidad de detección y corrección de errores. Sea \(d = 2r + 1\) para algún \(r \geq 0\text{.}\) Supongamos que \(\omega\) es una raíz \(n\)-ésima primitiva de la unidad sobre \({\mathbb Z}_2\text{,}\) y sea \(m_i(x)\) el polinomio minimal sobre \({\mathbb Z}_2\) de \(\omega^i\text{.}\) Si

\begin{equation*} g(x) = \lcm[ m_1(x), m_{2}(x), \ldots, m_{2r}(x)], \end{equation*}

entonces el código cíclico \(\langle g(t) \rangle\) en \(R_n\) se denomina código BCH de largo \(n\) y distancia \(d\text{.}\) Por el Teorema 22.21, la distancia mínima de \(C\) es al menos \(d\text{.}\)

(1) \(\Rightarrow\) (2). Si \(f(t)\) está en \(C\text{,}\) entonces \(g(x) \mid f(x)\) en \({\mathbb Z}_2[x]\text{.}\) Luego, para \(i = 1, \ldots, 2r\text{,}\) \(f( \omega^i) = 0\) pues \(g( \omega^i ) = 0\text{.}\) Recíprocamente, supongamos que \(f( \omega^i) = 0\) for \(1 \leq i \leq d\text{.}\) Entonces \(f(x)\) es divisible por cada \(m_i(x)\text{,}\) pues \(m_i(x)\) es el polinomio minimal de \(\omega^i\text{.}\) Por lo tanto, \(g(x) \mid f(x)\) porla definición de \(g(x)\text{.}\) Así, \(f(x)\) es una palabra del código.

(2) \(\Rightarrow\) (3). Sea \(f(t) = a_0 + a_1 t + \cdots + a_{n - 1}v t^{n - 1}\) be in \(R_n\text{.}\) La correspondiente \(n\)-tupla en \({\mathbb Z}_2^n\) es \({\mathbf x} = (a_0 a_1 \cdots a_{n - 1})^{\rm t}\text{.}\) By (2),

\begin{equation*} H {\mathbf x} = \begin{pmatrix} a_0 + a_1 \omega + \cdots + a_{n-1} \omega^{n-1} \\ a_0 + a_1 \omega^2 + \cdots + a_{n-1} (\omega^2)^{n-1} \\ \vdots \\ a_0 + a_1 \omega^{2r} + \cdots + a_{n-1} (\omega^{2r})^{n-1} \end{pmatrix} = \begin{pmatrix} f(\omega) \\ f(\omega^2) \\ \vdots \\ f(\omega^{2r}) \end{pmatrix} = 0 \end{equation*}

precisamente cuando \(f(t)\) está en \(C\text{.}\) Luego, \(H\) es una matriz verificadora para \(C\text{.}\)

(3) \(\Rightarrow\) (1). Por (3), un polinomio \(f(t) = a_0 + a_1 t + \cdots + a_{n - 1} t^{n - 1}\) está en \(C\) exactamente cuando \(f(\omega^i) = 0\) for \(i = 1, \ldots, 2r\text{.}\) El menor tal polinomio es \(g(t) = \lcm[ m_1(t),\ldots, m_{2r}(t)]\text{.}\) Por lo tanto, \(C = \langle g(t) \rangle\text{.}\)

Ejemplo22.23

Es fácil verificar que \(x^{15} - 1 \in {\mathbb Z}_2[x]\) se factoriza como

\begin{equation*} x^{15} - 1 = (x + 1)(x^2 + x + 1)(x^4 + x + 1)(x^4 + x^3 + 1)(x^4 + x^3 + x^2 + x + 1), \end{equation*}

donde cada uno de estos factores es irreducible. Sea \(\omega\) una raíz de \(1 + x + x^4\text{.}\) Le cuerpo de Galois \(\gf(2^4)\) es

\begin{equation*} \{ a_0 + a_1 \omega + a_2 \omega^2 + a_3 \omega^3 : a_i \in {\mathbb Z}_2 \text{ and } 1 + \omega + \omega^4 = 0 \}. \end{equation*}

Por el Ejemplo 22.8, \(\omega\) es una raíz 15 primitiva de la unidad. El polinomio minimal de \(\omega\) es \(m_1(x) = 1 + x + x^4\text{.}\) Es fácil ver que \(\omega^2\) y \(\omega^4\) también son raíces de \(m_1(x)\text{.}\) El polinomio minimal de \(\omega^3\) es \(m_2(x) = 1 + x + x^2 + x^3 + x^4\text{.}\) Por lo tanto,

\begin{equation*} g(x) = m_1(x) m_2(x) = 1 + x^4 + x^6 + x^7 + x^8 \end{equation*}

tiene raíces \(\omega\text{,}\) \(\omega^2\text{,}\) \(\omega^3\text{,}\) \(\omega^4\text{.}\) Como tanto \(m_1(x)\) como \(m_2(x)\) dividen a \(x^{15} - 1\text{,}\) el código BCH es un código \((15, 7)\text{.}\) Si \(x^{15} -1 = g(x)h(x)\text{,}\) entonces \(h(x) = 1 + x^4 + x^6 + x^7\text{;}\) por lo tanto, una matriz verificadora para este código es

\begin{equation*} \left( \begin{array}{ccccccccccccccc} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array} \right). \end{equation*}