开放科学(资源服务)标志码(OSID):

0 概述

极化码^[1]是ARIKAN于2008年提出的一种在理论上可达信道极限容量的编码方式。目前，极化码被应用在5G增强移动宽带场景中，作为5G的信道控制编码方式。极化码的构造依赖于一个特定的递归编码过程，研究人员根据其编码构造的特点提出了复杂度低的串行抵消(Successive Cancellation，SC)译码算法^[2]，但是在中短码长的情况下该算法的性能不理想。为提高译码的性能，文献[3-4]提出串行抵消列表(Successive Cancellation List，SCL)译码算法^[3-4]，该算法提高了极化码在有限块长度的性能，使得其能与低密度奇偶校验(Low-Density Parity-Check，LDPC)码^[5]和turbo码^[6]竞争。随后，奇偶校验码(Parity Check Codes，PCC)^[7]和循环冗余检验(Cyclic Redundancy Check，CRC)极化码的自适应SCL译码算法^[8]与CRC辅助SCL(CRC-Assistant SCL，CA-SCL)译码算法^[9]被提出，其中CA-SCL译码算法在搜索宽度L=32时，译码性能可以接近最大似然(Maximum-Likelihood，ML)译码界^[10]。并且，为降低时延，文献[11]提出一种基于基本路径替代的低时延自适应列表连续删除转换算法，针对不同列表的连续删除转换间存在重复路径的现象。虽然SCL译码算法显著降低了极化码码长为有限长时的BLER，但它具有较大的存储开销和较高的计算复杂度，且两者都与列表大小呈线性增长的关系。

2014年，AFISIADIS等^[12]提出具有较小存储开销和较低计算复杂度的SCF译码算法。与SCL的并行SC译码算法相比，该译码算法依赖更多后续的解码尝试，通过依次翻转不可靠的信息比特纠正SC译码过程中发生的错误。虽然该算法最坏的译码情况为翻转最大尝试次数仍不能译出正确的译码结果，但是在中高SNR下，它产生的平均计算复杂度与SC解码的平均计算复杂度近似，并且它的译码性能与L=2时的SCL译码算法相近。SCF译码算法是用CRC对译码结果进行校验，因此CRC检错能力会影响SCF译码的性能。2018年，KIM等^[13]提出交织辅助的SCF译码算法。无论是用CRC校验的SCF译码算法，还是用交织器辅助的ISCF译码算法，SCF译码算法提升的性能都是有限的。为解决SCF存在的问题，目前研究人员从2个方面进行了改进：

通过求解SC译码的首个判决错误(The First Decision Error，TFDE)的概率实现一位比特的翻转。但是在实际中，准确求解出TFDE的概率很难，文献[14]提出一种动态比特翻转译码算法，它通过求解近似TFDE的概率来动态生成比特翻转列表，实现一位甚至是多位比特的翻转，同时文献[15]在此基础上提出了误码率估计的SCF译码算法，该译码算法通过缩小翻转的集合，降低了计算度量值的复杂度。

通过提取不可靠的信息位组成一个较小的翻转集合使得在有限的翻转次数上优先翻转认为错误概率更高的比特。例如，文献[16]研究平均对数似然比(Log-Likelihood-Ratio，LLR)与错误比特信道的分布，提出阈值SCF译码算法，并运用比较器代替LLR的选择和排序，降低了计算的复杂度。文献[17]提出一种基于错误分布的SCF译码算法，该算法包含两个译码算法，一种算法是根据错误分布选取最大错误率的T位信息位组成固定的翻转集合，另一种译码算法则是设置错误分布阈值实现一个动态翻转集合，并运用LLR作为翻转的度量。同时为提升一位翻转SCF译码算法的性能，文献[18]提出分段的SCF译码算法。

为提升SCF译码算法的性能，本文基于串行抵消译码算法，分析对数似然比、极化信道可靠度、信息位所在的位置与SC译码算法发生TFDE之间的关系，并给出一个度量公式衡量SC译码结果的可靠度。

1 SCF译码算法

本节首先对SC译码算法^[2]进行分析。在SC译码算法中，解码器输入端的数据表示为$ {y}_{1}^{N} $，解码器的输出表示为$ \widehat{U}={u}_{1}^{N} $，其中$ {\widehat{u}}_{i} $表示$ {u}_{i} $的译码硬判决估计。在SC解码中，每个硬判决估计$ {\widehat{u}}_{i} $都取决于Y和前i-1个硬判决估计$ {\widehat{u}}_{1}^{i-1} $，LLR的表达式如式(1)所示：

$ {L}_{i}=\mathrm{l}\mathrm{b}\left(\frac{{P}_{r}({u}_{i}=0|Y, {\widehat{u}}_{1}^{i-1})}{{P}_{r}({u}_{i}=1|Y, {\widehat{u}}_{1}^{i-1})}\right) $

(1)

根据$ {L}_{i}^{} $估计SC译码算法的译码结果如式(2)所示：

$ {\widehat{u}}_{i}=h\left({L}_{i}\right)=\left\{\begin{array}{l}{u}_{i}, i\notin I\\ \frac{1-\mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}\left({L}_{i}\right)}{2}, i\in I\end{array}\right. $

(2)

其中：I为信息位集合，当$ {L}_{i}\ge 0 $时，$ \mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}\left({L}_{i}\right)=1 $，否则$ \mathrm{s}\mathrm{i}\mathrm{g}\mathrm{n}\left({L}_{i}\right)=-1 $。

然后对SCF译码算法原理进行阐述。传统的SCF译码算法的步骤为：1)对接收信号$ {y}_{1}^{N} $执行SC译码过程，得到极化码信息比特的译码估计值$ {\widehat{u}}_{1}^{K+\mathrm{r}} $，其中$ K+r $为原极化码的信息比特位数与CRC位数之和；2)用CRC去校验$ {\widehat{u}}_{1}^{K+\mathrm{r}} $，如果校验结果为0，则说明译码正确，输出译码结果并结束译码，否则再次执行SC译码过程，并设置最大的翻转次数T，对翻转次数初始化t=1；3)如果t > T，说明经过了T次比特翻转后仍不能得到正确的译码结果，结束译码；如果t < T+1，通过对每个信息位的$ \left|{L}_{i}\right| $排序，选出$ \left|{L}_{i}\right| $值最小的信息比特$ {u}_{i} $，在判决$ {u}_{1}, {u}_{2}, \cdots , {u}_{i-1} $的过程中，执行SC译码过程；在判决$ {u}_{i} $时，将$ {u}_{i} $按照与式(2)相反结果进行判决，随后用SC译码过程判决$ {u}_{i+1}, {u}_{i+2}, \cdots , {u}_{N} $；4)如果经过步骤3)后译码结果通过CRC校验，则译码结束；否则翻转次数t=t+1，继续执行步骤3)选择另一个信息比特$ {u}_{i} $进行翻转。

为改进SCF译码算法，本文研究极化码在执行SC译码过程中由于信道条件不理想造成比特错误译码的情况。图 1所示为由信道条件引起比特错误译码的个数造成块错误译码的分布。

图 1所示是仿真1 000 000次SCO-1^[12]译码算法去识别和记录SC译码过程中块发生错误时，由信道条件引起比特错误译码个数的概率分布，即该仿真不考虑译码过程中错误传播情况。其中SCO-1译码算法的工作原理是：该译码器预先知道原始输入序列，在执行SC译码的过程中发现译出的信息比特与原始的信息比特结果不一致时，将该信息比特的判决进行翻转并记录这个位置。因此，执行SCO-1译码算法可以纠正SC译码过程中由信道引起错误的第一个信息位。由图 1可知，在执行SC译码算法过程中大于58%的块发生错误是由TFDE造成的。图 2所示为正确翻转一位发生错误译码的信息比特获得的最佳性能，与SC译码算法相比最大可获得约0.7 dB的增益。

从图 2可以看出，准确地翻转TFDE可以明显降低BLER，但是SCO-1译码器是一个模拟仿真工具，在实际中还没有一个度量能百分之百地正确预测TFDE的位置。因此，下文将分析与TFDE相关的参数去确定执行SC译码过程中不可靠的信息比特译码。

2 改进的SCF译码算法

由于传统的SCF译码算法过于依赖LLR值，降低BLER的力度会存在限制。为对传统的SCF译码算法进行改进，本节将研究造成TFDE可能的因素，下文将研究当发生TFDE时，对数似然比、极化信道的可靠度等的分布情况。

由第1节可知，SC译码算法的译码估计公式如式(2)所示，使用这种硬判决机制去估计SC译码结果，再加上噪声的影响，使得$ \left|\mathrm{L}\mathrm{L}\mathrm{R}\right| $值越接近0，那么被误判的概率就越高。为进一步验证$ \left|\mathrm{L}\mathrm{L}\mathrm{R}\right| $值与TFDE之间的关系，图 3仿真了1 000 000次SCO-1译码算法来识别和记录TFDE的位置，并统计了TFDE发生在各个信息位的平均$ \left|\mathrm{L}\mathrm{L}\mathrm{R}\right| $值和所有信息位的平均$ \left|\mathrm{L}\mathrm{L}\mathrm{R}\right| $值。其中圆代表TFDE发生在各个信息位的平均$ \left|\mathrm{L}\mathrm{L}\mathrm{R}\right| $值，方形表示所有信息位的平均$ \left|\mathrm{L}\mathrm{L}\mathrm{R}\right| $值。

从图 3可以看出，发生TFDE的信息位的$ \left|\mathrm{L}\mathrm{L}\mathrm{R}\right| $值总是很小，因此可以得出$ \left|\mathrm{L}\mathrm{L}\mathrm{R}\right| $值在一定程度上是可以作为衡量某个信息位发生TFDE的指标。然而，仅根据$ \left|\mathrm{L}\mathrm{L}\mathrm{R}\right| $值来确定需要翻转的位置还不够准确。因此，还需要探讨一些参数去进行优化。

在中短码长情况下，SC译码算法性能不理想，主要是因为有限的码长信道极化不完全。由公式$ {P}_{e}^{i}\triangleq P({\widehat{u}}_{i}\ne {u}_{i}|{\widehat{u}}_{1}^{i-1}={u}_{1}^{i-1}, Y=y) $(用$ {P}_{e}^{i} $衡量极化信道可靠性的指标，见求解式(3)^[19])可知$ {P}_{e}^{i} $与TFDE有关，即某个信息位$ {P}_{e}^{i} $的值越小，该信息位为首个比特错误译码的概率也就越小。因此，初步认为极化信道可靠度与TFDE有关。为进一步验证极化信道可靠度和TFDE之间的关系，图 4和图 5统计了两者在不同信息位上的分布情况。

图 4表示各个信息位$ {P}_{e}^{i} $的分布，图 5表示各个信息位发生TFDE的频率分布。由图 4和图 5可知，在$ {P}_{e}^{i} $越大时TFDE的频率越高，因此证明了通过$ {P}_{e}^{i} $可以预估各个信息位发生TFDE的概率情况。

$ \begin{aligned}{P}_{e}^{i}\triangleq & P({\widehat{u}}_{i}\ne {u}_{i}|{\widehat{u}}_{1}^{i-1}={u}_{1}^{i-1}, Y=y)=\\ & \frac{1}{2}\mathrm{e}\mathrm{r}\mathrm{f}\mathrm{c}\left(\frac{\sqrt{E\left[{L}_{N}^{i}\right]}}{2}\right)\end{aligned} $

(3)

其中：

$ \mathrm{e}\mathrm{r}\mathrm{f}\mathrm{c}\left(x\right)=\frac{2}{\sqrt{\mathrm{\pi }}}{\int }_{x}^{\mathrm{\infty }}{\mathrm{e}}^{-{t}^{2}}\mathrm{d}t $

(4)

$ E\left[ {L_N^{2i - 1}} \right] = {\phi ^{ - 1}}\left( {1 - {{\left( {1 - \phi \left( {E\left[ {L_{\frac{N}{2}}^i} \right]} \right)} \right)}^2}} \right) $

(5)

$ E\left[{L}_{2N}^{2i}\right]=2E\left[{L}_{N/2}^{2i}\right] $

(6)

式(5)中的$ \phi \left(x\right) $如式(7)所示：

$ \phi \left(x\right)\approx \left\{\begin{array}{l}\sqrt{\frac{\mathrm{\pi }}{x}}\mathrm{e}\mathrm{x}\mathrm{p}\left(-\frac{x}{4}\right)\left(1-\frac{10}{7x}\right), x\ge 10\\ \mathrm{e}\mathrm{x}\mathrm{p}(-0.{452}_{}7{x}^{0.86}+0.{021}_{}8), \mathrm{ }0 < x < 10\end{array}\right. $

(7)

根据上述分析可以得出，判断一个信息比特发生错误译码的情况，可以综合考虑$ \left|\mathrm{L}\mathrm{L}\mathrm{R}\right| $值、极化信道可靠度等因素。又因为极化码的SC译码算法是一个串行译码的过程，即在SC译码过程中，会先对前面的信息比特进行译码，并且前面信息位的译码结果会影响后面信息位的译码结果。因此，当2个信息位为TFDE的概率相差不多时，需要先对前面的信息位进行比特翻转，所以将信息位的索引值作为判断TFDE的一个因素。

根据上述分析，下面分别对这3个参数取一定的权重，使得3个参数在不同的程度上共同决定信息位发生错误译码的程度。假设度量$ {M}_{i} $表达式如式(8)所示：

$ {M}_{i}={A}_{i}\times {P}_{i}\times {R}_{i} $

(8)

其中：$ {A}_{i} $表示第$ i $信息位的索引值$ i $所占的权重；$ {P}_{i} $表示第$ i $信息位的极化信道可靠度所占的权重；$ {R}_{i} $表示LLR值所占的权重，本文$ {R}_{i} $的取值为$ \left|{L}_{i}\right| $。$ {P}_{i} $所占的权重表达式如式(9)所示：

$ {P}_{i}=(1-{P}_{e}^{i})/{P}_{e}^{i} $

(9)

式(9)表示的是一个极化程度，但式(9)得到的值相对较大，为减少$ {P}_{i} $所占权重，式(10)为进一步处理后$ {P}_{i} $所占的权重。

$ {P_i} = {\rm{ln}}((1 - P_e^i)/P_e^i) \approx - {\rm{ln}}{\kern 1pt} {\kern 1pt} {\kern 1pt} P_e^i $

(10)

为得到$ {M}_{i} $的表达式，对$ {A}_{i} $取值进行说明，该权重的取值依据是：在2N的码长中，前面信息比特发生错误的概率比后面的信息比特发生错误的概率要高。又因为极化码码长为2的N次方，所以$ {A}_{i} $的取值规则具有码长的特点，如式(11)所示：

$ {A_i} = {\rm{floor}}\left( {{\rm{lb}}{\kern 1pt} {\kern 1pt} {\kern 1pt} i} \right) + 1$

(11)

其中：floor( )表示一个向下取整函数；$ i $表示信息比特的索引值，即第一个信息比特$ i=1 $，本文$ i $的最大值为$ K+r $。

综上，本文在传统SCF译码算法的基础上提出一个改进的度量公式，如式(12)所示：

$ {M}_{i}=\left(\mathrm{f}\mathrm{l}\mathrm{o}\mathrm{o}\mathrm{r}\right(\mathrm{l}\mathrm{b}i)+1)\times \left|{L}_{i}\right|\times (-\mathrm{l}\mathrm{n}{P}_{e}^{i}) $

(12)

该度量弱化了对$ \left|\mathrm{L}\mathrm{L}\mathrm{R}\right| $值的依赖，综合多个参数决定了信息位发生TFDE的程度。

PLR-SCF译码算法的步骤如下：

1) 对接收信号$ {y}_{1}^{N} $执行SC译码过程，得到极化码的信息比特译码估计值$ {\widehat{u}}_{1}^{K+r} $。

2) 用CRC去校验$ {\widehat{u}}_{1}^{K+r} $。如果校验结果为0，则说明译码正确，输出译码结果并结束译码，否则，再次执行SC译码过程，并设置最大的翻转次数T，对翻转次数初始化t=1，接下来执行步骤3)。

3) 如果t > T，说明经过T次比特翻转后仍不能得到正确的译码结果，结束译码；如果t < T+1，计算式(12)得到每个信息位的度量值$ {M}_{i} $，选出$ {M}_{i} $值最小的信息比特$ {u}_{i} $，执行SC译码过程来判决$ {u}_{1}, {u}_{2}, \cdots , {u}_{i-1} $。在判决$ {u}_{i} $时，将$ {u}_{i} $按照与式(2)相反结果进行判决，随后，用SC译码过程来判决$ {u}_{i+1}, {u}_{i+2}, \cdots , {u}_{N} $。

4) 如果经过步骤3)以后译出的信息比特序列通过CRC校验，则译码结束；否则翻转次数t=t+1，继续执行步骤3)选择另一个信息比特$ {u}_{i} $进行翻转。

3 仿真结果与分析 3.1 误块率分析

本节给出的所有仿真结果都假设在AWGN信道中。极化码级联CRC使用的参数为：N=512，K=256，r=16和N=1 024，K=512，r=16，分别表示为PC(512，256，16)和PC(1 024，512，16)。信息位选择的构造方法有极化重量(PW)构造方法^[20]、密度进化构造方法^[21]和高斯近似(Gaussian Approximation，GA)^[19]构造方法。在不同的信道条件下，最优的信道估计方法不同。由于本文的仿真是在AWGN信道中，因此选择GA的构造方法。CRC的生成多项式为$ g\left(x\right)={x}^{16}+{x}^{15}+{x}^{2}+1 $。下文对PLR-SCF译码算法、SCF算法^[12]、SC译码算法^[2]和SCO-1译码器^[12](一种模拟理想一位比特翻转的译码器，该译码器总能准确地识别出第一个发生错误的比特)的误块率进行比较，如图 6所示。

由图 6可知，在PC(512，256，16)的情况下，本文提出的PLR-SCF译码算法相比于SCF译码算法获得了大约0.12 dB的信噪增益，与SCO-1译码算法的BLER几乎相同。并且，在PC(1 024，512，16)的情况下，PLR-SCF译码算法相比于SCF译码算法也获得大约0.1 dB的信噪比增益，同时，在高SNR时与理想的SCO-1译码算法的BLER很接近，这说明本文提出的度量公式可以提高翻转到发生TFDE信息位的概率，进一步提高了译码的性能。

3.2 计算复杂度分析

为衡量本文提出的度量值在翻转方面的复杂度，如表 1所示为$ {T}_{\mathrm{m}\mathrm{a}\mathrm{x}} $=16时，PLR-SCF译码算法与文献[12]SCF译码算法的平均额外翻转次数的比较。

由表 1可知，与文献[12]SCF算法相比，本文的译码算法得到正确的译码结果，所需的比特翻转尝试次数最多可获得13.6%的降低，并且SNR越高该算法翻转到错误译码的信息比特的速度就越快，说明了PLR-SCF译码算法在识别一位错误信息比特的能力得到了增强。

4 结束语

本文提出一种基于对数似然比与极化信道可靠度的SCF译码算法PLR-SCF，通过仿真观察信息位发生TFDE时对数似然比、极化信道可靠度和信息位位置的分布情况，并根据观察到的结果为不同的参数设定权重值，使得设计出的度量公式能够更精确地衡量信息位译码结果可靠度。仿真结果表明，与SCF译码算法相比，PLR-SCF译码算法能够有效提高算法性能，降低利翻转的尝试次数。由于本文PLR-SCF译码算法主要实现一位比特翻转，下一步将研究多位比特翻转的译码算法，使译码算法性能得到更大提升。