Forney algorithm

Uses your system voice; voice and rate in settings.

Snapshot

≈ 3 min read

Names in other languages

No names in other languages are held for this entry yet.

Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.

In coding theory, 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 in 1965.

In coding theory, 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 in 1965.

Procedure

Need to introduce terminology and the setup... Code words look like polynomials. By design, the generator polynomial has consecutive roots α c , α c+1 , ..., α c+d−2 . Syndromes Error location polynomial \Lambda(x) = \prod_{i=1}^\nu (1- x \, X_i) = 1 + \sum_{i=1}^\nu \lambda_i \, x^i The zeros of Λ(x) are X 1 −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 can be determined by solving the linear system s_0 = e_1 \alpha^{(c + 0)\,i_1} + e_2 \alpha^{(c + 0)\,i_2} + \cdots \, s_1 = e_1 \alpha^{(c + 1)\,i_1} + e_2 \alpha^{(c + 1)\,i_2} + \cdots \, \cdots \, 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}} \, Where is the partial syndrome polynomial: S(x) = s_0 x^0 + s_1 x^1 + s_2 x^2 + \cdots + s_{2t-1} x^{2t-1}. Then evaluate the error values: e_j = - \frac{X_j^{1-c} \, \Omega(X_j^{-1})}{\Lambda'(X_j^{-1})} \, The value is often called the "first consecutive root" or "fcr". Some codes select , 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) which is the same as the finite field's multiplication operator, i.e. i\lambda = (1+\ldots+1)\lambda=\lambda+\ldots+\lambda. For instance, in characteristic 2, i\lambda=0, \lambda according as i is even or odd.

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

BCH code Reed–Solomon error correction

References

W. Wesley Peterson's book

Text derived from https://en.wikipedia.org/w/index.php?oldid=1320716449 under CC BY-SA 4.0; modifications have been made.

Provenance

snapshot enwiki-001320716449 · captured 1762417746.0 · version history

Cite this page as: encyclopegia.org, “Forney algorithm”, snapshot enwiki-001320716449. https://encyclopegia.org/a/forney-algorithm

Sources cited in this revision

No external citation was extracted for this revision. That is a statement about the source, not a claim that none exists.