Matriz de verificación de paridad

En teoría de 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 en clave . Puede usarse para decidir si un vector en particular es una palabra clave 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 clave c está en C si y sólo 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 equivalen a cero. Por ejemplo, la matriz de verificación de paridad.

${\displaystyle H=\left[{\begin{array}{cccc}0&0&1&1\\1&1&0&0\end{array}}\right]}$,

representa de forma compacta las ecuaciones de verificación de paridad,

${\displaystyle {\begin{aligned}c_{3}+c_{4}&=0\\c_{1}+c_{2}&=0\end{aligned}}}$,

eso debe cumplirse para que el vector sea una palabra clave de C . ${\displaystyle (c_{1},c_{2},c_{3},c_{4})}$

De la definición de la matriz de verificación de paridad se deduce 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 sean 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 determinado se puede derivar de su matriz generadora (y viceversa). ^[3] Si la matriz generadora para un código [ n , k ] está en forma estándar

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

entonces la matriz de verificación de paridad está dada por

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

porque

${\displaystyle GH^{\top }=P-P=0}$.

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

${\displaystyle G=\left[{\begin{array}{cc|ccc}1&0&1&0&1\\0&1&1&1&0\\\end{array}}\right]}$,

entonces su matriz de verificación de paridad es

${\displaystyle H=\left[{\begin{array}{cc|ccc}1&1&1&0&0\\0&1&0&1&0\\1&0&0&0&1\\\end{array}}\right]}$.

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

Síndromes

Para cualquier vector (fila) x del espacio vectorial ambiental, s = H x ^⊤ se llama síndrome de x . El vector x es una palabra clave si y sólo si s = 0 . El cálculo de los síndromes es la base del algoritmo de decodificación de síndromes . ^[4]

Ver también

• código hammam

Notas

1. por ejemplo, Roman 1992, p. 200
2. Romano 1992, pag. 201
3. Pless 1998, pag. 9
4. Pless 1998, pag. 20

Referencias

• Colina, Raymond (1986). Un primer curso de teoría de la codificación. Serie de Matemáticas Aplicadas y Ciencias de la Computación de Oxford. Prensa de la Universidad de Oxford . págs.69. ISBN 0-19-853803-0.
• 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
• JH van Lint (1992). Introducción a la teoría de la codificación. GTM . vol. 86 (2ª ed.). Springer-Verlag. págs.34. ISBN 3-540-54894-7.