Venkatesan Guruswami and Atri Rudra
Error Correction Up to the Information-Theoretic Limit
Abstract :
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 p (say 20%) of worst-case errors, these codes only
need close to a proportion p 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.
Versions
A related article