Dispersing the errors
Dr. Maureen Hunter | TLT President's Report December 2014
How a mathematical formula keeps credit cards, Websites and even scratched CDs functioning perfectly.
Double the value of alternate digits of the primary account number, beginning with the second digit from the right. The first right-hand digit is the check digit. (Source: click here).
“I’M SORRY. THAT CREDIT CARD NUMBER MUST BE WRONG. Please read it again.”
“4417123456789113,” I said to the customer service rep who was taking my Christmas shopping order over the phone.
“That number worked,” the rep said after a moment. “You should receive those music CDs in five to seven business days.”
I hung up and looked out the window. An early snowfall was beginning to accumulate on the grass. “Christmas will be here before you know it,” I said to my son, home from college. “But your little sister’s CDs should arrive in plenty of time. I hope she doesn’t scratch them.”
“You know, Mom, just like your credit card, CDs are mathematically encoded. Even if scratched, they usually play perfectly.”
“Well, that’s good,” I said, half listening. “I really thought I gave the sales rep the correct credit card number the first time.”
“Misread credit card numbers happen all the time,” my son said. “Did you know that the last number of your credit card is a check digit? Check digits are also used for airplane tickets, bank routing numbers, UPCs at stores, ISBNs on books, VIN numbers on cars and lots of other things, like CDs.” He pulled up an example of how check digits work from a Website on his computer.
“That’s interesting, but how do check digits help play a CD with scratches.” I asked.
“Good point,” he said. “To play music, just detecting errors isn’t good enough. CDs need to correct errors, and CDs can self-correct the typical 50,000 manufacturing errors and a half million errors from scratches. They use a Reed-Solomon Code, somewhat like for your credit card, but with multiple check digits that can correct errors, and they use interleaving.”
“Interleaving?” I questioned.
“When a CD is scratched, it corrupts a lot of 0s and 1s all in a row. So to not lose that music, you need to intersperse data in a lot of different places on the CD.”
“How does that work?” I asked.
“Well, instead of explaining interleaving with 0s and 1s, tell me a sentence. Anything,” he prodded.
“STLE is my favorite,” I blurted out.
He raised an eyebrow questioningly. “We’ll go with it. Say four letters in a row are lost when the message is sent, and you get
STLE -- -- FAVORITE. The message is no longer clear. So the solution is to interleave the message to disperse the errors. The sentence is put horizontally in a 4x4 grid like this.” He grabbed a piece of paper and drew quickly.
Then he added, “But it’s sent vertically. So reading down, you get
SIFR TSAI LMVT EYOE. So say you send the message and lose four letters that are next to each other, like a scratch on a CD.” He crossed the letters out from the last column. “When the message is read back horizontally, you’ve spread out those errors, and now you get
STL- IS M- FAV-RIT-.”
“That is easier to read because the missing letters aren’t grouped together,” I said.
“Of course, this is a simplified example,” he went on. “CDs use a Cross- Interleaved Reed-Solomon Code that has multiple check digits added on to the blocks, both horizontally and vertically. These check digits are used to detect and fill in missing 0s and 1s caused by the scratches and manufacturer’s defects. A half million errors on a 20-bit CD can be corrected. And, of course, CDs also deal with two channels for hearing music in stereo, and this needs to be interleaved.”
“And all this is packaged onto a CD?” I asked.
“That’s right. Mathematics is encoded into all digital music that we listen to today. This technology keeps computerized systems running. It’s used for data storage on your hard drive, for satellite communications and, yes, Mom, even for STLE’s Website, Webinars, podcasts, online courses, certification exams, publications...” His voice drifted off.
And this TLT article, I thought.
Maureen Hunter is the technical service manager for King Industries, Inc., in Norwalk, Conn. You can reach her at mhunter@kingindustries.com.