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.^[1]

Procedure

Need to introduce terminology and the setup...

Syndromes

Error location polynomialCite error: A <ref> tag is missing the closing </ref> (see the help page).

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

Then evaluate the error values:^[2]

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

Λ'(x) is the formal derivative of the error locator polynomical Λ(x):^[2]

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

Derivation

Lagrange interpolation

Erasures

Modification to handle erasures

References

^ Forney 1965
^ ^a ^b Cite error: The named reference Gill-Forney was invoked but never defined (see the help page).

Forney, Jr., G. (October 1965), "On Decoding BCH Codes", IEEE Transactions on Information Theory, 11 (4): 549–557, doi:10.1109/TIT.1965.1053825, ISSN 0018-9448
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

External links

[1] Forney 1965

[Gill-Forney-2] Cite error: The named reference Gill-Forney was invoked but never defined (see the help page).

[1]

[2]