19.3: Uso de la Matriz Generadora para Codificar

Notación

Es conveniente representar la cadena binaria\(x_1x_2 . . . x_n\) como un vector de columna:

\[ \left[ \begin{array}{ll} x_1\\ x_2\\ ...\\ x_n\\ \end{array} \right]. \]

Esto nos permite usar la multiplicación matricial para anexar bits de comprobación a una cadena:

Ejemplo\(\PageIndex{1}\)

Agregar un bit de comprobación de paridad a la cadena\(010\) rinde\(0101\). El mismo resultado se puede obtener multiplicando el vector de columna correspondiente a\(010\) por la siguiente matriz generadora:

\(G = \left[ \begin{array}{ll} 1\;\;0\;\;0 \\ 0\;\;1\;\;0 \\ 0\;\;0\;\;1 \\ 1\;\;1\;\;1 \\ \end{array} \right] = \left[ \dfrac{I_3}{A} \right] \)

donde\(I_k\) está la matriz de\(k \times k\) identidad, y\(A = [1\;\;\;1 \;\;\;1]\).

A saber (calculando todo el módulo aritmético\(2\)), tenemos

\( \left[ \begin{array}{ll} 0\\ 1\\ 0 \end{array} \right] = \left[ \begin{array}{ll} 0\\ 1\\ 0 \\ 1 \end{array} \right]. \)

De hecho, multiplicar cualquier cadena\(3\) -bit por\(G\) produce la misma cadena con su bit de comprobación de paridad anexado.

\( \left[ \begin{array}{ll} x_1\\ x_2\\ x_3 \end{array} \right] = \left[ \begin{array}{ll} x_1\\ x_2 \\ x_3 \\ x_1 + x_2 + x_3 \end{array} \right], \text{ and } x_1 + x_2 + x_3 (\text{mod } 2) = \left\{ \begin{array}{ll} 0 \text{ if even # of } 1\text{s}\\ 1 \text{ if odd # of } 1\text{s}\\ \end{array} \right. \)

Método General

Para algunos\(k\)\(r ∈ \mathbb{N}^+\),

• elegir una\(r \times k\) matriz\(A\) de\(0\) s y\(1\) s, y
• dejar\(G = \left[ \dfrac{I_k}{A} \right]\)

Al multiplicar una cadena de\(k\) bits por se\(G\) obtiene la misma cadena, con bits de\(r\) verificación anexados al final. Dejamos\(C\) ser el conjunto de todas las cadenas posibles\(Gx\), y llamamos a\(G\) la matriz generadora de este código.

Nota

En la siguiente sección, veremos cómo elegir\(G\) para que el código resultante\(C\) pueda corregir errores.

Aunque muchos códigos importantes de corrección de errores son construidos por otros métodos, solo discutiremos los que provienen de matrices generadoras (excepto en la Sección 19.5).

Definición: Código lineal binario

Cualquier código que provenga de una matriz generadora\(G\) (por el Método General descrito anteriormente) se dice que es un código lineal binario.

Ejemplo\(\PageIndex{2}\)

Encuentra todas las palabras clave del código lineal binario\(C\) correspondientes a la matriz generadora

\(G = \left[ \dfrac{I_3}{A} \right], \text{with } A = \left[ \begin{array}{ll} 1\;\;0\;\;1\\ 0\;\;1\;\;1 \end{array} \right]. \)

Solución

Tenemos

\(G = \left[ \dfrac{I_3}{A} \right], \text{with } A = \left[ \begin{array}{ll} 1\;\;0\;\;0\\ 0\;\;1\;\;0\\ 0\;\;0\;\;1\\ 1\;\;0\;\;1\\ 0\;\;1\;\;1 \end{array} \right]. \)

Usamos esta matriz para codificar cada una de las cadenas\(2^3 = 8\) binarias de longitud\(3\):

\[\begin{equation} \begin{split} &G\left[ \begin{array}{ll} 0\\ 0\\ 0 \end{array} \right] = \left[ \begin{array}{ll} 0\\ 0 \\ 0 \\ 0 \\0 \end{array} \right],\;\;\;\; &G\left[ \begin{array}{ll} 0\\ 0\\ 1 \end{array} \right] = \left[ \begin{array}{ll} 0\\ 0 \\ 1 \\ 1 \\1 \end{array} \right], \;\;\;\; &G\left[ \begin{array}{ll} 0\\ 1\\ 0 \end{array} \right] = \left[ \begin{array}{ll} 0\\ 1 \\ 0 \\ 0 \\1 \end{array} \right], \;\;\;\; &G\left[ \begin{array}{ll} 0\\ 1\\ 1 \end{array} \right] = \left[ \begin{array}{ll} 0\\ 1 \\ 1 \\ 1 \\0 \end{array} \right],\\[0.25in] &G\left[ \begin{array}{ll} 1\\ 0\\ 0 \end{array} \right] = \left[ \begin{array}{ll} 1\\ 0 \\ 0 \\ 1 \\0 \end{array} \right], &G\left[ \begin{array}{ll} 1\\ 0\\ 1 \end{array} \right] = \left[ \begin{array}{ll} 1\\ 0 \\ 1 \\ 0 \\1 \end{array} \right], &G\left[ \begin{array}{ll} 1\\ 1\\ 0 \end{array} \right] = \left[ \begin{array}{ll} 1\\ 1 \\ 0 \\ 1 \\1 \end{array} \right], &G\left[ \begin{array}{ll} 1\\ 1\\ 1 \end{array} \right] = \left[ \begin{array}{ll} 1\\ 1 \\ 1 \\0 \\0 \end{array} \right]. \end{split} \end{equation}\]

Entonces\(C = \{00000, 00111, 01001, 01110, 10010, 10101, 11011, 11100\}\).

Ejercicio\(\PageIndex{1}\)

Codificar cada una de las palabras dadas usando la matriz generadora\(G = \left[ \begin{array}{ll} I_k\\ A \end{array} \right]\). asociada a la matriz dada\(A\).

1)\(A = \left[ \begin{array}{ll} 1\;\;1\;\;0\;\;0\\ 1\;\;0\;\;0\;\;1 \end{array} \right]\). Palabras para codificar:\(0101\),\(0010\),\(1110\).

2)\(A = \left[ \begin{array}{ll} 1\;\;1\;\;0\\ 1\;\;0\;\;1 \\0\;\;1\;\;1 \\ 1\;\;1\;\;1 \end{array} \right]\). Palabras para codificar:\(110\),\(011\),\(111\),\(000\).

La matriz generadora proporciona una manera fácil de codificar los mensajes para su envío, pero es difícil utilizarla para decodificar un mensaje que ha sido recibido. Para ello, en la siguiente sección se introducirá una matriz ligeramente diferente. A partir de esta nueva matriz, será fácil determinar si el código correspondiente puede corregir cada error de un solo bit.