AATA Matrices Verificadora y Generadora

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*}$

$\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

Teorema8.25

Si $H \in {\mathbb M}_{m \times n}({\mathbb Z}_2)$ es una matriz verificadora canónica, entonces ${\rm Null}(H)$ consiste de todas las ${\mathbf x} \in {\mathbb Z}_2^n$ cuyos primeros $n-m$ bits son arbitrarios pero cuyos últimos $m$ bits están determinados por $H{\mathbf x} = {\mathbf 0}\text{.}$ Cada uno de los últimos $m$ bits sirve como control de paridad para algunos de los primeros $n-m$ bits. Luego, $H$ da lugar a un código de bloque $(n, n-m)\text{.}$

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.

Teorema8.26

Supongamos que $G$ es una matriz generadora estándar de $n \times k\text{.}$ Entonces $C = \left\{{\mathbf y} : G{\mathbf x} ={\mathbf y}\text{ para }{\mathbf x}\in {\mathbb Z}_2^k\right\}$ es un código de bloque $(n,k)\text{.}$ Más específicamente, $C$ es un código de grupo.

Demostració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.

Lema8.27

Sea $H = (A \mid I_m )$ una matriz verificadora canónica de $m \times n$ y $G = \left( \frac{I_{n-m} }{A} \right)$ la correspondiente matriz generadora estándar de $n \times (n-m)\text{.}$ Entonces $HG = {\mathbf 0}\text{.}$

Demostración

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.

Teorema8.28

Sea $H = (A \mid I_m )$ una matriz verificadora canónica de $m \times n$ y sea $G = \left( \frac{I_{n-m} }{A} \right)$ la correspondiente matriz generadora estándar de $n \times (n-m)\text{.}$ Sea $C$ el código generado por $G\text{.}$ Entonces ${\mathbf y}$ está en $C$ si y solo si $H {\mathbf y} = {\mathbf 0}\text{.}$ En particular, $C$ es un código lineal con matriz verificadora canónica $H\text{.}$

Demostración

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.

Proposición8.30

Sea ${\mathbf e}_i$ la $n$ -tupla binaria con un $1$ en la $i$ -ésima coordenada y $0$ en todas las demás y supongamos que $H \in {\mathbb M}_{m \times n}({\mathbb Z}_2)\text{.}$ Entonces $H{\mathbf e}_i$ es la $i$ -ésima columna de la matriz $H\text{.}$

Teorema8.31

Sea $H$ una matriz binaria de $m \times n\text{.}$ Entonces el espacio nulo de $H$ es un código que puede detectar un error si y solo si ninguna columna de $H$ consiste solamente de ceros.

Demostración

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*}$

$\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.

Teorema8.34

Sea $H$ una matriz binaria. El espacio nulo de $H$ es un código corrector de un error si $H$ no contiene columnas de puros ceros ni dos columnas iguales.

Demostración

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.