Para ganar más información sobre un código particular y desarrollar técnicas más eficientes de codificación, decodificación y detección de errores, necesitaremos agregar mayor estructura a nuestros códigos. Una forma de lograr esto es pedir que el código además sea un grupo. Un código de grupo o código lineales un código que además es un subgrupo de \({\mathbb Z}_2^n\text{.}\)
Para verificar que un código es un código de grupo, solo necesitamos verificar una cosa. Si sumamos dos elementos en el código, el resultado debe ser una \(n\)-tupla que nuevamente esté en el código. No es necesario verificar que el elemento inverso de la \(n\)-tupla esté en el código, pues cada palabra del código es su propio inverso, tampoco es necesario verificar que \({\mathbf 0}\) sea una palabra del código. Por ejemplo,
\begin{equation*}
(11000101) + (11000101) = (00000000).
\end{equation*}
Ejemplo8.16
Supongamos que tenemos un código que consiste de las siguientes 7-tuplas:
\begin{align*}
&(0000000) & & (0001111) & & (0010101) & & (0011010)\\
&(0100110) & & (0101001) & & (0110011) & & (0111100)\\
&(1000011) & & (1001100) & & (1010110) & & (1011001)\\
&(1100101) & & (1101010) & & (1110000) & & (1111111).
\end{align*}
Es una tarea sencilla, aunque tediosa la de verificar que este código es un subgrupo de \({\mathbb Z}_2^7\) y que por lo tanto, es un código de grupo. Este código detecta un error y corrige un error, pero calcular todas las distancias entre pares de palabras del código para determinar que \(d_{\min} = 3\) es un proceso largo y tedioso. Es mucho más sencillo ver que el peso mínimo de todas las palabras no nulas es 3. Como veremos pronto, esto no es una coincidencia. Pero la relación entre pesos y distancias en un código particular es fuertemente dependiente del hecho que el código sea un grupo.
Lema8.17
Sean \({\mathbf x}\) e \({\mathbf y}\) \(n\)-tuplas binarias. Entonces \(w({\mathbf x} + {\mathbf y}) = d({\mathbf x}, {\mathbf y})\text{.}\)
Demostración
Supongamos que \({\mathbf x}\) e \({\mathbf y}\) son \(n\)-tuplas binarias. Entonces la distancia entre \({\mathbf x}\) e \({\mathbf y}\) es exactamente el número de lugares en los que difieren \({\mathbf x}\) e \({\mathbf y}\text{.}\) Pero \({\mathbf x}\) e \({\mathbf y}\) difieren en una coordenada particular si y solo si la suma es 1 en esa coordenada, pues
\begin{align*}
1 + 1 & = 0\\
0 + 0 & = 0\\
1 + 0 & = 1\\
0 + 1 & = 1.
\end{align*}
Así, el peso de la suma es igual a la distancia entre las dos palabras.
Teorema8.18
Sea \(d_{\min}\) la distancia mínima para un código de grupo \(C\text{.}\) Entonces \(d_{\min}\) es el mínimo de todos los pesos de las palabras no nulas en \(C\text{.}\) Es decir,
\begin{equation*}
d_{\min} = \min\{ w({\mathbf x}) : { {\mathbf x} \neq {\mathbf 0} } \}.
\end{equation*}
Demostración
Observe que
\begin{align*}
d_{\min} & = \min \{ d({\mathbf x},{\mathbf y}) : {\mathbf x}\neq{\mathbf y} \}\\
&= \min \{ d({\mathbf x},{\mathbf y}) : {\mathbf x}+{\mathbf y} \neq {\mathbf 0} \}\\
&= \min\{ w({\mathbf x} + {\mathbf y}) : {\mathbf x}+{\mathbf y}\neq {\mathbf 0} \}\\
& = \min\{ w({\mathbf z}) : {\mathbf z} \neq {\mathbf 0} \}.
\end{align*}
SubsecciónCódigos Lineales
¶Del Ejemplo 8.16, es ahora fácil verificar que el mínimo peso distinto de cero es 3; luego, el código realmente detecta y corrige todos los errores individuales. Hemos reducido el problema de encontrar “buenos” códigos al de generar códigos de grupo. Una forma fácil de generar códigos de grupo, es emplear un poco de teoría de matrices.
Se define el producto interno de dos \(n\)-tuplas binarias como
\begin{equation*}
{\mathbf x} \cdot {\mathbf y} = x_1 y_1 + \cdots + x_n y_n,
\end{equation*}
donde \({\mathbf x} = (x_1, x_2, \ldots, x_n)^{\rm t}\) e \({\mathbf y} = (y_1, y_2, \ldots, y_n)^{\rm t}\) son vectores columna. Por ejemplo, si \({\mathbf x} = (011001)^{\rm t}\) e \({\mathbf y} = (110101)^{\rm t}\text{,}\) entonces \({\mathbf x} \cdot {\mathbf y} = 0\text{.}\) También podemos pensar el producto interno como el producto de un vector fila con un vector columna; es decir,
\begin{align*}
{\mathbf x} \cdot {\mathbf y} & = {\mathbf x}^{\rm t} {\mathbf y}\\
& =
\begin{pmatrix}
x_1 & x_2 & \cdots & x_n
\end{pmatrix}
\begin{pmatrix}
y_1 \\ y_2 \\ \vdots \\ y_n
\end{pmatrix}\\
& = x_{1}y_{1} + x_{2}y_{2} + \cdots + x_{n}y_{n}.
\end{align*}
Ejemplo8.19
Supongamos que las palabras a ser codificadas consisten de todas las 3-tuples binarias y que nuestro mecanismo de codificación es el de control de paridad. Para codificar una 3-tupla arbitraria, agregamos un cuarto bit para obtener un número par de unos. Note que una \(n\)-tupla arbitraria \({\mathbf x} = (x_1, x_2, \ldots, x_n)^{\rm t}\) tiene un número par de unos exactamente cuando \(x_1 + x_2 + \cdots + x_n = 0\text{;}\) luego, una 4-tupla \({\mathbf x} = (x_1, x_2, x_3, x_4)^{\rm t}\) tiene un número par de unos si y solo si \(x_1+ x_2+ x_3+ x_4 = 0\text{,}\) o
\begin{equation*}
{\mathbf x} \cdot {\mathbf 1} = {\mathbf x}^{\rm t} {\mathbf 1} =
\begin{pmatrix}
x_1 & x_2 & x_3 & x_4
\end{pmatrix}
\begin{pmatrix}
1 \\ 1 \\ 1 \\ 1
\end{pmatrix} = 0.
\end{equation*}
Este ejemplo nos da esperanza de que haya una conexión entre las matrices y la teoría de códigos.
Sea \({\mathbb M}_{m \times n}({\mathbb Z}_2)\) el conjunto de todas las matrices de \(m \times n\) con coeficientes en \({\mathbb Z}_2\text{.}\) Hacemos operaciones entre las matrices como siempre excepto que todas nuestras operaciones de suma y producto ocurren en \({\mathbb Z}_2\text{.}\) Defina el espacio nulo de una matriz \(H \in {\mathbb M}_{m \times n}({\mathbb Z}_2)\) como el conjunto de todas las \(n\)-tuplas binarias \({\mathbf x}\) tales que \(H{\mathbf x} = {\mathbf 0}\text{.}\) Denotamos el espacio nulo de una matriz \(H\) por \(\Null(H)\text{.}\)
Ejemplo8.20
Supongamos que
\begin{equation*}
H =
\begin{pmatrix}
0 & 1 & 0 & 1 & 0 \\
1 & 1 & 1 & 1 & 0 \\
0 & 0 & 1 & 1 & 1
\end{pmatrix}.
\end{equation*}
Para que una 5-tupla \({\mathbf x} = (x_1, x_2, x_3, x_4, x_5)^{\rm t}\) esté en el espacio nulo de \(H\text{,}\) \(H{\mathbf x} = {\mathbf 0}\text{.}\) Equivalentemente, se debe satisfacer el siguiente sistema de ecuaciones:
\begin{align*}
x_2 + x_4 & = 0\\
x_1 + x_2 + x_3 + x_4 & = 0\\
x_3 + x_4 + x_5 & = 0.
\end{align*}
El conjunto de las 5-tuplas binarias que satisfacen estas ecuaciones es
\begin{equation*}
(00000) \qquad (11110) \qquad (10101) \qquad (01011).
\end{equation*}
Es fácil determiar que este código es un código de grupo.
Teorema8.21
Sea \(H\) en \({\mathbb M}_{m \times n}({\mathbb Z}_2)\text{.}\) Entonces el espacio nulo de \(H\) es un código de grupo.
Demostración
Como cada elemento de \({\mathbb Z}_2^n\) es su propio inverso, lo único que necesita ser verificado es la clausura. Sean \({\mathbf x}, {\mathbf y} \in {\rm Null}(H)\) para alguna matriz \(H\) en \({\mathbb M}_{m \times n}({\mathbb Z}_2)\text{.}\) Entonces \(H{\mathbf x} = {\mathbf 0}\) y \(H{\mathbf y} = {\mathbf 0}\text{.}\) Así
\begin{equation*}
H({\mathbf x}+{\mathbf y}) = H{\mathbf x} + H{\mathbf y} = {\mathbf 0} + {\mathbf 0} = {\mathbf 0}.
\end{equation*}
Luego, \({\mathbf x} + {\mathbf y}\) está en el espacio nulo de \(H\) y por lo tanto es una palabra del código.
Un código es un código lineal si está determinado por el espacio nulo de alguna matriz \(H \in {\mathbb M}_{m \times n}({\mathbb Z}_2)\text{.}\)
Ejemplo8.22
Sea \(C\) el código dado por la matriz
\begin{equation*}
H =
\begin{pmatrix}
0 & 0 & 0 & 1 & 1 & 1 \\
0 & 1 & 1 & 0 & 1 & 1 \\
1 & 0 & 1 & 0 & 0 & 1
\end{pmatrix}.
\end{equation*}
Supongamos que se recibe la 6-tupla \({\mathbf x} = (010011)^{\rm t}\text{.}\) Es simplemente cuestión de multiplicar matrices para determinar si \({\mathbf x}\) está o no en el código. Como
\begin{equation*}
H{\mathbf x} =
\begin{pmatrix}
0 \\ 1 \\ 1
\end{pmatrix},
\end{equation*}
la palabra recibida no está en el código. Debemos intentar corregirla o pedir que sea transmitida nuevamente.
