En la teoría de la codificación , una matriz de verificación de paridad de un código de bloque lineal C es una matriz que describe las relaciones lineales que deben satisfacer los componentes de una palabra de código . Puede usarse para decidir si un vector en particular es una palabra de código y también se usa en algoritmos de decodificación.
Definición
Formalmente, una matriz de verificación de paridad, H de un código lineal C es una matriz generadora del código dual , C ⊥ . Esto significa que una palabra de código c está en C si y solo si el producto matriz-vector H c ⊤ = 0 (algunos autores [1] escribirían esto en una forma equivalente, c H ⊤ = 0 ).
Las filas de una matriz de verificación de paridad son los coeficientes de las ecuaciones de verificación de paridad. [2] Es decir, muestran cómo las combinaciones lineales de ciertos dígitos (componentes) de cada palabra de código son iguales a cero. Por ejemplo, la matriz de verificación de paridad
- ,
representa de forma compacta las ecuaciones de verificación de paridad,
- ,
que debe satisfacerse para el vector ser una palabra de código de C .
De la definición de la matriz de verificación de paridad se sigue directamente que la distancia mínima del código es el número mínimo d tal que cada d - 1 columnas de una matriz de verificación de paridad H son linealmente independientes, mientras que existen d columnas de H que son linealmente dependiente.
Crear una matriz de verificación de paridad
La matriz de verificación de paridad para un código dado se puede derivar de su matriz generadora (y viceversa). [3] Si la matriz del generador para un código [ n , k ] está en forma estándar
- ,
entonces la matriz de verificación de paridad viene dada por
- ,
porque
- .
La negación se realiza en el campo finito F q . Tenga en cuenta que si la característica del campo subyacente es 2 (es decir, 1 + 1 = 0 en ese campo), como en los códigos binarios , entonces - P = P , por lo que la negación es innecesaria.
Por ejemplo, si un código binario tiene la matriz generadora
- ,
entonces su matriz de verificación de paridad es
- .
Se puede verificar que G es un matriz, mientras que H es una matriz.
Síndromes
Para cualquier vector (fila) x del espacio vectorial ambiental, s = H x ⊤ se denomina síndrome de x . El vector x es una palabra de código si y solo si s = 0 . El cálculo de síndromes es la base del algoritmo de decodificación de síndrome . [4]
Ver también
Notas
- ^ por ejemplo, Roman 1992 , p. 200
- ^ Roman 1992 , p. 201
- ^ Pless 1998 , p. 9
- ^ Pless 1998 , p. 20
Referencias
- Hill, Raymond (1986). Un primer curso de teoría de la codificación . Serie de Ciencias de la Computación y Matemáticas Aplicadas de Oxford. Prensa de la Universidad de Oxford . pp. 69 . ISBN 0-19-853803-0.
- 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
- JH van Lint (1992). Introducción a la teoría de la codificación . GTM . 86 (2ª ed.). Springer-Verlag. págs. 34 . ISBN 3-540-54894-7.