Hi, I have implemented a Reed-Solomon coder/decoder (14,10) with symbols over GF(2^4) and I am having some problems with it's error detecting capacity. As far as I know such code can correct up to t=(n-k)/2 errors, and according to a book "Essentials of Error-Control Coding" by J.C.Moreira, it's minimum Hamming distance dmin=t2+1 (t2=n-k). It is said there too that when there is less than dmin-1 symbol errors, it is guaranteed that the codeword cannot be converted into another codeword. So returning to my code - it can correct up to 2 symbol errors and as I understand it, should detect for sure at least 4 errors. Everything works fine with correcting errors, seems to work fine detecting a situation with 3-symbol error too. Some problems occur when there are 4 symbol errors though. For example if encoder input data is: 0xA 0x0 0xC 0x6 0x7 0x4 0x7 0x4 0x7 0x4 and I deliberetely damage parity symbols produced by the encoder so that the string sent to the decoder is 0xFFFFA0C6747474 (it contains 4 symbol errors), it do not realise uncorrectable errors, instead tries to correct codeword (telling me that 2 errors occured). I am using a Berlekamp-Massey algorithm for finding error-locating polynominal described here http://www.ee.ucla.edu/~matache/rsc/node8.html and a Chien search to evaluate roots of it. Situation I described happens only with specific data string, with specific error patterns (in most cases decoder detects 4 symbol error situation) when the degree of computed error-locator poly = number of it's roots (accidentally i suppose). Digging a bit more I found out that in other implementations (like the one by Robert Morelos-Zaragoza - http://the-art-of-ecc.com/4_RS/), problem I described occurs too. Does anyone faced similar problem? Is it implementational problem? I will appreciate any help. Regards, Marek Rybczynski

# Reed-Solomon detecting capacity in practise

Started by ●October 13, 2007

Reply by ●October 14, 20072007-10-14

"MarkR" <redavq@wp.pl> wrote in message news:ztKdnX_13ZdFl4zanZ2dnUVZ_v2unZ2d@giganews.com...> Hi, > > I have implemented a Reed-Solomon coder/decoder (14,10) with symbols over > GF(2^4) and I am having some problems with it's error detecting capacity.Looks weird. Is (14,10) a shortened (15,11) ?> As far as I know such code can correct up to t=(n-k)/2 errors, and > according to a book "Essentials of Error-Control Coding" by J.C.Moreira, > it's minimum Hamming distance dmin=t2+1 (t2=n-k). It is said there too > that when there is less than dmin-1 symbol errors, it is guaranteed that > the codeword cannot be converted into another codeword. > So returning to my code - it can correct up to 2 symbol errors and as I > understand it, should detect for sure at least 4 errors.EITHER correct up to 2 errors OR detect 4 errors. You can't have it all at once.> Everything works fine with correcting errors, seems to work fine detecting > a situation with 3-symbol error too.It depends. There could be some undetected tripple error patterns as well.> Some problems occur when there are 4 > symbol errors though.Of course. This is what is expected.> I am using a Berlekamp-Massey algorithm for finding error-locating > polynominal described here http://www.ee.ucla.edu/~matache/rsc/node8.html > and a Chien search to evaluate roots of it.It doesn't matter. The error correction capacity is a property of a code.> Does anyone faced similar problem? Is it implementational problem? I will > appreciate any help.How much is the appreciation? Vladimir Vassilevsky DSP and Mixed Signal Consultant www.abvolt.com

Reply by ●October 25, 20072007-10-25

Hi Marek, If you have access to a c++ compiler there is a library I've written that freely available, which will allow you to test your assumptions. the library is called Schifra, the url is www.schifra.com and the particular example you should look at is schifra_reed_solomon_example04.cpp Arash Partow __________________________________________________ Be one who knows what they don't know, Instead of being one who knows not what they don't know, Thinking they know everything about all things. http://www.partow.net

Reply by ●October 25, 20072007-10-25

Hi Marek> I have implemented a Reed-Solomon coder/decoder (14,10) with symbols over > GF(2^4) and I am having some problems with it's error detecting capacity.Did you shorten the code, normally n is given by 2^m - 1 (Lin and Costello, etc.)> As far as I know such code can correct up to t=(n-k)/2 errors, and > according to a book "Essentials of Error-Control Coding" by J.C.Moreira, > it's minimum Hamming distance dmin=t2+1 (t2=n-k). It is said there too > that when there is less than dmin-1 symbol errors, it is guaranteed that > the codeword cannot be converted into another codeword. > So returning to my code - it can correct up to 2 symbol errors and as I > understand it, should detect for sure at least 4 errors.According to the theory, this is correct.> Everything works fine with correcting errors, seems to work fine detecting > a situation with 3-symbol error too. Some problems occur when there are 4 > symbol errors though. > For example if encoder input data is: 0xA 0x0 0xC 0x6 0x7 0x4 0x7 0x4 0x7 > 0x4 and I deliberetely damage parity symbols produced by the encoder so > that the string sent to the decoder is 0xFFFFA0C6747474 (it contains 4 > symbol errors), it do not realise uncorrectable errors, instead tries to > correct codeword (telling me that 2 errors occured). > > I am using a Berlekamp-Massey algorithm for finding error-locating > polynominal described herehttp://www.ee.ucla.edu/~matache/rsc/node8.html > and a Chien search to evaluate roots of it. > Situation I described happens only with specific data string, with > specific error patterns (in most cases decoder detects 4 symbol error > situation) when the degree of computed error-locator poly = number of it's > roots (accidentally i suppose).I had a similar problem when implementing the above in MATLAB. I can provide the MATLAB source if it would be of any help... I would be quite interested into the source of the problem, please let us know what the problem was. Kind Regards, Jaco