Forums

Erasures decoding of Reed Solomon codes

Started by Mike McLernon August 31, 2005
Hi,

I'm building an erasures decoder for Reed Solomon codes, and I'm having 
trouble when the number of erasures (without errors) exceeds (n-k)/2, the 
error-correcting capability of the code.  When my code has no errors, and 
only erasures, I would expect the error locator polynomial to be uniquely 1. 
When I have up to (n-k)/2 erasures, that's exactly what happens.  However, 
when the number of erasures exceeds (n-k)/2, my error locator polynomial 
exhibits unusual behavior.  I run into the following circumstances in these 
cases:

1)    the polynomial has no roots in the field of the code, or
2)    the polynomial has repeated roots, or
3)    the polynomial's roots are a subset of the erasure locations, or
4)    the polynomial's roots are different from the erasure locations.

Scenarios 1-3 seem reasonable, in that I can discard the information in the 
error locator polynomial.  I already have that information from the erasure 
locator polynomial.  However, scenario 4 is troublesome, and I'm not quite 
sure how to handle that one.

Any help would be appreciated.

Mike McLernon 


Hi Mike


> I'm building an erasures decoder for Reed Solomon codes, and I'm having > trouble when the number of erasures (without errors) exceeds (n-k)/2, the > error-correcting capability of the code. When my code has no errors, and > only erasures, I would expect the error locator polynomial to be uniquely 1. > When I have up to (n-k)/2 erasures, that's exactly what happens. However, > when the number of erasures exceeds (n-k)/2, my error locator polynomial > exhibits unusual behavior. I run into the following circumstances in these > cases:
Are you using the Massey-Berlekamp algorithm or Euclid's algorithm? As you know, a Reed-Solomon code can correct e+2t <= (less than or equal to) n-k, where e is the number of erasures and 2t is the number of errors. Usually you compute the erasure locator polynomial and use it as the initial polynomial for your error locator polynomial of your your decoding algorithm (I know this is true for Massey-Berlekamp, maybe one of the experts can confirm if this is true for Euclid as well...) I have Matlab source of an errors-and-erasures decoder for the Massey-Berlekamp decoder which is based on the notes - http://www.ee.ucla.edu/~matache/rsc/slide.html, if you are interested. Warm regards here from South Africa Jaco
Hi Jaco,

Thanks for sending me your thoughts -- unfortunately, I think that the 
example URL you sent me does not do the Berlekamp quite right.  It only 
iterates twice, and it should iterate four times.  There's also a mistake in 
the algebra -- a simple error of not copying a coefficient properly. 
Anyway, I'm able to reproduce the results given in Wicker, pg. 232, but I'm 
still not getting the general case quite right.  I am using Berlekamp, so at 
least we're on common ground there.

I'd be interested to know if your code works for cases where the number of 
erasures exceeds (n-k)/2.  If so, then we can conclude that I'm definitely 
doing something wrong.

Cheers,
Mike


<jaco.versfeld@gmail.com> wrote in message 
news:1125569564.964113.46080@g14g2000cwa.googlegroups.com...
> Hi Mike > > >> I'm building an erasures decoder for Reed Solomon codes, and I'm having >> trouble when the number of erasures (without errors) exceeds (n-k)/2, the >> error-correcting capability of the code. When my code has no errors, and >> only erasures, I would expect the error locator polynomial to be uniquely >> 1. >> When I have up to (n-k)/2 erasures, that's exactly what happens. >> However, >> when the number of erasures exceeds (n-k)/2, my error locator polynomial >> exhibits unusual behavior. I run into the following circumstances in >> these >> cases: > > Are you using the Massey-Berlekamp algorithm or Euclid's algorithm? > > As you know, a Reed-Solomon code can correct e+2t <= (less than or > equal to) n-k, where e is the number of erasures and 2t is the number > of errors. Usually you compute the erasure locator polynomial and use > it as the initial polynomial for your error locator polynomial of your > your decoding algorithm (I know this is true for Massey-Berlekamp, > maybe one of the experts can confirm if this is true for Euclid as > well...) > > I have Matlab source of an errors-and-erasures decoder for the > Massey-Berlekamp decoder which is based on the notes - > http://www.ee.ucla.edu/~matache/rsc/slide.html, if you are interested. > > Warm regards here from South Africa > Jaco >
Mike McLernon wrote:
> I'd be interested to know if your code works for cases where the number of > erasures exceeds (n-k)/2. If so, then we can conclude that I'm definitely > doing something wrong.
Hi Mike, I did a check on my code and as expected, it could decode successfully when the number of erasures exceeded (n-k)/2. I did run into a bug in my software - I could only decode erasures when the number was smaller than (n-k). The theory however states that you can correct up to d_{min} - 1 erasures, which for the RS case is (n-k) [d_{min} = n - k + 1]. Unfortunately, my bursary expired, and I now have to work it back for a large South African telecommunications company, which means that I don't get time to do any research. Otherwise I would fix the bug. However, I can provide you the Matlab code (and for anyone else interested)... Kind regards, Jaco Versfeld (If anyone knows of a research position in FEC, please let me know...)
Hi,Mike:
I met the same case with you. But i use the different BM written in Clark
and Cain. When the initialized psi has 2t order, the BM can not work well,
and can not tell me it can not work.
I am expected to discuss with you, if you have time.
 

> >Mike McLernon wrote: >> I'd be interested to know if your code works for cases where the number
of
>> erasures exceeds (n-k)/2. If so, then we can conclude that I'm
definitely
>> doing something wrong. > >Hi Mike, > >I did a check on my code and as expected, it could decode successfully >when the number of erasures exceeded (n-k)/2. I did run into a bug in >my software - I could only decode erasures when the number was smaller >than (n-k). The theory however states that you can correct up to >d_{min} - 1 erasures, which for the RS case is (n-k) [d_{min} = n - k + >1]. Unfortunately, my bursary expired, and I now have to work it back >for a large South African telecommunications company, which means that >I don't get time to do any research. Otherwise I would fix the bug. >However, I can provide you the Matlab code (and for anyone else >interested)... > >Kind regards, >Jaco Versfeld > >(If anyone knows of a research position in FEC, please let me know...) > >
> >I did a check on my code and as expected, it could decode successfully > >when the number of erasures exceeded (n-k)/2. I did run into a bug in > >my software - I could only decode erasures when the number was smaller > >than (n-k). The theory however states that you can correct up to > >d_{min} - 1 erasures, which for the RS case is (n-k) [d_{min} = n - k + 1]
When d_{min}-1 = n-k erasures have occurred, the erasure locator polynomial is of degree n-k and thus has n-k+1= d_{min} coefficients. The syndrome polynomial is of degree n-k-1and so has n-k coefficients. Many implementations fail in this extreme case because the implementer allots only n-k cells to hold the coefficients of the erasure locator (and errata locator) polynomials even though n-k+1 cells are needed. Hope this helps.
Le mercredi 31 ao&ucirc;t 2005 20:35:16 UTC+1, Mike McLernon a &eacute;crit&nbsp;:
> Hi, > > I'm building an erasures decoder for Reed Solomon codes, and I'm having > trouble when the number of erasures (without errors) exceeds (n-k)/2, the > error-correcting capability of the code. When my code has no errors, and > only erasures, I would expect the error locator polynomial to be uniquely 1. > When I have up to (n-k)/2 erasures, that's exactly what happens. However, > when the number of erasures exceeds (n-k)/2, my error locator polynomial > exhibits unusual behavior. I run into the following circumstances in these > cases: > > 1) the polynomial has no roots in the field of the code, or > 2) the polynomial has repeated roots, or > 3) the polynomial's roots are a subset of the erasure locations, or > 4) the polynomial's roots are different from the erasure locations. > > Scenarios 1-3 seem reasonable, in that I can discard the information in the > error locator polynomial. I already have that information from the erasure > locator polynomial. However, scenario 4 is troublesome, and I'm not quite > sure how to handle that one. > > Any help would be appreciated. > > Mike McLernon
can any one provide me the source code of reed solomon in matlab with BM or euclidien or PGZ method please? thx in advance
On Sat, 21 May 2016 14:55:38 -0700, kortas.manel wrote:

> Le mercredi 31 ao&ucirc;t 2005 20:35:16 UTC+1, Mike McLernon a &eacute;crit&nbsp;: >> Hi, >> >> I'm building an erasures decoder for Reed Solomon codes, and I'm having >> trouble when the number of erasures (without errors) exceeds (n-k)/2, >> the error-correcting capability of the code. When my code has no >> errors, and only erasures, I would expect the error locator polynomial >> to be uniquely 1. >> When I have up to (n-k)/2 erasures, that's exactly what happens. >> However, when the number of erasures exceeds (n-k)/2, my error locator >> polynomial exhibits unusual behavior. I run into the following >> circumstances in these cases: >> >> 1) the polynomial has no roots in the field of the code, or 2) >> the polynomial has repeated roots, or 3) the polynomial's roots are >> a subset of the erasure locations, or 4) the polynomial's roots are >> different from the erasure locations. >> >> Scenarios 1-3 seem reasonable, in that I can discard the information in >> the error locator polynomial. I already have that information from the >> erasure locator polynomial. However, scenario 4 is troublesome, and >> I'm not quite sure how to handle that one. >> >> Any help would be appreciated. >> >> Mike McLernon > can any one provide me the source code of reed solomon in matlab with BM > or euclidien or PGZ method please? thx in advance
Not for free, generally, and not if you're a student, ever. We and you both benefit from you doing your own homework. If you can't do your own homework -- switch majors. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com I'm looking for work -- see my website!
Tim Wescott  <seemywebsite@myfooter.really> wrote:

>On Sat, 21 May 2016 14:55:38 -0700, kortas.manel wrote: > >> Le mercredi 31 ao&ucirc;t 2005 20:35:16 UTC+1, Mike McLernon a &eacute;crit&nbsp;: >>> Hi, >>> >>> I'm building an erasures decoder for Reed Solomon codes, and I'm having >>> trouble when the number of erasures (without errors) exceeds (n-k)/2, >>> the error-correcting capability of the code. When my code has no >>> errors, and only erasures, I would expect the error locator polynomial >>> to be uniquely 1. >>> When I have up to (n-k)/2 erasures, that's exactly what happens. >>> However, when the number of erasures exceeds (n-k)/2, my error locator >>> polynomial exhibits unusual behavior. I run into the following >>> circumstances in these cases: >>> >>> 1) the polynomial has no roots in the field of the code, or 2) >>> the polynomial has repeated roots, or 3) the polynomial's roots are >>> a subset of the erasure locations, or 4) the polynomial's roots are >>> different from the erasure locations. >>> >>> Scenarios 1-3 seem reasonable, in that I can discard the information in >>> the error locator polynomial. I already have that information from the >>> erasure locator polynomial. However, scenario 4 is troublesome, and >>> I'm not quite sure how to handle that one. >>> >>> Any help would be appreciated. >>> >>> Mike McLernon >> can any one provide me the source code of reed solomon in matlab with BM >> or euclidien or PGZ method please? thx in advance > >Not for free, generally, and not if you're a student, ever. We and you >both benefit from you doing your own homework. If you can't do your own >homework -- switch majors.
Googling on something like "error correction cookbook" could get the OP an answer, but may not lead to understanding. I highly recommend McEliece's textbook for a clear description of the Euclidean algorithm (termed by some here the generalized Euclidean algorithm), from which one can easily code it into Matlab, C, or whatever. Once that is working for the errors-only case, it is not so difficult to add the erasure decoding case using Forney's polynomial, but you might need to consult a further textbook such as Berlekamp's. What many people fail to get entirely correct is detecting all of the undecodable cases. There are generally three tests that need to be applied to do this properly, and I believe in past posts to this group I've described how to do this. If one wants to learn the subject more completely, it's a good idea to be able to implement the main alternatives to the Euclidean algorithm -- the Berlekamp algorithm (sometimes called Massey -Berlekamp by some), and the Welch-Berlekamp algorithm (which also handles non-cyclic Reed-Solomon codes). With a bit more work these algorithms can be generalized to decode binary BCH codes and Algebraic Geometry (Goppa) codes. Steve
On Mon, 23 May 2016 12:46:22 -0500, Tim Wescott wrote:

> On Sat, 21 May 2016 14:55:38 -0700, kortas.manel wrote: > >> Le mercredi 31 ao&ucirc;t 2005 20:35:16 UTC+1, Mike McLernon a &eacute;crit&nbsp;: >>> Hi, >>> >>> I'm building an erasures decoder for Reed Solomon codes, and I'm >>> having trouble when the number of erasures (without errors) exceeds >>> (n-k)/2, the error-correcting capability of the code. When my code >>> has no errors, and only erasures, I would expect the error locator >>> polynomial to be uniquely 1. >>> When I have up to (n-k)/2 erasures, that's exactly what happens. >>> However, when the number of erasures exceeds (n-k)/2, my error locator >>> polynomial exhibits unusual behavior. I run into the following >>> circumstances in these cases: >>> >>> 1) the polynomial has no roots in the field of the code, or 2) >>> the polynomial has repeated roots, or 3) the polynomial's roots are >>> a subset of the erasure locations, or 4) the polynomial's roots are >>> different from the erasure locations. >>> >>> Scenarios 1-3 seem reasonable, in that I can discard the information >>> in the error locator polynomial. I already have that information from >>> the erasure locator polynomial. However, scenario 4 is troublesome, >>> and I'm not quite sure how to handle that one. >>> >>> Any help would be appreciated. >>> >>> Mike McLernon >> can any one provide me the source code of reed solomon in matlab with >> BM or euclidien or PGZ method please? thx in advance > > Not for free, generally, and not if you're a student, ever. We and you > both benefit from you doing your own homework. If you can't do your own > homework -- switch majors.
Boy, that was harsh. And I forgot the rider: we're pretty much universally opposed to _doing_ your homework for you, but there's quite a bit of us (myself included) who are delighted to _help_ you to understand your homework so that you might do it yourself. We _won't_ help to raise up a generation of ignorant engineers who spend a minimal amount of time screwing things up before becoming managers and _really_ screwing things up. But we're happy to help raise up the next generation of _competent_ engineers. -- Tim Wescott Wescott Design Services http://www.wescottdesign.com I'm looking for work -- see my website!