why are reed-solomon codes good at correcting burst errors?

Question

I'm trying to understand from an intuitive perspective why Reed-Solomon codes are so common in data storage devices where burst errors are very frequent.

Answer 1

Reed-Solomon codes over extension fields are useful for correcting bursts of errors in the base field. As codes whose codeword symbols are viewed as elements of the extension field, Reed-Solomon codes have no specific burst-correcting properties: they are designed for correcting random errors in the codeword symbols. But if each extension field element is viewed as a vector over the base field, then we have transformed a $[N,K]$ Reed-Solomon code over $\mathbb F_{2^8}$, say, into a $[8N, 8K]$ binary code. The Reed-Solomon code can correct up to $\left\lfloor \frac{N-K}{2}\right\rfloor$ symbol errors in the $N$ symbols. The binary code can be guaranteed to correct only $\left\lfloor \frac{N-K}{2}\right\rfloor$ bit errors in the $8N$ bits (after all, the bit errors might occur in $\left\lfloor \frac{N-K}{2}\right\rfloor$ different symbols, but it can correct many more errors too. Indeed, the $[8N, 8K]$ binary code is guaranteed to correct a single burst of bit errors of length as much as $8\left(\left\lfloor \frac{N-K}{2}\right\rfloor -1\right) +1$ bits. Verify for yourself that a longer burst could conceivably hit more than $\left\lfloor \frac{N-K}{2}\right\rfloor$ symbols and cause the Reed-Solomon code to fail. Of course, a single burst of length $8\left\lfloor \frac{N-K}{2}\right\rfloor$ bits could also be corrected if it is "phased just right" so that it is confined to $\left\lfloor \frac{N-K}{2}\right\rfloor$ symbols.

This should make the reason for the use of Reed-Solomon codes in memory systems obvious. Storage is typically organized into 8-bit bytes and while read or write errors can affect single bits, more major failures usually affect whole bytes at a time. Reed-Solomon codes over $\mathbb F_{2^8}$ are thus perfectly suited to the task. They can correct occasional random bit errors, as well as the burst errors that occur when one part of a memory bank fails.

Answer 2

Reed-Solomon codes are good at correcting burst errors for a couple of reasons. The first reason is by construction of the code. Take a message, say ABCD, that is to be transmitted. Reed-Solomon codes then take each "information" digit (A, B, C, or D), or symbol, and constructs a new sequence of a certain length that corresponds to the "information" digit.

For example, A may be constructed simply as AAAAAA, with a sequence of length 6. Thus, no matter how many corrupted bits occur in a sequence, it is only registered as one error in the message. Therefore, if errors occur in large clumps, like burst-errors, the number of corrupted symbols is a lot lower than the total number of bit errors.

Reed-Solomon codes also have a unique Decoding Scheme, that uses three parts: Euclid's Algorithm (to find the error polynomial), Chien Search (to find the locations of the errors), and the Forney Algorithm (to find magnitudes of the errors), which all require elevated mathematics, as well as a lot of computing power, to understand and perform. This Decoding-Scheme is another reason why Reed-Solomon codes are especially good at correcting burst errors.