Content deleted Content added
No edit summary |
|||
Line 4:
BCH codes use [[field theory (mathematics)|field theory]] and polynomials over finite fields. To detect errors a check polynomial can be constructed so the receiving end can detect if some errors had occurred.
:''m''<sub>1</sub>(''x'') = (''x'' - α)(''x'' - α<sup>2</sup>)(''x'' - α<sup>4</sup>)(''x'' - α<sup>8</sup>)=''x''<sup>4</sup> + ''x'' + 1.
If we wish to construct a code to correct 1 error we use ''m''<sub>1</sub>(''x''). Our codewords will be all the polynomials ''C''(''x'') satisfying▼
: ''
▲If we wish to construct a code to correct 1 error we use ''m''<sub>1</sub>(''x''). Our codewords will be
which has roots α, α<sup>2</sup>, α<sup>4</sup>, α<sup>8</sup>.
This does not allow us to choose many codewords - so we look for the minimal polynomial for the missing power of α from above - α<sup>3</sup>, and then the minimal polynomial for this is
:''m''<sub>3</sub>(''x'') = ''x''<sup>4</sup> + ''x''<sup>3</sup> + ''x''<sup>2</sup> + ''x'' + 1.
which has roots α<sup>3</sup>, α<sup>6</sup>, α<sup>12</sup>, α<sup>24</sup>=α<sup>9</sup>.
We take codewords having all of these as roots, so we form the polynomial
:''m''<sub>1,3</sub>(''x'') = ''m''<sub>1</sub>(''x'')''m''<sub>3</sub>(''x'') = ''x''<sup>8</sup> + ''x''<sup>7</sup> + ''x''<sup>6</sup> + ''x''<sup>4</sup>+1
and take codewords corresponding to polynomials of degree 14 such that
: ''C''(''x'') ≡ 0 (mod ''m''<sub>1,3</sub>(''x''))
So now ''C''(α) = ''C''(α<sup>2</sup>) = ... = ''C''(α<sup>8</sup>) = 0. (*)
Now in GF(16) we have 15 nonzero elements, and thus our polynomial will be of degree 14 with 8 check and 7 information bits - we have 8 check bits since we have (*).
| |||