SC译码为什么成立：逐次判决的基本思想

第 10 篇已经完成了信道构造：通过可靠性排序得到信息位集合 $\mathcal{A}$ 和冻结位集合 $\mathcal{A}^c$ 。编码端把输入向量 $\underline{u}$ 变成二元码字 $\underline{c}$ ，经过信道后得到接收观测 $\underline{y}$ 。译码端面对的问题是：只知道 $\underline{y}$ ，怎样把 $\underline{u}$ 恢复出来？

最直接的想法是最大似然（maximum likelihood，ML）译码：把所有候选信息向量都编码一次，选择最符合 $\underline{y}$ 的那个候选。这个方法在理论上清楚，但候选数量随 $K$ 指数增长。Polar 码的第一个低复杂度译码器是 successive cancellation（SC）译码，它把一次性的联合判决拆成按索引顺序进行的逐位判决。

本文继续采用 0-based 索引。码长为 $N=2^n$ ，信息长度为 $K$ ，码率为 $R=K/N$ 。接收观测统一写作 $\underline{y}$ ，底层信道输出的原始 LLR 写作 $\underline{\lambda}$ 。译码过程中产生的估计向量统一写作 $\hat{\underline{u}}$ 。

编码已经知道了，为什么译码又是另一件事

编码是确定性映射：

\underline{c}=\underline{u}\mathbf{G}_N\pmod 2

给定 $\underline{u}$ ，码字 $\underline{c}$ 唯一确定。若进入 BPSK 调制，则再由 $x_i=1-2c_i$ 得到实数发送符号；信道把这些符号变成带噪声的 $\underline{y}$ ，同一个观测可能对应多个候选输入。译码必须比较这些候选在信道模型下的后验概率。

如果只考虑信息位，联合 MAP 译码可以写成：

\hat{\underline{u}}_{\mathcal{A}}=\underset{\underline{v}_{\mathcal{A}}\in\{0,1\}^{K}}{\arg\max}\;P\left(\underline{u}_{\mathcal{A}}=\underline{v}_{\mathcal{A}}\mid\underline{y}\right)

冻结位已经预先约定为 0，因此候选空间有 $2^K$ 个，而不是 $2^N$ 个。即使这样， $K$ 稍大时穷举仍然不可行。SC 的关键不是忽略概率，而是利用概率的链式分解，把联合问题转换为一串条件问题。

什么是逐次消元译码

对任意一个候选输入向量，联合后验概率可以按链式法则分解：

P(\underline{u}\mid\underline{y})=\prod_{i=0}^{N-1}P\left(u_i\mid\underline{y},u_0^{i-1}\right)

这里 $u_0^{i-1}=(u_0,u_1,\ldots,u_{i-1})$ 表示当前位之前已经给定的比特序列；这说明，第 $i$ 位的后验概率天然带有一个条件：已知前面的比特取什么值。

SC 译码从 $i=0$ 开始。对每个索引 $i$ ，它先根据 $\underline{y}$ 和已经得到的比特估计 $\hat u_0^{i-1}$ ，计算当前位的条件后验，再立即输出 $\hat u_i$ 。输出结果会作为后续位的已知条件，这就是“successive cancellation”的含义：前面已经判定的比特被当作边信息，参与后面子信道的计算。

需要注意，SC 使用的是估计比特序列，而不是发送端真正的比特序列：

\hat{\underline{u}}=(\hat u_0,\hat u_1,\ldots,\hat u_{N-1})

如果某一步估错，错误的 $\hat u_i$ 可能进入后续递归，造成错误传播。这是 SC 复杂度低但性能受限的根本原因。

子信道后验概率如何定义

Polar 码把原始信道拆成 $N$ 个按索引排列的子信道。第 $i$ 个子信道的输入是 $u_i$ ，输出既包括原始观测 $\underline{y}$ ，也包括已经给定的比特序列 $u_0^{i-1}$ 。在这些比特给定时，对尚未处理的比特求和，可以定义：

W_N^{(i)}\left(\underline{y},u_0^{i-1}\mid u_i\right)=\frac{1}{2^{N-i-1}}\sum_{u_{i+1}^{N-1}}W^N\left(\underline{y}\mid\underline{u}\mathbf{G}_N\right)

其中 $W^N(\underline{y}\mid\underline{u}\mathbf{G}_N)$ 是 $N$ 次独立信道转移概率。求和的作用是把未知的后续比特 $u_{i+1}^{N-1}$ 边缘化；已经给定的比特不能求和，因为它们是当前判决的条件信息。

SC 实际使用的是已经得到的比特估计，因此在译码时对应的条件 LLR 写作：

L_N^{(i)}\left(\underline{y},\hat u_0^{i-1}\right)=\ln\frac{W_N^{(i)}\left(\underline{y},\hat u_0^{i-1}\mid0\right)}{W_N^{(i)}\left(\underline{y},\hat u_0^{i-1}\mid1\right)}

这个 $L_N^{(i)}$ 是第 $i$ 个合成子信道的 LLR，不要和底层信道的原始 LLR $\lambda_j$ 混为同一个量。第 12 篇会从似然比的乘法关系出发，具体推导如何用 $f$ 和 $g$ 递归计算它。

为什么 LLR 的符号就能给出判决

在二元输入等概的前提下，当前位的两个后验概率之比正好等于条件 LLR：

\frac{P\left(u_i=0\mid\underline{y},\hat u_0^{i-1}\right)}{P\left(u_i=1\mid\underline{y},\hat u_0^{i-1}\right)}=\exp\left(L_N^{(i)}\left(\underline{y},\hat u_0^{i-1}\right)\right)

因此，条件 MAP 判决只需比较 LLR 与 0：

\tilde u_i= \begin{cases} 0, & L_N^{(i)}\left(\underline{y},\hat u_0^{i-1}\right)\ge0,\\ 1, & L_N^{(i)}\left(\underline{y},\hat u_0^{i-1}\right)<0. \end{cases}

这里的 $\tilde u_i$ 表示“如果当前位是信息位，按照信道证据得到的临时判决”。当 LLR 为正时， $u_i=0$ 的后验更大；为负时， $u_i=1$ 的后验更大；等于 0 时两者同样可信，本文约定选择 0。

例如当前条件 LLR 为 $L_N^{(i)}=1.3$ ，且两个输入假设等概，则后验概率可写成：

P(u_i=0\mid\underline{y},\hat u_0^{i-1})=\frac{e^{1.3}}{1+e^{1.3}}\approx0.786, \qquad P(u_i=1\mid\underline{y},\hat u_0^{i-1})\approx0.214.

因此该位置的临时判决为 $\tilde u_i=0$ 。这个数值例子只说明 LLR 符号判决的含义；实际 SC 实现通常直接比较 LLR 与 0，不必显式计算指数。

Polar 码还知道哪些位置是冻结位，因此 SC 的最终规则分成两种情况：

\hat u_i= \begin{cases} 0, & i\in\mathcal{A}^c,\\ \tilde u_i, & i\in\mathcal{A}. \end{cases}

冻结位不是“LLR 很小所以判成 0”，而是编码规则已经规定它必须为 0。即使观测强烈支持 1，SC 也会把该位置固定为已知值；这部分已知信息随后会用于计算后续信息位的 LLR。

一个最小的逐位判决示意

取 $N=4$ ，设信息位集合为 $\mathcal{A}=\{2,3\}$ ，冻结位集合为 $\mathcal{A}^c=[0,3]\setminus\mathcal{A}=\{0,1\}$ 。下面的 LLR 数值表示某一次观测经过 SC 递归后得到的条件 LLR，用来展示判决顺序；它们不是把原始 $\lambda_j$ 直接逐项代入的结果。

索引 $i$	位类型	已使用比特	条件 LLR $L_4^{(i)}$	SC 输出
0	冻结位	空	$-0.8$	$\hat u_0=0$
1	冻结位	$\hat u_0=0$	$+0.4$	$\hat u_1=0$
2	信息位	$\hat u_0\hat u_1=00$	$-2.1$	$\hat u_2=1$
3	信息位	$\hat u_0\hat u_1\hat u_2=001$	$+1.3$	$\hat u_3=0$

这个表中最值得注意的是三点：

索引 0、1 虽然分别收到负、正 LLR，输出仍由冻结规则固定为 0。
索引 2 的判决结果 1 会成为索引 3 的已知条件；索引 3 不是在同一个“没有已判决比特”问题上独立判决。
如果索引 2 实际上判错，索引 3 使用的比特条件也会随之错误。SC 不会回头重新修改索引 2 的选择。

这正是逐次消元译码的两面性：已经判决的比特提供了计算后续子信道所需的边信息，同时也把早期错误传递给后续位置。

用条件后验把一次 SC 决策算开

为了把“已判决比特会改变后验”写成可计算的数字，仍取 $N=4$ 、冻结位 $u_0=u_1=0$ ，只观察两个信息位 $u_2,u_3$ 。下面给出一组抽象的条件 LLR 轨迹：

L_4^{(2)}=\ln\frac{P(u_2=0\mid\underline{y},00)}{P(u_2=1\mid\underline{y},00)}=\ln\frac{0.6}{0.4},

因此第 2 位的两个后验概率就是 $0.6$ 和 $0.4$ ，SC 先输出 $\hat u_2=0$ 。第 3 位的条件概率必须根据不同的 $u_2$ 分开定义；例如设

P(u_3=0\mid\underline{y},00,u_2=0)=0.6,qquad P(u_3=1\mid\underline{y},00,u_2=1)=0.99.

把它们改写成 LLR，可得在 $u_2=0$ 的已知条件下 $L_4^{(3)}=\ln(0.6/0.4)$ ，在 $u_2=1$ 的已知条件下 $L_4^{(3)}=\ln(0.01/0.99)$ 。SC 只沿着自己已经选定的比特序列继续计算，于是继续输出 $\hat u_3=0$ 。

如果把四个联合候选都列出，链式分解给出

\begin{aligned} P(0,0\mid\underline{y},00)&=0.6\times0.6=0.36,\\ P(0,1\mid\underline{y},00)&=0.6\times0.4=0.24,\\ P(1,0\mid\underline{y},00)&=0.4\times0.01=0.004,\\ P(1,1\mid\underline{y},00)&=0.4\times0.99=0.396. \end{aligned}

这个例子中特意让 $P(1,1\mid\underline{y},00)=0.396$ 大于 $P(0,0\mid\underline{y},00)=0.36$ 。因此联合 ML 会选 $(u_2,u_3)=(1,1)$ ，而 SC 因为在第 2 位先比较边缘后验 $0.6$ 与 $0.4$ ，已经锁定了 $u_2=0$ ，最终输出 $(0,0)$ 。这不是 SC 公式错误，而是逐次译码用“当前条件最优”近似“完整联合最优”的必然代价；SCL 通过同时保留 $u_2=0$ 和 $u_2=1$ 两条候选路径，让后续观测仍有机会选中联合概率更大的路径。

上面的数字只用于解释概率链式分解和贪心决策，不代替第 12 篇从底层 $\underline{\lambda}$ 通过 $f/g$ 递归得到条件 LLR 的物理计算。实际调试时，应把每组已判决比特对应的 $L_N^{(i)}$ 、后验概率和最终判决一起记录，才能区分“概率模型正确但 SC 选择受限”和“LLR 递归实现错误”这两类问题。

SC 与最大似然译码是什么关系

ML 译码直接比较完整码字的联合似然：

\hat{\underline{c}}_{\mathrm{ML}}=\underset{\underline{c}\in\mathcal{C}}{\arg\max}\;W^N(\underline{y}\mid\underline{c})

SC 则在每个索引上只保留一个当前最优的条件判决。换句话说，SC 把联合搜索树压缩成一条路径：每到一个信息位就选择 0 或 1 中后验较大的分支，随后不再保留另一分支。

当所有已判决比特都正确时，SC 使用的条件分布与真实发送序列一致，逐位 MAP 判决能够沿着正确路径推进。实际中一旦某个信息位判错，后续条件分布就可能偏离真实子信道，因此 SC 的性能通常低于 ML。

SC 的优势与天然局限

SC 的主要优势是结构简单、存储需求低，并且可以利用 Polar 码的递归结构达到近似 $O(N\log N)$ 的计算复杂度。

它的局限同样明确：

每个信息位只有一次硬判决机会，不能回溯。
早期错误会改变后续 LLR 的已知条件，形成错误传播。
在短码和中等信噪比下，SC 的性能可能明显落后于 SCL 或 CA-SCL。

因此，SC 并不是“把所有位独立做硬判决”。它是一个按索引递归计算条件 LLR、按冻结规则或 LLR 符号输出结果的串行译码过程。

调试 SC 译码器时应该观察什么

实现 SC 时，最有价值的调试量不是最终的 $\hat{\underline{u}}$ 一个数组，而是每一步的状态：

当前索引 $i$ 是否落在 $\mathcal{A}$ 或 $\mathcal{A}^c$ 。
当前条件 LLR $L_N^{(i)}$ 的符号和数量级是否合理。
已判决比特 $\hat u_0^{i-1}$ 是否与递归节点保存的部分和一致。
冻结位是否无条件写入 0，并参与后续 $g$ 分支计算。

下一篇将从子信道似然比的定义出发，逐步推导 SC 递归中的 $f$ 函数和 $g$ 函数。由此本文的“根据观测和已判决比特得到当前 LLR”会从概念描述变成可直接实现的公式。

小结

SC 译码利用后验概率的链式分解，把一次联合判决改写成按 $i=0,1,\ldots,N-1$ 顺序进行的条件判决。第 $i$ 位的条件 LLR 是：

L_N^{(i)}\left(\underline{y},\hat u_0^{i-1}\right)=\ln\frac{W_N^{(i)}\left(\underline{y},\hat u_0^{i-1}\mid0\right)}{W_N^{(i)}\left(\underline{y},\hat u_0^{i-1}\mid1\right)}

信息位根据 LLR 符号做 MAP 判决，冻结位则直接写入预先约定的 0。已经判决的比特会参与后续子信道计算，因此 SC 既获得了串行递归的低复杂度，也承担了错误传播的代价。

理解“为什么要按顺序判决”之后，下一步就是回答“当前 LLR 到底如何递归计算”。这就是 $f$ 和 $g$ 公式要解决的问题。

参考

E. Arıkan, “Channel polarization: A method for constructing capacity-achieving codes for symmetric binary-input memoryless channels,” IEEE Transactions on Information Theory, vol. 55, no. 7, pp. 3051–3073, Jul. 2009, doi: 10.1109/TIT.2009.2021379.
I. Tal and A. Vardy, “List decoding of polar codes,” IEEE Transactions on Information Theory, vol. 61, no. 5, pp. 2213–2226, May 2015, doi: 10.1109/TIT.2015.2410251.