# Decoding Cyclic Code

I am asked to decode this word but the concepts I've learnt tell me that the question can't be done.

Let C be a binary cyclic code generated by $$g(x) = 1 + x + x^8 + x^{12} + x^{14}$$ in F_2[x]/($x^{15}-1$). Assuming no more than 2 errors have occurred, decode $1 + x + x^2 + x^3 + x^6 + x^8 + x^{11} + x^{12} + x^{14}$.

Firstly, g(x) does not divide $x^{15}-1$, so g(x) does not generate a cyclic code. Secondly, even if it does, the dimension of the code would be 1, meaning there are 2 words in the code: Zero and g(x) itself.

Please correct me if my basic concepts are not right!:)

-
Where does it say $g$ must divide $x^{15}-1$? How do you deduce the dimension of the code is 1? –  Gerry Myerson Apr 16 '12 at 6:14
I learnt that each monic divisor of x^n-1 is the generator of some cyclic code and from Wikipedia, "A polynomial code is cyclic if and only if the generator polynomial divides $x^{n}-1$." –  newbowl Apr 16 '12 at 6:22
I deduce the dimension of code is 1 because I learnt that if the degree of g(x) = n-k, then dim(C) = k. –  newbowl Apr 16 '12 at 6:24
My advice is to try and decode assuming that the double-error-correcting BCH-code was intended (see my answer for an explanation). Simply in order not to alienate your teacher ;-) –  Jyrki Lahtonen Apr 16 '12 at 6:49
Okay, thank you so much! (Yes, my teacher tends to set questions with errors.) –  newbowl Apr 16 '12 at 7:26

Yes, you're right on both accounts. In the context of cyclic codes it is standard that the generator polynomial is a factor of $x^L-1$, where $L$ is the length of the code. Something is wrong.
Algebraically $g(x)$ and $\gcd(g(x), x^{15}-1)$ generate the same cyclic code (= an ideal of the ring $F_2[x]/(x^{15}-1)$), so one might think that you are first expected to compute the greatest common divisor. But I would be very hesitant in calling $g(x)$ a generator polynomial in that case (e.g. the standard encoding algorithms cannot use this $g(x)$), so I very much doubt that that's what was meant.
Mind you, $\gcd(g(x), x^{15}-1)=(1+x+x^4)(1+x+x^2+x^3+x^4)$ is the generator polynomial of a double-error-correcting BCH-code of length 15. This fits in a way, but I still think that the problem set up is misguided.
For example van Lint defines the generator polynomial of a cyclic code to be the lowest degree polynomial in the code. Consequently (polynomial division) it then must be a factor of $x^L-1$. –  Jyrki Lahtonen Apr 16 '12 at 6:59
I would like to double check one fact. Suppose g(x) is the one given in the question. g*(x) is the gcd(g(x),$x^{15}-1$). Then r(x) mod g(x) is the same as r(x) mod g*(x) right? That is, they have the same syndrome right? –  newbowl Apr 16 '12 at 8:59
@newbowl, no! You have to use the syndrome modulo $g^*(x)$. As you observed, very few (only two) polynomials are congruent to zero mod $g(x)$, but all $2^7$ polynomials of the code generated by $g^*(x)$ are congruent to zero modulo $g^*(x)$. –  Jyrki Lahtonen Apr 16 '12 at 9:11