Hi: I am a newbie on Reed-Solomon coding, and I was wondering what happens when the received message has more errors than the error correcting capacity 2t. I would say that the decoding fails completely, but I am not sure. Could anybody explain this to me?, is there anyway to prevent my decoding from crashing when the received message contains more than 2t errors? Thanks
Reed-Solomon error correction capacity
Started by ●November 6, 2008
Reply by ●November 6, 20082008-11-06
On Nov 6, 7:22 am, "marval" <agent59865...@spamcorptastic.com> wrote:> Hi: > > I am a newbie on Reed-Solomon coding, and I was wondering what happens > when the received message has more errors than the error correcting > capacity 2t. I would say that the decoding fails completely, but I am not > sure. > Could anybody explain this to me?, is there anyway to prevent my decoding > from crashing when the received message contains more than 2t errors? > > ThanksFirst, remember that the error correcting capacity is only 2t for erasures (i.e., when the error location is known). It's only t for those errors for which the location and magnitude are unknown. To determine if there are more errors than the RS decoder can correct, compare the degree of the LRS polynomial typically calculated by the BM algorithm with the number of roots (typically determined by the Chien search algorithm) of this polynomial. If number of roots is unequal to the degree of the polynomial, then there are too many errors for the RS to correct. Darol Klawetter
Reply by ●November 6, 20082008-11-06
marval wrote:> Hi: > > I am a newbie on Reed-Solomon coding, and I was wondering what happens > when the received message has more errors than the error correcting > capacity 2t.For the hard decision, the corrupt codeword can either fall on the no man land, so you know that it can't be corrected; or it will be aliased to the adjacent codeword and mistakenly decoded. For the soft decision, the corrupt codeword will be decoded to the most likely codeword which is going to be wrong. I would say that the decoding fails completely, but I am not> sure. > Could anybody explain this to me?, is there anyway to prevent my decoding > from crashing when the received message contains more than 2t errors?The standard practice is adding some integrity check for data, like CRC, for example. So you know that the decoding process failed. Vladimir Vassilevsky DSP and Mixed Signal Design Consultant http://www.abvolt.com
Reply by ●November 6, 20082008-11-06
Vladimir Vassilevsky <antispam_bogus@hotmail.com> wrote:>marval wrote:>> I am a newbie on Reed-Solomon coding, and I was wondering what happens >> when the received message has more errors than the error correcting >> capacity 2t.>For the hard decision, the corrupt codeword can either fall on the no >man land, so you know that it can't be corrected; or it will be aliased >to the adjacent codeword and mistakenly decoded. For the soft decision, >the corrupt codeword will be decoded to the most likely codeword which >is going to be wrong.I think it's worth pointing out that optimal soft-decision RS decoding is still relatively rare. The most interesting work has been done by Sudan, Vardy, and Koetter. I do not know of a commercial implementation. Less ambitiously, there are approaches involving multiple decoding iterations that provide some soft-decision behavior. For example, if a conventional decode fails, erase the two least reliable symbols and try again. In my experience the performance gains of such methods is usually small, on the order of 0.2 dB or so for the AWGN case. Such algorithms are not too uncommon in rotating memory. Steve
Reply by ●November 6, 20082008-11-06
Steve Pope wrote:> I think it's worth pointing out that optimal soft-decision RS decoding > is still relatively rare. The most interesting work has been > done by Sudan, Vardy, and Koetter. I do not know of a commercial > implementation.IIRC they employed the convolutional code and the soft decision RS as the outer code in the Voyager project as an improvement to the initial hard decision receiver.> Less ambitiously, there are approaches involving multiple > decoding iterations that provide some soft-decision behavior. > For example, if a conventional decode fails, erase the two > least reliable symbols and try again. In my experience the > performance gains of such methods is usually small, on the > order of 0.2 dB or so for the AWGN case. Such algorithms are not > too uncommon in rotating memory.Forney suggested many soft or softer methods similar to what you described; trellis algorithms can be used as well. Vladimir Vassilevsky DSP and Mixed Signal Design Consultant http://www.abvolt.com
Reply by ●November 6, 20082008-11-06
Vladimir Vassilevsky <antispam_bogus@hotmail.com> wrote:>Steve Pope wrote:>> I think it's worth pointing out that optimal soft-decision RS decoding >> is still relatively rare. The most interesting work has been >> done by Sudan, Vardy, and Koetter. I do not know of a commercial >> implementation.>IIRC they employed the convolutional code and the soft decision RS as >the outer code in the Voyager project as an improvement to the initial >hard decision receiver.>> Less ambitiously, there are approaches involving multiple >> decoding iterations that provide some soft-decision behavior.Yes, in some deep-space communications an iterative decoding algorithm was developed to improve the performance of the concatenated code, by about 1.2 dB. This did not involve a full, soft-decision decode of the RS layer though. It more resembles turbo decoding. I can come up with a reference to the deep-space work if anyone's interested. Steve
Reply by ●November 7, 20082008-11-07
>>>>> "Vladimir" == Vladimir Vassilevsky <antispam_bogus@hotmail.com> writes:Vladimir> marval wrote: >> Hi: >> I am a newbie on Reed-Solomon coding, and I was wondering what >> happens >> when the received message has more errors than the error correcting >> capacity 2t. Vladimir> For the hard decision, the corrupt codeword can either fall on the no Vladimir> man land, so you know that it can't be corrected; or it will be Vladimir> aliased to the adjacent codeword and mistakenly decoded. For the soft Vladimir> decision, the corrupt codeword will be decoded to the most likely Vladimir> codeword which is going to be wrong. Vladimir> I would say that the decoding fails completely, but I am not >> sure. Could anybody explain this to me?, is there anyway to prevent >> my decoding >> from crashing when the received message contains more than 2t errors? Vladimir> The standard practice is adding some integrity check for data, like Vladimir> CRC, for example. So you know that the decoding process failed. But doesn't the RS code already have pretty good detection capabilities? Would adding a CRC really improve things more than, say, adding another RS parity word or two? Ray
Reply by ●November 7, 20082008-11-07
Raymond Toy wrote:>>>>>> "Vladimir" == Vladimir Vassilevsky <antispam_bogus@hotmail.com> writes: > > Vladimir> marval wrote: > > >> Hi: > >> I am a newbie on Reed-Solomon coding, and I was wondering what > >> happens > >> when the received message has more errors than the error correcting > >> capacity 2t. > > Vladimir> For the hard decision, the corrupt codeword can either fall on the no > Vladimir> man land, so you know that it can't be corrected; or it will be > Vladimir> aliased to the adjacent codeword and mistakenly decoded. For the soft > Vladimir> decision, the corrupt codeword will be decoded to the most likely > Vladimir> codeword which is going to be wrong. > > Vladimir> I would say that the decoding fails completely, but I am not > >> sure. Could anybody explain this to me?, is there anyway to prevent > >> my decoding > >> from crashing when the received message contains more than 2t errors? > > Vladimir> The standard practice is adding some integrity check for data, like > Vladimir> CRC, for example. So you know that the decoding process failed. > > But doesn't the RS code already have pretty good detection > capabilities? Would adding a CRC really improve things more than, > say, adding another RS parity word or two?When the decoding produces no error indication but is nevertheless wrong. Jerry -- Engineering is the art of making what you want from things you can get. �����������������������������������������������������������������������
Reply by ●November 7, 20082008-11-07
On Fri, 07 Nov 2008 14:15:51 -0500, Jerry Avins <jya@ieee.org> wrote:>Raymond Toy wrote: >>>>>>> "Vladimir" == Vladimir Vassilevsky <antispam_bogus@hotmail.com> writes: >> >> Vladimir> marval wrote: >> >> >> Hi: >> >> I am a newbie on Reed-Solomon coding, and I was wondering what >> >> happens >> >> when the received message has more errors than the error correcting >> >> capacity 2t. >> >> Vladimir> For the hard decision, the corrupt codeword can either fall on the no >> Vladimir> man land, so you know that it can't be corrected; or it will be >> Vladimir> aliased to the adjacent codeword and mistakenly decoded. For the soft >> Vladimir> decision, the corrupt codeword will be decoded to the most likely >> Vladimir> codeword which is going to be wrong. >> >> Vladimir> I would say that the decoding fails completely, but I am not >> >> sure. Could anybody explain this to me?, is there anyway to prevent >> >> my decoding >> >> from crashing when the received message contains more than 2t errors? >> >> Vladimir> The standard practice is adding some integrity check for data, like >> Vladimir> CRC, for example. So you know that the decoding process failed. >> >> But doesn't the RS code already have pretty good detection >> capabilities? Would adding a CRC really improve things more than, >> say, adding another RS parity word or two? > >When the decoding produces no error indication but is nevertheless wrong. > >JerryExactly. When there are too many errors the RS can (and often will) pick a valid codeword that is not the codeword that was transmitted. With a valid, but incorrect, codeword selected it will not indicate any error syndrome and the only way to know for certain whether the data is correct is with some other detection method, like a CRC. If the system only ever operates in a region where codeword aliasing never happens, then this isn't needed. The error curves for RS systems are quite steep, though, so often the difference between being error-free and having aliased codewords is only a dB or two. Eric Jacobsen Minister of Algorithms Abineau Communications http://www.ericjacobsen.org Blog: http://www.dsprelated.com/blogs-1/hf/Eric_Jacobsen.php
Reply by ●November 7, 20082008-11-07
>>>>> "Eric" == Eric Jacobsen <eric.jacobsen@ieee.org> writes:Eric> On Fri, 07 Nov 2008 14:15:51 -0500, Jerry Avins <jya@ieee.org> wrote: >> Raymond Toy wrote: >>> But doesn't the RS code already have pretty good detection >>> capabilities? Would adding a CRC really improve things more than, >>> say, adding another RS parity word or two? >> >> When the decoding produces no error indication but is nevertheless wrong. >> >> Jerry Eric> Exactly. When there are too many errors the RS can (and often will) Eric> pick a valid codeword that is not the codeword that was transmitted. Eric> With a valid, but incorrect, codeword selected it will not indicate Eric> any error syndrome and the only way to know for certain whether the Eric> data is correct is with some other detection method, like a CRC. Yes, I understand the RS code could produce no error indication, and the CRC could detect that. (I guess that's particularly good since CRCs are good at detecting burst errors and the RS failure will produce burst errors.) But the CRC takes extra bits, so if I added an extra parity word or two to the RS code, would I get better or worse performance than with the CRC? Ray
