¿Cómo se crea una matriz generadora para un código Hamming (7, 4)?

Question

Veo que se crea una matriz generadora con las siguientes fórmulas:

$$G = \left[I_{k}|P\right]$$

No entiendo qué es P en este caso. En mis notas, me dicen que en una situación de código Hamming (7, 4) mi $$G = \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 1 & 0 & 1 & 1 \end{pmatrix}$$

donde P sería

$$P=\begin{pmatrix} 1 & 0 & 1 \\ 1 & 1 & 1 \\ 1 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix}$$

¿Cómo se genera esta P?

Answer 1

La forma estándar de averiguar la matriz de paridad $G_{k,n}$ para un código Hamming es construir primero la matriz de paridad de comprobación $H_{n-k,n}$ de forma sistemática.

Para ello, recordamos que un código Hamming tiene $d=3$ (distancia mínima). Por lo tanto, las columnas de $H$ tienen la propiedad de que podemos encontrar un conjunto de $3$ columnas linealmente dependientes, pero no $2$ columnas o menos. Como estamos en $GF(2)$ (código binario) esto equivale a decir que las columnas de $H$ debe ser distinta (y diferente de cero). Entonces las columnas de $H$ sólo corresponden a la $2^{n-k}-1$ diferentes tuplas binarias no nulas. Podemos optar por construirlo de forma sistemática, así, por ejemplo:

$$H= \begin{pmatrix} 1 &1 &0& 1 &1& 0 &0\\ 0 &1 &1 &1 &0 &1 &0\\ 1 &1& 1 &0& 0 &0& 1 \end{pmatrix} = [P^t \mid I_{n-k}]$$

Tenga en cuenta que también puede elegir otras permutaciones de las primeras 4 columnas.

A partir de esto, se obtiene $G=[I_k \mid P ]$

Answer 2

$G$ representa el mapeo de la entrada a las palabras clave del código. Se obtiene el vector de palabras de código $c$ multiplicando el vector de entrada $v$ desde la izquierda de $G$ : $$c = vG.$$

Así, se ve que el vector de entrada $\begin{pmatrix} 1 & 0 & 0 & 0 \end{pmatrix}$ se asigna a la primera fila de $G$ (si dudas de mí, haz el cálculo), y los otros vectores base estándar se asignan a las otras filas de $G$ .

Así, se puede construir una matriz $G$ tomando una base de sus vectores de entrada, y decidiendo a qué palabras de código corresponden, estas palabras de código serán las filas de su $G$ . Por supuesto, al hacer esto, no se garantiza que su matriz $G$ estará en el de $\left[I \mid P \right]$ Para conseguirlo tendrás que realizar reducciones de filas en tu matriz.

Esto describe en términos muy generales cómo se construye un código lineal. Suele ser más fácil para los códigos Hamming.

Entonces, construyamos $G$ para el $(7,4)$ Código Hamming. Nótese que estamos trabajando sobre el campo finito con dos elementos $\mathbb F_2$ .

Tenemos cuatro bits de entrada $b_1, b_2, b_3, b_4$ . Definimos tres bits de paridad como: $$\begin{align} p_1 &= b_1 + b_2 + b_3 \\ p_2 &= b_2 + b_3 + b_4 \\ p_3 &= b_1 + b_2 + b_4 \\ \end{align}$$

y nuestra palabra clave es $$\begin{pmatrix} b_1 & b_2 & b_3 & b_4 & p_1 & p_2 & p_3 \end{pmatrix}.$$

Podemos ver que esto facilita la construcción de la primera parte de nuestro $G$ será simplemente la matriz identidad, ya que podemos ver que $$\begin{pmatrix} b_1 & b_2 & b_3 & b_4 \end{pmatrix} \begin{pmatrix} I_4 & P \end{pmatrix} = \begin{pmatrix} b_1 & b_2 & b_3 & b_4 & - & - & - \end{pmatrix}$$ independientemente de lo que $P$ es. Ahora sólo tenemos que utilizar las ecuaciones para $p_1, p_2, p_3$ anterior y transformarlo en una matriz: $$\begin{pmatrix} p_1 & p_2 & p_3 \end{pmatrix} = \begin{pmatrix} b_1 & b_2 & b_3 & b_4 \end{pmatrix} \underbrace{ \begin{pmatrix} 1 & 0 & 1\\ 1 & 1 & 1\\ 1 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix}}_{= P}$$

Esta es una forma alternativa de verlo. Usamos la base estándar para nuestras palabras de entrada y calculamos cuáles serán las palabras de código para los vectores base, usando las ecuaciones de paridad anteriores. Esto nos da las filas de nuestro $G$ matriz.

Para $e_1 = \begin{pmatrix} 1 & 0 & 0 & 0\end{pmatrix}$ obtenemos $p_1 = 1, p_2 = 0, p_3 = 1$ Así que $$e_1G = \begin{pmatrix} 1 & 0 & 0 & 0 & 1 & 0 & 1\end{pmatrix}$$ Lo mismo ocurre con los demás vectores de base: $$\begin{align} e_2G &= \begin{pmatrix} 0 & 1 & 0 & 0 & 1 & 1 & 1 \end{pmatrix} \\ e_3G &= \begin{pmatrix} 0 & 0 & 1 & 0 & 1 & 1 & 0 \end{pmatrix} \\ e_4G &= \begin{pmatrix} 0 & 0 & 0 & 1 & 0 & 1 & 1 \end{pmatrix} \end{align}$$ y estas serán las filas de nuestro $G$ es decir $$G = \begin{pmatrix} e_1G \\ e_2G \\ e_3G \\ e_4G \end{pmatrix}$$