How to analysis the relationship between the accuracy of erasure and the probability of decoding in RS code

Question

As we all know, in RS code, when provide erasure (the position of error symbol), the decoding capacity of RS code is stronger. Specifically, $2e+v \leq (n-k)$, where $e$ is the number of errors, $v$ the number of erasures and $(n-k)$ the number of RS code characters (called nsym in the code) [1].

It has been seen in many materials, but there is no analysis about the relationship between the accuracy of erasure and the probability of decoding in RS code. Which means that the provided erasure may be wrong.

Currently, I have split the possibility into three kinds of condition (it may be merged later):

• (1) $E > n-k$;
• (2) $\frac{n-k}2 < E \leq n-k$;
• (3) $E \leq \frac{n-k}2$.

$E$ is the total number of actual errors.

For the condition (1), the probability of successfully decoding is 0.

For the condition (2), because $2e+v = (n-k) = T$, so $e = \frac{T-v}2$, the actual number of error $E$ can be represented as $e+v= \frac{T-v}2 + v = \frac{T+v}2$. Which means that, when provide one erasure, the capacity of block decoding is increased by 1/2, and it is limited by the $2e+v \leq (n-k)$. So, when the correct erasure provided, the number of detected error $e$ is decreased. Because the number of actual errors $E$ is larger than the $\frac{(n-k)}2$, so the probability of successfully decoding block is totally relied on the accuracy of erasure. So, the the probability is easy to get.

For the condition (3), and this is where I am blocked now. In this condition, actually, without the provided erasure the RS can decoded successfully 100%. But, as for the erasure provider, it can not know the actual number of errors $E$, thus it always provides the erasure. But I can not analysis the accuracy of provided erasure to the probability of successfully decoding block in this condition.

I have tried some examples that for the RS(n=20,k=12). The $E=4 \leq \frac{(n-k)}2$,

• when I provide 4 erasure (2 correct, 2 wrong) or seven erasure (3 correct , 4 wrong) or eight erasure (4 correct, 4 wrong), RS can still successfully decode the block. But when the any above wrong erasure increases, the RS can not successfully decode the block. And I want to formally analysis this condition like condition (2).

Could you help me to formally analysis this problem? Thanks very much!

Answer 1

Based on the comments below the original post, I am going to take a stab at rephrasing and answering the original question.

We wish to transmit symbols $$X_1,...,X_k,$$ where $X_i$ lies in some finite field $\mathbb{F}$. We use a Reed-Solomon code to encode them as $$Y_1,...,Y_n,$$ with $n\geq k$. We receive observations $$Z_1,...,Z_n,$$ which are some sort of noisy measurement of the $Y_i$.

Per the comments, we can extract some probabilistic ("soft") information from the $Z_i$. Define the distributions $$d_i(a)=\Pr(Y_i=a|Z_i)$$ for each $i=1,...n$ and each $a\in\mathbb{F}$. (This definition implicitly assumes that the channel noise is independent between symbols; if not, we'd use something more general, like $d_i(a)=\Pr(Y_i=a|Z_1,...,Z_n)$.)

Let $W_i=\arg\max_a d_i(a)$, i.e., $W_i$ is the most likely estimate for $X_i$ a priori (i.e., using $Z_i$ but ignoring the structure of the error correcting code). Let $E$ be the number of errors amongst the $W_i$ (i.e., $E=\sum_{i:X_i\neq W_i}1$)

It seems that the original poster used something like the following algorithm to try to recover (a maximum likelihood estimate of) the X_i:

1. Try to decode $(W_1,...,W_n)$. If $2E\leq n-k$, the decoding will succeed. If not...
2. On failure, find the $W_i$ we are least confident in (i.e., $\arg \min_i d_i(W_i)$), and replace that symbol with an erasure. Try to decode. Suppose $W_i$ was actually incorrect. Then the decoding will succeed if $2E-1 \leq n-k$. If not...
3. On failure, find the next least confident $W_i$ and replace it with an erasure. If both of the erased symbols were incorrect, the decoding will succeed if $2E-2\leq n-k$. If exactly one of the erased symbols was incorrect, the decoding will succeed if $2E-1\leq n-k$. If not...
4. And so forth.

The probabilities $d_i$ let us guess which symbols to erase in an intelligent order, so this process is much better than an exhaustive search. This process is also fairly simple to implement using off-the-shelf software.

HOWEVER, our underlying problem is to decode a Reed-Solomon codeword that is presented with probabilistic information. In that situation, it is much better to incorporate the probabilistic information directly. The classic result along these lines is by Koetter, 2003. Algebraic soft-decision decoding of Reed-Solomon codes.

Since that paper's publication, and in the wake of the LDPC/belief propagation revolution in error correction, there have been a number of iterative approaches; try Googling "soft decoding reed solomon code" to find a few hundred of them. I'm sure you can find some software implementing it, too.

If you use all the partial probabilistic information, it is no longer meaningful to count the number of errors. No symbol is "correct" or "incorrect"; it just has a probability distribution over all possible symbols. So trying to understand errors in terms of $E$ may not be the appropriate metric to consider.