1
$\begingroup$

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

  • 0
    Where does it say $g$ must divide $x^{15}-1$? How do you deduce the dimension of the code is 1?2012-04-16
  • 0
    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$."2012-04-16
  • 0
    I deduce the dimension of code is 1 because I learnt that if the degree of g(x) = n-k, then dim(C) = k.2012-04-16
  • 0
    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 ;-)2012-04-16
  • 0
    Okay, thank you so much! (Yes, my teacher tends to set questions with errors.)2012-04-16

1 Answers 1

2

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.

  • 0
    For example [van Lint](http://books.google.fi/books/about/Introduction_to_Coding_Theory.html?id=tvQhRUFh7EwC&redir_esc=y) 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$.2012-04-16
  • 0
    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?2012-04-16
  • 0
    @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)$.2012-04-16
  • 0
    Yes, right! *KNOCK MY HEAD HARD*2012-04-16