2
$\begingroup$

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?:

  • 0
    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?2012-11-11

2 Answers 2

1

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.

  • 0
    I see, thanks heaps!2012-11-11
1

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.