Editing BCH code (section)

==== Explanation of the decoding process ====
The goal is to find a codeword which differs from the received word minimally as possible on readable positions. When expressing the received word as a sum of nearest codeword and error word, we are trying to find error word with minimal number of non-zeros on readable positions. Syndrom <math>s_i</math> restricts error word by condition

:<math>s_i=\sum_{j=0}^{n-1}e_j\alpha^{ij}.</math>

We could write these conditions separately or we could create polynomial

:<math>S(x)=\sum_{i=0}^{d-2}s_{c+i}x^i</math>

and compare coefficients near powers <math>0</math> to <math>d-2.</math>

:<math>S(x) \stackrel{\{0,\cdots,\,d-2\}}{=} E(x)=\sum_{i=0}^{d-2}\sum_{j=0}^{n-1}e_j\alpha^{ij}\alpha^{cj}x^i.</math>

Suppose there is unreadable letter on position <math>k_1,</math> we could replace set of syndromes <math>\{s_c,\cdots,s_{c+d-2}\}</math> by set of syndromes <math>\{t_c,\cdots,t_{c+d-3}\}</math> defined by equation <math>t_i=\alpha^{k_1}s_i-s_{i+1}.</math> Suppose for an error word all restrictions by original set <math>\{s_c,\cdots,s_{c+d-2}\}</math> of syndromes hold,
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>

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>

One could consider looking for error positions from the point of view of eliminating influence of given positions similarly as for unreadable characters. If we found <math>v</math> positions such that eliminating their influence leads to obtaining set of syndromes consisting of all zeros, than there exists error vector with errors only on these coordinates.
If <math>\Lambda(x)</math> denotes the polynomial eliminating the influence of these coordinates, we obtain

:<math>S(x)\Gamma(x)\Lambda(x) \stackrel{\{k+v, \cdots, d-2\}}{=} 0.</math>

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 \frac{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.