en>Zfeinst: no longer stub

2012-08-29T12:19:56Z

no longer stub

New page

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 code]]s and [[Reed–Solomon error correction|Reed–Solomon codes]] (a subclass of BCH codes). [[Dave Forney|George David Forney, Jr.]] developed the algorithm.<ref>{{Harvnb|Forney|1965}}</ref>

==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<ref>{{Harvnb|Gill|unknown|p=24}}</ref>

:<math>\Lambda(x) = \prod_{i=1}^\nu (1- x \, X_i) = 1 + \sum_{i=1}^\nu \lambda_i \, x^i</math>

The zeros of Λ(''x'') are ''X''1−1, ..., ''X''''ν''−1. The zeros are the reciprocals of the error locations <math>X_j = \alpha^{i_j}</math>.

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 <math>e_j</math> can be determined by solving the linear system

:<math>s_0 = e_1 \alpha^{(c + 0)\,i_1} + e_2 \alpha^{(c + 0)\,i_2} + \cdots \, </math>
:<math>s_1 = e_1 \alpha^{(c + 1)\,i_1} + e_2 \alpha^{(c + 1)\,i_2} + \cdots \, </math>
:<math> \cdots \, </math>

However, there is a more efficient method known as the Forney algorithm, which is based on [[Lagrange polynomial|Lagrange interpolation]]. First calculate the error evaluator polynomial<ref name="Gill-Forney">{{Harvnb|Gill|unknown|p=47}}</ref>

:<math>\Omega(x) = S(x)\,\Lambda(x) \pmod{x^{2t}} \, </math>


Where ''S''(''x'') is the partial syndrome polynomial:<ref>{{Harvtxt|Gill|unknown|p=48}}</ref>
:<math>S(x) = s_0 x^0 + s_1 x^1 + s_2 x^2 + \cdots + s_{2t-1} x^{2t-1}.</math>

Then evaluate the error values:<ref name="Gill-Forney"/>


:<math>e_j = - \frac{X_j^{1-c} \, \Omega(X_j^{-1})}{\Lambda'(X_j^{-1})} \, </math>


Some codes select ''c'' = 1, so the expression simplifies to:
:<math>e_j = - \frac{\Omega(X_j^{-1})}{\Lambda'(X_j^{-1})}</math>

==Formal derivative==
{{Main|Formal derivative}}

Λ'(''x'') is the [[formal derivative]] of the error locator polynomial Λ(''x''):<ref name="Gill-Forney"/>
:<math>\Lambda'(x) = \sum_{i=1}^{\nu} i \, \cdot \, \lambda_i \, x^{i-1}</math>


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]]

{{Harvtxt|Gill|unknown|pp=52–54}} gives a derivation of the Forney algorithm.

==Erasures==
Define the erasure locator polynomial
:<math>\Gamma(x) = \prod (1- x \, \alpha^{j_i})</math>
Where the erasure locations are given by ''ji''. Apply the procedure described above, substituting Γ for Λ.

If both errors and erasures are present, use the error-and-erasure locator polynomial
:<math>\Psi(x) = \Lambda(x) \, \Gamma(x)</math>

==See also==
*[[BCH code]]
*[[Reed–Solomon error correction]]

==References==
{{reflist|30em}}
*{{Citation
|first= G.
|last= Forney, Jr.
|authorlink=Dave Forney
|title= On Decoding BCH Codes
|journal= [[IEEE Transactions on Information Theory]]
|volume= 11
|issue= 4
|date= October 1965
|pages= 549–557
|issn= 0018-9448
|doi= 10.1109/TIT.1965.1053825}}
*{{Citation
|last=Gill
|first= John
|title= EE387 Notes #7, Handout #28
|year= unknown
|accessdate= April 21, 2010
|pages=42–45
|publisher= Stanford University
|url= http://www.stanford.edu/class/ee387/handouts/notes7.pdf
|doi=}}
* [[W. Wesley Peterson]]'s book

==External links==

{{DEFAULTSORT:Forney algorithm}}
[[Category:Error detection and correction]]
[[Category:Coding theory]]

Indifference price - Revision history

en>Zfeinst: no longer stub