Forums

Q on Reed-Solomon Uncorrectable Errors

Started by Ken Ryan March 30, 2009
Hello!

I have a Reed-Solomon design which is a shortened (15,11) code (to 
(12,8).  I am nowhere near done running test patterns through it yet, 
but it does seem to be correcting the 1 and 2 error cases properly. 
However I was expecting it to be able to reliably detect the three-error 
cases and indicate uncorrectability.  Instead I have some three-error 
vectors which are not detected as uncorrectable (it corrects to the 
wrong code, of course).  I am checking the order of the locator 
polynomial (<= 2) as well as checking the number of roots (= order of
polynomial).  I also rerun the syndromes after correcting the word.  So 
far all of the uncorrectable cases are caught in the rerunning of syndromes.

Is it generally true that with four check symbols one can detect three 
errors (but not correct them)?  Am I misunderstanding something or do I 
have a bug still?  If it is true that not all three-error cases can be 
detected, can someone point me to how I can determine the probability of 
miscorrecting (for the 3-error case)?

Thanks in advance!

	Ken
On Mar 30, 6:02&#2013266080;am, Ken Ryan <newsr...@leesburg-geeks.org> asked:
> Hello! > > I have a Reed-Solomon design which is a shortened (15,11) code (to > (12,8). &#2013266080;I am nowhere near done running test patterns through it yet, > but it does seem to be correcting the 1 and 2 error cases properly. > However I was expecting it to be able to reliably detect the three-error > cases and indicate uncorrectability. &#2013266080;Instead I have some three-error > vectors which are not detected as uncorrectable (it corrects to the > wrong code, of course). &#2013266080;I am checking the order of the locator > polynomial (<= 2) as well as checking the number of roots (= order of > polynomial). &#2013266080;I also rerun the syndromes after correcting the word. &#2013266080;So > far all of the uncorrectable cases are caught in the rerunning of syndromes. >
> Is it generally true that with four check symbols > one can detect three errors (but not correct them)? &#2013266080;
True in general, but since you are also correcting two errors, you cannot detect *all* cases of three errors; some of these, as you have discovered, will be "corrected" to the wrong codeword which happens to differ in two places from the received word.
> Am I misunderstanding something
Yes, you are misunderstanding the claim that with four check symbols one can detect three errors but not correct them. (In fact one can even detect four errors but not correct them.) When one tries to do *both* error correction *and* error detection on the same received word, there is a trade-off: the more that you want to do of one, the less you can do of the other. For example, if you change your decoder so that it corrects one error but does not try and correct two errors (even when it does find a valid error-locator polynomial etc.), you will see that all triple errors are correctly detected.
> or do I have a bug still?
That is also entirely possible. --Dilip Sarwate

Ken Ryan wrote:

> Hello! > > I have a Reed-Solomon design which is a shortened (15,11) code (to > (12,8). I am nowhere near done running test patterns through it yet, > but it does seem to be correcting the 1 and 2 error cases properly. > However I was expecting it to be able to reliably detect the three-error > cases and indicate uncorrectability. Instead I have some three-error > vectors which are not detected as uncorrectable (it corrects to the > wrong code, of course).
This is what expected. BTW, for the same block size and rate, there probablly could be the better code then shortened RS.
> I am checking the order of the locator > polynomial (<= 2) as well as checking the number of roots (= order of > polynomial). I also rerun the syndromes after correcting the word. So > far all of the uncorrectable cases are caught in the rerunning of > syndromes.
> Is it generally true that with four check symbols one can detect three > errors (but not correct them)?
Either detect OR correct. Not both.
> Am I misunderstanding something or do I > have a bug still?
This is very possible.
> If it is true that not all three-error cases can be > detected, can someone point me to how I can determine the probability of > miscorrecting (for the 3-error case)?
Vladimir Vassilevsky DSP and Mixed Signal Design Consultant http://www.abvolt.com
Vladimir Vassilevsky  <antispam_bogus@hotmail.com> wrote:

>Ken Ryan wrote:
>> I have a Reed-Solomon design which is a shortened (15,11) code (to >> (12,8).
>This is what expected. BTW, for the same block size and rate, there >probably could be the better code then shortened RS.
Yes, according to Sloane, there is a nonlinear binary code with distance 7 and the same parameters (it would be a shortened (63,47) code). Such a code would correct any three random bit errors. The RS would work better only if errors were non-random. Steve
dvsarwate@yahoo.com wrote:
 > Yes, you are misunderstanding the  claim that with
 > four check symbols one can detect three errors but
 > not correct them.  (In fact one can even detect four
 > errors but not correct them.)  When one tries to do
 > *both* error correction *and* error detection on the
 > same received word, there is a trade-off: the more that
 > you want to do of one, the less you can do of the other.
 > For example, if you change your decoder so that it
 > corrects one error but does not try and correct two
 > errors (even when it does find a valid error-locator
 > polynomial etc.), you will see that all triple errors are
 > correctly detected.

Vladimir Vassilevsky wrote:
 > This is what expected. BTW, for the same block size and rate, there
 > probablly could be the better code then shortened RS.



Thank you, Dilip and Vladimir!  I can at least stop spinning my wheels.

Is there some way to characterize X% chance of detecting 3-symbol 
errors, Y% chance of detecting 4-symbol errors, etc.?  Or is running 
test cases and collecting statistics the only feasible way?  (I know
I'm going to be asked this question).


	Ken
Steve Pope wrote:
> Yes, according to Sloane, there is a nonlinear binary code > with distance 7 and the same parameters (it would be a shortened > (63,47) code). Such a code would correct any three random bit errors. > The RS would work better only if errors were non-random.
Thanks. I'll get some scattered single-bit errors, but I need to be able to handle four-bit clumps of errors as well. It sounds like RS is still what I want. Ken
Ken Ryan  <newsryan@leesburg-geeks.org> wrote:

>Is there some way to characterize X% chance of detecting 3-symbol >errors, Y% chance of detecting 4-symbol errors, etc.?
Certainly, these percentages (once you define exactly what you're talking about) can be stated exactly based on pure combinatorics. Steve
Steve Pope wrote:
> Ken Ryan <newsryan@leesburg-geeks.org> wrote: > >> Is there some way to characterize X% chance of detecting 3-symbol >> errors, Y% chance of detecting 4-symbol errors, etc.? > > Certainly, these percentages (once you define exactly what > you're talking about) can be stated exactly based on pure > combinatorics.
Do you happen to know of someplace you can point me where I can learn how to do this? Thanks! Ken
Ken Ryan  <newsryan@leesburg-geeks.org> wrote:

>Steve Pope wrote:
>> Ken Ryan <newsryan@leesburg-geeks.org> wrote:
>>> Is there some way to characterize X% chance of detecting 3-symbol >>> errors, Y% chance of detecting 4-symbol errors, etc.? >> >> Certainly, these percentages (once you define exactly what >> you're talking about) can be stated exactly based on pure >> combinatorics.
>Do you happen to know of someplace you can point me where I can learn >how to do this?
Usually you can assume that any uncorrectable error pattern gives you a random syndrome (out of the 2^16 syndrome patterns for your code). You can calculate how many of these syndromes correspond to 0, 1, or 2 errors. (Making sure you only consider valid error locations for the shortened code.) Those would be the misdecodes, while the rest of them would be the detectable uncorrectables. There is a respect in which this assumption is not quite exact, but the difference is probably not too significant. Steve
Steve Pope wrote:
> Ken Ryan <newsryan@leesburg-geeks.org> wrote: > >> Steve Pope wrote: > >>> Ken Ryan <newsryan@leesburg-geeks.org> wrote: > >>>> Is there some way to characterize X% chance of detecting 3-symbol >>>> errors, Y% chance of detecting 4-symbol errors, etc.? >>> Certainly, these percentages (once you define exactly what >>> you're talking about) can be stated exactly based on pure >>> combinatorics. > >> Do you happen to know of someplace you can point me where I can learn >> how to do this? > > Usually you can assume that any uncorrectable error pattern > gives you a random syndrome (out of the 2^16 syndrome > patterns for your code). You can calculate how many of > these syndromes correspond to 0, 1, or 2 errors. (Making > sure you only consider valid error locations for the > shortened code.) Those would be the misdecodes, while the rest > of them would be the detectable uncorrectables. > > There is a respect in which this assumption is not > quite exact, but the difference is probably not too > significant. > > Steve
OK, thanks for the explanation. I need to think on it a bit - this is a learning curve for me! Ken