Encontrar los conjuntos de información de un código lineal.

Question

Estoy tratando de entender mejor los códigos lineales, así que decidí trabajar con problemas de varios libros de texto. Estoy teniendo problemas para entender cómo hacer este problema, y me preguntaba si alguien puede guiarme en la dirección correcta.

Problema La matriz $G = [I_{4} | A]$ , donde $$ G = \left[ \begin{array}{cccc|ccc} 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1\end{array} \right] $$

es una matriz generadora en forma estándar para un $[7,4]$ código binario, denotado por $\mathcal{H}_3$ . La matriz de comprobación de paridad para $\mathcal{H}_3$ es $$H = [A^{T} | I_{3}] = \left[ \begin{array}{cccc|ccc} 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 1 \end{array} \right]. $$

Encuentre al menos cuatro conjuntos de información en $\mathcal{H}_3$ . Encuentra al menos un conjunto de cuatro coordenadas que no formen un conjunto de información. $\blacksquare$

El libro define un conjunto de información de la siguiente manera: Dado un $[n,k]$ código lineal $\mathcal{C}$ una matriz generadora para $\mathcal{C}$ es cualquier $k \times n$ matriz $G$ cuyas filas forman una base para $\mathcal{C}$ . Para cualquier conjunto de $k$ columnas independientes de $G$ el conjunto de coordenadas correspondiente forma un conjunto de información para $\mathcal{C}$ .

Cualquier ayuda se agradecería mucho ya que llevo bastante tiempo mirando esto. Gracias.

Answer 1

Tal como interpreto la definición de "conjunto de información" de su libro, el "conjunto de coordenadas" que corresponde a un conjunto de columnas es literalmente el índice de esas columnas en la matriz $G$ . Así que si $$G=\left[\begin{array}{cccc|ccc} 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \end{array}\right],$$ el "conjunto de coordenadas" correspondiente a "la primera, segunda, cuarta y séptima columnas" es literalmente sólo (1,2,4,7). Dado que estas columnas no son linealmente independientes, éste sería un ejemplo de un conjunto de cuatro coordenadas que no forman un conjunto de información.

Que $G$ tiene cuatro columnas independientes es lo que le permite codificar de forma única un mensaje de longitud cuatro. Si tomas cualquier mensaje de cuatro dígitos $m$ y multiplicar $mG$ entonces la palabra clave de 7 dígitos resultante puede traducirse de forma única al mensaje original; si $G$ tenían menos de $4$ columnas independientes, esta multiplicación daría el mismo resultado para más de un mensaje de 4 dígitos, y en cierto sentido se perdería información. Nunca podrías estar seguro de haber descodificado correctamente ciertos mensajes.

Otra forma de pensar en la situación es que porque $G$ tiene cuatro columnas independientes, tiene rango 4 y, por lo tanto, al ponerla en forma de escalón reducido por filas, será una matriz generadora estándar (la $G$ en este ejemplo ya es una matriz generadora estándar). Sin embargo, si no lo fuera, y aún así tuviera cuatro columnas independientes, podrías convertirla fácilmente. Ahora bien, si te fijas en lo que ocurre cuando multiplicas $mG$ el resultado es el mensaje $m$ con tres dígitos adicionales añadidos al final. Si las columnas de la matriz de identidad estuvieran en otras coordenadas, la palabra clave tendría el mensaje $m$ reordenados como esas columnas, con dígitos adicionales insertados donde están las otras columnas.

Espero que esta divagación haya sido útil y no aún más confusa. Este documento tiene una explicación bastante buena de los conjuntos de información también (ver p. 39). (No estoy seguro de a quién atribuir el mérito, pero el documento procede originalmente de la página web de la MSU de Jonathan Hall)

Answer 2

¿Tiene problemas para encontrar conjuntos de 4 columnas independientes/dependientes en $G$ ? o ¿tiene problemas para encontrar el conjunto de coordenadas correspondiente, dado el conjunto de 4 columnas independientes?

Si tu problema es el primero de los anteriores, la pregunta es si sabes lo que significa que un conjunto de vectores sea (linealmente) independiente, y cómo probar un conjunto de vectores para esta propiedad. ¿Puedes ver, por ejemplo, que las 4 primeras columnas de $G$ son independientes, mientras que las columnas 2, 3, 4 y 5 no lo son? Hay una combinación lineal no trivial de las columnas 2 a 5 que da el vector cero, es decir, la 5ª menos la suma de las otras tres; pero no hay ninguna combinación lineal de las 4 primeras columnas que dé cero, salvo la combinación con los cuatro coeficientes que son cero.

Si esto no le sirve de ayuda, considere la posibilidad de incluir más información en su pregunta sobre dónde está exactamente su dificultad.