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 de código 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 de código de un código lineal C mediante

${\displaystyle w=sG}$

donde w es una palabra clave del código lineal C y s es cualquier vector de entrada. Se supone que tanto w como s son vectores 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 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 (así, q = 2 indica un código binario , etc.). El número de bits redundantes se indica con . ${\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 verificación de paridad para un código (y viceversa). Si la matriz generadora G está en forma estándar, entonces la matriz de verificació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}}}$,

¿Dónde está la transpuesta de la matriz ? Esto es una consecuencia del hecho de que una matriz de verificación de paridad 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 (denotados C ₁ ~ C ₂ ) si un código se puede obtener del otro mediante las dos transformaciones siguientes: ^[5]

1. permutar arbitrariamente los componentes, y
2. escalar independientemente cualquier componente mediante un elemento distinto de cero.

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

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

1. permutar filas
2. escalar filas por 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 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 genera códigos equivalentes. ${\displaystyle UG={\begin{bmatrix}I_{k}|P\end{bmatrix}}}$ ${\displaystyle {\begin{bmatrix}I_{k}|P\end{bmatrix}}}$

Ver también

• Código Hamming (7,4)

Notas

1. MacKay, David, JC (2003). Teoría de la información, inferencia y algoritmos de aprendizaje (PDF) . Prensa de la Universidad de Cambridge . pag. 9.ISBN​ 9780521642989. Debido 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 asumido que y son vectores de 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 (...). ... Se puede considerar que las filas de la matriz generadora definen los vectores base.{{cite book}}: CS1 maint: multiple names: authors list (link)
2. Ling y Xing 2004, pág. 52
3. Romano 1992, pag. 198
4. Romano 1992, pag. 200
5. Pless 1998, pag. 8
6. Galés 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 correctores de errores (3.ª ed.), Wiley Interscience, ISBN 0-471-19047-0
• Roman, Steven (1992), Teoría de la información y codificació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

Otras lecturas

• MacWilliams, FJ ; Sloane, NJA (1977), La teoría de los códigos correctores de errores , Holanda Septentrional, ISBN 0-444-85193-3

enlaces externos

• Matriz generadora en MathWorld