列表译码

形式陈述 ​

取整数 $n\ge 1$、$q\ge 2$，设非空 $C\subseteq {\mathrm{\Sigma }}^n$ 是一个 $q$ 元信道码理路信道码Channel code把消息映为信道输入码字并从带噪输出恢复消息的编码—译码对。，并用Hamming 距离理路Hamming 距离Hamming distance等长字中不同坐标的数量；由逐位比较、三角不等式和 Hamming 球解释检错与唯一纠错半径。定义 $B_H(y,r)=\{x\in {\mathrm{\Sigma }}^n:d_H(x,y)\le r\}$。给定错误比例 $0\le \rho \le 1$ 与整数列表上界 $L\ge 1$，若对每个接收词 $y\in {\mathrm{\Sigma }}^n$ 都有

则称 $C$ 是 $(\rho ,L)$ list-decodable。有限长度文献也常直接用整数半径 $t$ 写成 $(t,L)$；在比例与整数之间转换时必须保留取整约定。参数 $L$ 是最坏接收词上的列表大小，不是平均候选数，也不能从定义中省略。

这正是列表恢复理路列表恢复List recovery从每个坐标给定的小候选集合中找出在足够多坐标命中的全部码字。在每坐标输入单元素集合 $S_i=\{y_i\}$、命中比例 $\alpha =1-\rho$ 时的特例。若该接口允许空集合，先补成单元素、列出候选，再按原命中条件过滤即可；取整满足 $\lceil (1-\rho )n\rceil =n-\lfloor \rho n\rfloor$，没有改变半径。

组合列表可译码性只限制球内码字数。算法性列表译码还要求存在算法，在给定 $y$ 后找出所有满足 $d_H(c,y)\le \rho n$ 的 $c\in C$，或对应消息，并在输入长度及允许的列表规模上多项式时间运行。一个码可能在组合上具有小列表，却没有已知高效方法枚举它；反过来，算法不能遗漏球内候选再把较短输出称为完整列表译码。

若码的最小距离为 $d$，那么半径 $t=\lfloor (d-1)/2\rfloor$ 的每个 Hamming 球至多含一个码字，即 $(t,1)$ 唯一可译码。列表译码允许 $L>1$，因此可把半径推过这一保证，但不会消除歧义：译码器输出的是一组都与接收词相容的候选，最终选出哪一个需要额外信息或应用语义。

对固定的 $q$ 元字母表和 $0\le \rho <1-1/q$，定义码率与 q 元熵

列表译码容量是一条存在性边界。对任意固定间隙 $\epsilon >0$ 和充分大的块长 $n$，存在码 $C_n\subseteq {\mathrm{\Sigma }}^n$ 满足

并且是 $(\rho ,L)$ 列表可译码的，其中 $L=O_{q,\rho }(1/\epsilon )$，与 $n$ 无关。随机码以高概率达到这一区域，因此也证明这种码族存在；这不自动给出显式构造或多项式时间译码器。

这一存在结论可用概率方法理路概率方法Probabilistic method通过证明随机选取对象具有正概率满足性质来推出确定性对象存在。证明。设 $0<\rho <1-1/q$，并先考虑 $0<\epsilon <1-H_q(\rho )$。从全部 $N=q^n$ 个词中均匀无放回选取 $M=\lfloor q^{n(1-H_q(\rho )-\epsilon /2)}\rfloor$ 个不同词。固定一个球及 $L+1$ 个被选位置，它们都落入该球的概率至多为 $(V/N{)}^{L+1}$，其中 $V=|B_H(y,\lfloor \rho n\rfloor )|\le q^{n{H}_q(\rho )}$。对球心与位置组应用并集上界理路并集界Union bound · Boole 不等式多个坏事件中至少一个发生的概率，不超过各事件概率之和。，得到

取 $L+1>2/\epsilon$，右侧趋零，而取整后的码率在充分大 $n$ 时仍至少为 $1-H_q(\rho )-\epsilon$。无放回选择使码字从一开始就互异；当 $\rho =0$ 时，直接取全空间即可得到 $L=1$。若目标码率下界非正，单码字码已经满足存在结论。

反过来，若一族码的码率满足 $R(C_n)>1-H_q(\rho )+\epsilon$，Hamming 球体积的平均计数已经是 $q^{\mathrm{\Omega }(\epsilon n)}$，所以至少有一个接收词周围含指数多个码字。这里的量词不是“所有低于容量的码都好”，而是“容量以下存在小列表码，容量以上任何码族都无法保持多项式最坏列表”。