Forney algorithm

The Forney algorithm (or Forney's algorithm) calculates the error values at known error locations. It is used as one of the steps in decoding BCH codes and Reed–Solomon codes (a subclass of BCH codes). George David Forney, Jr. developed the algorithm.

Procedure

Need to introduce terminology and the setup...

Syndromes

Error location polynomial

The zeros of Λ(x) are X₁^-1, ... , X_ν^-1. The zeros are the reciprocals of the error locations $X_{j}=\alpha ^{i_{j}}$.

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.

In the more general case, the error weights $e_{j}$ can be determined by solving the linear system

$s_{1}=e_{1}\alpha ^{c\,i_{1}}+e_{2}\alpha ^{c\,i_{2}}+\ldots$

$s_{2}=e_{1}\alpha ^{(c+1)\,i_{1}}+e_{2}\alpha ^{(c+1)\,i_{2}}+\ldots$

. . .

However, there is a more efficient method known as the Forney algorithm, which is based on Lagrange interpolation. First calculate the error evaluator polynomial

$\Omega (x)=S(x)\,\Lambda (x){\pmod {x^{2t}}}$

Then evaluate the error values:

$e_{j}=-{\frac {X_{j}^{1-c}\,\Omega (X_{j}^{-1})}{\Lambda '(X_{j}^{-1})}}$

For a narrow-sense BCH codes, c = 1, so the expression simplifies to:

$e_{j}=-{\frac {\Omega (X_{j}^{-1})}{\Lambda '(X_{j}^{-1})}}$

Formal derivative

Main article: Formal derivative

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

$\Lambda '(x)=\Sigma _{i=1}^{\nu }i\lambda _{i}x^{i-1}$

Derivation

Lagrange interpolation

Erasures

Modification to handle erasures

See also

• BCH code
• Reed–Solomon error correction

References

• Forney, Jr., G. (October 1965), "On Decoding BCH Codes", IEEE Transactions on Information Theory, 11 (4): 549–557, doi:10.1109/TIT.1965.1053825
• Gill, John (unknown), EE387 Notes #7, Handout #28 (PDF), Stanford University, pp. 42–45, retrieved April 21, 2010 {{citation}}: Check date values in: |year= (help)CS1 maint: year (link)
• W. Wesley Peterson's book