skip to content
PSYCHO VIRTUAL

List-Decoding (5/5)

/ 2 min read

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 m1m_1 and m2m_2 which we encode using E(m1)E(m_1). Assuming a minimum distance dd, we transmit this message and the channel distorts the message with d/2d/2-errors which distorts E(m1)E(m_1) into rr which is exactly in between E(m1)E(m_1) and E(m2)E(m_2). Now we have no way of determining whether m1m_1 or m2m_2 is the correct message.

Theorem 1.0: For the code C:=RS[F,L,d]C := RS[\mathbb{F}, L, d], parameters δ[0,1]\delta \in [0,1], and f:LFf:L \rightarrow \mathbb{F}. We define List(f,d,δ)List(f, d, \delta) as the list of code-words in CC with at most δ\delta relative Hamming distance from ff. Such that CC is (δ,l)(\delta, \mathcal{l})-list decodable if List(f,d,δ)lList(f, d, \delta) \le \mathcal{l} for every ff.

Johnson Bound

Theorem 1.1: The code RS[F,L,d]RS[\mathbb{F}, L, d] is (1pη,12ηp)(1 - \sqrt{p} - \eta, {1 \over 2\eta\sqrt{p} })-list decodable for every η(0,1p)\eta \in (0, 1 - \sqrt{p}) where p:=dLp := {d \over |L|} is the rate of the code.

Error Bounds

We define the function err(d,p,δ,m)err^*(d, p, \delta, m) for both unique and list decoding as follows:

  1. Unique decoding regime δ(0,1p2)\delta \in (0, {1-p \over 2}):

err(d,p,δ,m):=(m1)dpFerr^*(d, p, \delta, m) := {(m - 1) \cdot d \over p \cdot \mathbb{F}}

  1. List decoding regime δ(1p2,1p)\delta \in ({1-p \over 2}, 1 - \sqrt{p}):

err(d,p,δ,m):=(m1)d2F(2min{1pδ,p20})err^*(d, p, \delta, m) := {(m - 1) \cdot d^2 \over \mathbb{F}\cdot (2 \cdot min\{1 - \sqrt{p} - \delta, {\sqrt{p} \over 20} \}) }

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