列表译码

形式陈述 ​

设 $C\subseteq {\mathrm{\Sigma }}^n$ 是 $q$ 元码，$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\cap B_H(y,\lfloor \rho n\rfloor )|\le L,$$

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

组合列表可译码性只限制球内码字数。算法性列表译码还要求存在算法，在给定 $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 元熵

$$R(C_n)=\frac{1}{n}{\log }_q|C_n|,H_q(\rho )=\rho {\log }_q(q-1)-\rho {\log }_q\rho -(1-\rho ){\log }_q(1-\rho ).$$

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

$$R(C_n)\ge 1-H_q(\rho )-\epsilon$$

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

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

直觉 ​

唯一译码把接收词交给一个最近的码字，一旦两个候选都足够近就必须失败或冒险猜测。列表译码接受“噪声证据暂时不足以唯一裁决”，先把所有合理候选保留下来。只要列表始终很短，后续的一小段校验、上下文约束或认证信息就可能完成选择。

允许列表相当于把码字周围必须互不相交的球改成可以有限重叠的球。重叠次数 $L$ 是新的资源：半径越大，通常要容忍更长列表；容量界说明超过某条率—半径曲线后，局部重叠会从可控数量跃升为指数数量。

例子与边界 ​

取二元码

$$C=\{0000,1100,1010\}$$

和接收词 $y=1000$。三个码字与 $y$ 的距离都为 $1$，所以半径 $1$ 内无法唯一译码，但完整候选列表恰为这三个码字。若系统另有经过认证的消息摘要，它可以检查三项并选出正确消息；没有独立信息时，列表译码本身不能断言其中哪一个曾被发送。

Reed–Solomon 码公理库Reed–Solomon 码Reed–Solomon code以低次数多项式在互异域元素处的取值向量形成的最大距离可分码。展示算法性突破。Guruswami–Sudan 方法通过插值构造一个在大量接收点上带重数为零的二元多项式，再因式分解找出所有低次数消息多项式；对码率 $R$，它可在适当参数下把错误比例推进到接近 $1-\sqrt{R}$，超过传统约 $(1-R)/2$ 的唯一译码半径。该结论利用 RS 的代数结构，不能推广成“任意列表可译码码都有插值算法”。

列表小也不等于列表好找。组合证明可能只说明每个球最多含 $L$ 个码字，却仍需扫描整个指数大码本；声称高效时必须给出码表示、算法、运行时间和输出完整性。反过来，只找到若干近邻而漏掉其他合法候选，是启发式搜索，不满足上述列表译码接口。

超过列表译码容量时，问题不只是算法尚未改进。若码率高于 $1-H_q(\rho )$ 一个常数量级，平均球占有数的计数已经呈指数增长，因此至少某个球包含指数多码字，任何显式输出完整列表的算法都要花指数时间。容量是组合障碍，而非某个译码器的性能上限。

推论与应用 ​

列表译码用于高噪声通信、级联码、复杂性理论、稀疏恢复和从部分正确信息中恢复多项式。它把“码的几何重叠受控”与“存在高效恢复算法”分成两个可独立研究的目标，也让外层校验、子空间约束或密码认证能作为消歧层组合进系统。

与 Hamming 界比较时，唯一译码要求半径 $\lfloor (d-1)/2\rfloor$ 的球不交，列表译码只控制更大球的重叠数；与 Johnson 类界比较时，最小距离可以推出某段半径内的通用列表上界，但通常达不到容量。任何具体结论都应同时报告码率 $R$、半径 $\rho$、列表大小 $L$、字母表 $q$ 以及译码复杂度。

参考资料

• Peter Elias, “List Decoding for Noisy Channels,” 1957, and John M. Wozencraft, early sequential/list-decoding work。
• Madhu Sudan, “Decoding of Reed Solomon Codes beyond the Error-Correction Bound,” Journal of Complexity 13(1), 1997。
• Venkatesan Guruswami and Madhu Sudan, “Improved Decoding of Reed–Solomon and Algebraic-Geometric Codes,” IEEE Transactions on Information Theory 45(6), 1999。
• Venkatesan Guruswami, List Decoding of Error-Correcting Codes, Springer, 2004。