磁记录中极化码低复杂迭代SCAN译码算法研究

李桂萍, 李聪娜

(1.西安工业大学 计算机科学与工程学院， 陕西 西安 710021； 2.陆军边海防学院 科研处， 陕西 西安 710108)

极化码(Polar Codes)[1]是理论上能够证明可达信道容量限的一种编码技术，其因具有规则的编码结构、明确的构造方法以及低复杂的编译码算法而成为纠错码领域的研究热点。在连续删除译码算法SC(Successive Cancellation)下，当码长无限增大时，极化码具有良好的渐进性能。但是在短码下，极化码的性能却是次优的。针对这一问题，一些学者提出了许多改进的SC译码算法，如连续删除列表译码算法SCL(Successive Cancellation List)[2]、栈译码SD(Stack Decoding)算法[3]以及自适应SCL译码算法[4]等。尽管在列表宽度或栈深度足够大时，这些改进译码算法能够达到最大似然(Maximum Likelihood)译码的性能，但是它们都是基于串行译码机制的硬判决译码算法，无法满足高输出通信应用的需求，也无法满足磁记录等场合对软信息的需求。后来Fayyaz U U等在SC译码算法的基础上提出了软输出连续删除译码算法(Soft Cancellation, SCAN)[5]，解决了软信息的输出问题。本文针对SCAN算法，研究降低译码复杂度和空间复杂度的方法，以及如何提高译码性能等。

1 极化码SC译码算法与置信传播译码算法

(1)

上述过程中L0(0,i)表示译码器接收到的码长为N的码字序列中第i位的LLR值；Ln(i,0)为译码过程第n(这里n=logN,N为码长)阶段第i位的LLR值。式(1)中补集Ic表示固定位下标集合，由于上述译码过程是基于极化码因子图[6-7](如图1所示)执行的，因此Ln(i,0)可通过式(2)或式(3)的递归计算得到。其中，因子图上第λ(其中λ∈{0,1,…,n})列第φ(φ∈{0,…,2λ-1})组中第ω(ω∈{0,…,2n-λ-1})个节点的对应似然值Lλ(φ,ω)的计算方法为：

当φ为偶数时

Lλ(φ,ω)=Lλ-1(φ,2ω)ΔLλ-1(φ,2ω+1)

(2)

当φ为奇数时

(3)

其中式(2)中符号Δ表示的运算如式(4)所示：

(4)

Bλ-1(φ,2ω)=Bλ(φ-1,ω)⨁Bλ(φ,ω)

(5)

Bλ-1(φ,2ω+1)=Bλ(φ,ω)

(6)

图1 码长为8的极化码对应的因子图

同SC译码算法相比，置信传播BP(Belief Propagation)译码算法[8-10]的执行也是基于因子图对似然值进行迭代更新的，但是更新内容以及顺序不尽相同。在BP 算法中因子图上每个节点均传输两种与LLR值相关的信息，即：Li,j和Ri,j。这里Li,j表示因子图上节点(i,j)向左传播的LLR值；Ri,j为节点(i,j)向右传播的消息，其中i=0,1,…,n表示列号，j=0,1,…,N-1表示行号。在BP算法执行前，对因子图上第一列节点的LLR值L0,j和最后一列节点的LLR值Rn,j进行初始化，初始化L0,j的方法同SC译码算法；初始化Rn，j的方法为：当j为信息位时，使Rn,j=0，否则Rn,j=∞ 。因子图中某一个极化单元上各节点相关信息的两种LLR传播方向如图2所示，图中变量j0、j1、j2与j3分别表示相应节点。向左和向右传输的LLR值更新规则分别如式(7)-式(10)所示。

BP译码算法每次迭代均包括从右向左和从左向右这两个方向上的消息更新过程，且每个方向上的更新逐列进行，但在每一列中可以并行更新相应的消息。因此BP译码算法在每一次迭代中均需存储N(logN+1)个LLRs值、在实数域上执行2NlogN次的加法运算和比较运算[5]。

图2 因子图一个极化单元中各节点相关信息传播方向 Li+1,j2=f(Ri+1,j3+Li,j1,Li,j0)

(7)

Li+1,j3=f(Ri+1,j2,Li,j0)+Li,j1

(8)

Ri,j0=f(Ri+1,j2,Ri+1,j3+Li,j1)

(9)

Ri,j1=f(Ri+1,j2,Li,j0)+Ri+1,j3

(10)

2 极化码低复杂迭代SCAN译码算法

基于SC译码算法的SCAN算法与BP译码算法的区别是消息更新的时序不同，SCAN算法中对第i列的似然值Li,j或Ri,j更新时，并不是直接并行更新而是将该列的N个似然值分成2i组，逐次更新该组中的N/2i似然值。与BP译码算法相比较，SCAN译码算法在每次迭代中具有相同的计算复杂度，但收敛速度更快，且空间复杂度较低。本文基于原SCAN算法，通过改变左向LLR值和右向LLR值的更新时序提出了进一步降低译码复杂度和空间复杂度的软输出译码算法。

2.1 通信传输模型设计

图3 本文通信传输模型

2.2 本文算法基本原理

本文提出的改进SCAN算法的基本原理如下：

首先根据列号i值将极化单元上的消息传递时序分为i=0与i>0两种情况：①当i=0、计算第1列的左向似然值L1,j3时，为了把所有行号j3+1为偶数的右向似然值带入到下次的迭代过程中，在单元图上计算L1,j3时仍采用原规则公式(7)，即L1,j3=f(R1,j3+1+L0,j2,L0,j1)，具体见图4；②当i>0且j为偶数时，由于前一阶段的计算过程在实数域上保留了已计算似然值的总和，从而消除了Ri,j+1与Li,j之间的依赖性，这样在后面的迭代中就不需再用每列中序号为偶数的右向LLR值，因此计算Li,j按照规则Li+1,j2=f(Li,j1,Li,j0)进行更新，具体见图5。

图4 因子图第1列左向LLR值更新规则

图5 因子图第1列后所有列左向LLR值更新规则

本文算法对软信息的更新时序同原SCAN算法，仍按照SC译码的顺序对因子图上的软信息进行更新。由图4和图5可知，实现本文算法不需为每一个节点分配存储空间，因此具有较低的空间复杂度。

若令L表示维数为logN+1的向量，则L={L[0],L[1],…,L[logN]}，其中L[i]是维数为2logN-i的向量，用于存储因子图第i列左向LLR值。将所有的右向LLR值根据其j值分为奇数组R0={R0[0],R0[1],…，R0[n-1]}和偶数组Re={Re[0],Re[1],…,Re[n]}两组。维数为2logN-i的数组R0[i]表示第i列中所有序号为奇数的右向LLR值；数组Re[1]表示第i列中所有序号为偶数的右向LLR值，维数也为2logN-i。在上述参数的基础上，本文提出的改进算法包括如下几个重要的步骤：

步骤1，设置最大迭代次数iternum

步骤2，每一次迭代中，按顺序j=0,1,…,N-1逐次更新左向LLR，并对右向LLR值进行初始化：若j为偶数，且当前位是固定位，则Re[j][0]=∞，否则设置Re[j][0]=0；若j为奇数，且当前位是固定位，则R0[j][0]=∞，否则设置R0[j][0]=0，同时更新右向LLR。

上述步骤的实现过程如图6所示，图7为进一步描述该算法的执行流程。

在本文改进算法中，需要对左向和右向传播的LLR值进行更新，具体更新算法为：

(1) 左向LLR值更新算法LLR(j,L,R0,Re)

输入：j,L,R0,Re

步骤1，首先将j表示成logN位的二进制形式

图6 低复杂改进SCAN算法主程序实现过程

图7 本文提出算法的执行主流程

tlogN-1tlogN-2…t0，其中t0表示最低位。若j是非0偶数，从tlogN-1tlogN-2…t0最低位开始查找等于1的位，若存在k满足tk+1=1(0≤k≤logN-1)且所有r≤k的tr均为0，则sj=logN-(k+1)；若j=0，则sj=1；若j为奇数(即此时t0=1)，则sj=logN，列号i=sj。

步骤2，对因子图上第i列中前2logN-i个节点对应的左向LLR值依次进行更新。更新规则为:

L[i][k]=f(L[i-1][2k],L[i-1][2k+1]+R0[i][k]) 若j=0

(11)

L[i][k]=L[i-1][2k]+f(L[i-1][2k]+Re[i][k]) 若j>0

(12)

步骤3，分别对第i列之后的所有列逐次更新前2logN-i个节点对应的左向LLR值：

L[i][k]=f(L[i-1][2k],L[i-1][2k+1])

上述左向LLR值更新函数LLLR(j,L,R0,Re)的程序实现过程如图8所示。

图8 左向LLR值更新函数LLLR(j,L,R0,Re)的程序实现过程

(2) 右向LLR值更新函数RLLR(j,L,R0,Re)

输入：j,L,R0,Re

步骤1，从最右边开始选取tlogN-1tlogN-2…t0中tk=0的最小整数k，计算ej=logN-k;若不存在这样的k，则令ej=0。

步骤2，从第logN-1列到第ej+1列按序更新前2logN-i个下标为奇数的节点对应的右向LLR值

R0[i][2k]=f(Re[i+1][k],Re[i+1][k]+L[i][2k+1])

(13)

R0[i][2k+1]=R0[i+1][k]+f(Re[i+1][k]+L[i][2k])

(14)

其中logN-1≤i≤ej+1。

步骤3，i=ej，对该列中前2logN-i个下标为偶数的节点按式(15)和式(16)更新其对应的右向LLR值：

Re[i][2k]=f(Re[i+1][k],R0[i+1][k]+L[i][2k+1])

(15)

Re[i][2k+1]=R0[i+1][k]+f(Re[i+1][k]+L[i][2k])

(16)

2.3 复杂度分析

由因子图可知，BP译码算法需为每列LLR值分配N个存储空间，因此空间复杂度为N(logN+1)；而原SCAN算法的空间复杂度则降低为4N-2+NlogN/2[5]。这两种算法所需浮点运算的复杂度均为2NlogN[5-7]。通过分析提出算法的主要流程，可计算出本文算法的空间复杂度已降至5N-3，浮点运算复杂度为N(3logN+1)/2，与BP译码算法以及原SCAN算法相比减少了N(n-1)/2。因此，本文提出的改进算法具有较低的空间复杂度和计算复杂度。

3 仿真结果与分析

在二元加性高斯白噪声信道下，选取码长分别为1 024和4 096且码率为0.5、0.7的极化码，采用BPSK调制，比较了极化码在SC译码算法、BP译码算法、原SCAN译码算法以及本文译码算法下的性能。

3.1 码例为(1 024,512)的极化码不同译码算法性能比较

从仿真结果可知(图9)，利用本文译码算法在迭代次数为2时的极化码具有与SC译码算法相当的性能，且优于相同迭代次数的原SCAN译码算法；随着迭代次数的增加，极化码在本文算法下的性能优于SC译码算法，如当迭代次数为4时，性能增益大约为0.15 dB。与BP译码算法相比，极化码在本文译码算法下的性能也明显较优，这是因为极化码因子图上存在大量的短环，导致BP不能有效收敛。

3.2 码例为(4 096,2 867)的极化码不同译码算法性能比较

本文进一步研究了码长较长、码率较大时极化码在本文译码算法下的性能。仿真结果表明(见图10)，与SC译码算法相比，极化码在本文译码算法下当迭代次数为4时仍能获得大约0.18 dB的性能增益；与原SCAN译码算法相比，本文译码算法在相同迭代次数下仍具有较优的性能。

图9 (1 024,512)极化码不同译码算法下性能

图10 (4 096,2 867)极化码不同译码算法下性能

4 结 语

本文基于原SCAN算法，通过改变左向LLR值和右向LLR值的更新时序提出了进一步降低译码复杂度和空间复杂度的软输出译码算法。与原SC译码算法相比，提出的算法可减少译码过程中浮点运算量，并能够减少因子图中为每列节点分配的存储空间，同时具有更快的收敛速度，是一种能更好的为磁记录等应用场景提供软信息的有效译码算法。

[1] Arikan E. Channel polarization: a method for constructing capacity achieving codes for symmetric binary-input memoryless channels[J]. IEEE Transactions Information Theory, 2009, 55(77): 3051-3073.

[2] Tal I, Vardy A. List decoding of polar codes[J]. IEEE Transactions Information Theory, 2015, 61(5):2213-2226.

[3] Niu K, Chen K. Stack decoding of polar codes[J]. Electronics Letters, 2012, 48(12): 695-697.

[4] Li B, Shen H, Tse D. An adaptive successive cancellation list decoder for polar codes with cyclic redundancy check[J]. IEEE Communications Letters, 2012, 16(12): 2044-2047.

[5] Fayyaz U U, Barry J R. Low-complexity soft-output decoding of polar codes[J]. IEEE Selected Areas Communications, 2014, 32(5): 958-966.

[6] Forney G D. Codes on graphs: normal realizations[J]. IEEE Transactions Information Theory, 2001, 47(2): 520-548.

[7] Eslami A, Pishro-Nik H. On finite-length performance of polar codes: stopping sets, error floor and concatenated design[J]. IEEE Transactions on Communications, 2013, 61(3): 919-929.

[8] Yuan B, Parhi K K. Early stopping criteria for energy-efficient low-latency belief-propagation polar code decoders[J]. IEEE Transactions Signal Processing, 2014, 62(24): 6496-6506.

[9] Arkan E. A performance comparison of polar codes and Reed-Muller codes[J]. IEEE Communications Letters, 2008, 12(6): 447-449.

[10] Zhang Y, Liu A, Pan X, et al. A modified belief propagation polar decoder[J]. IEEE Communications Letters, 2014, 18(7): 1091-1094.