Matriz estándar - Standard array

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

Definición

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

1. La primera fila enumera todas las palabras de código (con la palabra de código 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 i-ésima fila y la j-ésima columna es la suma del i-ésimo líder de clase lateral y la j-ésima palabra de código.

Por ejemplo, el [ 5 , 2 ] -code = { 0 , 01101, 10110, 11011} tiene una matriz estándar de la siguiente manera: ${\ Displaystyle C_ {3}}$

0	01101	10110	11011
10000	11101	00110	01011
01000	00101	11110	10011
00100	01001	10010	11111
00010	01111	10100	11001
00001	01100	10111	11010
11000	10101	01110	00011
10001	11100	00111	01010

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 representa el código.

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

Construyendo una matriz estándar

Debido a que cada vector posible puede aparecer solo una vez en una matriz estándar, se debe tener cuidado durante la construcción. Se puede crear una matriz estándar de la siguiente manera:

1. Enumere las palabras de código de , comenzando con 0 , como la primera fila ${\ Displaystyle C}$
2. Elija cualquier vector de peso mínimo que no esté ya en la matriz. Escriba esto 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 de código en la parte superior de cada columna. La suma de la i-ésima clase líder y la j-ésima palabra de código se convierte en la entrada en la fila i, columna j.
4. Repita los pasos 2 y 3 hasta que se enumeren todas las filas / clases laterales y cada vector aparezca exactamente una vez.

La suma de vectores se realiza mod q. Por ejemplo, los códigos binarios se agregan mod 2 (que equivale a la suma XOR bit a bit). Por ejemplo, en , 11000 + 11011 = 00011. ${\ Displaystyle Z_ {2}}$

Que la selección de diferentes líderes de clase lateral creará una matriz estándar ligeramente diferente pero equivalente, y no afectará los resultados al decodificar.

Ejemplo de construcción

Sea el código binario [4,2]. es decir, C = {0000, 1011, 0101, 1110}. Para construir la matriz estándar, primero enumeramos las palabras de código en una fila. ${\ Displaystyle C}$

0000

1011

0101

1110

Luego seleccionamos un vector de peso mínimo (en este caso, peso 1) que no se ha utilizado. Este vector se convierte en el líder de la clase lateral para la segunda fila.

0000	1011	0101	1110
1000

Siguiendo el paso 3, completamos la fila agregando el líder de clase lateral a cada palabra de código.

0000	1011	0101	1110
1000	0011	1101	0110

Luego repetimos los pasos 2 y 3 hasta completar todas las filas. Paramos cuando llegamos a las filas. ${\ Displaystyle q ^ {nk} = 2 ^ {4-2} = 2 ^ {2} = 4}$

0000	1011	0101	1110
1000	0011	1101	0110
0100	1111	0001	1010
0010	1001	0111	1100

En este ejemplo, no podríamos haber elegido el vector 0001 como líder de la clase lateral de la fila final, aunque cumple con el criterio de tener un peso mínimo (1), porque el vector ya estaba presente en la matriz. Sin embargo, podríamos haberlo elegido como el primer líder de clases laterales y haber construido una matriz estándar diferente.

Decodificación mediante matriz estándar

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 de código en . Por ejemplo, digamos que estamos usando el código C = {0000, 1011, 0101, 1110} y hemos construido la matriz estándar correspondiente, como se muestra en el ejemplo anterior. Si recibimos el vector 0110 como mensaje, encontramos ese vector en la matriz estándar. Luego restamos el líder de clases laterales del vector, a saber, 1000, para obtener el resultado 1110. Hemos recibido la palabra de código 1110. ${\ Displaystyle C}$

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

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

Ver también

• Código lineal

Referencias

• Hill, Raymond (1986). Un primer curso de teoría de la codificación . Serie Oxford de Matemáticas Aplicadas y Ciencias de la Computación. Prensa de la Universidad de Oxford . ISBN   978-0-19-853803-5 .