7 List Decoding

7.1 Overview

This chapter defines list-decodable codes and proves the list-decoding capacity theorem: for any \(0\lt \rho \le 1-1/q\) and \(L\ge 1\), there exist codes of rate

\[ r \; =\; 1 - H_q(\rho ) - \tfrac {1}{L} \]

that are \((\rho ,L)\)-list-decodable.

7.2 List-decodable codes

Definition 7.1 List-decodable code

✓

A code \(C\) is \((\rho ,L)\)-list-decodable if every Hamming ball of radius \(\lfloor \rho n\rfloor \) contains at most \(L\) codewords of \(C\).

7.3 Counting lemmas

Lemma 7.2 Existence of list-decodable codes

✓

If the ball volume \(V\) and code size \(M\) satisfy the counting inequality

\[ |\alpha |^n\cdot \tbinom {V}{L+1}\cdot \tbinom {|\alpha |^n-(L+1)}{M-(L+1)} \; \lt \; \tbinom {|\alpha |^n}{M}, \]

then there exists a code \(C\) of size \(M\) that is \((p,L)\)-list-decodable.

Lemma 7.3 Binomial ratio bound

✓

For \(k\le M\le N\),

\[ \frac{\binom {N-k}{M-k}}{\binom {N}{M}} \; \le \; \Bigl(\frac{M}{N}\Bigr)^k. \]

Lemma 7.4 Counting inequality for list decoding

✓

For the choice \(r = 1-H_q(\rho )-1/L\), \(M=\lfloor q^{rn}\rfloor \), and \(V=\lfloor q^{H_q(\rho )n}\rfloor \), whenever \(L\lt M\le q^n\),

\[ q^n\cdot \tbinom {V}{L+1}\cdot \tbinom {q^n-(L+1)}{M-(L+1)} \; \lt \; \tbinom {q^n}{M}. \]

7.4 List-decoding capacity

Theorem 7.5 List-decoding capacity

✓

For any \(q=|\alpha |\), \(0\lt \rho \le 1-1/q\), and \(L\ge 1\), there exist codes of rate \(r = 1-H_q(\rho )-1/L\) that are \((\rho ,L)\)-list-decodable.