Forney algorithm

Enjoyed the article? Share:

In [[coding 1}}, so the expression simplifies to:

$e_j = - \frac{\Omega(X_j^{-1})}{\Lambda'(X_j^{-1})}$

Formal derivative

Λ'(x) is the formal derivative of the error locator polynomial Λ(x):

$\Lambda'(x) = \sum_{i=1}^{\nu} i \, \cdot \, \lambda_i \, x^{i-1}$

In the above expression, note that i is an integer, and λ_i would be an element of the finite field. The operator · represents ordinary multiplication (repeated addition in the finite field) and not the finite field's multiplication operator.

Derivation

Lagrange interpolation gives a derivation of the Forney algorithm.

Erasures

Define the erasure locator polynomial

$\Gamma(x) = \prod (1- x \, \alpha^{j_i})$

Where the erasure locations are given by j_i. Apply the procedure described above, substituting Γ for Λ.

If both errors and erasures are present, use the error-and-erasure locator polynomial

$\Psi(x) = \Lambda(x) \, \Gamma(x)$

See Also on BitcoinWiki

• BCH code
• Reed–Solomon error correction

Source

http://wikipedia.org/