Incoding theory, the Forney algorithm (orForney'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]
The zeros of Λ(x) are X1−1, ..., Xν−1. The zeros are the reciprocals of the error locations .
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 ej can be determined by solving the linear system
However, there is a more efficient method known as the Forney algorithm, which is based on Lagrange interpolation. First calculate the error evaluator polynomial[3]
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) which is the same as the finite field's multiplication operator, i.e.
For instance, in characteristic 2, according as i is even or odd.
Gill, John (n.d.), EE387 Notes #7, Handout #28(PDF), Stanford University, pp. 42–45, archived from the original(PDF) on June 30, 2014, retrieved April 21, 2010