Checking whether a code is cyclic by using the generator matrix

Question

I was wondering whether it is possible to conclude whether a code is cyclic or not from the generator matrix of a code. If so, how could one do this? Thank you in advance!

Answer 1

Not very directly.

Recall that for a $(n,k)$ cyclic code any codeword is of the form $c(x) = g(x) u(x)$ where $g(x)$, the GP, is a factor of $x^n+1$ and has degree $n-k$.

First factor $x^n+1$ to find all the possible factors of degree $n-k$ (candidate GPs).

Then represent each row of $G$ as a polynomial $c(x)$, factor them, and check if all are multiple of one of the candidate GPs. If so, the code is cyclic.

Answer 2

In addition to leonbloy's suggestion we have the following alternative.

Undoubtedly you remember from linear algebra how to algorithmically test whether a given vector is in the row space of a matrix? Just add the vector to be tested to the matrix as an extra row and check (by reducing it to row echelon form) whether the rank of the matrix increases (negative) or stays the same (affirmative). This is particularly efficient if the matrix itself was already in the row echelon form. In particular, this is the case if the generator matrix of your code is in a systematic form.

All you need to is the following:

If the cyclic shift (by one position) of each row of the generator matrix $G$ is a codeword (i.e. in the row space of $G$) then the code is cyclic. Otherwise it is not.

It is easy to see why this works. If that condition is satisfied then, by linearity, the cyclic shift by one position of any codeword will again be a codeword. By induction it then follows that the same applies to all the cyclic shifts.

Earlier I mentioned systematic generator matrices as a particular case. Another easy case is that when the rows of $G$ correspond to the monomial multiples $x^i g(x)$ of the generator polynomial $g(x)$, $0\le i<n-k$. For example, to show that $g(x)=x^3+x+1$ generates a cyclic binary code of length $7$ we could use a generator matrix consisting of the four shifts of $g(x)=1101000$. That is $$ G=\left(\begin{array}{ccccccc} 1&1&0&1&0&0&0\\ 0&1&1&0&1&0&0\\ 0&0&1&1&0&1&0\\ 0&0&0&1&1&0&1 \end{array}\right). $$ With generator matrices like this the above procedure is particularly simple. The cyclic shifts of the top three rows are obviously codewords because the next row is the cyclic shift. All we need to do is to verify that the cyclic shift of the bottom row, that is $1000110$ is a codeword. But we quickly realize that it is the sum of the top three rows. Just as well because this is one cyclic incarnation of the $[7,4,3]$ Hamming code.

---

The underlying principle in this test is the following. A cyclic code of length $n$ can be viewed as a submodule of the space $\Bbb{F}_q^n$ that we view as a module of the cyclic group $C_n=\langle c\rangle$ of order $n$, $c$ acting by cyclically shifting the components. If a code (= a subspace) $C$ is stable under the action of the generating element $c$, that is $c(C)\subseteq C$, then it is automatically also stable under the entire group (consisting of all the powers of $c$). Looking at codes of length as subspaces of the quotient ring $\Bbb{F}_q[X]/\langle x^n-1\rangle$ we recover the same test in the form: a subspace $C$ is a cyclic code if and only if $xC\subseteq C$.