Polar Code（9）CA-SCL译码算法

前言

循环冗余校验（Cyclic redundancy check，CRC）是一种信道检错技术，在实际数字通信系统中已经得到了广泛应用。对于Polar码而言，在SCL译码结束时得到一组候选路径，能够以非常低的复杂度与CRC进行联合检测译码，选择能够通过CRC检测的候选序列作为译码器输出序列，从而提高译码算法的纠错能力。

CA-SCL译码算法

文献[1]提出了CRC辅助的SCL（CRC-aided SCL，CA-SCL）译码算法，在信息比特序列中添加CRC校验比特序列，利用SCL译码算法正常译码获得\(L\)条搜索路径，然后借助“正确信息比特可以通过CRC校验”的先验信息，对这\(L\)条搜索路径进行挑选，从而输出最佳译码路径。给定Polar码码长为\(N\)，CRC校验码码长为\(m\)，若极化码的信息为长度为\(K\)，编码信息比特的长度为\(k\)，如图1所示，有\(K=k+m\)。Polar码的码率仍然为\(R={K}/{N}\;\)。

定义\({ {L}^{\left( i \right)}}\)为SCL译码码树第\(i\)层对应的候选路径集合，搜索列表宽度为\(L\)的CRC-aided SCL译码算法表示为CA-SCL（L），有如下算法步骤：

1、初始化：候选路径列表初始化为一条空路径，对应的路径度量值设置为0：\({ {L}^{\left( 0 \right)}}=\left\{ \varnothing \right\}\)，\(M\left( \varnothing \right)=0\)。

2、扩展：对于列表中的每个序列，产生2个长度为\(i\)的序列，分别对应译码\({ {\hat{u}}_{i}}\)为比特0或1，即

\[{ {L}^{\left( i \right)}}=\left\{ \left( d_{1}^{i-1},{ {d}_{i}} \right)|d_{1}^{i-1}\in { {L}^{\left( i-1 \right)}},{ {d}_{i}}\in \left\{ 0,1 \right\} \right\}\]

对于每个\(d_{1}^{i}\in { {L}^{\left( i \right)}}\)更新路径度量值。

3、竞争：若经过步骤2后，列表中的路径数未达到\(L\)条，则跳过此步；否则，保存路径度量值最小的\(L\)条路径，并删除其余路径。

4、CRC辅助路径选择：重复步骤2和3直到码树第\(N\)层。把列表中的候选路径按度量值从小到大排序，依次进行CRC校验。第1个通过CRC校验的路径即为译码器输出的估计序列。若没有路径通过CRC检测，则把第1条路径作为译码器输出估计序列。

小结

CA-SCL译码算法是对SCL算法的增强，SCL的内核不变，只是在Polar编码之前给信息比特添加CRC，在SCL译码获得候选路径之后，进行CRC校验辅助路径选择，以较低的复杂度提升了Polar译码性能。

参考文献

[1] Niu K, Chen K. CRC-Aided Decoding of Polar Codes[J]. IEEE Communications Letters, 2012, 16(10):1668-1671.