BCH code: Difference between revisions

Revision as of 03:32, 30 September 2019

Revision as of 03:39, 30 September 2019

Line 348:

An alternate process of finding both the polynomial Λ and the error locator polynomial is based on Yasuo Sugiyama's adaptation of the [[Extended Euclidean algorithm]].<ref>Yasuo Sugiyama, Masao Kasahara, Shigeichi Hirasawa, and Toshihiko Namekawa. A method for solving key equation for decoding Goppa codes. Information and Control, 27:87–99, 1975.</ref> Correction of unreadable characters could be incorporated to the algorithm easily as well.

Let <math>k_1, ... , k_k</math> be positions of unreadable characters. One creates polynomial localising these positions <math>\Gamma(x)=\prod_{i=1}^k(x\alpha^{k_i}-1).</math>

Set values on unreadable positions to 0 and compute the syndromes.

Line 377:

than

:<math>t_i=\alpha^{k_1}s_i-s_{i+1}=\alpha^{k_1}\sum_{j=0}^{n-1}e_j\alpha^{ij}-\sum_{j=0}^{n-1}e_j\alpha^j\alpha^{ij}=\sum_{j=0}^{n-1}e_j\left(\alpha^{k_1} - \alpha^j\right)\alpha^{ij}.</math>

New set of syndromes restricts error vector

:<math>f_j=e_j\left(\alpha^{k_1} - \alpha^j\right)</math>

the same way the original set of syndromes restricted the error vector <math>e_j.</math> Except the coordinate <math>k_1,</math> where we have <math>f_{k_1}=0,</math> an <math>f_j</math> is zero, if <math>e_j = 0.</math> For the goal of locating error positions we could change the set of syndromes in the similar way to reflect all unreadable characters. This shortens the set of syndromes by <math>k.</math>

Line 387:

In polynomial formulation, the replacement of syndromes set <math>\{s_c,\cdots,s_{c+d-2}\}</math> by syndromes set <math>\{t_c,\cdots,t_{c+d-3}\}</math> leads to

:<math>T(x) = \sum_{i=0}^{d-3}t_{c+i}x^i=\alpha^{k_1}\sum_{i=0}^{d-3}s_{c+i}x^i-\sum_{i=1}^{d-2}s_{c+i}x^{i-1}.</math>

Therefore,

:<math>xT(x) \stackrel{\{1,\cdots,\,d-2\}}{=} \left (x\alpha^{k_1} - 1 \right )S(x).</math>

After replacement of <math>S(x)</math> by <math>S(x)\Gamma(x)</math>, one would require equation for coefficients near powers <math>k,\cdots,d-2.</math>

Line 402:

In Euclidean algorithm, we try to correct at most <math>\tfrac{1}{2}(d-1-k)</math> errors (on readable positions), because with bigger error count there could be more codewords in the same distance from the received word. Therefore, for <math>\Lambda(x)</math> we are looking for, the equation must hold for coefficients near powers starting from

:<math>k + \left \lfloor \tfracfrac{1}{2} (d-1-k) \right \rfloor.</math>

In Forney formula, <math>\Lambda(x)</math> could be multiplied by a scalar giving the same result.

It could happen that the Euclidean algorithm finds <math>\Lambda(x)</math> of degree higher than <math>\tfrac{1}{2}(d-1-k)</math> having number of different roots equal to its degree, where the Fourney formula would be able to correct errors in all its roots, anyway correcting such many errors could be risky (especially with no other restrictions on received word). Usually after getting <math>\Lambda(x)</math> of higher degree, we decide not to correct the errors. Correction could fail in the case <math>\Lambda(x)</math> has roots with higher multiplicity or the number of roots is smaller than its degree. Fail could be detected as well by Forney formula returning error outside the transmitted alphabet.

===Correct the errors===