22.2: Códigos polinomiales

Con conocimiento de anillos polinomiales y campos finitos, ahora es posible derivar códigos más sofisticados que los del Capítulo 8. Primero recordemos que un código\((n, k)\) -block consiste en una función de codificación uno a uno\(E:{\mathbb Z}^{k}_{2} \rightarrow {\mathbb Z}^{n}_{2}\) y una función de decodificación\(D:{\mathbb Z}^{n}_{2} \rightarrow {\mathbb Z}^{k}_{2}\text{.}\) El código corrige errores si\(D\) está en. Un código es un código lineal si es el espacio nulo de una matriz\(H \in {\mathbb M}_{k \times n}({\mathbb Z}_2)\text{.}\)

Nos interesa una clase de códigos conocidos como códigos cíclicos. Dejar\(\phi : {\mathbb Z}_2^k \rightarrow {\mathbb Z}_2^n\) ser un código binario\((n,k)\) -block. Entonces\(\phi\) es un código cíclico si por cada palabra de código\((a_1, a_2, \ldots, a_n )\text{,}\) la\(n\) -tupla desplazada cíclicamente\((a_n, a_1, a_2, \ldots, a_{n - 1} )\) es también una palabra de código. Los códigos cíclicos son particularmente fáciles de implementar en una computadora usando registros de desplazamiento [2, 3].

Ejemplo\(22.14\).

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

\[ 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{and} \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}\text{.} \nonumber \]

Solución

Los mensajes en el primer código se codifican de la siguiente manera:

\[ \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} \nonumber \]

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

\[ \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} \nonumber \]

Este código no puede ser cíclico, ya que\((101101)\) es una palabra clave pero no\((011011)\) es una palabra clave.

Códigos polinomiales

Nos gustaría encontrar un método fácil de obtener códigos lineales cíclicos. Para lograr esto, podemos usar nuestro conocimiento de campos finitos y anillos polinomiales sobre\({\mathbb Z}_2\text{.}\) Cualquier binaria\(n\) -tupla puede interpretarse como un polinomio en\({\mathbb Z}_2[x]\text{.}\) Declarado de otra manera, la\(n\) -tupla\((a_0, a_1, \ldots, a_{n - 1} )\) corresponde al polinomio

\[ f(x) = a_0 + a_1 x + \cdots + a_{n-1} x^{n - 1}\text{,} \nonumber \]

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

\[ 1 + 0 x + 0 x^2 + 1 x^3 + 1 x^4 = 1 + x^3 + x^4\text{.} \nonumber \]

Por el contrario, con cualquier polinomio\(f(x) \in {\mathbb Z}_2[x]\) con\(\deg f(x) \lt n\) 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]\) 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 polinomio correspondiente en\({\mathbb Z}_2[x]\text{.}\) Para codificar\(f(x)\text{,}\) multiplicamos por\(g(x)\text{.}\) Las palabras de código en\(C\) son todos esos polinomios en\({\mathbb Z}_2[x]\) de grado menor\(n\) que los que son divisibles por\(g(x)\text{.}\) Códigos obtenidos de esta manera se denominan códigos polinomiales.

Ejemplo\(22.15\).

Si lo dejamos\(g(x)= 1 + x^3\text{,}\) podemos definir un\((6,3)\) -code de la\(C\) siguiente manera. Para codificar una\(3\) -tupla\(( a_0, a_1, a_2 )\text{,}\) multiplicamos el polinomio correspondiente\(f(x) = a_0 + a_1 x + a_2 x^2\) por\(1 + x^3\text{.}\) Estamos definiendo un mapa\(\phi : {\mathbb Z}_2^3 \rightarrow {\mathbb Z}_2^6\) por\(\phi : f(x) \mapsto g(x) f(x)\text{.}\) Es fácil comprobar que este mapa es un homomorfismo grupal. 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 (ver Ejercicio\(20.5.15\), Capítulo 20). Vamos a calcular el núcleo de\(\phi\text{.}\) Observar 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\ texto {.} \ end {alinear*}

Solución

Dado que los polinomios sobre un campo 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 uno a uno.

Para calcular una matriz generadora solo\(C\text{,}\) necesitamos examinar la forma en que\(x^2\) se codifican los polinomios\(1\text{,}\)\(x\text{,}\) y:

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

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

\[ H = \begin{pmatrix} 1 & 0 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 \end{pmatrix}\text{.} \nonumber \]

Dado que el peso más pequeño de cualquier palabra de código distinta de cero es\(2\text{,}\) este código tiene la capacidad de detectar todos los errores individuales.

Los anillos de polinomios tienen una gran estructura; por lo tanto, nuestro objetivo inmediato es establecer un vínculo entre los códigos polinomiales y la teoría de anillos. Recordemos que\(x^n - 1 = (x - 1)( x^{n - 1} + \cdots + x + 1)\text{.}\) El anillo del factor

\[ R_n = {\mathbb Z}_2[x]/ \langle x^n - 1 \rangle \nonumber \]

puede considerarse como el anillo de polinomios de la forma

\[ f(t) = a_0 + a_1 t + \cdots + a_{n - 1} t^{n - 1} \nonumber \]

que satisfacen la condición\(t^n = 1\text{.}\) Es un ejercicio fácil para demostrarlo\({\mathbb Z}_2^n\) y\(R_n\) son isomórficos como espacios vectoriales. A menudo identificaremos elementos\({\mathbb Z}_2^n\) con elementos de esta\({\mathbb Z}[x] / \langle x^n - 1 \rangle\text{.}\) manera podemos interpretar un código lineal como un subconjunto de\({\mathbb Z}[x] / \langle x^n - 1 \rangle\text{.}\)

La estructura de anillo adicional en los códigos polinomiales es muy poderosa en la descripción de códigos cíclicos. Un desplazamiento cíclico de una\(n\) -tupla se puede describir mediante multiplicación polinómica. Si\(f(t) = a_0 + a_1 t + \cdots + a_{n - 1} t^{n - 1}\) es un polinomio de código en\(R_n\text{,}\) entonces

\[ tf(t) = a_{n - 1} + a_0 t + \cdots + a_{n - 2} t^{n - 1} \nonumber \]

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

Teorema\(22.16\).

Un código lineal\(C\) en\({\mathbb Z}_2^n\) es cíclico si y solo si es un ideal en\(R_n = {\mathbb Z}[x] / \langle x^n - 1 \rangle\text{.}\)

Prueba

Dejar\(C\) ser un código cíclico lineal y supongamos que\(f(t)\) está en\(C\text{.}\) Entonces también\(t f(t)\) debe estar en\(C\text{.}\) Consecuentemente,\(t^k f(t)\) está en\(C\) para todos\(k \in {\mathbb N}\text{.}\) Dado que\(C\) es un código lineal, cualquier combinación lineal de las palabras de código también\(f(t), tf(t), t^2f(t), \ldots, t^{n-1}f(t)\) es una palabra de código; por lo tanto , por cada polinomio\(p(t)\text{,}\)\(p(t)f(t)\) está en\(C\text{.}\) Por lo tanto,\(C\) es un ideal.

Por el contrario, deja\(C\) ser 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 clave en\(C\text{.}\) Entonces\(t f(t)\) es una palabra de código en\(C\text{;}\) eso es,\((a_1, \ldots, a_{n-1}, a_0)\) está en\(C\text{.}\)

El teorema nos\(22.16\) dice que conocer los ideales de\(R_n\) equivale a conocer los códigos cíclicos lineales en\({\mathbb Z}_2^n\text{.}\) Afortunadamente, los ideales en\(R_n\) son fáciles de describir. El homomorfismo natural del anillo\(\phi : {\mathbb Z}_2[x] \rightarrow R_n\) definido por\(\phi[f(x)] = f(t)\) es un homomorfismo surytivo. El núcleo de\(\phi\) es el ideal generado\(x^n - 1\text{.}\) por Por Teorema\(16.34\), cada ideal\(C\) en\(R_n\) es de la forma\(\phi(I)\text{,}\) donde\(I\) es un ideal en\({\mathbb Z}_2[x]\) que contiene\(\langle x^n - 1 \rangle\text{.}\) Por Teorema\(17.20\), sabemos que cada ideal\(I\) en\({\mathbb Z}_2[x]\) es un ideal principal, ya que\({\mathbb Z}_2\) es un campo. Por lo tanto,\(I = \langle g(x) \rangle\) para algún polinomio monico único en\({\mathbb Z}_2[x]\text{.}\) Dado que\(\langle x^n - 1 \rangle\) está contenido en\(I\text{,}\) él debe ser el caso que\(g(x)\) divide\(x^n - 1\text{.}\) En consecuencia, cada ideal\(C\) en\(R_n\) es de la forma

\[ C = \langle g(t) \rangle = \{ f(t)g(t) : f(t) \in R_n \text{ and } g(x) \mid (x^n - 1) \text{ in } {\mathbb Z}_2[x] \}\text{.} \nonumber \]

El polinomio monico único del grado más pequeño que genera\(C\) se denomina polinomio generador mínimo de\(C\text{.}\)

Ejemplo\(22.17\).

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

\[ x^7 - 1 = (1 + x)(1 + x + x^3)(1+ x^2 + x^3)\text{.} \nonumber \]

Solución

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

\[ 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}\text{.} \nonumber \]

En general, podemos determinar una matriz generadora para un\((n, k)\) -code\(C\) por la manera en que\(t^k\) se codifican los elementos. Dejar\(x^n - 1 = g(x) h(x)\) entrar\({\mathbb Z}_2[x]\text{.}\) Si\(g(x) = g_0 + g_1 x + \cdots + g_{n-k} x^{n-k}\) y\(h(x) = h_0 + h_1 x + \cdots + h_k x^k\text{,}\) luego la\(n \times k\) matriz

\[ 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} \nonumber \]

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

\[ 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}\text{.} \nonumber \]

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

Proposición\(22.18\).

Dejar\(C = \langle g(t) \rangle\) ser un código cíclico en\(R_n\) y supongamos que\(x^n - 1 = g(x) h(x)\text{.}\) Entonces\(G\) y\(H\) son generador y matrices de verificación de paridad para\(C\text{,}\) respectivamente. Además,\ (HG = 0\ text { . }\

Ejemplo\(22.19\).

En Ejemplo\(22.17\),

\[ x^7 - 1 = g(x) h(x) = (1 + x + x^3)(1 + x + x^2 + x^4)\text{.} \nonumber \]

Solución

Por lo tanto, una matriz de comprobación de paridad para este código es

\[ 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}\text{.} \nonumber \]

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

\[ \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} \nonumber \]

se llama la matriz de Vandermonde. El determinante de esta matriz se llama determinante Vandermonde. Necesitaremos el siguiente lema en nuestra investigación de códigos cíclicos.

Lema\(22.20\).

Dejen\(\alpha_1, \ldots, \alpha_n\) ser elementos en un campo\(F\) con\(n \geq 2\text{.}\) Entonces

\[ \det \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} = \prod_{1 \leq j \lt i \leq n} (\alpha_i - \alpha_j)\text{.} \nonumber \]

En particular, si los\(\alpha_i\) 's son distintos, entonces el determinante es distinto de cero.

Prueba

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

\[ 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}\text{.} \nonumber \]

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

\[ p(x) = (x - \alpha_1)(x - \alpha_2) \cdots (x - \alpha_{n-1}) \beta\text{,} \nonumber \]

donde

\[ \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}\text{.} \nonumber \]

Por nuestra hipótesis de inducción,

\[ \beta = (-1)^{n+n} \prod_{1 \leq j \lt i \leq n - 1} (\alpha_i - \alpha_j)\text{.} \nonumber \]

Si dejamos que\(x = \alpha_n\text{,}\) el resultado ahora siga inmediatamente.

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

Teorema\(22.21\).

Dejar\(C = \langle g(t) \rangle\) ser un código cíclico en\(R_n\) y supongamos que\(\omega\) es una raíz primitiva\(n\) th de unidad sobre\({\mathbb Z}_2\text{.}\) Si los poderes\(s\) consecutivos de\(\omega\) son raíces de \(g(x)\text{,}\)entonces la distancia mínima de\(C\) es al menos\(s + 1\text{.}\)

Prueba

Supongamos que

\[ g( \omega^r) = g(\omega^{r + 1}) = \cdots = g( \omega^{r + s - 1}) = 0\text{.} \nonumber \]

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

\[ f(x) = a_{i_0} x^{i_0} + a_{i_1} x^{i_1} + \cdots + a_{i_{s - 1}} x^{i_{s - 1}} \nonumber \]

ser algún polinomio en\(C\text{.}\) Será suficiente para demostrar que todos los\(a_i\)'s deben ser 0. Desde

\[ g( \omega^r) = g(\omega^{r + 1}) = \cdots = g( \omega^{r + s - 1}) = 0 \nonumber \]

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

\[ f( \omega^r) = f(\omega^{r + 1}) = \cdots = f( \omega^{r + s - 1}) = 0\text{.} \nonumber \]

Equivalentemente, tenemos el siguiente sistema de ecuaciones:

\ begin {alinear*} 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} (omeg\ a^ {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\ texto {.} \ end {alinear*}

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

\ begin {alinear*} (\ 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_0}) ^ {r + s - 1} x_0 + (\ omega^ {i_0} _1}) ^ {r + s - 1} x_1 + \ cdots + (\ omega^ {i_ {s - 1}}) ^ {r + s - 1} x_ {n - 1} & = 0\ text {.} \ end {alinear*}

Sin embargo, este sistema tiene una solución única, ya que el determinante de la matriz

\[ \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} \nonumber \]

se puede demostrar que es distinto de cero usando Lema\(22.20\) y las propiedades básicas de los determinantes (Ejercicio). Por lo tanto, esta solución debe ser\(a_{i_0} = a_{i_1} = \cdots = a_{i_{s - 1}} = 0\text{.}\)

Códigos BCH

Algunos de 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, son códigos BCH. Tanto los sistemas de comunicación europeos como los transatlánticos utilizan códigos BCH. Las palabras informativas a codificar son de longitud\(231\text{,}\) y\(24\) se utiliza un polinomio de grado para generar el código. Ya\(231 + 24 = 255 = 2^8-1\text{,}\) que estamos tratando con un código\((255, 231)\) -block. Este código BCH detectará seis errores y tiene una tasa de fallas 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 menor grado que tenga las mayores capacidades de detección y corrección de errores. Dejemos\(d = 2r + 1\) para algunos\(r \geq 0\text{.}\) Supongamos que\(\omega\) es\(n\) una raíz primitiva de unidad sobre\({\mathbb Z}_2\text{,}\) y deja\(m_i(x)\) ser el polinomio mínimo sobre\({\mathbb Z}_2\) de\(\omega^i\text{.}\) Si

\[ g(x) = \lcm[ m_1(x), m_{2}(x), \ldots, m_{2r}(x)]\text{,} \nonumber \]

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

Teorema\(22.22\).

Dejar\(C = \langle g(t) \rangle\) ser un código cíclico en\(R_n\text{.}\) Las siguientes declaraciones son equivalentes.

1. El código\(C\) es un código BCH cuya distancia mínima es al menos\(d\text{.}\)
2. Un polinomio de código\(f(t)\) está en\(C\) si y solo si\(f( \omega^i) = 0\) para\(1 \leq i \lt d\text{.}\)
3. La matriz
   \[ H = \begin{pmatrix} 1 & \omega & \omega^2 & \cdots & \omega^{n-1}\\ 1 & \omega^2 & \omega^{4} & \cdots & \omega^{(n-1)(2)} \\ 1 & \omega^3 & \omega^{6} & \cdots & \omega^{(n-1)(3)} \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ 1 & \omega^{2r} & \omega^{4r} & \cdots & \omega^{(n-1)(2r)} \end{pmatrix} \nonumber \]

   es una matriz de comprobación de paridad para\(C\text{.}\)

Prueba

(1)\(\Rightarrow\) (2). Si\(f(t)\) está en\(C\text{,}\) entonces\(g(x) \mid f(x)\) en\({\mathbb Z}_2[x]\text{.}\) Por lo tanto, para\(i = 1, \ldots, 2r\text{,}\)\(f( \omega^i) = 0\) desde\(g( \omega^i ) = 0\text{.}\) Inversamente, supongamos que\(f( \omega^i) = 0\) para\(1 \leq i \leq d\text{.}\) Entonces\(f(x)\) es divisible por cada\(m_i(x)\text{,}\) puesto\(m_i(x)\) es el polinomio mínimo de\(\omega^i\text{.}\) Por lo tanto,\(g(x) \mid f(x)\) por la definición de\(g(x)\text{.}\) Consecuentemente,\(f(x)\) es una palabra clave.

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

\[ 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 \nonumber \]

exactamente cuando\(f(t)\) está en\(C\text{.}\) Así,\(H\) es una matriz de verificación de paridad para\(C\text{.}\)

(3)\(\Rightarrow\) (1). Por (3), un polinomio de código\(f(t) = a_0 + a_1 t + \cdots + a_{n - 1} t^{n - 1}\) está\(C\) exactamente en cuándo\(f(\omega^i) = 0\) para\(i = 1, \ldots, 2r\text{.}\) El polinomio más pequeño de este tipo es\(g(t) = \lcm[ m_1(t),\ldots, m_{2r}(t)]\text{.}\) Por lo tanto,\(C = \langle g(t) \rangle\text{.}\)

Ejemplo\(22.23\).

Es fácil verificar que\(x^{15} - 1 \in {\mathbb Z}_2[x]\) tenga una factorización

\[ 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)\text{,} \nonumber \]

donde cada uno de los factores es un polinomio irreducible. Deja\(\omega\) ser una raíz de\(1 + x + x^4\text{.}\) El campo Galois\(\gf(2^4)\) es

\[ \{ 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 \}\text{.} \nonumber \]

Solución

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

\[ g(x) = m_1(x) m_2(x) = 1 + x^4 + x^6 + x^7 + x^8 \nonumber \]

tiene raíces\(\omega\text{,}\)\(\omega^2\text{,}\)\(\omega^3\text{,}\)\(\omega^4\text{.}\) Ya que ambos\(m_1(x)\) y\(m_2(x)\) dividir\(x^{15} - 1\text{,}\) el código BCH es un\((15, 7)\) -código. 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 de verificación de paridad para este código es

\[ \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)\text{.} \nonumber \]

 

Teorema 22.22.

 

1.  

 

Comprobante.

 

Ejemplo 22.23.