The greatest scientific minds are pondering the implications of NASA’s Mars rover Curiosity. There have been lively interactions and discussions in internet forums. One that caught our eye was the question of error correction and data loss, posted on Reddit, and explained in depth by a user named “Stubb.” How can Curiosity send a panoramic picture of Mars’ surface, and receive a software update without losing some data to the vastness of space? Well, as the old saying goes, what part of “A Reed-Solomon code is described by (n, k), where n is the block length and k the number of data symbols” can’t you understand?
Since simply asking for a repeat of the information is impossible, and only a certain amount of redundancy is practical, NASA uses two types of algorithms concurrently to encode and decode data and fix errors. The first is something called a “Reed-Solomon Code,” which, at least by NASA’s standards, is easy to encode, because it involves matrix multiplication. Matrix multiplication (which does not involve Kung Fu or wearing sunglasses indoors) arranges numbers both horizontally and vertically into a matrix, and then multiplies those matrices to get another matrix. Within that matrix, there are intentional redundancies. Decoding that information isn’t exactly humanly possible, but the computers that do decode it detect errors with 100% accuracy. Note that I said “detect,” not “fix.”
The second part of the encoding is something called “convolutional code.” A matrix multiplication scheme outputs blocks of data, whereas a convolutional code outputs bursts of data. A convolutional encoder takes in one data stream and outputs two or more. When that decoder is overloaded, it produces errors in bursts as well. So what you have are blocks that contain redundant data, which are then sent through multiple redundant data streams. By coupling the two codes, you manage to get a system that can reconstruct lost data with striking accuracy.VoIP codecs aren’t nearly as complicated, of course, because there are other types of redundancies and error correction in place. It may not directly affect your phone calls now, but, like memory foam, NASA’s decoding technologies should certainly help you sleep better at night.