列表恢复

普通接收词在每个位置只提出一个猜测；列表恢复允许上游算法说“这个坐标可能是这几个符号之一”。目标码字不必在所有位置都进入候选集，只需命中足够多位置。它因而适合级联码：内码译码器可为每个外码坐标产生一个小列表，外码的 list-recovery 算法再把跨坐标一致的全局消息拼出来。

三个参数承担不同风险。增大 $\ell$ 让每个坐标更宽容，却增加伪候选；降低 $\alpha$ 允许更多坏坐标，也增加伪候选；$L$ 则记录最坏输入下允许保留多少全局解释。只说“可列表恢复”而不列出三者，无法判断结论强弱。

取三元重复码

和输入集合

令 $\alpha =2/3$。码字 111 在三处都命中；000 只在第一处命中；222 只在第二处命中。因此达标候选集恰为 $\{111\}$，这个实例的输出列表大小是一。

若把第三个集合改为 $\{0,2\}$，则 000 命中第一、三处，111 命中第一、二处，222 命中第二、三处，三个码字全部达到 $2/3$ agreement。相同码和相同 $\ell =2$，只改输入列表就使最坏输出达到三，说明 $L$ 必须对所有集合列量化，而不能由一次成功运行估计。

信息论界还依赖字母表。对随机码作粗略计数时，一个固定码字在随机大小 $\ell$ 的集合中命中的概率约为 $\ell /|\mathrm{\Sigma }|$；当 $\ell$ 与字母表同量级，列表输入几乎不提供筛选信息。声称达到“list-recovery capacity”时，需要同时固定码率、字母表、$\ell$ 的增长方式、agreement 和列表大小，不能直接照搬 $1-R$ 的普通大字母表列表译码口号。

列表恢复是把局部不确定性组合成全局候选的标准接口。级联码中，内码负责把噪声压成逐坐标小列表，外码负责跨位置一致性；基于 expander 的放大、tensor/product codes 的局部算法以及交互式编码也会调用同一接口。接口的价值在于调用者无需知道外码如何插值，只需提供集合列并遵守 $\ell ,\alpha$ 条件。

折叠 Reed–Solomon 与重数码利用同一多项式在相关评价或导数数据间的代数一致性获得强列表恢复性质。具体半径与复杂度依赖折叠参数、重数、域大小和插值维数，应由各构造页承担，而本页只固定输入输出语义。