Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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!:)

share|cite|improve this question
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
up vote 2 down vote accepted

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.

share|cite|improve this answer
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
Yes, right! KNOCK MY HEAD HARD – newbowl Apr 16 '12 at 9:32

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.