10 List Decoding

10.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.

10.2 List-decodable codes

Definition 10.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\).

10.3 Counting lemmas

Lemma 10.2 Existence of list-decodable codes

✓

Let \(\alpha \) be a finite field, and fix natural numbers \(n\), \(L\), \(M\) and a real number \(p\) with \(0 \le p \le 1\), \(1 \le L\), \(L \lt M\), and \(M \le \left\lvert \alpha \right\rvert ^n\). Suppose \(V\) is a natural number bounding the volume of every Hamming ball of radius \(\lfloor pn\rfloor \), in the sense that each such ball around an arbitrary word \(y \in \alpha ^n\) contains at most \(V\) codewords, and suppose that

\[ \left\lvert \alpha \right\rvert ^n \cdot \binom {V}{L+1} \cdot \binom {\left\lvert \alpha \right\rvert ^n - (L+1)}{\, M-(L+1)\, } \; \lt \; \binom {\left\lvert \alpha \right\rvert ^n}{M}. \]

Then there exists a code \(C\) of length \(n\) over \(\alpha \) consisting of exactly \(M\) codewords that is \((p,L)\)-list-decodable.

Lemma 10.3 Binomial ratio bound

✓

Let \(N\), \(M\), and \(k\) be natural numbers with \(k \le M \le N\). Then the ratio of binomial coefficients satisfies

\[ \frac{\binom {N-k}{M-k}}{\binom {N}{M}} \; \le \; \left(\frac{M}{N}\right)^{k}, \]

where the quantities are compared as real numbers.

Lemma 10.4 Counting inequality for list decoding

✓

Fix an integer alphabet size \(q \ge 2\), a real number \(p\), and integers \(n\) and \(L \ge 1\). Set the rate

\[ r \; =\; 1 - H_q(p) - \frac{1}{L}, \]

and define

\[ M \; =\; \bigl\lfloor q^{\, r n} \bigr\rfloor , \qquad V \; =\; \bigl\lfloor q^{\, H_q(p)\, n} \bigr\rfloor . \]

Assume that \(0 \lt M \le q^n\) and \(L \lt M\). Then

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

10.4 List-decoding capacity

Theorem 10.5 List-decoding over a q-ary alphabet

✓

Let \(\alpha \) be a finite field, write \(q = \left\lvert \alpha \right\rvert \) for the number of its elements, and fix a real number \(p\) with \(0 \lt p \le 1 - \tfrac {1}{q}\) together with an integer \(L \ge 1\). In this regime one considers block codes over the alphabet \(\alpha \) that admit list decoding from a \(p\)-fraction of symbol errors with output lists of size at most \(L\), and the associated rate \(r\) they can achieve.