Reed-Solomon detecting capacity in practise

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

"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

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

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