8.4: Matrices Generadoras y Comprobación de Paridad
- Page ID
- 111133
Necesitamos encontrar una forma sistemática de generar códigos lineales así como métodos rápidos de decodificación. Al examinar las propiedades de una matriz\(H\) y al elegir cuidadosamente\(H\text{,}\) es posible desarrollar métodos muy eficientes de codificación y decodificación de mensajes. Para ello, se introducirán generadores estándar y matrices canónicas de comprobación de paridad.
Supongamos que\(H\) es una\(m \times n\) matriz con entradas en\({\mathbb Z}_2\) y\(n \gt m\text{.}\) Si las últimas\(m\) columnas de la matriz forman la matriz de\(m \times m\) identidad,\(I_m\text{,}\) entonces la matriz es una matriz canónica de verificación de paridad. Más específicamente,\(H= (A \mid I_m)\text{,}\) dónde\(A\) está la\(m \times (n-m)\) matriz
\[ \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} \nonumber \]
y\(I_m\) es la matriz\(m \times m\) de identidad
\[ \begin{pmatrix} 1 & 0 & \cdots & 0 \\ 0 & 1 & \cdots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \cdots & 1 \end{pmatrix}\text{.} \nonumber \]
Con cada matriz canónica de comprobación de paridad podemos asociar una matriz generadora\(n \times (n-m)\) estándar
\[ G = \left( \frac{I_{n-m}}{A} \right)\text{.} \nonumber \]
Nuestro objetivo será mostrar que\(G {\mathbf x} = {\mathbf y}\) existe un\(\mathbf x\) satisfactorio si y solo si\(H{\mathbf y} = {\mathbf 0}\text{.}\) Dado un bloque de mensaje\({\mathbf x}\) a codificar, la matriz nos\(G\) permitirá codificarlo rápidamente en una palabra clave lineal\({\mathbf y}\text{.}\)
Supongamos que tenemos las siguientes ocho palabras para ser codificadas:
\[ (000), (001), (010), \ldots, (111)\text{.} \nonumber \]
Para
\[ A = \begin{pmatrix} 0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix}\text{,} \nonumber \]
el generador estándar asociado y las matrices de comprobación de paridad canónicas son
\[ G= \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 1 & 1 \\ 1 & 1 & 0 \\ 1 & 0 & 1 \end{pmatrix} \nonumber \]
y
\[ H = \begin{pmatrix} 0 & 1 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 \end{pmatrix}\text{,} \nonumber \]
respectivamente.
Solución
Observe que las filas en\(H\) representan las comprobaciones de paridad en ciertas posiciones de bits en una\(6\) -tupla. Las\(1\) s en la matriz de identidad sirven como verificaciones de paridad para las\(1\) s en la misma fila. Si\({\mathbf x} = (x_1, x_2, x_3, x_4, x_5, x_6)\text{,}\) entonces
\[ {\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}\text{,} \nonumber \]
que produce un sistema de ecuaciones:
\ begin {alinear*} x_2 + x_3 + x_4 & = 0\\ x_1 + x_2 + x_5 & = 0\\ x_1 + x_3 + x_6 & = 0\ texto {.} \ end {alinear*}
Aquí\(x_4\) sirve como un bit de verificación para\(x_2\) y\(x_3\text{;}\)\(x_5\) es un bit de verificación para\(x_1\) y\(x_2\text{;}\) y\(x_6\) es un bit de verificación para\(x_1\) y\(x_3\text{.}\) La matriz de identidad mantiene\(x_4\text{,}\)\(x_5\text{,}\) y\(x_6\) de tener que verificarse entre sí. De ahí,\(x_1\text{,}\)\(x_2\text{,}\) y\(x_3\) puede ser arbitrario pero\(x_4\text{,}\)\(x_5\text{,}\) y\(x_6\) debe elegirse para asegurar la paridad. El espacio nulo de\(H\) se calcula fácilmente para ser
\[ \begin{array}{cccc} (000000) & (001101) & (010110) & (011011) \\ (100011) & (101110) & (110101) & (111000). \end{array} \nonumber \]
Una forma aún más fácil de calcular el espacio nulo es con la matriz generadora\(G\) (Tabla\(8.24\)).
\(Table \text { } 8.24\). Un código generado por matriz
| Mensaje Palabra\(\mathbf x\) | Palabra de código\(G \mathbf x\) |
| \(000\) | \(000000\) |
| \(001\) | \(001101\) |
| \(010\) | \(010110\) |
| \(011\) | \(011011\) |
| \(100\) | \(100011\) |
| \(101\) | \(101110\) |
| \(110\) | \(110101\) |
| \(111\) | \(111000\) |
Si\(H \in {\mathbb M}_{m \times n}({\mathbb Z}_2)\) es una matriz canónica de verificación de paridad, entonces\(\Null(H)\) consiste en todos\({\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 un bit de comprobación de paridad par para algunos de los primeros\(n-m\) bits. De ahí,\(H\) da lugar a un código\((n, n-m)\) -block.
Dejamos la prueba de este teorema como ejercicio. A la luz del teorema, los primeros\(n - m\) bits en\({\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 tres primeros bits son los bits de información y los tres últimos son los bits de verificación.
Supongamos que\(G\) es una matriz generadora\(n \times k\) estándar. Entonces\(C = \left\{{\mathbf y} : G{\mathbf x} ={\mathbf y}\text{ for }{\mathbf x}\in {\mathbb Z}_2^k\right\}\) es un código\((n,k)\) -block. Más específicamente,\(C\) es un código de grupo.
- Prueba
-
Dejar\(G {\mathbf x}_1 = {\mathbf y}_1\) y\(G {\mathbf x}_2 ={\mathbf y}_2\) ser dos palabras clave. Entonces\({\mathbf y}_1 + {\mathbf y}_2\) está en\(C\) desde
\[ G( {\mathbf x}_1 + {\mathbf x}_2) = G {\mathbf x}_1 + G {\mathbf x}_2 = {\mathbf y}_1 + {\mathbf y}_2\text{.} \nonumber \]
También debemos mostrar que dos bloques de mensaje no pueden codificarse en la misma palabra de código. Es decir, debemos demostrar 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
\[ G {\mathbf x} - G {\mathbf y} = G( {\mathbf x} - {\mathbf y}) = {\mathbf 0}\text{.} \nonumber \]
Sin embargo, las primeras\(k\) coordenadas en\(G( {\mathbf x} - {\mathbf y})\) son exactamente\(x_1 -y_1, \ldots, x_k - y_k\text{,}\) ya que están determinadas por la matriz de identidad,\(I_k\text{,}\) parte de\(G\text{.}\) Por lo tanto,\(G( {\mathbf x} - {\mathbf y}) = {\mathbf 0}\) exactamente cuando\({\mathbf x} = {\mathbf y}\text{.}\)
Antes de que podamos probar la relación entre las matrices canónicas de comprobación de paridad y las matrices generadoras estándar, necesitamos probar un lema.
Dejar\(H = (A \mid I_m )\) ser una matriz\(m \times n\) canónica de comprobación de paridad y\(G = \left( \frac{I_{n-m} }{A} \right)\) ser la matriz generadora\(n \times (n-m)\) estándar correspondiente. Entonces\(HG = {\mathbf 0}\text{.}\)
- Prueba
-
Let\(C = HG\text{.}\) La entrada\(ij\) th en\(C\) es
\ begin {alinear*} c_ {ij} & =\ suma_ {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} +\ suma_ {k=n-m+1} ^n\ delta_ {i- (m-n), k} a_ {kj}\\ & = a_ {ij} + a_ {ij}\\ & = 0\ text {,}\ end {align*}
donde
\[ \delta_{ij} = \begin{cases} 1 & i = j \\ 0 & i \neq j \end{cases} \nonumber \]
es el delta Kronecker.
Dejar\(H = (A \mid I_m )\) ser una matriz\(m \times n\) canónica de comprobación de paridad y dejar\(G = \left( \frac{I_{n-m} }{A} \right) \) ser la matriz generadora\(n \times (n-m)\) estándar asociada con\(H\text{.}\) Let\(C\) be the code generated by\(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 de verificación de paridad canónica\(H\text{.}\)
- Prueba
-
Primero supongamos que\({\mathbf y} \in C\text{.}\) Entonces\(G {\mathbf x} = {\mathbf y}\) para algunos\({\mathbf x} \in {\mathbb Z}_2^m\text{.}\) Por Lema 8.27,\(H {\mathbf y} = HG {\mathbf x} = {\mathbf 0}\text{.}\)
Por el contrario, supongamos que\({\mathbf y} = (y_1, \ldots, y_n)^\transpose\) está en el espacio nulo de\(H\text{.}\) Necesitamos encontrar una\({\mathbf x}\) en\({\mathbb Z}_2^{n-m}\) tal que\(G {\mathbf x}^\transpose = {\mathbf y}\text{.}\) Dado que debe satisfacerse\(H {\mathbf y} = {\mathbf 0}\text{,}\) el siguiente conjunto de ecuaciones:
\ begin {alinear*} 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+2} & = 0\\ &\ vdots\\ a_ {m1} y_1 + a_ {m2} y_2 +\ cdots + a_ {m, n-m} y_ {n-m} + y_ {n-m+m} & = 0\ text {.} \ end {alinear*}
Equivalentemente,\(y_{n-m+1}, \ldots, y_n\) están determinados por\(y_1, \ldots, y_{n-m}\text{:}\)
\ begin {alinear*} y_ {n-m+1} & = a_ {11} y_1 + a_ {12} y_2 +\ cdots + a_ {1, n-m} y_ {n-m}\\ y_ {n-m+2} & = a_ {21} y_1 + a_ {22} y_2 +\ cdots + a_ {2, n-m} y_ {n-m}\\ &\ vdots\\ y_ {n} & = a_ {m1} y_1 + a_ {m2} y_2 +\ cdots + a_ {m, n-m} y_ {n-m}\ texto {.} \ end {alinear*}
En consecuencia, podemos dejar\(x_i = y_i\)\(i= 1, \ldots, n - m\text{.}\)
Sería útil si pudiéramos calcular la distancia mínima de un código lineal directamente desde su matriz\(H\) para determinar las capacidades de detección y corrección de errores del código. Supongamos que
\ begin {alinear*} {\ mathbf e} _1 & = (100\ cdots 00) ^\ transpone\\ {\ mathbf e} _2 & = (010\ cdots 00) ^\ transpone\\ &\ vdots\\ {\ mathbf e} _n & = (000\ cdots 01) ^\ transpose\ end {align*}
son las\(n\) -tuplas en\({\mathbb Z}_2^n\) de peso\(1\text{.}\) Para una matriz\(m \times n\) binaria\(H\text{,}\)\(H{\mathbf e}_i\) es exactamente la columna\(i\) th de la matriz\(H\text{.}\)
Observe que
\[ \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}\text{.} \nonumber \]
Anotamos este resultado en la siguiente proposición y dejamos la prueba como ejercicio.
\({\mathbf e}_i\)Sea la\(n\) -tupla binaria con a\(1\) en la coordenada\(i\) th y\(0\) 's en otra parte y supongamos que\(H \in {\mathbb M}_{m \times n}({\mathbb Z}_2)\text{.}\) Entonces\(H{\mathbf e}_i\) es la\(i\) th columna de la matriz\ (H\ text { . }\
Dejar\(H\) ser una matriz\(m \times n\) binaria. Entonces el espacio nulo de\(H\) es un solo código de detección de errores si y solo si ninguna columna de\(H\) consiste completamente en ceros.
- Prueba
-
Supongamos que\(\Null(H)\) es un único código de detección de errores. Entonces la distancia mínima del código debe ser al menos\(2\text{.}\) Dado que el espacio nulo es un código de grupo, es suficiente requerir que el código no contenga palabras de código de menos de peso que no\(2\) sean la palabra de código cero. Es decir, no\({\mathbf e}_i\) debe ser una palabra clave para\(i = 1, \ldots, n\text{.}\) Dado que\(H{\mathbf e}_i\) es la\(i\) ésima columna de\(H\text{,}\) la única manera en que\({\mathbf e}_i\) podría estar en el espacio nulo de\(H\) sería si la columna\(i\) th fueran todos ceros, lo cual es imposible; de ahí que el código debe tener la capacidad para detectar al menos errores individuales.
Por el contrario, supongamos que ninguna columna de\(H\) es la columna cero. Por Proposición\(8.30\),\(H{\mathbf e}_i \neq {\mathbf 0}\text{.}\)
Si consideramos las matrices
\[ H_1 = \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{pmatrix} \nonumber \]
y
\[ H_2 = \begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 \end{pmatrix}\text{,} \nonumber \]
Solución
entonces el espacio nulo de\(H_1\) es un solo código de detección de errores y el espacio nulo de no\(H_2\) es.
Incluso podemos hacerlo mejor que el Teorema\(8.31\). Este teorema nos da condiciones sobre una matriz\(H\) que nos indican cuando el peso mínimo del código formado por el espacio nulo de\(H\) es También\(2\text{.}\) podemos determinar cuándo es la distancia mínima de un código lineal\(3\) examinando la matriz correspondiente.
Si dejamos
\[ H = \begin{pmatrix} 1 & 1 & 1 & 0 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \end{pmatrix} \nonumber \]
y quieren determinar si\(H\) es o no la matriz canónica de comprobación de paridad para un código de corrección de errores,
Solución
es necesario cerciorarse de que\(\Null(H)\) no contenga ninguna\(4\) -tuplas de peso Es\(2\text{.}\) decir,\((1100)\text{,}\)\((1010)\text{,}\)\((1001)\text{,}\)\((0110)\text{,}\)\((0101)\text{,}\) y no\((0011)\) debe estar en\(\Null(H)\text{.}\) El siguiente teorema establece que efectivamente podemos determinar que el código generado por \(H\)es la corrección de errores al examinar las columnas de\(H\text{.}\) Aviso en este ejemplo que no sólo no\(H\) tiene columnas cero, sino que además no hay dos columnas iguales.
Dejar\(H\) ser una matriz binaria. El espacio nulo de\(H\) es un solo código de corrección de errores si y solo si\(H\) no contiene ninguna columna cero y no hay dos columnas de\(H\) idénticas.
- Prueba
-
La\(n\) -tupla\({\mathbf e}_{i} +{\mathbf e}_{j}\) tiene\(1\) s en las entradas\(i\) th y\(j\) th y 0s en otros lugares, y\(w( {\mathbf e}_{i} +{\mathbf e}_{j}) = 2\) para\(i \neq j\text{.}\) Since
\[ {\mathbf 0} = H({\mathbf e}_{i} +{\mathbf e}_{j}) = H{\mathbf e}_{i} + H{\mathbf e}_{j} \nonumber \]
solo puede ocurrir si las columnas\(i\) th y\(j\) th son idénticas, el espacio nulo de\(H\) es un solo código de corrección de errores.
Supongamos ahora que tenemos una matriz canónica de comprobación de paridad\(H\) con tres filas. Entonces podríamos preguntar cuántas columnas más podemos agregar a la matriz y aún así tener un espacio nulo que es un solo código de detección de errores y un solo código de corrección de errores. Dado que cada columna tiene tres entradas, hay\(2^3 = 8\) posibles columnas distintas. No podemos agregar las columnas
\[ \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}\text{.} \nonumber \]
Entonces podemos agregar hasta cuatro columnas y aún así mantener una distancia mínima de\(3\text{.}\)
En general, si\(H\) es una matriz\(m \times n\) canónica de verificación de paridad, entonces hay posiciones de\(n-m\) información en cada palabra clave. Cada columna tiene\(m\) bits, por lo que hay\(2^m\) posibles columnas distintas. Es necesario que las columnas\({\mathbf 0}, {\mathbf e}_1, \ldots, {\mathbf e}_m\) sean excluidas, dejando columnas\(2^m - (1 + m)\) restantes para información si todavía estamos para mantener la capacidad no sólo de detectar sino también de corregir errores individuales.