CRC与CRC-Polar：为什么 CRC 能帮助 SCL 选择候选路径

第 14 篇介绍了 SCL 译码。它在每个信息位保留多个候选，最后得到一组可能的输入序列。问题是：如果有两条甚至多条路径的路径度量都比较小，译码器还需要一个额外标准来判断哪条路径更可信。

CRC 就是这个额外标准。发送端在消息向量后附加一小段由消息向量计算得到的校验比特；接收端对每条候选序列重新计算校验。如果候选序列不满足这个关系，就把它排除。把 CRC 放在 Polar 编码之前，得到 CRC-Polar；接收端再用 CRC 辅助 SCL 选择路径，这种译码方法称为 CA-SCL（CRC-aided SCL）。CRC-Polar 是编码方案，CA-SCL 是译码方法，二者不是同一个概念。

CRC-polar

本文先解释 CRC 本身，再把 CRC 放进 Polar 编码和 SCL 译码流程中。全文使用一个 CRC-4 的完整例子，所有模 2 运算都逐步写出。

先看 CRC 要解决什么问题

CRC 的全称是循环冗余校验（Cyclic Redundancy Check）。它的作用不是纠正错误，而是检查一段比特是否仍然满足发送端留下的代数关系。

假设发送端要发送消息向量

\underline{m}=(m_0,m_1,\ldots,m_{A-1})

接收端得到一段候选比特。即使候选比特长度正确，里面也可能有一个或多个比特发生错误。CRC 为每个消息向量计算一个固定长度的校验结果。正确的消息向量与正确的校验结果之间满足特定关系；随机错误序列通常不满足这个关系。

因此，CRC 可以判断“这条候选是否满足预先约定的校验关系”，但不能单独回答“错误应该改成什么”。在 CRC-Polar 中，Polar 码负责利用信道信息产生候选，CRC 负责从候选中排除不满足约束的序列。

CRC 的数学定义

CRC 使用二元域 $\mathbb{F}_2$ 上的多项式。写多项式时，通常用普通的 $+$ 把非零项列出来；把多项式展开成比特串并进行具体运算时，系数相加才表现为异或：

0\oplus0=0,\qquad 0\oplus1=1,\qquad 1\oplus0=1,\qquad 1\oplus1=0

把消息向量的比特从左到右看作多项式的高次项到低次项。例如

(1,1,0,1)\longleftrightarrow M(D)=D^3+D^2+1

选择一个次数为 $L_{\mathrm{CRC}}$ 的生成多项式 $g(D)$ 。它决定了 CRC 的计算规则。本文使用

g(D)=D^4+D+1

它的系数序列是 $10011$ ，所以 CRC 长度为

L_{\mathrm{CRC}}=4

设 $M(D)$ 是消息向量对应的多项式。先乘以 $D^{L_{\mathrm{CRC}}}$ ，相当于在消息向量末尾补 $L_{\mathrm{CRC}}$ 个 0。然后用 $g(D)$ 做模 2 除法，所得余数记为 $R_{\mathrm{CRC}}(D)$ ：

D^{L_{\mathrm{CRC}}}M(D)=Q(D)g(D)+R_{\mathrm{CRC}}(D),\qquad \deg R_{\mathrm{CRC}}(D)<L_{\mathrm{CRC}}

发送端把这个余数作为校验比特附加到消息向量后面：

T(D)=D^{L_{\mathrm{CRC}}}M(D)+R_{\mathrm{CRC}}(D)

这里的 $+$ 是二元域上的多项式加法；如果只看对应的系数比特，它才等价于逐位异或。由余数的定义可知， $T(D)$ 能被 $g(D)$ 整除：

T(D)=Q(D)g(D)

这就是 CRC 的核心：正确的消息向量和校验比特拼在一起后，除以生成多项式的余数必须为 0。

CRC-4 的完整计算例子

第一步：写出消息向量和生成多项式

取一个 4 比特消息向量：

\underline{m}=1101

它对应的多项式为 $M(D)=D^3+D^2+1$ 。生成多项式为 $g(D)=D^4+D+1$ ，系数序列为 $10011$ 。

由于生成多项式的次数是 4，先在消息向量后补 4 个 0：

1101\ \longrightarrow\ 11010000

第二步：进行模 2 长除法

模 2 长除法与普通长除法的对齐方式相同，但减法换成异或。每次找到当前最左侧的 1，就把 $10011$ 对齐到这个位置。

第一次，当前序列的最左侧是 1。将 $10011$ 对齐后异或：

\begin{array}{r} 11010000\\ \oplus\ 10011000\\ \hline 01001000 \end{array}

结果 $01001000$ 的最左侧有效 1 位于第二个位置，所以把生成多项式右移一位：

\begin{array}{r} 01001000\\ \oplus\ 01001100\\ \hline 00000100 \end{array}

此时剩余部分已经没有足够的位数再放下 5 位生成多项式，因此最后 4 位 $0100$ 就是 CRC 余数：

R_{\mathrm{CRC}}(D)\longleftrightarrow 0100

所以发送序列为

\underline{m}_{\mathrm{CRC}}=1101\Vert0100=11010100

这里的 $\Vert$ 表示连接，不是加法。

第三步：验证整除关系

把完整序列 $11010100$ 再除以 $10011$ ：

\begin{array}{r} 11010100\\ \oplus\ 10011000\\ \hline 01001100\\ \oplus\ 01001100\\ \hline 00000000 \end{array}

余数为 0000，说明 $11010100$ 满足 CRC 约束。

现在只把完整序列的最后一位，也就是 CRC 部分的最后一位，从 0 改成 1，得到错误候选 $11010101$ 。消息向量 $1101$ 没有改变。前面的第一步不变，第二步变成

\begin{array}{r} 01001101\\ \oplus\ 01001100\\ \hline 00000001 \end{array}

余数为 $0001$ ，因此这个候选不通过 CRC。

CRC 为什么能发现很多错误

设发送的合法序列为 $T(D)$ ，接收错误对应的多项式为 $E(D)$ ，那么接收序列为

\hat{T}(D)=T(D)+E(D)

由于 $T(D)$ 能被 $g(D)$ 整除， $\hat{T}(D)$ 的余数只取决于 $E(D)$ ：

\operatorname{rem}\left(\hat{T}(D),g(D)\right) =\operatorname{rem}\left(E(D),g(D)\right)

因此，只要错误多项式 $E(D)$ 不能被 $g(D)$ 整除，CRC 就能发现错误。只有当 $E(D)$ 恰好是生成多项式的倍数时，错误才可能漏检。

如果把错误序列近似看成均匀随机序列，长度为 $L_{\mathrm{CRC}}$ 的 CRC 通过错误候选的概率约为

2^{-L_{\mathrm{CRC}}}

例如 CRC-4 的近似误通过概率为 $1/16$ ，CRC-6 约为 $1/64$ 。这只是随机错误假设下的近似值，真实概率还会受到信道、Polar 码结构和候选路径相关性的影响。

CRC-Polar 是怎样组合起来的

CRC-Polar 不是另一种独立的 Polar 生成矩阵，而是把 CRC 校验和 Polar 码串联起来：

先生成 $A$ 个消息比特；
根据生成多项式计算 $L_{\mathrm{CRC}}$ 个校验比特；
将消息比特和校验比特合并成 $K=A+L_{\mathrm{CRC}}$ 个信息比特；
把这 $K$ 个比特放入 Polar 码的信息位集合 $\mathcal{A}$ ；
其余位置 $\mathcal{A}^c$ 固定为 0；
进行 Polar 编码、调制和传输；
接收端用 SCL 得到多条候选，再用 CRC 检查这些候选。

这里最重要的顺序是：CRC 必须在 Polar 编码之前加入。这样，消息向量和 CRC 才会一起受到 Polar 码保护，译码后的候选信息序列中也才保留着它们之间的校验关系。 }

一个 CRC-Polar 的具体放置例子

继续使用刚才的消息向量：

\underline{m}=1101,\qquad \underline{r}=0100,\qquad \underline{m}_{\mathrm{CRC}}=11010100

为了只展示 CRC 比特如何进入 Polar 输入序列，先人为指定一个便于手算的信息位集合：

N=16,\qquad A=4,\qquad L_{\mathrm{CRC}}=4,\qquad K=8

再假设构造得到的信息位集合为

\mathcal{A}=\{8,9,10,11,12,13,14,15\}

这只是便于手算的教学布局。把 $11010100$ 按顺序放入这些位置，得到 Polar 输入序列

\underline{u}_0^{15}=(0,0,0,0,0,0,0,0,1,1,0,1,0,1,0,0)

前 8 个位置是冻结位，后 8 个位置依次装入

(m_0,m_1,m_2,m_3,r_0,r_1,r_2,r_3)=(1,1,0,1,0,1,0,0)

之后，Polar 变换只把 $\underline{u}$ 变成码字；它不需要知道哪些比特属于消息向量，哪些比特属于 CRC。对 Polar 编码器来说，这 8 个位置都是信息位。消息向量与 CRC 的区别只在发送前生成、接收后检查时有意义。

真实构造中， $\mathcal{A}$ 通常由可靠性排序得到，不一定是连续的后 8 个位置。此时仍然按信息位索引的升序，把 $m_{\mathrm{CRC}}$ 的第 $k$ 个比特放入 $\mathcal{A}$ 中的第 $k$ 个位置。

SCL 为什么需要 CRC

SCL 在信息位处分裂路径，并根据路径度量保留 $L_{\max}$ 条候选。路径度量只描述“这条路径与接收 LLR 是否相符”，它不知道消息向量和 CRC 之间的代数关系。

因此，错误路径可能出现下面的情况：它在信道意义下暂时更占优势，路径度量比正确路径还小，但它携带的消息向量和 CRC 并不匹配。只看路径度量时，译码器会选错；加入 CRC 后，这条路径会被排除。

先看一次路径度量比较

假设某条路径当前的路径度量为 $PM=0.42$ ，当前位的条件 LLR 为 $\Lambda=1.6$ 。由第 14 篇的概率关系：

q(0)=\frac{1}{1+e^{-1.6}}\approx0.832,\qquad q(1)=\frac{1}{1+e^{1.6}}\approx0.168

两个候选的增量分别是

\Delta(0,1.6)=-\ln q(0)\approx0.184,\qquad \Delta(1,1.6)=-\ln q(1)\approx1.784

所以扩展后的两个路径度量约为

PM(0)=0.42+0.184=0.604,\qquad PM(1)=0.42+1.784=2.204

在译码过程中，SCL 按这种方式累计和比较路径度量；CRC 不参与当前位的 LLR 计算，也不改变这两个增量。CRC 只在候选信息序列完整形成后检查它是否满足校验关系。

完整候选形成后的 CRC 筛选

假设 SCL 最后保留了下面 3 条候选。表中的序列都是从 Polar 输入向量的 $\mathcal{A}$ 位置按升序提取出的消息与 CRC 序列：

候选	消息与 CRC 序列	路径度量 $PM$	CRC 结果
$\ell_0$	11010101	1.08	失败
$\ell_1$	11010100	1.21	通过
$\ell_2$	10001011	1.35	通过

SCL 只比较路径度量，会选择 $\ell_0$ ，因为 $1.08$ 最小。但 $\ell_0$ 的序列除以 $10011$ 的余数是 $0001$ ，它不满足 CRC。

$\ell_1$ 的余数为 0000， $\ell_2$ 除以 $10011$ 的余数也为 0000，因此它们都满足 CRC。于是 CA-SCL 先留下

\mathcal{S}_{\mathrm{CRC}}=\{\ell_1,\ell_2\}

再在这个集合中比较路径度量，最终选择 $\ell_1$ 。CRC 没有改变路径度量的大小，而是改变了“哪些候选有资格参加最后比较”。

CA-SCL 的完整判决规则

设 SCL 结束后存活路径的编号集合为 $\mathcal{S}_{N-1}$ ，通过 CRC 的路径集合为

\mathcal{S}_{\mathrm{CRC}} =\left\{\ell\in\mathcal{S}_{N-1}: \operatorname{CRC}\left(\hat{\underline{m}}^{(\ell)}\right)=0\right\}

本文采用下面的两步判决规则：

如果 $\mathcal{S}_{\mathrm{CRC}}$ 非空，只在通过 CRC 的路径中选 $PM$ 最小者；
如果没有任何路径通过 CRC，就在全部存活路径中选 $PM$ 最小者。

\hat{\ell}= \begin{cases} \displaystyle\arg\min_{\ell\in\mathcal{S}_{\mathrm{CRC}}}PM_\ell^{(N-1)}, &\mathcal{S}_{\mathrm{CRC}}\ne\varnothing,\\ \displaystyle\arg\min_{\ell\in\mathcal{S}_{N-1}}PM_\ell^{(N-1)}, &\mathcal{S}_{\mathrm{CRC}}=\varnothing \end{cases}

第二条是本文采用的回退规则；有些系统也会在这种情况下直接报告校验失败。CRC 是检验条件，不是绝对正确性的证明；如果正确路径已经在 SCL 的中间剪枝中被删除，或者所有存活路径都受到严重噪声影响，列表中可能没有任何候选通过 CRC。无论采用哪种处理，都应记录“没有路径通过 CRC”这一状态。

CRC 与路径度量区别

路径度量和 CRC 解决的是两个不同问题：

量	作用	使用时机
条件 LLR	描述当前比特更支持 0 还是 1	每个位判决时
路径度量 $PM$	累计路径与接收信号的匹配程度	每次扩展和剪枝时
CRC	检查完整消息与 CRC 序列的代数关系	候选序列形成后

如果在信息位刚判决几位时就提前做 CRC，校验对象还没有完整形成，得到的结果没有意义。正确做法是：SCL 按 LLR 和路径度量完成列表搜索，等候选序列的全部 $K$ 个信息比特都确定后，再统一提取和检查 CRC。

另一方面，CRC 也不能替代路径度量。可能有两条路径都通过 CRC，此时仍需用 $PM$ 比较它们与接收信号的匹配程度。

CRC 长度与 Polar 码参数的关系

加入 CRC 后，真正进入 Polar 信息位集合的长度不是消息向量长度 $A$ ，而是

K=A+L_{\mathrm{CRC}}

因此 Polar 码率应按

R=\frac{K}{N}

这里的 $R=K/N$ 是把 CRC 也计入后的 Polar 码率；如果只计算消息向量相对于码长的传输效率，则应写成 $R_{\mathrm{msg}}=A/N$ 。在固定 $A$ 和 $N$ 时，CRC 越长， $K$ 越大，母码码率 $R$ 会升高，但消息向量的传输效率 $R_{\mathrm{msg}}$ 不变。如果固定 $K$ 和 $N$ ，CRC 越长则可承载的消息比特越少。选择 CRC 长度时，需要在误检概率、码率、列表宽度和目标 BLER 之间折中。

还要区分两种错误：

如果正确路径仍在列表中，CRC 有机会从错误路径中选出正确路径；
如果正确路径已经被剪枝删除，CRC 无法把它重新找回来。

所以增大 $L_{\max}$ 和选择合适的 CRC 长度通常需要一起考虑。

小结

CRC 的计算可以归结为一句话：把消息向量后补 $L_{\mathrm{CRC}}$ 个 0，用生成多项式做模 2 除法，得到余数并附加到消息向量后面；接收端重新除法，余数为 0 才通过。

CRC-Polar 的关键顺序是：

\text{消息向量} \longrightarrow \text{CRC} \longrightarrow \text{消息向量+CRC} \longrightarrow \text{Polar编码} \longrightarrow \text{SCL候选} \longrightarrow \text{CRC筛选}

SCL 用路径度量回答“哪条路径更符合信道观测”，CRC 用代数关系回答“哪条完整序列满足发送约束”。CA-SCL 先保留通过 CRC 的候选，再在其中选择路径度量最小者；如果无人通过，则回退到全部存活路径中的最小路径。

下一篇将讨论有限码长下的 Polar 码性能，说明为什么 CRC、列表宽度和系统 Polar 码的结构会共同影响 BER、BLER 与 FER。

参考

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.
K. Niu and K. Chen, “CRC-aided decoding of polar codes,” IEEE Communications Letters, vol. 16, no. 10, pp. 1668–1671, Oct. 2012, doi: 10.1109/LCOMM.2012.090312.121720.
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.