# Forney algorithm

Jump to: navigation, search

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]

## 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[2]

${\displaystyle \Lambda (x)=\prod _{i=1}^{\nu }(1-x\,X_{i})=1+\sum _{i=1}^{\nu }\lambda _{i}\,x^{i}}$

The zeros of Λ(x) are X1−1, ..., Xν−1. The zeros are the reciprocals of the error locations ${\displaystyle 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 ej can be determined by solving the linear system

${\displaystyle s_{0}=e_{1}\alpha ^{(c+0)\,i_{1}}+e_{2}\alpha ^{(c+0)\,i_{2}}+\cdots \,}$
${\displaystyle s_{1}=e_{1}\alpha ^{(c+1)\,i_{1}}+e_{2}\alpha ^{(c+1)\,i_{2}}+\cdots \,}$
${\displaystyle \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[3]

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

Where S(x) is the partial syndrome polynomial:[4]

${\displaystyle 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:[3]

${\displaystyle e_{j}=-{\frac {X_{j}^{1-c}\,\Omega (X_{j}^{-1})}{\Lambda '(X_{j}^{-1})}}\,}$

The value c is often called the "first consecutive root" or "fcr". Some codes select c = 1, so the expression simplifies to:

${\displaystyle e_{j}=-{\frac {\Omega (X_{j}^{-1})}{\Lambda '(X_{j}^{-1})}}}$

## Formal derivative

Main article: Formal derivative

Λ'(x) is the formal derivative of the error locator polynomial Λ(x):[3]

${\displaystyle \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) and not the finite field's multiplication operator.

## Derivation

Lagrange interpolation

Gill (n.d., pp. 52–54) gives a derivation of the Forney algorithm.

## Erasures

Define the erasure locator polynomial

${\displaystyle \Gamma (x)=\prod (1-x\,\alpha ^{j_{i}})}$

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

${\displaystyle \Psi (x)=\Lambda (x)\,\Gamma (x)}$

## References

1. ^ Forney 1965
2. ^ Gill n.d., p. 24
3. ^ a b c Gill n.d., p. 47
4. ^ Gill (n.d., p. 48)