En la teoría de la 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 por
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 lineal-código 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 yq 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.
La forma estándar para una matriz generadora es, [2]
- ,
dónde es el matriz de identidad y P es unamatriz. Cuando la matriz generadora está en forma estándar, el código C es sistemático en sus primeras k posiciones de coordenadas. [3]
Se puede usar una matriz generadora para construir la matriz de verificación de paridad para un código (y viceversa). Si la matriz del generador G está en forma estándar,, entonces la matriz de verificación de paridad para C es [4]
- ,
dónde es la transposición de la matriz. Esto es una consecuencia del hecho de que una matriz de verificación de paridad dees una matriz generadora del código dual .
G es un matriz, mientras que H es una matriz.
Códigos equivalentes
Los códigos C 1 y C 2 son equivalentes (indicados C 1 ~ C 2 ) si un código se puede obtener del otro mediante las dos transformaciones siguientes: [5]
- permutar arbitrariamente los componentes, y
- escalar independientemente por un elemento distinto de cero cualquier componente.
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]
- permutar filas
- escalar filas por un escalar distinto de cero
- agregar filas a otras filas
- permutar columnas, y
- escalar columnas por un escalar distinto de cero.
Por lo tanto, podemos realizar Gauss Eliminación de G . De hecho, esto nos permite asumir 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 generar códigos equivalentes.
Ver también
Notas
- ^ 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 de 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 por una operación lineal,
dónde es la matriz generadora del código ... He asumido que y son vectores de columna. Si en cambio son vectores de fila, entonces esta ecuación se reemplaza por
... 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 la codificación utilizan las convenciones de multiplicación por la izquierda (...). ... Las filas de la matriz generadora pueden verse como la definición de los vectores base. - ^ Ling y Xing 2004 , p. 52
- ^ Roman 1992 , p. 198
- ^ Roman 1992 , p. 200
- ^ Pless 1998 , p. 8
- ^ 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 de corrección de errores (3a ed.), Wiley Interscience, ISBN 0-471-19047-0
- Roman, Steven (1992), Teoría de la información y la codificación , GTM , 134 , Springer-Verlag, ISBN 0-387-97812-7
- Galés, 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 de corrección de errores , Holanda Septentrional, ISBN 0-444-85193-3
enlaces externos
- Matriz generadora en MathWorld