[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ón8.3Matrices Verificadora y Generadora

Debemos encontrar una forma sistemática de generar códigos lineales así como métodos rápidos de decodificación. Examinando las propiedades de la matriz \(H\) y eligiendo \(H\) cuidadosamente, es posible desarrollar métodos muy eficientes para codificar y decodificar mensajes. Con este objetivo, introduciremos la matriz generadora estándar y la matriz verificadora canónica.

Supongamos que \(H\) es una matriz de \(m \times n\) con coeficiente en \({\mathbb Z}_2\) y \(n \gt m\text{.}\) las últimas \(m\) columnas de la matriz forman la matriz identidad de \(m \times m\text{,}\) \(I_m\text{,}\) entonces la matriz es una matriz verificadora canónica. Más específicamente, \(H= (A \mid I_m)\text{,}\) donde \(A\) es la matriz de \(m \times (n-m)\)

\begin{equation*} \begin{pmatrix} a_{11} & a_{12} & \cdots & a_{1,n-m} \\ a_{21} & a_{22} & \cdots & a_{2,n-m} \\ \vdots & \vdots & \ddots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{m,n-m} \end{pmatrix} \end{equation*}

y \(I_m\) es la matriz identidad de \(m \times m\)

\begin{equation*} \begin{pmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{pmatrix}. \end{equation*}

Con cada matriz verificadora canónica podemos asociar una matriz generadora estándar de \(n \times (n-m)\)

\begin{equation*} G = \left( \frac{I_{n-m}}{A} \right). \end{equation*}

Nuestro objetivo será mostrar que existe un \(\mathbf x\) que satisfaga \(G {\mathbf x} = {\mathbf y}\) si y solo si \(H{\mathbf y} = {\mathbf 0}\text{.}\) dado un bloque \({\mathbf x}\) a ser codificado, la matriz \(G\) nos permitirá codificarlo rápidamente a una palabra \({\mathbf y}\) del código lineal.

Ejemplo8.23

Supongamos que tenemos las siguientes ocho palabras por codificar:

\begin{equation*} (000), (001), (010), \ldots, (111). \end{equation*}

Para

\begin{equation*} A = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix}, \end{equation*}

la matrices generadora estándar y verificadora canónica son

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

y

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

respectivamente.

Observe que las filas en \(H\) representan las verificaciones de paridad en ciertas posiciones de las 6-tuplas. Los unos en la matriz identidad sirven como verificadores de paridad para los unos en la misma fila. Si \({\mathbf x} = (x_1, x_2, x_3, x_4, x_5, x_6)\text{,}\) entonces

\begin{equation*} {\mathbf 0} = H{\mathbf x} = \begin{pmatrix} x_2 + x_3 + x_4 \\ x_1 + x_2 + x_5\\ x_1 + x_3 + x_6 \end{pmatrix}, \end{equation*}

lo que produce un sistema de ecuaciones:

\begin{align*} x_2 + x_3 + x_4 & = 0\\ x_1 + x_2 + x_5 & = 0\\ x_1 + x_3 + x_6 & = 0. \end{align*}

Acá \(x_4\) sirve como bit de control para \(x_2\) y \(x_3\text{;}\) \(x_5\) es un bit de control para \(x_1\) y \(x_2\text{;}\) y \(x_6\) es un bit de control para \(x_1\) y \(x_3\text{.}\) La matriz identidad impide que \(x_4\text{,}\) \(x_5\text{,}\) y \(x_6\) tengan que controlarse entre ellos. Luego, \(x_1\text{,}\) \(x_2\text{,}\) y \(x_3\) pueden ser arbitrarios pero \(x_4\text{,}\) \(x_5\text{,}\) y \(x_6\) deben ser escogidos de manera de asegurar las paridades respectivas. Se calcula fácilmente que el espacio nulo de \(H\) es

\begin{equation*} \begin{array}{cccc} (000000) & (001101) & (010110) & (011011) \\ (100011) & (101110) & (110101) & (111000). \end{array} \end{equation*}

Una forma aún más fácil de calcular el espacio nulo es con la matriz generadora \(G\) (Tabla 8.24).

Palabra de Mensaje \(\mathbf x\) Palabra del código \(G \mathbf x\)
000 000000
001 001101
010 010110
011 011011
100 100011
101 101110
110 110101
111 111000
Cuadro8.24Un código generado por una matriz

Dejamos la demostración de este teorema como ejercicio. A la luz del teorema, los primeros \(n - m\) bits de \({\mathbf x}\) se denominan bits de información y los últimos \(m\) bits se denominan bits de verificación. En el Ejemplo 8.23, los primeros tres bits son de información y los últimos tres son bits de verificación.

Sean \(G {\mathbf x}_1 = {\mathbf y}_1\) y \(G {\mathbf x}_2 ={\mathbf y}_2\) dos palabras del código. Entonces \({\mathbf y}_1 + {\mathbf y}_2\) está en \(C\) pues

\begin{equation*} G( {\mathbf x}_1 + {\mathbf x}_2) = G {\mathbf x}_1 + G {\mathbf x}_2 = {\mathbf y}_1 + {\mathbf y}_2. \end{equation*}

Debemos mostrar además que dos bloques de mensaje diferentes no pueden ser codificados a la misma palabra del código. Es decir, debemos mostrar que si \(G {\mathbf x} = G {\mathbf y}\text{,}\) entonces \({\mathbf x} = {\mathbf y}\text{.}\) Supongamos que \(G {\mathbf x} = G {\mathbf y}\text{.}\) Entonces

\begin{equation*} G {\mathbf x} - G {\mathbf y} = G( {\mathbf x} - {\mathbf y}) = {\mathbf 0}. \end{equation*}

Pero las primeras \(k\) coordenadas en \(G( {\mathbf x} - {\mathbf y})\) son exactamente \(x_1 -y_1, \ldots, x_k - y_k\text{,}\) pues están determinadas por la matriz identidad, \(I_k\text{,}\) que es parte de \(G\text{.}\) Luego, \(G( {\mathbf x} - {\mathbf y}) = {\mathbf 0}\) si y solo si \({\mathbf x} = {\mathbf y}\text{.}\)

Antes de demostrar la relación entre la matriz verificadora canónica y la matriz generadora estándar, demostraremos un lema.

Sea \(C = HG\text{.}\) El coeficiente \(ij\)th de \(C\) es

\begin{align*} c_{ij} & = \sum_{k=1}^n h_{ik} g_{kj}\\ & = \sum_{k=1}^{n-m} h_{ik} g_{kj} + \sum_{k=n-m+1}^n h_{ik} g_{kj}\\ & = \sum_{k=1}^{n-m} a_{ik} \delta_{kj} + \sum_{k=n-m+1}^n \delta_{i-(m-n),k} a_{kj}\\ & = a_{ij} + a_{ij}\\ & = 0, \end{align*}

donde

\begin{equation*} \delta_{ij} = \begin{cases} 1, & i = j \\ 0, & i \neq j \end{cases} \end{equation*}

es la delta de Kronecker.

Primero supongamos que \({\mathbf y} \in C\text{.}\) Entonces \(G {\mathbf x} = {\mathbf y}\) para algún \({\mathbf x} \in {\mathbb Z}_2^m\text{.}\) Por el Lema 8.27, \(H {\mathbf y} = HG {\mathbf x} = {\mathbf 0}\text{.}\)

Recíprocamente, supongamos que \({\mathbf y} = (y_1, \ldots, y_n)^{\rm t}\) está en el espacio nulo de \(H\text{.}\) Debemos encontrar \({\mathbf x}\) en \({\mathbb Z}_2^{n-m}\) tal que \(G {\mathbf x}^{\rm t} = {\mathbf y}\text{.}\) Como \(H {\mathbf y} = {\mathbf 0}\text{,}\) se debe satisfacer el siguiente conjunto de ecuaciones:

\begin{align*} a_{11} y_1 + a_{12} y_2 + \cdots + a_{1, n-m} y_{n-m} + y_{n-m+1} & = 0\\ a_{21} y_1 + a_{22} y_2 + \cdots + a_{2, n-m} y_{n-m} + y_{n-m+1} & = 0\\ & \vdots \\ a_{m1} y_1 + a_{m2} y_2 + \cdots + a_{m, n-m} y_{n-m} + y_{n-m+1} & = 0. \end{align*}

Equivalentemente, \(y_{n-m+1}, \ldots, y_n\) están determinados por \(y_1, \ldots, y_{n-m}\text{:}\)

\begin{align*} y_{n-m+1} & = a_{11} y_1 + a_{12} y_2 + \cdots + a_{1, n-m} y_{n-m}\\ y_{n-m+1} & = a_{21} y_1 + a_{22} y_2 + \cdots + a_{2, n-m} y_{n-m}\\ & \vdots\\ y_{n-m+1} & = a_{m1} y_1 + a_{m2} y_2 + \cdots + a_{m, n-m} y_{n-m}. \end{align*}

Por ende podemos tomar \(x_i = y_i\) para \(i= 1, \ldots, n - m\text{.}\)

Sería bueno poder calcular la distancia mínima de un código lineal directamente a partir de su matriz \(H\) para poder determinar las capacidades de detección y corrección de errores del código. Supongamos que

\begin{align*} {\mathbf e}_1 & = (100 \cdots 00)^{\rm t}\\ {\mathbf e}_2 & = (010 \cdots 00)^{\rm t}\\ & \vdots\\ {\mathbf e}_n & = (000 \cdots 01)^{\rm t} \end{align*}

son la \(n\)-tuplas en \({\mathbb Z}_2^n\) de peso 1. Para una matriz binaria \(H\) de \(m \times n\text{,}\) \(H{\mathbf e}_i\) es exactamente la columna \(i\)-ésima de la matriz \(H\text{.}\)

Ejemplo8.29

Observe que

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

Enunciamos el resultado en la siguiente proposición y dejamos su demostración como ejercicio.

Supongamos que \({\rm Null}(H)\) es un código que detecta un error. Entonces la distancia mínima del código debe ser al menos 2. Como el espacio nulo es un código de grupo, es necesario que el código no tenga ninguna palabra de peso menor a 2 aparte de la palabra cero. Es decir, \({\mathbf e}_i\) no debe ser una palabra del código para \(i = 1, \ldots, n\text{.}\) Como \(H{\mathbf e}_i\) es la \(i\)-ésima columna de \(H\text{,}\) la \(i\)-ésima columna no tiene puros ceros.

Recíprocamente, supongamos que ninguna columna de \(H\) es la columna cero. Por la Proposición 8.30, \(H{\mathbf e}_i \neq {\mathbf 0}\text{;}\) luego, la distancia mínima del código es al menos 2, y el código tiene la capacidad de detectar un error..

Ejemplo8.32

Si consideramos las matrices

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

y

\begin{equation*} H_2 = \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{pmatrix}, \end{equation*}

entonces el espacio nulos de \(H_1\) es un código que detecta un error y el espacio nulo de \(H_2\) no lo es.

Podemos mejorar el Teorema 8.31. Este teorema nos entrega condiciones sobre la matriz \(H\) que nos dicen cuándo el peso mínimo del código formado por el espacio nulo de \(H\) es 2. También podemos determinar cuándo la distancia mínima de un código lineal es 3 examinando la matriz correspondiente.

Ejemplo8.33

Si hacemos

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

y queremos determinar si \(H\) es la matriz verificadora canónica para un código corrector de un error, es necesario asegurarse que \({\rm Null}(H)\) no contenga ninguna 4-tupla de peso 2. Es decir, \((1100)\text{,}\) \((1010)\text{,}\) \((1001)\text{,}\) \((0110)\text{,}\) \((0101)\text{,}\) y \((0011)\) no deben estar en \({\rm Null}(H)\text{.}\) El próximo teorema establece que podemos saber si el código determinado por \(H\) es corrector de errores examinando las columnas de \(H\text{.}\) Note en este ejemplo que no solo \(H\) no tiene columnas nulas, sino que tampoco tiene columnas repetidas.

La \(n\)-tupla \({\mathbf e}_{i} +{\mathbf e}_{j}\) tiene unos en la posiciones \(i\)-ésima y \(j\)-ésima y ceros en las demás, y \(w( {\mathbf e}_{i} +{\mathbf e}_{j}) = 2\) para \(i \neq j\text{.}\) Como

\begin{equation*} {\mathbf 0} = H({\mathbf e}_{i} +{\mathbf e}_{j}) = H{\mathbf e}_{i} + H{\mathbf e}_{j} \end{equation*}

Solo puede ocurrir si la \(i\)-ésima y la \(j\)-ésima columnas son idénticas. Como no contiene palabras de peso menor o igual a 2, el espacio nulo de \(H\) es un código corrector de un error.

Supongamos ahora que tenemos una matriz verificadora canónica \(H\) con tres filas. Nos podemos preguntar cuántas columnas le podemos agregar a la matriz y seguir teniendo un espacio nulo que sea un código que detecte y corrija un error. Como cada columna tiene tres entradas, hay \(2^3 = 8\) columnas diferentes posibles. No podemos agregar las columnas

\begin{equation*} \begin{pmatrix} 0 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}, \begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}. \end{equation*}

Podemos entonces agregar hasta cuatro columnas manteniendo una distancia mínima de 3.

En general, si \(H\) es una matriz verificadora canónica de \(m \times n\text{,}\) entonces hay \(n-m\) posiciones de información en cada palabra del código. Cada columna tiene \(m\) bits, así es que hay \(2^m\) posibles columnas diferentes. Es necesario que las columnas \({\mathbf 0}, {\mathbf e}_1, \ldots, {\mathbf e}_m\) sean excluidas, dejando \(2^m - (1 + m)\) columnas restantes para información si queremos mantener la habilidad de no solo detectar sino también corregir un error.