Matriz estándar

En teoría de la codificación , una matriz estándar (o matriz de Slepian) es una${\displaystyle q^{nk}}$por${\displaystyle q^{k}}$matriz que enumera todos los elementos de un conjunto particular${\displaystyle \mathbb {F} _{q}^{n}}$espacio vectorial . Se utilizan matrices estándar para decodificar códigos lineales ; es decir, para encontrar la palabra clave correspondiente a cualquier vector recibido.

Una matriz estándar para un código [ n , k ] es una${\displaystyle q^{nk}}$por${\displaystyle q^{k}}$matriz donde:

1. La primera fila enumera todas las palabras clave (con la palabra clave 0 en el extremo izquierdo).
2. Cada fila es una clase lateral con el líder de la clase lateral en la primera columna.
3. La entrada en la fila i y la columna j es la suma del líder del grupo lateral i y la palabra clave j.

Por ejemplo, el código [ 5 , 2 ]${\displaystyle C_{3}}$= { 0 , 01101, 10110, 11011} tiene una matriz estándar como la siguiente:

Lo anterior es solo una posibilidad para la matriz estándar; si se hubiera elegido 00011 como el primer líder de clase lateral de peso dos, se habría construido otra matriz estándar que representara el código.

La primera fila contiene el vector 0 y las palabras clave de${\displaystyle C_{3}}$( El 0 es en sí mismo una palabra clave). Además, la columna de la izquierda contiene los vectores de peso mínimo , enumerando primero los vectores de peso 1 y luego los de peso 2. Asimismo, cada vector posible en el espacio vectorial aparece exactamente una vez.

Dado que cada vector posible solo puede aparecer una vez en un arreglo estándar, se debe tener cuidado durante su construcción. Un arreglo estándar se puede crear de la siguiente manera:

1. Enumera las palabras clave de${\displaystyle C}$, comenzando con 0 , como la primera fila
2. Elija cualquier vector de peso mínimo que no esté ya en el arreglo. Escriba este como la primera entrada de la siguiente fila. Este vector se denomina " líder de clase lateral" .
3. Complete la fila agregando el líder de clase lateral a la palabra clave en la parte superior de cada columna. La suma del i-ésimo líder de clase lateral y la j-ésima palabra clave se convierte en la entrada de la fila i, columna j.
4. Repita los pasos 2 y 3 hasta que se hayan listado todas las filas/clases laterales y cada vector aparezca exactamente una vez.

La suma de vectores se realiza módulo q. Por ejemplo, los códigos binarios se suman módulo 2 (lo que equivale a una suma XOR bit a bit). Por ejemplo, en${\displaystyle Z_{2}}$, 11000 + 11011 = 00011.

Seleccionar diferentes líderes de clases laterales creará una matriz estándar ligeramente diferente pero equivalente, y no afectará los resultados al decodificar.

Para decodificar un vector usando una matriz estándar, reste el vector de error (o líder de clase lateral) del vector recibido. El resultado será una de las palabras clave en${\displaystyle C}$Por ejemplo, supongamos que usamos el código C = {0000, 1011, 0101, 1110} y hemos construido el arreglo estándar correspondiente, como se muestra en el ejemplo anterior. Si recibimos el vector 0110 como mensaje, lo buscamos en el arreglo estándar. Luego, restamos el primer elemento de la clase lateral del vector, que es 1000, para obtener el resultado 1110. Hemos recibido la palabra clave 1110.

La decodificación mediante una matriz estándar es una forma de decodificación del vecino más cercano . En la práctica, la decodificación mediante una matriz estándar requiere grandes cantidades de almacenamiento: un código con 32 palabras clave requiere una matriz estándar con${\displaystyle 2^{32}}$entradas. Otras formas de decodificación, como la decodificación de síndromes , son más eficientes.

La decodificación mediante un array estándar no garantiza que todos los vectores se decodifiquen correctamente. Si recibimos el vector 1010, el array estándar anterior decodificaría el mensaje como 1110, una palabra clave a una distancia de 1. Sin embargo, 1010 también está a una distancia de 1 de la palabra clave 1011. En tal caso, algunas implementaciones podrían solicitar que se reenvíe el mensaje, o bien el bit ambiguo podría marcarse como un borrado y un código externo posterior podría corregirlo. Esta ambigüedad es otra razón por la que a veces se utilizan diferentes métodos de decodificación.

• Código lineal

• Hill, Raymond (1986). Un primer curso de teoría de la codificación . Serie Oxford de Matemáticas Aplicadas e Informática. Oxford University Press . ISBN 978-0-19-853803-5.