Código de Hamming de longitud $8$ auto-dual

Question

Estoy leyendo un documento de N.J.A Sloane sobre códigos autoduales, y él presenta el código de Hamming binario de longitud $8$ con matriz generadora $$ G = \begin{bmatrix} 1&1&1&1&1&1&1&1\\ 0&1&1&1&0&1&0&0\\ 0&0&1&1&1&0&1&0\\ 0&0&0&1&1&1&0&1 \end{bmatrix}$$

Donde si asignamos etiquetas a las columnas de izquierda a derecha; $\infty, 0,1,2,3,4,5,6$, entonces la segunda fila tiene $1's$ donde la columna está etiquetada por un residuo cuadrático módulo $7$. Luego hacemos un desplazamiento cíclico para obtener las filas restantes.

¿Qué se está haciendo aquí? Supongo que simplemente ignoramos la primera fila y la primera columna ya que esto solo extiende la matriz. He investigado sobre códigos de residuos cuadráticos pero no encuentro la relación entre ellos y esta matriz generadora. ¿Podría alguien explicar qué se está haciendo aquí?

El documento al que hago referencia se puede encontrar aquí; https://arxiv.org/abs/math/0612535.

Answer 1

Existe un código de residuo cuadrático (QR) de longitud $p$ sobre el campo finito $GF(m)$ siempre que $p$ y $m$ sean primos, $p$ sea impar y $m$ sea residuo cuadrático módulo $p$.

Resulta que el Código de Hamming (7,4,3) y el Código de Golay (23,12,7), ambos sobre $GF(2)$ (por lo tanto $m=2$), también pueden expresarse como códigos QR.

A medida que $p$ aumenta, los códigos QR ya no son muy eficientes, con su distancia mínima asintóticamente $O(\sqrt{p}) pero para longitudes cortas producen los dos códigos perfectos mencionados anteriormente.

Edición: La calculadora en línea de magma es muy útil para cálculos en teoría de códigos. Puedes acceder aquí.

Al ingresar

QRCode(GF(2),7); HammingCode(GF(2),3);

obtienes

[7, 4, 3] "Código de Residuo Cuadrático" Código Lineal sobre GF(2)

y

[7, 4, 3] "Código de Hamming (r = 3)" Código Lineal sobre GF(2)

y muestra la misma matriz generadora para ambos.

Answer 2

El código es auto dual. La matriz generadora es también la matriz de comprobación de paridad. Si consideras la matriz $G$ como la matriz de comprobación de paridad, entonces al eliminar la primera fila y la primera columna se obtiene la matriz de comprobación de paridad del código de Hamming 7,4,3.