¿Cómo hallar la distancia mínima de un código BCH de sentido estricto?

Question

Conozco la distancia diseñada, $d$ es un límite inferior para la distancia mínima, $d(C)$ .

Normalmente, en los ejemplos que he visto, lo que hacemos es encontrar el polinomio generador $g(x)$ del código, entonces de $d \le d(C) \le w(g)$ donde $w(g)$ es el peso de la palabra clave $g(x)$ siempre ocurre que $w(g)=d$ . Está claro que esto no siempre funciona. ¿Y si la última igualdad no se cumple? ¿Hay alguna manera de encontrar la distancia mínima sin encontrar primero el polinomio generador?

Por ejemplo, en nuestro texto, para el código BCH de sentido estricto de longitud 23 con $d=5$ se dice que la distancia mínima es $7$ . ¿Cómo lo consiguen?

Answer 1

Se trata de un código muy especial $C$ conocido como código binario de Golay. Para obtener $d_{min}=7$ puedes hacer lo siguiente.

• El campo de extensión más pequeño que contiene una raíz 23 de la unidad es $GF(2^{11})$ . Lo vemos, por ejemplo, aplicando repetidamente el Frobenius (es decir, elevando al cuadrado). Si $\alpha$ es una raíz 23 de la unidad, sus conjugados son $$\alpha,\alpha^2,\alpha^4,\alpha^8,\alpha^{16},\alpha^9,\alpha^{18},\alpha^{13},\alpha^3,\alpha^6,\alpha^{12}.$$
• Así que ya ves que el polinomio mínimo de $\alpha$ también tiene como ceros $\alpha^2$ , $\alpha^3$ y $\alpha^4$ . Por lo tanto, el límite BCH dice que $d_{min}\ge5$ .
• Para que el resto funcione, es necesario producir una matriz generadora de $C$ . Si conoces un polinomio generador $g(x)$ es fácil. Otra forma es calcular el idempotente de $C$ . Por el mismo cálculo vemos que los idempotentes en el anillo $R=GF(2)[x]/\langle x^{23}+1\rangle$ son $$e(x)=x+x^2+x^3+x^4+x^6+x^8+x^9+x^{12}+x^{13}+x^{16}+x^{18}$$ su recíproco $\tilde{e}(x)=x^{23}e(\dfrac1x)$ y lo que se obtenga añadiendo $1$ a uno de ellos (la suma $e+\tilde{e}$ también es un idempotente, pero genera el código de repetición, por lo que no es interesante).
• IIRC $e(x)$ genera un código que queremos. El código es de 12 dimensiones, y se obtiene una base para $C$ escribiendo las palabras $x^ie(x), 0\le i\le 11$ .
• Ampliar $C$ a un código $C^+$ de longitud $24$ añadiendo un bit de comprobación de paridad global.
• A continuación viene el paso clave: Compruebe que los vectores base que generan $C^+$ todas tienen pesos divisibles por cuatro, y que son ortogonales entre sí. Demostrar (por inducción sobre el número de generadores que aparecen en la suma) que todas las palabras de $C^+$ tienen pesos divisibles por cuatro.
• Concluir que $d_{min}(C^+)\ge8$ y, por tanto $d_{min}(C)\ge7$ .