What happens when the errors larger than t (RS FEC)?

[icsoul]

It seems that there are few papers introduce the case that the number of errors is larger than the RS code error correction capability.

For RS(n,k), n-k=2t,

What result wolud be at the decoder output when the number of errors(En) larger than t.

When the En >t, I'm interest in the following problems:
1. if the decoder could correct t errors and the other errors are left?
2. or the decoder don't correct any error at all?
3. if the decoder could give the number and location of the errors?

 

[ring0]

When using conventional algorithms based on syndrome equation (like Berlekamp-Massey algorithm), you indeed can't fix more errors than t.

When En>t the decoder doesn't fix any errors at all. Usually the decoder is able to identify such situation and report this codeword as undecodeable. However, there is probability (quite a little though) that the decoder won't identify such a situation and "fix" errors incorrectly (in fact, adding errors to the codeword).

When En>t the decoder can't give number or locations of errors. However, if you know their locations, you can use erasure decoding to correct up to 2t errors.

There are also algorithms (notably Guruswami-Sudan algorithm) which are able to correct more than t errors in some circumstances.

 

[icsoul]

"However, there is probability (quite a little though) that the decoder won't identify such a situation and "fix" errors incorrectly (in fact, adding errors to the codeword)."

You mean this case could not be avoided?

 

[ring0]

Theoretically, it cannot be avoided.

If the code has minimum distance d=2t then there are at least two codewords differing in 2t symbols. Imagine that we transmit one of these codewords, and noise adds t+1 errors by changing t+1 symbols from the codeword to the corresponding symbols from the other codeword, exactly in the places where these codewords are different.

In this case the received codeword will be more similar to the second codeword (with distance t-1) that to the transmitted one (with distance t+1).

For most RS codes probability of such a case is rather low, because there are indeed not many codewords differing only in 2t symbols. Nevertheless, for the simple RS code correcting 1 error (with two correcting symbols) this probability must be taken into account.