How CD's really work
The purpose of this page is to explain some of the inner workings of the data stored on CDs. There are many misconceptions about how CDs hold data, especially as regards to error correction. I intend to explain how data really is stored on a CD, and why that particular method is used. I am not going to concern myself with too much technobabble either, this document is not meant so much for scientists or mathematicians, just ordinary folk.
Bits and Bytes
You are probably aware that data is stored as a series of pits on the CD. A laser picks out the bit patterns, spiralling out from the centre, and after a bit of work, we will end up with a stream of data. This data can represent audio, by storing the amplitude of the waveform we hear, or graphics and programs by storing a series of bytes just like on a hard disk. There is no fundamental difference between the two forms of CD, but the way that data is interpreted is different.
If we look at how we end up with the music we hear, we have to start at the stream of data that is picked up by the laser. The pits on a CD are extremely small, measured in terms of millionths of a metre across. We can represent a 1 bit by storing a pit into the CD, and a zero by putting the opposite of a pit, a "land" if you like. First of all, why can't we simply store all the data in sequence on the disc? Certainly such a CD player could be designed, but there are several immediate problems. Firstly, if there are too many 1's or 0's in a row, the electronics won't be able to sort them all apart, it needs a fair distribution of 1's and 0's to operate. Imagine a piece of silence, which of course is a frequent occurrence, that will be stored as zeroes. So a form of encoding exists which puts 14 bits out for each 8 bits required. These 14 bits are arranged so that there aren't too many 1's or 0's in a row. Add three syncing up bits, and you finally have the data which is encoded on the disc.
So we are reading these bytes from the CD, seventeen bits being translated into bytes, what happens from here?
How can a CD survive scratches?
First of all, if that was the end of the story and our data simply was stored in order, imagine what would happen on a scratch. Remember that a CD's pits are microscopically small, a tiny scratch will wipe out hundreds of pits, that is very bad news if we want to keep our data intact, and avoid nasty clicks like we used to have on vinyl.
First of all we need to spread the data around, that way any defects do not all happen at once, and we can take steps to remedy the errors if they occur apart from one another. Secondly, we need to ideally be able to correct the data. This is more important for data CD's, for instance CD-ROMs, and video CD's.
Correcting the data is the most intriguing part of CD technology, but there is a price to pay. Considering the data that is extracted from the CD, after we have done the translation from 14 bits to 8 bits, we have 32 bytes of data coming in. Of those 32 bytes, 3/4, i.e. 24 bytes, are destined for our own use, the rest are needed for the error correction. So if we were to say for the sake of easy maths that there are 74 Minutes of data on a CD, we could have 98 minutes if we were to forgo the error stuff. That's not the end of the story either, for CD-ROM, you only end up with 2048 bytes for every 2324 bytes, this is because whereas you might get away with an error on a CD AUDIO, it is somewhat vital to keep every last byte of a program or graphic.
A Short Digression into How Error Correction might work
To get a feel for how error correction might work, consider a series of data bytes, and we will show them in a table like
|
Now, suppose we add another number to the right, and also to the bottom, which is the sum of all the numbers, so
|
Now suppose we change one of the numbers in our data, say change the central 7 to 8. How can we identify where the error has occurred? Well if we check the columns, we find the central one doesn't add up. Also if check the rows, we likewise find the central one doesn't check out, so we can pinpoint immediately the central 7 as being wrong. Also since we have the total, we can work out what the correct value should be, and fix the error.
The method of correcting errors on CD data is similiar. We will not go into the precise mechanics, but it is worth exploring what types of errors are fixed.
The First Stage of Error Correction
We have seen that out of 32 bytes read from the CD as one "frame", we only use 24 bytes in our final data. Four of the bytes are used in the first stage of correction, the remaining four are not used till the second part. This first stage is called C1, if you like Correction one. At this point, we have 28 bytes of data, plus four bytes which help us locate any errors, just like in our previous section. Using some funky mathematics, we can detect if those 28 bytes are correct, and if not we can fix a single error straight away, making those 28 bytes good. If we cannot fix the error, there are now only a couple of options open. Some CD players attempt to fix two errors, which is possible if there really are just two errors, however the mathematics is not so reliable for more than two errors. Several errors could create a situtation that looks like only two errors, and we can end up with a frame that we think is good, but is in fact bad.
Having found a bad C1 frame, we do not know at this stage which bytes are in error, all we know is that there are at least two errors.
As we mentioned before, the data on a CD is scattered. For instance before we take a C1 frame of data, the data we treat is alternating from the current block of data, and the previous. A further scattering happens to the C1 frames, so that we only take one byte out of the 28 at a time, into the C2 processing, the second stage of error correction. Each byte out of C1 is delayed by a whole frame, so the first byte will be used 112 frames later, the second 108 frames later, until the last byte which is used immediately. The blocks are dealt with in sets of four, this also helps the spread of errors, since any continuous burst of errors that could occur is spread throughout 112 frames.
The Second Stage of Error Correction
At this C2 stage, we have 28 bytes which have come from 28 different C1 frames. Each of those frames was either good or bad, we can remember this with a small lookup table. At the C2 stage, we have 28 bytes, four of which are designed to help us determine if the data is good, and to effect a correction. This time round we know which bytes are wrong, and also how many of these faults exist, as contrasted to the C1 frame, where we only knew that the data did not check out.
Using some more clever mathematics, we can now fix up to four of those errors. Any more than that, and we are skuppered.
What Happens if the Error Correction Fails.
For an audio CD, our data is not quite at the end of its journey. There is still a final de-interleave of the C2 blocks which means that every faulty byte of the 24 that are output is surrounded by 2 (hopefully) good bytes from the neighbouring C2 block. Of course if you are unlucky enough to have two bad C2 blocks in a row, then this is not the case. For an audio CD, we can make a guess of what a byte ought to have been, by looking at the surrounding values, and interpolating the value. For a video CD, there is often an error bit in your MPEG decoder that can be set just before the bad bit is sent, and for pure DATA CDs, we would now hope that the last layer of error correction will find and fix the error - this is beyond the scope of this discussion.
Is There Any Way to Fix More Errors!?
The way CD players are currently built relies on a very limited hardware set of RAM, i.e. temporary storage. Given some more space, various options open up for correcting more errors.
With a 4K buffer to hold the data between the C1 and C2 stage, it is possible to redo the C1 fix-one-error operation after you have done the C2 fix-four-errors stage. Since each byte of the C2 stage comes from a different C1, any time that we correct a C2's error, we can go back to the C1 of which that byte was a part, fix a single error if possible, and clear the flag that marks that C1 frame as bad for the C2's yet to come. This means that at best we can be fixing 32 errors at C1, and also 28 errors at C2, but those are extreme conditions. Often of course you will be fixing C1 errors too late to benefit the C2's that have already gone by, but on average you will be fixing about 40 percent more C2 errors. Given infinite storage and processor power, you could continue to reprocess C1 and C2 frames, but since decoding is normally done real time, this is not usually practical. This is a fairly radical correction strategy described in this paragraph, please contact me for more information.
The interesting thing about subcodes is their location in the stream, they are sort of outside the main stream itself. A subcode is a byte that occurs for every "frame", i.e. one byte for every 32 input, 24 output bytes. These are interpreted 98 bytes at a time, as this is the amount pertaining to 1/75th of a second.
To make life more difficult for everyone, the data within this 7K per second bonanza has to be considered as 8 sets of bits, so the 98 bytes are interpreted as 8 sets of 98 bits, 12 bytes plus a couple of sync bits. In this form, these subcode "channels" are labelled as P (top bit) Q then RSTUVW. The P channel goes high during the start of a track, which I think is a throwback to older days for simpler players. The Q channel contains exciting time stamp information. In brief this data tells of your current minute second and block (1/75th of second) relative to the start of the track, and the absolute time, which is relative to the start of the whole disc. There is also a checksum so a player can be sure that the data is accurate. This is a CRC, which I will detail at a later date. The reason for this is that there is no error correction information to help you with the subcodes, since the subcode byte exists in effect outside the space/time continuum of the 32 byte frames.
The Table of Contents is stored at the start of the disc, before any real data. Its purpose is to identify the tracks present on the CD, the time that they occur, and the type of data present. The information is stored in the subcodes, and is repeated for a number of seconds. This is done so as to allow for a certain amount of damage to CDs, since the CRC in the subcodes will indicate a bad entry in the TOC. However, a serious scratch to the TOC area (the inner-most part of the CD) is likely to cause a TOC to be unreadable, this is a big cause for CD's becoming unplayable, especially where there are a large number of tracks.
At a later date I will list all of the details of the TOC in this section.