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,即

对于每个$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.