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

# Erasures decoding of Reed Solomon codes

Started by ●August 31, 2005

Reply by ●September 1, 20052005-09-01

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

Reply by ●September 1, 20052005-09-01

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 >

Reply by ●September 3, 20052005-09-03

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...)

Reply by ●November 29, 20052005-11-29

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 numberof>> erasures exceeds (n-k)/2. If so, then we can conclude that I'mdefinitely>> 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...) > >

Reply by ●November 29, 20052005-11-29

> >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.

Reply by ●May 21, 20162016-05-21

Le mercredi 31 août 2005 20:35:16 UTC+1, Mike McLernon a écrit :> 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 McLernoncan any one provide me the source code of reed solomon in matlab with BM or euclidien or PGZ method please? thx in advance

Reply by ●May 23, 20162016-05-23

On Sat, 21 May 2016 14:55:38 -0700, kortas.manel wrote:> Le mercredi 31 août 2005 20:35:16 UTC+1, Mike McLernon a écrit : >> 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 advanceNot 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!

Reply by ●May 23, 20162016-05-23

Tim Wescott <seemywebsite@myfooter.really> wrote:>On Sat, 21 May 2016 14:55:38 -0700, kortas.manel wrote: > >> Le mercredi 31 août 2005 20:35:16 UTC+1, Mike McLernon a écrit : >>> 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

Reply by ●May 24, 20162016-05-24

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ût 2005 20:35:16 UTC+1, Mike McLernon a écrit : >>> 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!