5 votos

Construir el código binario de Golay desde el código binario extendido de Golay

Estoy estudiando la construcción de los binarios de código de Golay usando el binario extendido código de Golay $\mathcal{G}$. Es bien sabido que la extensión del código de Golay es una $[24,2^{12},8]_2$-código y puede ser construido a partir de la generación de la matriz de $$ {I} \choose {A} $$ where $I$ is the $12 \times 12$ identity matrix and $$ is the matrix of anti-adjacency of the set of vertices of an icosahedron. I studied some usual results about the extended binary Golay code. For instance: $$ is orthogonal, or $\forall \; x \in \mathcal{G}: w(x) \en \{0,8,12,16,24\}$ where $w(x)$ denotes the weight of $x$, ...

Ahora se afirma que es posible construir un perfecto $[23,2^{12},7]_2$-código con la siguiente construcción: considerar la extendida código de Golay $\mathcal{G}$, pick $i \in \{1, \ldots, 24\}$ y establezca $$\mathcal{G}_i := \{x_1 \ldots \hat{x}_i \ldots x_{24} \mid x_1 \ldots x_{24} \in \mathcal{G} \}$$ A continuación, $\mathcal{G}_i$ es una perfecta $[23,2^{12},7]_2$-código.

Ahora bien, la comprobación de la perfección no es un problema, ya que es suficiente para comprobar el Hamming obligado (si asumimos que $\mathcal{G}_i$ es de hecho un $[23,2^{12},7]_2$-código). Sin embargo, ¿por qué no es posible elegir a $i \in \{1, \ldots , 24\}$ de tal manera inteligente, que $\mathcal{G}_i$ tiene un mínimo de distancia de 8 en vez de 7? Sé que de todas las informaciones en internet sobre el código de Golay que no es posible, sin embargo, me gustaría ver una prueba directa de que, es decir, que no implica la unicidad del código de Golay, por ejemplo. Si me reformular mi pregunta se convierte en: si seleccionamos dos palabras en la distancia $8$, se puede elegir $i \in \{1, \ldots, 24\}$ de manera tal que el $i^{th}$ carta difiere y eliminar en cada palabra, de modo que la distancia mínima se convierte en verdad 7. ¿Por qué es siempre el caso?

5voto

La razón por la que esto no funciona es la siguiente. Hay 759 palabras de peso 8 en el código de Golay. Entre ellos se cubren todos los 24 de posiciones de bits (la elección del índice i) muchas veces. (Transitividad de la automorphism grupo implica que todos los puestos están cubiertos con la misma frecuencia, por lo que podemos decir, más precisamente, de que cada posición tiene un '1' en 253 palabras de peso 8 y un '0' en 506 palabras de peso 8). Por lo tanto, no importa en que posición se le cae, se vuelve un poco del peso de 8 palabras en peso de 7 palabras. Como el cero de la palabra es también allí, la distancia de Hamming, a continuación, no puede ser$>7$.

Para dar una totalmente convincente solución tendría que presentan un conjunto de palabras de peso 8, que cubren todos los 24 posiciones. Como no sé el preciso orden de las posiciones de bits en su construcción, no puedo hacer eso de forma fiable. Si usted publica el generador de la matriz completamente, entonces deberíamos ser capaces de hacer esto de manera rápida.

1voto

Rich Puntos 1767

Aquí es el argumento más simple que he encontrado finalmente. Hay que recordar que el Hamming.

Teorema de la Que $C$ ser un $[n,M,d]_q$-código. Entonces $q^n \geq M ~ \sum_{i=1}^t{{n}\choose{i}}(q-1)^i$ $t$ Dónde está el mayor número entero suh que $d\geq 2t+1$.

Un $[23,2^{12},8]_2$-código violaría el Hamming limitado, por lo tanto no puede existir y la distancia mínima tiene que disminuir (por a lo más 1).

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X