Good codes in practice for correcting combination of errors and erasures

Question

In practice, both errors and erasures might be introduced in the channel. Could you point me to some good codes for correcting such combinations. Also what are their correction capabilities?

Answer 1

The answer depends on several things.

If your channel (or receiver) produces erasures and errors, then the relevant metric is the Hamming metric, as a code with minimum distance $d$ can correct a combination of $t$ errors and $e$ erasures, iff $d>2t+e$. Therefore a code with good Hamming distance may be the way to go (if an efficient decoding algorithm is known for it). I say "may", because other considerations may be more pressing. For example, you may want to use longer blocks (often a good idea, because the errors are then averaged out better).

If the errors/erasures affect individual bits more or less independently, then you need a binary code. If OTOH the errors/erasure come in lumps (or "bursts"), then it is better to view them as byte-errors (or symbol errors, pick a symbol size that gives the best results), and RS-codes are your friend, because RS-decoders don't care how many bits in a symbol are incorrect. This may also be the case, when the input to your decoder is the output of another code (think: the microcode in CD-ROM that tries to interpret a single byte from the disk). If RS-codes have too short block lengths for your purposes, you can try an algebraic-geometry code instead, but sadly I have never seen an application, where the savings would have been significant.

A generic erasure decoding algorithm for a binary linear code that has an error-correcting-algorithm is to do two error-correction attempts: one with all erasures replaced with ones, and another with all erasures replaced with zeros. At least one of those decoding attempts will succeed, if the inequality $2t+e\lt d$ holds. If both succeed, then you need to compare the two outputs to find the better match. This does not work with byte-errors, but the RS-codes (as well as the AG-codes) have errors-and-erasures decoding algorithms.

If your channel (and receiver) actually produce soft errors (= full continuum of likelihoods for a given bit to be 0 or 1), then you should try either a convolutional code, a turbo code, or an LDPC-code depending on the block length. If your blocks are long (over 10000 bits or thereabouts) I would try using an LDPC-code anyway, but I don't have any experience using an LDPC-code with errors-and-erasures only. Surely somebody has tried it, and can give rules of thumb on "how to treat the output of a hard decision receiver in a belief propagation algorithm".

Answer 2

Your question is vague and open-ended. Here is a good book that you might start with (full text online):

• http://www.inference.phy.cam.ac.uk/mackay/itila/

Answer 3

Since you asked a reference, the early access pre-edit version of a paper that addresses exactly this problem you're considering just appeared in the IEEE Transactions on Information Theory:

K. A. S. Abdel-Ghaffar, J. H. Weber, Parity-check matrices separating erasures from errors, IEEE Trans. Inf. Theory, in press.

The word "practical" can imply way too many things and doesn't only apply to considering both errors and erasures. But if we restrict ourselves to the special meaning you used, the introduction of the above paper explains the problem very well.

Here are the two general approaches to handling a combination of errors and erasures that are applicable to any code:

1. you temporarily treat the erasures as errors by assigning a random alphabet, decode normally with different assignments, and compare the results (i.e., what Jyrki explained) or
2. you ignore the positions suffering erasures for the moment, correct errors in the received message by using the corresponding punctured code of the original code, and correct erasures normally at the last step.

The paper considers linear codes and explains how to turn your parity-check matrix into a new one suitable for the second approach without changing the basic code parameters such as the minimum distance.

Reading the first section of the paper will give you a good answer to your specific question in terms of the approach Jyrki explained (and provides a reference to the specific decoding algorithm for Reed-Solomon codes Jyrki mentioned). And learning about the other approach will complement your knowledge on this problem.

In any case, basically you can use a good linear code to handle a channel that may produce both errors and erasures in some way or another with pretty much the same idea as the standard error correction method because you can take advantage of the minimum distance regardless of whether you're dealing with errors or erasures.

A little more formally, let $d$ and $e$ be the minimum distance of a code of your choice and the number of erasures in a received message respectively. Assume that $e' < d$. Then there exists a pair of nonnegative integers $e'$, $r$ satisfying $e+2e'+r < d$ such that if the number of errors does not exceed $e'$, then all errors and erasures can be corrected. The situation is similar for error detection. (The paper refers to R. M. Roth, Introduction to Coding Theory. Cambridge, UK: Cambridge University Press, 2006 for this fact if you would like a textbook.)

So, the question is not really which code you should use. It's about which decoding algorithm is good for this type of channel.

With that said, strictly speaking, it does matter which code you use because excellent decoding algorithms are often applicable only to limited classes of codes. But all else being equal, what makes a code suitable for your purpose is the existence of practical encoding/decoding algorithms that work for your code. The correction capability in an ideal situation are already determined by the minimum distance alone.