级联码

级联码（concatenated code）由 G. David Forney Jr. 在 1966 年的专著中提出：外码的每个符号交给一个内码去编码，两级各司其职——外码（通常 Reed–Solomon）扛突发与残余错误，内码（通常短卷积码）匹配物理信道。距离按乘法 d·D 增长，编译码复杂度按多项式增长，Forney 由此证明了第一个"构造性地逼近 Shannon 容量"的定理。它做了二十年深空通信标准，是 turbo/LDPC 之前的最优工程方案，也是量子阈值定理的结构模板。

结构：两级编码

取外码 $[N,K,D]$ over ${\mathbb{F}}_{2^k}$（每个外符号是 $k$ 比特），内码 $[n,k,d]$ over ${\mathbb{F}}_2$。级联编码分两步：

1. $K$ 个信息符号（共 $Kk$ 比特）经外码编码为 $N$ 个 ${\mathbb{F}}_{2^k}$ 符号；
2. 每个外符号（$k$ 比特向量）经内码编码为 $n$ 比特码字，串接成总长 $Nn$ 的码字。

总码是 ${\mathbb{F}}_2^{Nn}$ 上的 $[Nn,Kk]$ 线性码，码率 $R=(K/N)(k/n)=R_{\text{out}}{R}_{\text{in}}$Forney 2009 (Scholarpedia)。

距离乘性：d ≥ d_in · D_out

论证：设级联码字非零。其第 $i$ 段（内码码字）非零当且仅当第 $i$ 个外符号 $m_i\ne 0$——内码是单射线性映射（$k$ 维信息空间嵌入 $n$ 维空间），$m_i\ne 0\Rightarrow m_i{G}_{\text{in}}\ne 0$。非零外码字至少有 $D$ 个非零符号；每个非零段作为内码字至少重 $d$。故

$d_{\text{concat}}\ge d\cdot D.$

∎ 距离按乘法而非加法增长是级联的本质收益：乘性下界随内、外码各自的设计同步放大，而码率只按两级乘积温和缩水——单级码要在同样长度撑起同样距离，通常要付出大得多的码率代价（对照 Singleton 界 $d\le n-k+1$ 即知，见classical-bounds）。当然乘性只是下界，实际距离由内码重量分布与外码的组合结构共同决定。

两级译码与错误局部化

译码自内向外：内码用软判决 Viterbi（卷积码的最大似然序列译码）解调出外符号（可带可靠性信息），外码用代数译码（Berlekamp–Massey，见reed-solomon）纠正残余符号错。关键的工程机理是错误被局部化：内译码把零散的比特级噪声”圆整”为少量的符号级错误——这正是 RS 擅长的突发形态；内码失败产生的相关错误被限制在单个外符号内，不再扩散。两级之间还可多次往返（迭代级联），这是 turbo 码思想的雏形Forney 2009 (Scholarpedia)。

Forney 定理：构造性逼近容量

定理（Forney 1966）：对任意速率 $R<C$，存在级联码族与多项式时间的编译码算法，使误码率随码长趋于零。思路：内码按信道匹配选取（把信道”整形”为接近二进制对称的高质量信道），外码随机选取（避开最坏码），外码长度只需多项式级即可压低错误率Forney 2009 (Scholarpedia)。

历史地位：Shannon 1948 的可达性证明用随机编码，非构造（码书指数大、译码查表指数复杂度）；Forney 把”存在”变成”可构造、可多项式译码”——编码理论的构造史由此从”能不能”转向”多快、多省”。此后 turbo 与 LDPC 把复杂度进一步压向线性（见channel-capacity）。

历史：深空标准与现代演化

RS 外码 + 卷积内码的组合自 1970 年代起是 NASA/ESA 深空任务与 CCSDS 标准的核心（Voyager 起的 20 年间基本无对手）。Forney 本人在 Scholarpedia 条目中梳理了它的现代演化：turbo 码 = 并行级联 + 迭代译码（1993），LDPC = 稀疏图上的扁平级联（见ldpc-classical）——级联思想没有消失，而是从”两级串行”变形为”图上的多约束分解”Forney 2009 (Scholarpedia)。

图:码级联的结构示意——每个外层符号由一个内层码块承载,错误被内层局部化后由外层统一清理;量子侧的级联把同样的递推用于把错误率逐层指数压低(来源:QE017)

量子侧：从 Shor 码到阈值定理

级联结构以三种面目进入量子纠错：Shor 九比特码本身可读作”比特翻转码 × 相位翻转码”的级联（见shor-code）；Knill–Laflamme 把经典级联的构造与译码系统量子化（见concatenated-quantum）；阈值定理的核心递推——把每个物理比特换成码块、每个门换成容错 gadget，错误率按 $p\mapsto c{p}^2$ 逐层压低——正是级联”距离乘性 + 错误局部化”的量子版（见threshold-theorem）。

延伸阅读

• reed-solomon
• channel-capacity
• concatenated-quantum
• threshold-theorem
• ldpc-classical