Encuentre el mínimo $n$ tal que existe $[n,n-5]$ código binario cíclico con polinomio generador $g(x)=1+x^4+x^5$

Question

Encuentre el mínimo $n$ ya que existe $[n,n-5]$ código binario cíclico con polinomio generador $g(x)=1+x^4+x^5$ .

No pude averiguar la respuesta. La única forma que se me ocurre es averiguar todas las factorizaciones de $x^n-1$ para cada $n>5$ pero es un trabajo muy duro y no creo que sea lo que deba hacer. Estoy aprendiendo con el libro de Raymond Hill Primer curso de teoría de la codificación y no he podido encontrar ningún teorema que me ayude a resolverlo.

Gracias.

Answer 1

Sugerencia: Puede factorizar $$ \begin{aligned} g(x)=(x^5+x^4+x^3)+(x^3+1)&=x^3(x^2+x+1)+(x+1)(x^2+x+1)\\ &=(x^3+x+1)(x^2+x+1). \end{aligned} $$ Me arriesgo a decir que el mismo ejercicio se ha resuelto como ejemplo para estos dos factores. Si no es así, puedes tratar los factores por separado utilizando el método de Leox (+1). Estos factores irreducibles dan valores más pequeños para $n$ . Como son coprime se puede aprovechar. Después de todo $g(x)\mid x^n-1$ si ambos factores lo hacen. Recuerde que $x^n-1\mid x^m-1$ si $n\mid m$ .

Answer 2

La factorización de $g$ en irreducibles es $$1 + x^4 + x^5 = (x^2 + x + 1)(x^3 + x + 1).$$

Dejemos que $a$ sea un cero de $x^2 + x + 1$ . Desde $x^2 + x + 1$ es irreducible, $[\mathbb F_2(a) : \mathbb F_2] = \operatorname{deg}(x^2 + x = 1) = 2$ Así que $\mathbb F_2(a) = \mathbb F_4$ y $a\in \mathbb F_4^\times$ . Porque $\lvert \mathbb F_4\rvert ^\times = 3$ es primo, obtenemos el orden multiplicativo de $a$ como $3$ ( $1$ no es posible ya que $a\neq 1$ ).

Del mismo modo, todos los ceros de $x^3 + x + 1$ tienen orden multiplicativo $7$ .

Su está buscando el más pequeño $n\geq 1$ con $g\mid x^n - 1$ . Equivalentemente, $n$ es el número más pequeño con $z^n = 1$ para todos los ceros de $g$ (aquí utilizamos que $g$ no tiene raíces repetidas). Por lo tanto, $$n = \operatorname{lcm}(3,7) = 21.$$

Answer 3

Dejemos que $\alpha$ sea una raíz de $g(x).$ Entonces tenemos que $\alpha^5=\alpha^4+1$ . ( Trabajamos en $\mathbb{Z}_2$ ) Por lo tanto, obtenemos $$ \begin{gather*} \alpha^6=\alpha^5+\alpha=\alpha^4+\alpha+1,\\ \alpha^7=\alpha^5+\alpha^2+\alpha=\alpha^4+\alpha^2+\alpha+1,\\ \ldots \end{gather*} $$ y así sucesivamente hasta obtener $\alpha^n=1$ para algunos $n.$ Entonces $n$ es la longitud del código cíclico.