This is a draft of my notes on List-Decoding. Because this topic touches heavily on computational complexity, as well as information and coding theory, readers should consider consider this pages as very much a work in progress.
List Decoding
In this appendix we provide a short background on key coding theory concepts such as list-decoding and error-bounds. When working with error-correcting codes, we seek to balance the trade-offs between our coding data rate(the amount of non-redundant information in our code) and the error rate(the fraction of symbols that can be corrupted and still allow message recovery).
List-decoding seeks to find the optimal solution for these trade-offs by outputting a list of close code-words(one of which is correct), instead of a single code-word.
See [Gur07] and [Gur04] for an depth exploration of list-decoding.
List Decoding
Say we have two messages and which we encode using . Assuming a minimum distance , we transmit this message and the channel distorts the message with -errors which distorts into which is exactly in between and . Now we have no way of determining whether or is the correct message.
Theorem 1.0: For the code , parameters , and . We define as the list of code-words in with at most relative Hamming distance from . Such that is -list decodable if for every .
Johnson Bound
Theorem 1.1: The code is -list decodable for every where is the rate of the code.
Error Bounds
We define the function for both unique and list decoding as follows:
- Unique decoding regime :
- List decoding regime :
Decoding Algorithms (WIP)
Berlekamp-Welch
Sudan
Guruswami-Sudan
REF
[Gur07] Venkatesan Guruswami. “Algorithmic results in list decoding”. In Foundations and Trends in Theoretical Computer Science, volume 2(2), 2007. https://www.cs.cmu.edu/~venkatg/pubs/papers/listdecoding-NOW.pdf
[Gur04] Venkatesan Guruswami. “List decoding of error-correcting codes”. In Lecture Notes in Computer Science, no. 3282, Springer, 2004. https://www.cs.cmu.edu/~venkatg/pubs/papers/frozen.pdf