So here's what I understand so far:

$\mathbb F = \frac{\mathbb Z_{2}[x]}{x^4+x+1} = GF(16)$

The code is written as $[x^{14},x^{13},x^{12},x^{11},x^{10},x^{9},x^{8}$ $|$ $x^{7},x^{6},x^{5},x^{4},x^{3},x^{2},x^{1},x^{0}]$

So we write the message $[1,1,0,1,1,0,1] = x^{14}+x^{13}+x^{11}+x^{10}+x^{8}$ and we get the first part of the code:

$[1,1,0,1,1,0,1$ $|$ $x^{7},x^{6},x^{5},x^{4},x^{3},x^{2},x^{1},x^{0}]$

We divide $x^{14}+x^{13}+x^{11}+x^{10}+x^{8}$ by $(x^8+x^7+x^6+x^4+1)$ and we get $(x^6+x^4+x^2+x)$ with remainder $(x^7+x^5+x^4+x^2+x)$

Taking the coefficients of the remainder we get the encoded BCH code
$[1,1,0,1,1,0,1$ $|$ $1,0,1,1,0,1,1,0]$

My question is: Why do we divide by $(x^8+x^7+x^6+x^4+1)$? Where did that come from?:

  • $\begingroup$ What does your book say about this? What is the definition of BCH code that you know and how is the generator polynomial determined? Is there a table of BCH codes where you might find $x^8+x^7+x^6+x^4+1$ listed? $\endgroup$ – Dilip Sarwate Nov 11 '12 at 5:25
  • $\begingroup$ I'm not really sure - I'm working off some examples I copied from class and we seem to have gotten $(x^8+x^7+x^6+x^4+1)$ by dividing $(x^4+x+1)$ by "The minimum polynomial" or some sort? $\endgroup$ – Arvin Nov 11 '12 at 5:39

Let $\alpha$ be a root of $m_{\alpha}(x)=x^4+x+1$ in the field $GF(16)$. As this polynomial is primitive, $\alpha$ is of order $15$. Therefore $\alpha^3$ is of order five. Thus the minimal polynomial of $\alpha^3$ is $m_{\alpha^3}(x)=x^4+x^3+x^2+x+1$. The generator polynomial of a double-error-correcting BCH-code is $$ m_{\alpha}(x)m_{\alpha^3}(x)=(x^4+x+1)(x^4+x^3+x^2+x+1)=x^8+x^7+x^6+x^4+1. $$

The rest of the calculation is basic use of the generator polynomial that has undoubtedly been explained in you textbook/lecture notes.

Related topics have been discussed in another question, see Dilip Sarwate's answer and the Wikipedia article linked to in that question. It is about Reed-Solomon codes, but the algebra is more or less the same as in the case of BCH-codes.

  • $\begingroup$ Why is the minimum polynomial $(x^4+x^3+x^2+x+1)$? Is that just the smallest polynomial with order $5$ in $\mathbb Z_2[x]$? $\endgroup$ – Arvin Nov 11 '12 at 7:41
  • 1
    $\begingroup$ @Arvin: The element $\beta:=\alpha^3$ is a fifth root of unity. So $\beta^5=1$ and it is a zero of $$x^5-1=(x-1)(x^4+x^3+x^2+x+1).$$ Because $\beta\neq1$, it has to be a zero of the latter factor. It is not immediately clear, but not too difficult either, to show that the polynomial $x^4+x^3+x^2+x+1$ is irreducible in $\mathbb{F}_2[x]$. Therefore it has to be the minimal polynomial. $\endgroup$ – Jyrki Lahtonen Nov 11 '12 at 7:48
  • $\begingroup$ I see, thanks heaps! $\endgroup$ – Arvin Nov 11 '12 at 8:08

Yes, the question is somewhat incomplete (as pointed by Dilip Sarwate and Jyrki Lahtonen).

This is a 2-error correcting (primitive narrow-sense) BCH code. The generator polynomial is the smallest binary polynomial that has $\alpha, \alpha^2, \alpha^3, \alpha^4$ as its roots. This is precisely the LCM of the minimal polynomials of those four roots. Also, the minimal polynomial of $\alpha, \alpha^2, \alpha^4$ are the same polynomial.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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