smallest length code given the generator polynomial

Question

I'm interested in finding, with proof, the smallest length n of a binary linear cyclic code with a generator polynomial of degree 7.

I know that since the code is linear and cyclic, the dimension of the code is given by k = n - t, where t is deg$(g(x))$ = 7.

So I'm thinking that I can state that n = k + t and the shortest length occurs when k is minimal, i.e. k = 0 and therefore n = t = 7, giving a code of size $q^k = 2^0$ exclusively containing $g(x)$? This doesn't seem right to me, I don't think that's even linear.

Is there something I'm missing?

Answer 1

The smallest length of a cyclic code generated by $g(x)\in\Bbb{F}_2[x]$ is the smallest $\ell$ such that $g(x)\mid x^\ell-1$.

This $\ell$ is a bit awkward to figure out. We need the following observations:

• If $g(x)=\prod_{j=1}^n p_j(x)^{a_j}$ is its factorization into irreducible polynomials $p_j(x)$ (distinct for distinct $j$), then $g(x)\mid x^\ell-1$ if and only if $p_j(x)^{a_j}\mid x^\ell-1$ for all $j$.
• When $a_j=1$, the smallest such $\ell$ is the (multiplicative) order of the zeros of $p_j(x)$. Call that $\ell_j$.
• Given that $p_j(x)\mid x^{\ell_j}-1$ it follows that $$p_j(x)^{2^n}\mid (x^{\ell_j}-1)^{2^n}=x^{2^n\ell_j}-1.$$ It follows (not trivial, but not too difficult either) that the smallest integer $m_j$ such that $p_j(x)^{a_j}\mid x^{m_j}-1$ is gotten from the formula $$ m_j=2^{t_j}\ell_j, $$ where $t_j$ is the smallest integer such that $2^{t_j}\ge a_j$.
• From all of the above it follows that $$\ell=\operatorname{lcm}\{m_j\mid j=1,2,\ldots,n\}.$$

Now we are well placed to attack the question. The only possible linear factor $x+1$ has $\ell_j=1$. The only possible quadratic factor $x^2+x+1$ has $\ell_j=3$. The irreducible cubics have both $\ell_j=7$ because $7=2^3-1$ is a Mersenne prime. Among the quartics there is a single irreducible $x^4+x^3+x^2+x+1$ with $\ell_j=5$, the others have roots of order $15$. Quintics won't do much because $\ell_j=31$ (Mersenne). With sextics there is a single irreducible with $\ell_j=9$, the rest are higher ($21$ or $63$). Septics give $\ell_j=127$ (Mersenne again).

Candidates: I'm sure that what you want is on this list :-)

• We could use $g(x)=(x+1)^7=\sum_{j=0}^7x^j$. This has $\ell=8$. But, as you see, the code is the repetition code of length $8$. If you want to dismiss that as well, I understand.
• If we add a single quadratic factor we get $g(x)=(x+1)^5(x^2+x+1)$. But, $5$ exceeds $2^2$, so this polynomial has $\ell=\operatorname{lcm}(8,3)=24$.
• If we try $g(x)=(x+1)^3(x+2+x+1)^2$ we get $m_1=2^2\cdot 1$, $m_2=2\cdot3$, and $\ell=\operatorname{lcm}(4,6)=12$. This is probably the shortest non-trivial one. It still has repeated roots, and that is sometimes undesirable. Other $g(x)$ with linear and quadratic factors only don't really help. There is another with $\ell=12$, namely $g(x)=(x+1)(x^2+x+1)^3$.
• The lowest $\ell$ among polynomials with no repeated zeros (i.e. $a_j=1$ for all $j$) is $g(x)=(x+1)(x^3+x+1)(x^3+x^2+1)$. It has $\ell=7$ meaning that this generates a zero-dimensional code. I don't want to include that. Observe that we cannot use $7=2+2+3$ because we only have a single irreducible quadratic.
• With $7=3+4$ the best we can do is $g(x)=(x^3+x+1)(x^4+x^3+x^2+x+1)$ with $\ell_1=7$, $\ell_2=5$ and $\ell=35$.
• $7=2+5$ because the quintic factor has $\ell_j=31$, this forces us to $\ell=3\cdot31=93$. The degrees corresponding to Mersenne primes are bad.
• But $7=1+6$ yields a short cyclic code if we use the ninth cyclotomic polynomial $x^6+x^3+1$ as the irreducible sextic with $\ell_1=9$. Therefore $$g(x)=(x+1)(x^6+x^3+1)$$ generates a cyclic code of length $9$ and rank $k=2$.

Looks like the shortest non-trivial code with a septic generator polynomial has length 9. The repetition code is always cyclic, but would not be my pick.