>I have implemented an errors-and-erasures decoder
>based on the Massey-Berlekamp algorithm (although I still don't know
>why it is working - during the honour's maths course, the lecturer only
>mentioned that it is a brilliant way for decoding, but couldn't explain
>why it works...).

You may read Massey's famous 1969's paper where he established the link
between Berlekamp algorithm and the ML decoding of BCH codes. For me
Berlekamp-Massey algorithm is the simplest to implment. 

Some points in short here:

1. A (n,k) RS code is defined as time domain sequences in GF(2^m) whose
spectrum (DFT in GF(2^m)) vanishes within a window whose length is d-1.

2. Calculating the syndrone of length d-1 means taking the DFT of the
received sequence. You want to guess which time doamin error sequence can
have a spectrum as the syndrone within the window. There're of course many
such error patterns since the spectrum is only specific within the d-1 long
window and d-1 < n. But the ML decoding criteria tells you that the error
sequence corresponding to the most likely transmitted code word should
have as least "1"s in it as possible (minimum Hamming weight).

3. Now comes the Berlekamp algorithm: it works out a linear feedback shift
register (LFSR) with minium length L (linear complexity) which can generate
a spectrum whose leading part is defined by the syndrone. Step the LFSR
further you get the complete spectrum of the error sequence of length n.
Blahut's theorem tells you that taking IDFT of the resulting spectrum you
get a time domain error sequence with Hamming weight L (linear complexity
in the frequency domain = Hamming weight in the time domain). Since
Berlekamp gives you a minimum complexity you have found the minimum
Hamming weight.

4. The rest is subtracting the error sequence with the minimum Hamming
weight from the received sequence, you're done with the ML decoding.

For me it is the eaiest implementation.

Lanbaba
		
This message was sent using the Comp.DSP web interface on
www.DSPRelated.com

Hi,

Is there a performance difference between the Massey-Berlekamp decoder
and the decoder based on Euclid's algorithm for Reed-Solomon decoding?
(decoding failures, speed of execution, etc.)

Which one is the most popular in practical systems, and which one is
the easiest to implement?

(Does anyone have pointers in literature where an Errors-and-Erasures
Euclid decoder is discussed, especially the theory that can lead to an
implementation?  I have implemented an errors-and-erasures decoder
based on the Massey-Berlekamp algorithm (although I still don't know
why it is working - during the honour's maths course, the lecturer only
mentioned that it is a brilliant way for decoding, but couldn't explain
why it works...).

On the subject of RS decoders, have anyone figured out how the decoders
described by Truong et al. work?  I tried to implement them in Matlab,
but it was not very successful.

Any suggestions and pointers to the literature will be greatly
appreciated
Jaco Versfeld