Matriz generadora

En teoría de codificación , una matriz generadora es una matriz cuyas filas forman la base de un código lineal . Las palabras clave son todas las combinaciones lineales de las filas de esta matriz, es decir, el código lineal es el espacio de filas de su matriz generadora.

Terminología

Si G es una matriz, genera las palabras clave de un código lineal C mediante

${\displaystyle w=sG}$

donde w es una palabra de código del código lineal C , y s es cualquier vector de entrada. Se supone que tanto w como s son vectores de fila. ^[1] Una matriz generadora para un código lineal tiene formato , donde n es la longitud de una palabra de código, k es el número de bits de información (la dimensión de C como un subespacio vectorial), d es la distancia mínima del código y q es el tamaño del campo finito , es decir, el número de símbolos en el alfabeto (por lo tanto, q = 2 indica un código binario , etc.). El número de bits redundantes se denota por . ${\displaystyle [n,k,d]_{q}}$ ${\displaystyle k\times n}$ ${\displaystyle r=n-k}$

La forma estándar para una matriz generadora es, ^[2]

${\displaystyle G={\begin{bmatrix}I_{k}|P\end{bmatrix}}}$,

donde es la matriz identidad y P es una matriz. Cuando la matriz generadora está en forma estándar, el código C es sistemático en sus primeras k posiciones de coordenadas. ^[3] ${\displaystyle I_{k}}$ ${\displaystyle k\times k}$ ${\displaystyle k\times (n-k)}$

Se puede utilizar una matriz generadora para construir la matriz de comprobación de paridad de un código (y viceversa). Si la matriz generadora G está en forma estándar, , entonces la matriz de comprobación de paridad para C es ^[4] ${\displaystyle G={\begin{bmatrix}I_{k}|P\end{bmatrix}}}$

${\displaystyle H={\begin{bmatrix}-P^{\top }|I_{n-k}\end{bmatrix}}}$,

donde es la transpuesta de la matriz . Esto es una consecuencia del hecho de que una matriz de verificación de paridad de es una matriz generadora del código dual . ${\displaystyle P^{\top }}$ ${\displaystyle P}$ ${\displaystyle C}$ ${\displaystyle C^{\perp }}$

G es una matriz, mientras que H es una matriz. ${\displaystyle k\times n}$ ${\displaystyle (n-k)\times n}$

Códigos equivalentes

Los códigos C ₁ y C ₂ son equivalentes (denominados C ₁ ~ C ₂ ) si un código puede obtenerse del otro mediante las dos transformaciones siguientes: ^[5]

1. permutar arbitrariamente los componentes, y
2. escalar independientemente por un elemento distinto de cero cualquiera de sus componentes.

Los códigos equivalentes tienen la misma distancia mínima.

Las matrices generadoras de códigos equivalentes se pueden obtener entre sí mediante las siguientes operaciones elementales : ^[6]

1. permutar filas
2. escalar filas mediante un escalar distinto de cero
3. agregar filas a otras filas
4. permutar columnas, y
5. escalar columnas mediante un escalar distinto de cero.

Por lo tanto, podemos realizar la eliminación gaussiana en G . De hecho, esto nos permite suponer que la matriz generadora está en la forma estándar. Más precisamente, para cualquier matriz G podemos encontrar una matriz invertible U tal que , donde G y generan códigos equivalentes. ${\displaystyle UG={\begin{bmatrix}I_{k}|P\end{bmatrix}}}$ ${\displaystyle {\begin{bmatrix}I_{k}|P\end{bmatrix}}}$

Véase también

• Código de Hamming (7,4)

Notas

1. MacKay, David, JC (2003). Teoría de la información, inferencia y algoritmos de aprendizaje (PDF) . Cambridge University Press . pág. 9. ISBN. 9780521642989Debido a que el código Hamming es un código lineal, se puede escribir de forma compacta en términos de matrices de la siguiente manera. La palabra de código transmitida se obtiene de la secuencia fuente mediante una operación lineal, ${\displaystyle \mathbf {t} }$ ${\displaystyle \mathbf {s} }$

   ${\displaystyle \mathbf {t} =\mathbf {G} ^{\intercal }\mathbf {s} }$

   ¿Dónde está la matriz generadora del código? He supuesto que y son vectores columna. Si en cambio son vectores fila, entonces esta ecuación se reemplaza por ${\displaystyle \mathbf {G} }$ ${\displaystyle \mathbf {s} }$ ${\displaystyle \mathbf {t} }$

   ${\displaystyle \mathbf {t} =\mathbf {sG} }$

   ... Me resulta más fácil relacionarme con la multiplicación por la derecha (...) que con la multiplicación por la izquierda (...). Sin embargo, muchos textos de teoría de codificación utilizan las convenciones de multiplicación por la izquierda (...). ...Las filas de la matriz generadora pueden considerarse como la definición de los vectores base.{{cite book}}: CS1 maint: multiple names: authors list (link)
2. Ling y Xing 2004, pág. 52
3. Romano 1992, pág. 198
4. Romano 1992, pág. 200
5. Pless 1998, pág. 8
6. Welsh 1988, págs. 54-55

Referencias

• Ling, San; Xing, Chaoping (2004), Teoría de la codificación: un primer curso , Cambridge University Press, ISBN 0-521-52923-9
• Pless, Vera (1998), Introducción a la teoría de los códigos de corrección de errores (3.ª ed.), Wiley Interscience, ISBN 0-471-19047-0
• Roman, Steven (1992), Teoría de la codificación y la información , GTM , vol. 134, Springer-Verlag, ISBN 0-387-97812-7
• Welsh, Dominic (1988), Códigos y criptografía , Oxford University Press, ISBN 0-19-853287-3

Lectura adicional

• MacWilliams, FJ ; Sloane, NJA (1977), La teoría de los códigos de corrección de errores , North-Holland, ISBN 0-444-85193-3

Enlaces externos

• Matriz generadora en MathWorld