Doi: 10.1145/1467247.1467269
by Venkatesan guruswami and Atri Rudra
Ever since the birth of coding theory almost 60 years ago, researchers have been pursuing the elusive goal of constructing the “best codes,” whose encoding introduces the minimum possible redundancy for the level of noise they can correct. In this article, we survey recent progress in list decoding that has led to efficient error-correction schemes with an optimal amount of redundancy, even against worst-case errors caused by a potentially malicious channel. To correct a proportion r (say 20%) of worst-case errors, these codes only need close to a proportion r of redundant symbols. The redundancy cannot possibly be any lower information theoretically. This new method holds the promise of correcting a factor of two more errors compared to the conventional algorithms currently in use in diverse everyday applications.
Coping with corrupt data is an essential part of our modern day lives; even if most of the time we are blissfully unaware of it. When we watch television, the TV has to deal with signals that get distorted during transmission. While talking on our cellphones, the phone has to work with audio signals that get corrupted during transmission through the atmosphere though we definitely are aware of it when the connection is poor. When we surf the Internet, the TCP/IP protocol has to account for packets that get lost or garbled while being routed. When we watch movies on DVDs, the player has to overcome loss of data due to scratches. Even when we buy our groceries, the scanner has to deal with distorted barcodes on packages.
The key ingredient in coping with errors in these and many other applications is an error-correcting code or just code for brevity. The idea behind codes is conceptually simple: add redundancy to the information so that even if the resulting data gets corrupted, e.g. packets get corrupted during routing or the DVD gets some scratches, the original information can still be recovered.
Ideally, we would like to add a small amount of redundancy and at the same time be able to correct many errors. As one might expect, these are conflicting goals and striking the right balance is where things get interesting. For example, consider the code where every information bit is repeated say a 100 times (this is known as the repetition code). Intuitively, this code should do well. In particular, the following is a natural error-recovery procedure or a decoding algorithm: for every consecutive 100 bits of the data, identify whether the majority of the bits is 0 or 1, and output the corresponding bit. Unless we happen to be unlucky, this decoding algorithm can recover from quite a few errors. The downside is that every 100 bits of data contain only one bit
of information—imagine how large a DVD would need to be in order to store a movie with such redundancy. On the other extreme is the parity code, which appends the parity of the information bits at the end of the message. This code uses the minimum amount of redundancy possible but has poor error-recovery capabilities. Indeed, even if just two bits get flipped, it can go undetected. For example, 0001 gets encoded as 00011 under the parity code. If the first two bits get corrupted and we receive 11011, we would misinterpret the original message to be 1101. Imagine Clark Gable saying at the end of your small parity encoded DVD for Gone with the Wind, “Frankly, my dear, I don’t give a ham !”
To capture this inherent tension between the redundancy and the error tolerance of codes, let us define codes and some key parameters formally. A code C is given by an encoding map of the form C : Σk → Σn (for integers k < n) which encodes a sequence of k symbols from Σ into a larger sequence of n symbols. Given a message m Î Σk, C(m) is known as the corresponding codeword. The parameters k, n, and Σ are called the dimension, block length, and alphabet of C, respectively. We will often use the ratio R = k/n, which is called the rate of C. Note that R exactly captures the amount of information contained per bit of a codeword. The Hamming distance between two strings in Σn is the number of coordinates where they differ. The minimum distance of a code is defined to be the small-est Hamming distance between two distinct codewords.
Thus, our question of interest can be now re-stated as follows: given a code C of rate R, what is the maximum fraction of errors (which we will henceforth refer to as r) that can be tolerated by C Now as every codeword has k symbols of information, it is intuitive that in the worst case at least k symbols of a codeword should be uncorrupted to have any hope of recovering the original information. In other words, we can only have r ≤ (n − k)/n = 1 − R, irrespective of the computational power of the decoder.
The main focus of this article is the following question:
Can we construct a code C of rate R that can be efficiently decoded from close to a 1 − R fraction of errors?
Quite surprisingly, we will show the answer to be yes. Thus, the above simple information-theoretic limit can in fact be approached. In particular, for small rates, we can recover from situations where almost all of the data can be corrupted. For example, we will be able to recover even if Clark Gable were to spout “alhfksa, hy meap xH don’z hive b hayn!” There are
The original version of this paper was published in IEEE Transactions on Information Theory, 2008.
References:
Archives