Upper bounds for the dimension of a binary cyclic code

Question

Let $\mathbb{F}_2 = \{0,1\}$ denote the field with two elements. Consider a binary $N$-tuple $a = a_0 a_1 \ldots a_{N-1}$, of elements $a_i \in \mathbb{F}_2$. The cyclic code $C_a$ corresponding to $a$ is the vector space, over $\mathbb{F}_2$, which is spanned by the cyclic shifts of $a$. That is, $$ C_a = Span\{ (a_0, a_1, \ldots, a_{N-1}), \ (a_{N-1}, a_0, \ldots, a_{N-2}), \ \ldots, \ (a_1, a_2, \ldots, a_0) \}. $$ The dimension of $C_a$ is then the rank of the $N \times N$ matrix whose rows are the tuples above. I'm interested in knowing whether, in a general setting, one may be able to obtain upper bounds for the rank given certain knowledge of the tuples. For instance, if you know that the sequence $a$ has certain amount of runs of $0$'s (or 1's), and how long these are, could one possibly give an upper bound based on this? What pieces of information may be useful to obtain a good upper bound? Thanks!

Answer 1

A polynomial time algorithm for calculating the rank of $C_a$ is described in most books on algebraic coding theory. All you need to do is to calculate the gcd of $x^N-1$ and $a(x):=\sum_ia_ix^i$. If that gcd is of degree $k$, then $\dim C_a=N-k$.

Cyclicity of a linear code is a very strong property severely constraining the number of codes you can get. It makes the algebra much more interesting - for example by giving us the toolbox of (discrete) Fourier analysis to play with. But it also means that nearly all kind of randomizing tends to trivialize the code, as those usually don't mesh with the algebra of cyclicity. For example, changing a single one of the coefficients $a_i$ often means that the above gcd becomes trivial, and your code becomes useless.

Therefore any general bound based on lengths of runs is unlikely to exist, because changing one of the run lengths by one leads to unpredictable changes in the code.

To get an idea of the algebraic/number theoretic flavor of this phenomenon consider the following toy example. Let $N=24$. If you use $a=1111\,1111\,0000\,0000\,0000\,0000$, a run of eight 1s followed by sixteen 0s, then the above gcd is of degree $7$, and the code has rank $17$. Basically because $8\mid 24$. But if you use a run of seven 1s followed by seventeen 0s, the gcd becomes trivial and the cyclic shifts of $a$ span all of $\Bbb{F}_2^{24}$. And divisibility properties like this only give us full information when there is a single run of 1s.

---

Proving the result in the first paragraph. When looking at cyclic codes of length $N$ we work with the ring $R=\Bbb{F}_2[x]/\langle x^N-1\rangle$. When we turn all the words of the code $C_a$ into polynomials they form a set $C$ that is 1) closed under addition (because $C_a$ is linear), and 2) closed under multiplication by $x$ (because $C_a$ is cyclic). Therefore $C$ is an ideal of $R$. Let $I$ be the ideal of $\Bbb{F}_2[x]$ consisting of all the polynomial with their image in the ideal $C$. By basic properties of the polynomial ring the ideal $I$ is generated by its lowest degree non-zero element, $g(x)$. Because $C$ is spanned by the remainders of $x^ka(x)$ modulo $x^N-1$ ($k$ = the number of shifts), it follows that $g(x)=\gcd(a(x),x^N-1)$.

The space $C$ is then spanned by those polynomials $x^ig(x)$ that have degrees $<N$. If $k=\deg g(x)$, then the choices for $i$ are $0,1,\ldots,N-1-k$, and there are clearly $N-k$ of them.