2

I'm a software developer with a moderate mathematical background, and I've been trying to write a software implementation of reed-solomon decoding from scratch, as a learning experience.

I'm using the following paper as my main resource for developing the decoder, and it seems they don't explain something well, or I don't see the connection.

http://downloads.bbc.co.uk/rd/pubs/whp/whp-pdf-files/WHP031.pdf

The process of decoding takes the received message as a polynomial $R(x)$, calculates the syndromes as a polyomial S(x). The next step runs the Euclidean algorithm on S(x) to output lambda(x) and omega(x), which are then fed to later stages of the decoder.

The paper indicates that $\Lambda(x)$ can be calculated from $S(x)$ using Berlekamp's algorithm, however, it does not seem to indicate how to calculate $\Omega(x)$ using Berlekamp's algorithm, or perhaps from $\Lambda(x)$.

If only Euclid's algorithm can be used to calculate $\Omega(x)$, what's the point of explaining how $\Lambda(x)$ can be calculated using Berlekamp's?

Either there is no point, which would be strange, and thus I have to perform Euclid's algorithm no matter what, or there is a point, and somehow I can calculate $\Omega(x)$ either during Berlekamp's or from the products thereof.

What gives?

Some direction in the paper and the approach -

Page 21 shows a block diagram of the system. Pages 15 through 21 show the basic definitions of each part of the process.

The received message $R(x)$ is a sequence of bytes that is treated as a polynomial on the galois field.

From $R(x)$ we calculate the syndromes, represented as either coefficients $S_0, S_1, ...$ or as the polynomial formed from those coefficients $S(x)$. The syndromes are repeatedly used during the error detection, location, and correction process. Pages 22 through 24 show a worked example of various methods to calculate the coefficients of $S(x)$.

From $S(x)$ we can use Euclid's to calculate $\Omega(x)$ and $\Lambda(x)$. Page 25 shows a worked example of this. $\Omega(x)$ is the error magnitude polynomial, and $\Lambda(x)$ is the error locator polynomial.

From $\Lambda(x)$ we run the Chien search (pages 29,30) to calculate the error positions polynomial $X(x)$.

From $\Omega(x)$ and the derivative of $\Lambda(x)$, $\Lambda'(x)$, we calculate the error value polynomial $\frac{\Omega(x)}{\Lambda'(x)}$ using Forney's method (page 31).

Using the zero elements of the error locations polynomial, we add the indicated elements of the error value polynomial to the received message $R(x)$ to produce the corrected message transmitted message $T(x)$, and thus complete the task.

antiduh
  • 151
  • Could you give the pages where those polynomials are defined, or you define them. That paper has 47 pages. – OR. Jul 19 '13 at 23:59
  • Ah, my apologies. I'll fill that in. – antiduh Jul 20 '13 at 13:27
  • As I am working on the same topic, here are my two pennies (even if the post is gettingold now): an important step in the process of error correction is indeed the computation of the error location polynomial $\Lambda (x)$ from the syndromes. As far as I know, there are three approaches available: 1) direct solution of a Toeplitz system (known as the Peterson-Gorenstein-Zierler method), 2) Berlekamp's algorithm (incremental construction of the polynomial) and 3) the extended Euclidean algorithm (computation of a gcd). –  Mar 20 '14 at 16:56
  • This is a late comment, but the pdf file has an error regarding the encoded message. The encoded message T(x) = M(x) x^(n-k) - r(x). The remainder is subtracted to produce an encoded message. If using binary field based coefficients, it doesn't matter (add and subtract are the same, both are xor), but if using a non-binary based finite field, it matters. Take a look at wiki article for Reed Solomon – rcgldr Mar 29 '16 at 23:45

1 Answers1

3

I seem to have found my answer, and I'm embarrassed I didn't see it earlier. Sorry to have drawn your attention for such a simple mistake.

Page 19 shows exactly how to derive $\Omega(x)$ from $S(x)$ and $\Lambda(x)$ -

$\Omega(x) = \left[S(x) \Lambda(x)\right]\ mod\ x^{2t}$

$\Omega_0 = S_b$

$\Omega_1 = S_{b+1} + S_b \Lambda_1 $

..

antiduh
  • 151