Matriz de comprobación de paridad

En teoría de codificación , una matriz de comprobació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 utilizarse para decidir si un vector en particular es una palabra de código y también se utiliza en algoritmos de decodificación.

Definición

Formalmente, una matriz de comprobació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 comprobación de paridad son los coeficientes de las ecuaciones de comprobació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 comprobació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 comprobación de paridad,

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

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

De la definición de la matriz de comprobació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 comprobación de paridad H son linealmente independientes mientras que existen d columnas de H que son linealmente dependientes.

Creación de una matriz de comprobación de paridad

La matriz de comprobación de paridad para un código dado 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 comprobació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 . Nótese 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 comprobació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 denomina síndrome de x . El vector x es una palabra clave si y solo si s = 0. El cálculo de síndromes es la base del algoritmo de decodificación de síndromes . ^[4]

Véase también

• Código de Hamming

Notas

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

Referencias

• Hill, Raymond (1986). Un primer curso de teoría de la codificación. Oxford Applied Mathematics and Computing Science Series. Oxford University Press . 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 (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
• JH van Lint (1992). Introducción a la teoría de la codificación. GTM . Vol. 86 (2.ª ed.). Springer-Verlag. pp. 34. ISBN. 3-540-54894-7.