Generator polynomial cyclic codes

Question

How do I find the generator polynomial for a q-ary cyclic code. I know that for a binary cyclic code, a polynomial that divides $x^n - 1$ can be considered as a generator polynomial (e.g. $1 + x + x^3$ divides $x^7 - 1$ and thus $g(x) = 1 + x + x^3$.

But for non-binary cases I am unsure what is a necessary and sufficient condition to find a generator polynomial. Can someone please give an example. I know that for RS codes $g(x) = (x - a_1)(x - a_2)$. But are there other codes as well ?

Also, if $q = 2^m$, then does this constitute as a special case with additional properties?

If $g(x) \mid x^n - 1$ then $\langle g(x) \rangle$ gives a cyclic code independently of the field. — user 1987, May 25 '17 at 16:55

score 0 · Accepted Answer · answered May 25 '17 at 18:07

For instance $\langle (x + 1)(x+2)\rangle$ is a cyclic code over GF$(3)$ of length 6 and dimension 4.

In fact, all cyclic codes of length $n$ over GF$(q)$ are given by the following procedure. Let $$g_1^{k_1}\cdots g_l^{k_l} = x^n - 1$$ be the irreducible factorization of $x^n - 1$ over GF$(q)$. If $C$ is cyclic code of length $n$ then $C = \langle g(x) \rangle$ where $g$ is a combination of $g_i^{l_i}$s.

For the example that I mentioned, what I did is factor $x^6 - 1$ over GF$(3)$, namely, $$x^6 - 1 = (x+1)^3(x+2)^3$$ and then I took some combination of irreducble factors.

If this was the answer you were looking for, accept it so that is considered closed. — user 1987, May 26 '17 at 00:14

Generator polynomial cyclic codes

1 Answers1