Forums

Reed solomon-error correction

Started by nezhate March 8, 2007
Hi all,
What does the reed solomon decoder outputs in the case when we have
more than "t" errors to correct?
Does he correct some errors and leave other errors as they came, or he
will correct any thing (i.e the data that was in the input will appear
in the output)?
Thanks in advance!

On 9 mar, 04:08, "nezhate" <mazouz.nezh...@gmail.com> wrote:
> Hi all, > What does the reed solomon decoder outputs in the case when we have > more than "t" errors to correct? > Does he correct some errors and leave other errors as they came, or he > will correct any thing (i.e the data that was in the input will appear > in the output)? > Thanks in advance!
If you have more than "t" errors, the decoder cannot correct anything... So you have to detect this failure to bypass the decoder... by comparing the number of zero in the locator and the degree of the locator polynomial from the berlekamp algorithm

nezhate wrote:

> Hi all, > What does the reed solomon decoder outputs in the case when we have > more than "t" errors to correct? > Does he correct some errors and leave other errors as they came, or he > will correct any thing (i.e the data that was in the input will appear > in the output)?
If there is more errors then it can be corrected by the code, the attempt to correct it only makes the things worse. The good decoder should detect this situation. Vladimir Vassilevsky DSP and Mixed Signal Design Consultant http://www.abvolt.com
On Mar 9, 7:56 am, Vladimir Vassilevsky <antispam_bo...@hotmail.com>
wrote:

> If there is more errors then it can be corrected by the code, the > attempt to correct it only makes the things worse. The good decoder > should detect this situation.
One other possibility is that the decoder output is the *wrong* codeword because the received word is at distance t or less from the wrong codeword and at distance more than t from the transmitted codeword. This is a *valid* decoding in that the decoder has found the codeword that is at distance t or less from the received word, and that is exactly what the decoder is designed to do! Of course, the output is incorrect because the codeword produced is not the one that was transmitted: too many errors have occurred in the channel. This event -- that the decoder output is a valid codeword but *not* the transmitted codeword -- is quite rare: its probability is generally much smaller than the probability that the decoder is unable to correct the errors (because more than t errors have occurred) and indicates this failure to the destination of the data, or requests a repeat transmission from the data source. --Dilip Sarwate
On 9 Mar 2007 06:40:14 -0800, "dvsarwate@gmail.com"
<dvsarwate@gmail.com> wrote:

>On Mar 9, 7:56 am, Vladimir Vassilevsky <antispam_bo...@hotmail.com> >wrote: > >> If there is more errors then it can be corrected by the code, the >> attempt to correct it only makes the things worse. The good decoder >> should detect this situation. > > >One other possibility is that the decoder output is the *wrong* >codeword because the received word is at distance t or less >from the wrong codeword and at distance more than t from >the transmitted codeword. This is a *valid* decoding in that >the decoder has found the codeword that is at distance t or >less from the received word, and that is exactly what the decoder >is designed to do! Of course, the output is incorrect because >the codeword produced is not the one that was transmitted: too >many errors have occurred in the channel. This event -- that >the decoder output is a valid codeword but *not* the transmitted >codeword -- is quite rare: its probability is generally much smaller >than the probability that the decoder is unable to correct the >errors (because more than t errors have occurred) and indicates >this failure to the destination of the data, or requests a repeat >transmission from the data source. > >--Dilip Sarwate
Dilip beat me to it. This definitely happens in real systems. We tried to use the decoder output error syndrome to measure codeword error rate on one system, but the SNR region between which there were no errors and where the codewords started aliasing was too narrow to be useful for our purposes at the time. If the input error rate is too high the decoder may have no way to know that it's not decoding incorrectly if it can find a valid codeword within acceptable distance to what was received. Eric Jacobsen Minister of Algorithms Abineau Communications http://www.ericjacobsen.org

Eric Jacobsen wrote:


>>>If there is more errors then it can be corrected by the code, the >>>attempt to correct it only makes the things worse.
[...]
>> This event -- that >> the decoder output is a valid codeword but *not* the transmitted >>codeword -- is quite rare: its probability is generally much smaller >>than the probability that the decoder is unable to correct the >>errors
[...]
> This definitely happens in real systems. We tried to use the decoder > output error syndrome to measure codeword error rate on one system, > but the SNR region between which there were no errors and where the > codewords started aliasing was too narrow to be useful for our > purposes at the time.
Agreed completely. For the good codes, there is not much of no man's land between the spheres of the radius t. Hence the code should not be used to the full error correction capacity, and/or there should be some other means to ensure the integrity of the data.
> If the input error rate is too high the decoder may have no way to > know that it's not decoding incorrectly if it can find a valid > codeword within acceptable distance to what was received.
For the normal operation, the input BER should be at least several times less then the maximum correcting capacity of the code. Vladimir Vassilevsky DSP and Mixed Signal Design Consultant http://www.abvolt.com
On Mar 9, 3:40 pm, "dvsarw...@gmail.com" <dvsarw...@gmail.com> wrote:
> On Mar 9, 7:56 am, Vladimir Vassilevsky <antispam_bo...@hotmail.com> > wrote: > > > If there is more errors then it can be corrected by the code, the > > attempt to correct it only makes the things worse. The good decoder > > should detect this situation. > > One other possibility is that the decoder output is the *wrong* > codeword because the received word is at distance t or less > from the wrong codeword and at distance more than t from > the transmitted codeword. This is a *valid* decoding in that > the decoder has found the codeword that is at distance t or > less from the received word, and that is exactly what the decoder > is designed to do! Of course, the output is incorrect because > the codeword produced is not the one that was transmitted: too > many errors have occurred in the channel. This event -- that > the decoder output is a valid codeword but *not* the transmitted > codeword -- is quite rare: its probability is generally much smaller > than the probability that the decoder is unable to correct the > errors (because more than t errors have occurred) and indicates > this failure to the destination of the data, or requests a repeat > transmission from the data source. > > --Dilip Sarwate
Hi again! I implemented on FPGA RS decoder using your paper (Berlekamp-massey algorithm). when there is t errors or less, all works and the decoder correct the received code. when I have more than t errors, the decoder (of courses!) can't correct the received code and it outputs the received code as it is. Should I consider that in this case my decoder is well working? Does this agrees with the theoretical part? Thanks.
>On 9 mar, 04:08, "nezhate" <mazouz.nezh...@gmail.com> wrote: >> Hi all, >> What does the reed solomon decoder outputs in the case when we have >> more than "t" errors to correct? >> Does he correct some errors and leave other errors as they came, or he >> will correct any thing (i.e the data that was in the input will appear >> in the output)? >> Thanks in advance! > >If you have more than "t" errors, the decoder cannot correct >anything... >So you have to detect this failure to bypass the decoder... by >comparing the number of zero in the locator and the degree of the >locator polynomial from the berlekamp algorithm > >
So, let me see if I have understood this: if the number of errors is greater than "t", the decoder doesn't work at all, am I right? My question is: is there any way of preventing this? or at least try to correct it? Thanks,