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.[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.
forney, algorithm, coding, theory, forney, algorithm, calculates, error, values, known, error, locations, used, steps, decoding, codes, reed, solomon, codes, subclass, codes, george, david, forney, developed, algorithm, contents, procedure, formal, derivative,. 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 1 Contents 1 Procedure 2 Formal derivative 3 Derivation 4 Erasures 5 See also 6 ReferencesProcedure editNeed to introduce terminology and the setup Code words look like polynomials By design the generator polynomial has consecutive roots ac ac 1 ac d 2 SyndromesError location polynomial 2 L x i 1 n 1 x X i 1 i 1 n l i x i displaystyle Lambda x prod i 1 nu 1 x X i 1 sum i 1 nu lambda i x i nbsp The zeros of L x are X1 1 Xn 1 The zeros are the reciprocals of the error locations X j a i j displaystyle X j alpha i j nbsp 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 s 0 e 1 a c 0 i 1 e 2 a c 0 i 2 displaystyle s 0 e 1 alpha c 0 i 1 e 2 alpha c 0 i 2 cdots nbsp s 1 e 1 a c 1 i 1 e 2 a c 1 i 2 displaystyle s 1 e 1 alpha c 1 i 1 e 2 alpha c 1 i 2 cdots nbsp displaystyle cdots nbsp 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 W x S x L x mod x 2 t displaystyle Omega x S x Lambda x pmod x 2t nbsp Where S x is the partial syndrome polynomial 4 S x s 0 x 0 s 1 x 1 s 2 x 2 s 2 t 1 x 2 t 1 displaystyle S x s 0 x 0 s 1 x 1 s 2 x 2 cdots s 2t 1 x 2t 1 nbsp Then evaluate the error values 3 e j X j 1 c W X j 1 L X j 1 displaystyle e j frac X j 1 c Omega X j 1 Lambda X j 1 nbsp The value c is often called the first consecutive root or fcr Some codes select c 1 so the expression simplifies to e j W X j 1 L X j 1 displaystyle e j frac Omega X j 1 Lambda X j 1 nbsp Formal derivative editMain article Formal derivative L x is the formal derivative of the error locator polynomial L x 3 L x i 1 n i l i x i 1 displaystyle Lambda x sum i 1 nu i cdot lambda i x i 1 nbsp In the above expression note that i is an integer and li 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 l 1 1 l l l displaystyle i lambda 1 ldots 1 lambda lambda ldots lambda nbsp For instance in characteristic 2 i l 0 l displaystyle i lambda 0 lambda nbsp according as i is even or odd Derivation editLagrange interpolationGill n d pp 52 54 gives a derivation of the Forney algorithm Erasures editDefine the erasure locator polynomial G x 1 x a j i displaystyle Gamma x prod 1 x alpha j i nbsp Where the erasure locations are given by ji Apply the procedure described above substituting G for L If both errors and erasures are present use the error and erasure locator polynomial PS x L x G x displaystyle Psi x Lambda x Gamma x nbsp See also editBCH code Reed Solomon error correctionReferences edit Forney 1965 Gill n d p 24 a b c Gill n d p 47 Gill n d p 48 Forney 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 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 W Wesley Peterson s book Retrieved from https en wikipedia org w index php title Forney algorithm amp oldid 1223153625, wikipedia, wiki, book, books, library,