Forums

Massey-Berlekamp vs Euclid's decoding?

Started by Unknown October 19, 2005
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

>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