They use error control codes, which add redundant information to the transmitted data. The receiver uses this redundant data to detect and correct up to a certain fraction of erroneous bytes.
Reed-Solomon codes are a widely used error control code and one of the backbones of deep-space communications. They're handy because they can naturally operate on blocks of 8-bit bytes. An example Reed-Solomon code will take 223 input bytes and append 32 redundant bytes to transmit a total of 255 bytes. The receiver can correct up to 16 errors in the received block.
A Reed-Solomon code is described by (n, k), where n is the block length and k the number of data symbols. Only certain combinations of n and k work out mathematically. The above example is (255, 223). A Reed-Solomon code will correct (n-k)/2 erroneous symbols. Encoding is fast and easy—simple matrix multiplication. Decoding is not something you'd want to try by hand. The code can also detect up to (n-k) errors with 100% confidence. This is useful if you want to request retransmission, but that's not usually an option when the sender is a couple of light minutes or hours away!
Deep space missions usually couple a Reed-Solomon code with a convolutional code. Convolutional codes operate on streams of bits instead of blocks like the Reed-Solomon code. The convolutional encoder takes in one data stream and outputs two or more. So for every input bit, you might get two or three output bits. During encoding, you first pass the data through Reed-Solomon encoder, then run it through the convolutional encoder before it's sent out over the air.
Convolutional decoders tend to produce bursts of errors when overloaded, and block codes are very good at fixing such bursts. On the receive side, the convolutional decoder will fix most of the errors. Any that get through are (hopefully) fixed by the Reed-Solomon code. This is the technology that got us the pictures from Voyager. Picking the codes is a combination of art and science (mostly science).
Every CD player includes a Reed-Solomon decoder to correct read errors. The decoding algorithms were pushing the limits of purpose-built semiconductors around 1980 but are no big deal today.
These approaches are getting phased out for more powerful but far more computationally difficult to decode Turbo Codes. Turbo Codes are like convolutional codes, but with a very clever decoding algorithm that wrings out some extra performance.
Did my Ph.D. on error control coding back in the day…
Edit (history lesson): Block codes like the Reed-Solomon code mentioned above draw from abstract algebra and field arithmetic. It's an example of where a mathematical curiosity from the 1800s suddenly became an integral part of everyday life with the advent of digital communications and storage. Évariste Galois gets of the credit for discovering the math. He has quite an interesting and tragic life story.
A fun thing about Reed-Solomon codes is that the original paper showed that these codes had terrific error control properties, but the decoder presented by the authors was little better than an exhaustive search and completely intractable in practice. The race was then on to design a practical encoder. This ended up being the Berlekamp-Massey Algorithm (BMA), which students of error control call the Black Magic Algorithm. It effectively reverse engineers a linear-feedback shift register. And that's the simple explanation ;-)
The math behind convolutional codes is a bit more varied. Designing the encoder comes from abstract algebra, but the Viterbi decoder used since the '60s came from pure brilliance and maximizing expected values (that goes back to Gauss & least squares). Andrew Viterbi, who developed the namesake algorithm, went on to found a company that you might have heard of: Qualcomm. The algorithm is used wherever you need to find the maximum-likelihood path through a Markov chain, which occurs in speech and character recognition.
I didn't do much with Turbo codes and can't say too much about them. The idea behind the decoder is that two decoding units work on the problem separately and periodically share their best guess and confidence regarding the transmitted sequence. It would be like you and a friend working on two copies of the same crossword puzzle and periodically comparing notes about your guesses and how confident you feel about them.
No comments:
Post a Comment