Content deleted Content added
Line 336:
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\left(x\alpha^{k_i} - 1\right).</math>
Set values on unreadable positions to 0 and compute the syndromes.
Line 386:
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
| |||