Editing BCH code (section)

===Calculate error values===
Once the error locations are known, the next step is to determine the error values at those locations. The error values are then used to correct the received values at those locations to recover the original codeword.

For the case of binary BCH, (with all characters readable) this is trivial; just flip the bits for the received word at these positions, and we have the corrected code word. In the more general case, the error weights <math>e_j</math> can be determined by solving the linear system
: <math>\begin{align}
      s_c & = e_1 \alpha^{c\,i_1} + e_2 \alpha^{c\,i_2} + \cdots \\
  s_{c+1} & = e_1 \alpha^{(c + 1)\,i_1} + e_2 \alpha^{(c + 1)\,i_2} + \cdots \\
          & {}\ \vdots
\end{align}</math>

==== Forney algorithm ====
However, there is a more efficient method known as the [[Forney algorithm]].

Let
:<math>S(x) = s_c + s_{c+1}x + s_{c+2}x^2 + \cdots + s_{c+d-2}x^{d-2}.</math>
:<math>v \leqslant d-1, \lambda_0 \neq 0 \qquad \Lambda(x) = \sum_{i=0}^v\lambda_i x^i = \lambda_0 \prod_{k=0}^{v} \left(\alpha^{-i_k}x - 1\right).</math>

And the error evaluator polynomial<ref name="Gill-Forney">{{Harvnb|Gill|n.d.|p=47}}</ref>
:<math>\Omega(x) \equiv S(x) \Lambda(x) \bmod{x^{d-1}}</math>

Finally:
:<math>\Lambda'(x) = \sum_{i=1}^v i \cdot \lambda_i x^{i-1},</math>

where
:<math>i \cdot x := \sum_{k=1}^i x.</math>

Than if syndromes could be explained by an error word, which could be nonzero only on positions <math>i_k</math>, then error values are
:<math>e_k = -{\alpha^{i_k}\Omega\left(\alpha^{-i_k}\right) \over \alpha^{c\cdot i_k}\Lambda'\left(\alpha^{-i_k}\right)}.</math>

For narrow-sense BCH codes, ''c'' = 1, so the expression simplifies to:
:<math>e_k = -{\Omega\left(\alpha^{-i_k}\right) \over \Lambda'\left(\alpha^{-i_k}\right)}.</math>

==== Explanation of Forney algorithm computation ====
It is based on [[Lagrange polynomial|Lagrange interpolation]] and techniques of [[generating function]]s.

Consider <math>S(x)\Lambda(x),</math> and for the sake of simplicity suppose <math>\lambda_k = 0</math> for <math>k > v,</math> and <math>s_k = 0</math> for <math>k > c + d - 2.</math> Then

:<math>S(x)\Lambda(x) = \sum_{j=0}^{\infty}\sum_{i=0}^j s_{j-i+1}\lambda_i x^j.</math>

:<math>\begin{align}
  S(x)\Lambda(x)
    &= S(x) \left \{ \lambda_0\prod_{\ell=1}^v \left (\alpha^{i_\ell}x-1 \right ) \right \} \\
    &= \left \{ \sum_{i=0}^{d-2}\sum_{j=1}^v e_j\alpha^{(c+i)\cdot i_j} x^i \right \} \left \{ \lambda_0\prod_{\ell=1}^v \left (\alpha^{i_\ell}x-1 \right ) \right \} \\
    &= \left \{ \sum_{j=1}^v e_j \alpha^{c i_j}\sum_{i=0}^{d-2} \left (\alpha^{i_j} \right )^i x^i \right \} \left \{ \lambda_0\prod_{\ell=1}^v \left (\alpha^{i_\ell}x-1 \right ) \right \} \\
    &= \left \{ \sum_{j=1}^v e_j \alpha^{c i_j} \frac{\left (x \alpha^{i_j} \right )^{d-1}-1}{x \alpha^{i_j}-1} \right \} \left \{ \lambda_0 \prod_{\ell=1}^v \left (\alpha^{i_\ell}x-1 \right ) \right \} \\
    &= \lambda_0 \sum_{j=1}^v e_j\alpha^{c i_j} \frac{ \left (x\alpha^{i_j} \right)^{d-1}-1}{x\alpha^{i_j}-1} \prod_{\ell=1}^v \left (\alpha^{i_\ell}x-1 \right ) \\
    &= \lambda_0  \sum_{j=1}^v e_j\alpha^{c i_j} \left ( \left (x\alpha^{i_j} \right)^{d-1}-1 \right ) \prod_{\ell\in\{1,\cdots,v\}\setminus\{j\}} \left (\alpha^{i_\ell}x-1 \right )
\end{align}</math>

We want to compute unknowns <math>e_j,</math> and we could simplify the context by removing the <math>\left(x\alpha^{i_j}\right)^{d-1}</math> terms. This leads to the error evaluator polynomial
:<math>\Omega(x) \equiv S(x) \Lambda(x) \bmod{x^{d-1}}.</math>

Thanks to <math>v\leqslant d-1</math> we have
:<math>\Omega(x) = -\lambda_0\sum_{j=1}^v e_j\alpha^{c i_j} \prod_{\ell\in\{1,\cdots,v\}\setminus\{j\}} \left(\alpha^{i_\ell}x - 1\right).</math>

Thanks to <math>\Lambda</math> (the Lagrange interpolation trick) the sum degenerates to only one summand for <math>x = \alpha^{-i_k}</math>

:<math>\Omega \left(\alpha^{-i_k}\right) = -\lambda_0 e_k\alpha^{c\cdot i_k}\prod_{\ell\in\{1,\cdots,v\}\setminus\{k\}} \left(\alpha^{i_\ell}\alpha^{-i_k} - 1\right).</math>

To get <math>e_k</math> we just should get rid of the product. We could compute the product directly from already computed roots <math>\alpha^{-i_j}</math> of <math>\Lambda,</math> but we could use simpler form.

As [[formal derivative]]
:<math>\Lambda'(x) = \lambda_0\sum_{j=1}^v \alpha^{i_j}\prod_{\ell\in\{1,\cdots,v\}\setminus\{j\}} \left(\alpha^{i_\ell}x - 1\right),</math>

we get again only one summand in
:<math>\Lambda'\left(\alpha^{-i_k}\right) = \lambda_0\alpha^{i_k}\prod_{\ell\in\{1,\cdots,v\}\setminus\{k\}} \left(\alpha^{i_\ell}\alpha^{-i_k} - 1\right).</math>

So finally
:<math>e_k = -\frac{\alpha^{i_k}\Omega \left(\alpha^{-i_k}\right)}{\alpha^{c\cdot i_k}\Lambda' \left(\alpha^{-i_k}\right)}.</math>

This formula is advantageous when one computes the formal derivative of <math>\Lambda</math> form
:<math>\Lambda(x) = \sum_{i=1}^v \lambda_i x^i</math>

yielding:
:<math>\Lambda'(x) = \sum_{i=1}^v i \cdot \lambda_i x^{i-1},</math>

where
:<math>i\cdot x := \sum_{k=1}^i x.</math>