Reed Solomon Decoder, Forney’s Equation

In the previous articles, I described how to find the syndromes, the error locater polynomial, and the roots of that polynomial.  The last bit of information needed is the error magnitudes.  Forney’s equation can be used to determine this. 

Forney’s equation is as follows:

  • S(x) = S_n x^{n-1} + ... + S_2 x + S_1
  • \Lambda(x) = \Lambda_{m-1}x^{m-1}+ ... +\Lambda_1 x + \Lambda_0
  • \Omega(x) = (\Lambda(x) S(x)) \% x^{n}
  • \Lambda^\prime(x) = \Lambda_{m-1}x^{m-2} + ... + \Lambda_3 x^2 \Lambda_1
  •  e_k = \frac{\Omega(X_k^{-1})}{\Lambda^\prime(X_k^{-1})}

In the above equations, X_k^{-1} is the k’th root of the error locater polynomial.  It is not the inverse of the root.  In this context, X_k refers to the inverse of the root, and log(X_k) gives the location of the error.

There are a few steps to the calculation.  \Omega(x) must be determined, and both \Omega(x) and \Lambda^\prime(x) must be evaluated with the roots of the error locater polynomial being raised several powers.  Finally, the evaluated \Lambda^\prime(X_k^{-1}) must itself be inverted and multiplied by the evaluated \Omega(X_k^{-1}).

The implementation again uses an array of Galois Field multipliers, as well as the N-input summing circuit.  The basic algorithm used in my implementation is:

Starting with the lowest terms for omega and lprime.  Initialize
the root vector to all 1's.  eg 0x01.
1.)  Calculate the next value of omega.  omega_n is computed by
adding all products of lambda_a * S_b where a + b = n.
2.)  Multiply the root vector by omega_n.  Save the result as "the
omega vector."
3.)  Multiply the root vector by the appropriate value from lambda.
The result is stored in "the lprime vector."
4.)  Multiply the input roots by the root vector.  The result is
stored back to "the root vector."
5.)  Repeat until the omega and lprime vectors hold the evaluated
values of omega(Ek^-1) and lprime(Ek^-1) for each root, Ek^-1.
6.)  Find the inverse of each element in the lprime vector, and
multiply this by each corresponding element in the omega vector.

In my implementation I store the syndromes, in reverse order, in a vector that is longer then the number of terms in the error locater polynomial.  Shifting this vector up on each iteration allows the value of omega to be calculated naturally.  The remainder is simply selecting the correct inputs to the multipliers at the correct times.

In my implementation, the computation of the error magnitudes was the largest portion of the design, mainly because of the need to store temporary results.  It is likely that some creative resource reuse could reduce the number of registers, and possibly reduce the amount of logic needed.  The code for this part of the decoder is: VHDL: Reed-Solomon Decoder Forney Equation.

This entry was posted in FPGA and tagged . Bookmark the permalink.

Comments are closed.