The first trick for dealing with burst errors is to change the setting from Z2 to a larger field. We built the BCH codes using polynomials in Z2[x]/(xn + 1). The Reed-Solomon codes are just BCH codes using polynomials in GF(2m)[x]/(xn + 1). Suppose for example that we let m = 3 and n = 7, so we are working messages of 7 characters from GF(8). The elements of the field of order 8 are, as you should have answered on the last exam, 0, 1, x, x+1, x2, x2+1, x2+x, and x2+x+1. We can represent each of these polynomials as a set of three bits for the coefficients, 000, 001, 010, 011, 100, 101, 110, and 111. A typical 7 character message might be 001010111001101011001, or splitting this up into the separate characters, 001,010,111,001,101,011,001. Now suppose we have chosen our BCH code to correct any two errors in the message. A burst error must change at least 5 bits (and probably more) to change more than 2 characters in the message. For example, if we change the first 5 bits of the message we get 110,100,111,001,101,011,001. This message differs from the first message in only the first two characters, 110 instead of 001, and 100 instead of 010. Since only two characters of the message were changed and the BCH code corrects any two errors, the message will be correctly decoded despite a 5 bit burst error.
The second trick for handling burst errors is called "interleaving." Suppose we have the following blocks of encoded data
011010110100101 110101010100101 000101010001010 100101001111010 010111010101001Rather than transmit them in order, left to right, we instead read them top to bottom
01010 11000 10000 01111 etc.We then use another error-correcting code to transmit each of the new 5 bit blocks (or whatever length block suits your fancy). Suppose an error causes a block to be received incorrectly. Instead of losing 5 consecutive data bits, you lose one bit from each of the 5 original blocks. The error correction for the original blocks will then fix those single errors, and so no actual data is lost.
CDs use both these techniques. The data is originally compressed using a Reed-Solomon code. The blocks of data from the first Reed-Solomon code are then interleaved to form new blocks. These new blocks are then encoded using a second Reed-Solomon code. By compounding different error-correcting codes, CDs are able to correct the loss of data along several millimeters of surface. The data on a CD is recorded in circles, while most scratches will be radial and thus perpendicular to the direction the data is recorded. Since most scratches are less than a single millimeter wide (though they may be quite long), this means that CDs are very unlikely to lose data due to scratches.
There isn’t really a lot of new math in this handout. But since we’ve spent some time building error-correcting codes, I wanted you to see an example of how they are used in practice, and especially an example your students will be familiar with. There are a few more details to the coding used on a CD that I haven’t discussed. The interleaved blocks are offset to provide a smoother flow of data. Limitations on the laser sensitivity force some extra tricks to be used when converting 0s and 1s to pits and lands on the surface of the CD. Track control information is embedded between blocks of data. But the key features, and especially the important role of polynomial division and understanding the link between linear factors and roots of a polynomial, are exactly as I’ve sketched in the last couple of handouts. As always, you are welcome to stop by my office to discuss the extra details I’ve left out or any other part of the course.