On Tue, 24 May 2016 12:14:12 -0500, Tim Wescott
<seemywebsite@myfooter.really> wrote:

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

That's about as well as I've seen that put for a while.

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!

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

-- 

Tim Wescott
Wescott Design Services
http://www.wescottdesign.com

I'm looking for work -- see my website!

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

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

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

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

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