高斯近似辅助下速率适配的缩短极化码算法

王留洋，陈海强*，孙友明，黎相成，方毅仁

(1.广西大学计算机与电子信息学院， 广西南宁，530004；2.广西多媒体通信与网络技术重点实验室， 广西南宁530004)

0 引言

Polar码是由ARIKAN[1-2]提出的一种新型信道编码技术，也是迄今为止首个可被严格证明在任意二进制输入离散无记忆对称信道(binary-input discrete memoryless channel, BI-DMC)中能够达到香农极限的纠错码。Polar码同时兼顾优秀的译码性能和较低的编译码复杂度，因此已被采纳为5G控制信道及广播信道的信道编码方案。Polar码的译码算法包括基于信道融合和分裂结构设计的串行抵消(successive cancellation, SC)译码及其列表式(successive cancellation list, SCL)译码算法[3-4]、带循环冗余校验的改进算法(CRC-aided successive cancellation list, CASCL)[5]以及基于置信传播(belief propagation, BP)的译码算法[6]等，它们在译码性能上各有优劣。

Polar码的码长受到其生成矩阵中基矩阵影响，使得通常情况下得到的码长只能为2的幂次方，需要一些特别的技术手段对Polar码进行改进和设计，以提高其适用范围。为了统一规范，3 GPP组织根据Polar码的码长、码率等因素，给出了三种Polar的速率适配方案，分别为重复(repetition)方案、打孔(puncture)方案[7]、缩短(shorten)方案[8]。在此基础上极化码的参数捷变技术[9]、基于分段凿孔的极化码级联方案[10]以及结合混合自动请求重传技术的极化码[11]也相继被提出，一定程度提高了Polar码的适用性。

笔者在文献[8]基础上提出了一种基于高斯近似辅助筛选凿孔位的构造算法，能够方便快捷地得到速率兼容的缩短凿孔极化码(rate-compatible shorten punctured polar, RCSPP)。通过引入高斯近似值辅助，将极化后性能较差的信道从生成矩阵中作为凿孔位删除并得到补充冻结集，在译码时将凿孔向量中传输冻结比特的信道信息传递给译码器，可以使得剩余子信道的误码率得到降低。本文算法分为三阶段：①由实际传输码字M构造码长为N的极化码的生成矩阵；②在生成矩阵中结合高斯近似信息及|Q(Np)|最小的原则依次选出(N-M)个凿孔位，并将其对应列号添加入凿孔向量Np中并得到补充冻结集；③在译码时，将凿孔向量中传输冻结比特的对数似然比(log likelihood ratio, LLR)接收值设置为无穷大(或无穷小)。仿真结果显示，本文算法相比于传统的准均匀凿孔(quasi-uniform puncturing, QUP)方案[7]及缩短方案[8]在误比特率(bit error rate, BER)方面均能获得译码增益，可作为Polar码的一种缩短凿孔方案参考。

1 系统模型

(1)

在实际通信应用中，传输的码长往往不是符合N=2n的Polar码，在下文中，令N表示Polar码的母码长度，M表示实际传输的Polar码长，K表示信息位的长度，则Polar码传输的实际码率R=K/M，令凿孔向量的大小|Np|=N-M，表示需要对母码N进行多少个位置的凿孔操作，通过控制凿孔向量Np的大小就能灵活调控Polar的实际码长、码率。凿孔的实质是将编码后的某些码字移除，被移除的码字将不会在实际信道中传输。缩短方案可以看成是凿孔法的一种，只不过在凿孔位置的选取上存在重大差异。通常凿孔方案下，接收端并不知道凿孔比特位置传输的信息，因此在译码开始前，译码器通常将这些比特对应位置的LLR值设置为0，但是在缩短方案下选取的凿孔位置必须对应冻结比特位置，从而在译码时译码器对这些凿孔位置上的先验信息是已知的(其LLR值设置为无穷大值或者无穷小值)，因此可以降低子信道的错误概率。

2 基于高斯近似辅助筛选凿孔位的缩短算法

信道极化后的最差的子信道会对Polar码的误码性能产生重要影响，因此在凿孔时，如何制定策略，将最差的子信道选入到凿孔位中是提高速率适配的Polar码性能的关键问题。传统缩短凿孔方案[8]并没有针对这个问题作出改善，其构造过程是直接将生成矩阵GN的后|Np|行和对应的列删除，并将码长为N的Polar码的最后|Np|位设为冻结比特，从而得到码长为M的缩短凿孔Polar码。本文利用文献[8]的原理，在生成矩阵GN中逐个选取行和列进行删除，直到删除的数量达到|Np|。不一样的是，本文在凿孔策略中引入了信道高斯近似值的辅助，通过信道高斯近似值的辅助可以将选入凿孔向量的列所对应的较差的子信道添加入冻结集中，在一定程度上可提升所得到的凿孔Polar码的性能。

2.1 高斯近似辅助参数计算

高斯近似法[12]是Polar码中用来对极化后信道的可靠性估计的计算方法。相比与密度进化法[13]，使用高斯近似法不仅可以降低计算复杂度，同时在加性高斯白噪声(additive white gaussian noise, AWGN)信道下也能得到满足要求的精度。假设在信道中发送全零码字，并采用BPSK调制形式,码字中的映射关系则为1→-1，0→1。则接收端接收信号的LLR计算公式如下：

(2)

f(x)=f(-x)ex。

(3)

(4)

其中φ-1(x)为φ(x)的反函数，φ(x)的函数表达式为:

(5)

(6)

其中函数Q(x)为余补误差函数，其表达式定义如下：

(7)

2.2 缩短算法原理

在这一小节中，笔者将阐述基于高斯近似辅助筛选凿孔位算法的原理，通过这种算法可以确保选取的凿孔位是由冻结位组成并在译码时保证译码器对这些凿孔位上的先验信息是已知的。

令F表示Polar码中冻结位信息的集合，集合中存放了冻结对应的信息，令gi表示Polar码生成矩阵GN的第i列，其中i=1,2…,N。令Q(gi)表示生成矩阵第gi列中“1”的位置信息。以码长为4的Polar码为例，其生成矩阵为：

(8)

生成矩阵中第2列为g2=(0,1,0,1)T，其列中对应“1”的位置信息为Q(g2)={3,4}。为了确保选取的凿孔比特信息ci=ugi被译码器所知，冻结集F中应包含所有gi列中“1”的位置信息，即满足以下条件：

Q(gi)⊆F。

(9)

可以直观地推导出这个条件，令uQ(gi)表示Q(gi)中的信息比特位置，而码字信息ci仅仅受到uQ(gi)中信息的影响，当uQ(gi)中的信息全部属于冻结比特时，在译码时就可以将信息传递给译码器，表明该比特信息是凿孔比特的同时有属于冻结比特。

实际应用中为了构造码长为M的Polar码，本文需要选取|Np|=(N-M)个凿孔比特，令Q(Np)为补充冻结集，由上述原理可知，当i∈Np时，可以由式(9)推出：

(10)

当然由于受到Np取值范围的限制，补充冻结集Q(Np)中包含“1”的位置信息的数量也存在一个下界即：

|Q(Np)|≥|Np|=N-M。

(11)

可通过Polar码生成矩阵的结构关系证明，由于生成矩阵GN=BNF⊗n，其中F⊗n为一个下三角矩阵，并且满足对角线上的元素均为“1”，而BN仅为反序排序置换矩阵，只影响生成矩阵中列的排序，并不影响矩阵列的构造，当选取F⊗n矩阵中的最后(N-M)列作为凿孔向量时，此时|Q(Np)|的数量最小，且满足当i∈Np时，i∈Q(Np)。

2.3 基于高斯近似辅助的缩短凿孔算法

上述传统的缩短算法[8]，其选取凿孔向量Np的补充冻结集Q(Np)，并不是通过信道的可靠度来选取的，仅利用了|Q(Np)|最小的原则，一些好的极化信道可能会被选入补充冻结集中，从而影响的性能。本文算法是在信道的高斯近似值的辅助及|Q(Np)|最小的原则两个限制条件下在Polar码的生成矩阵中选取凿孔向量Np及补充冻结集Q(Np)，可以在满足|Q(Np)|最小的原则的条件下，尽量将“差”的极化信道选取到冻结集中。仿真发现，基于这种方法，可获得更好的性能。

基于高斯近似辅助筛选凿孔位的缩短算法步骤如下：

输入：实际传输码长M，信道参数σ2；

Step 3:当i=1:N-M时，执行以下步骤：

Step 4:计算生成矩阵GN中每一列的列重，记录列重为1的列号gi和数量n；

Step 5:当n=1时，将该列列号gi添加入凿孔向量Np中并将Q(gi)添加入补充冻结集Q(Np)中；

Step 6:删除GN中列号为gi的列及Q(gi)中1位置信息对应的行(对应n=1)；

Step 7:当n>1时，判断n个列的Pe(Q(gi))的大小，将Pe(Q(gi))最大的列的列号gi添加入凿孔向量Np中并将Q(gi)添加入补充冻结集Q(Np)中；

Step 8:删除GN中列号为gi的列及Q(gi)中1位置信息对应的行(对应n>1)；

输出：得到凿孔向量Np及补充冻结集Q(Np)。

(12)

需要挑选|Np|=N-M=3个凿孔位添加入凿孔向量Np中，使用本文提出的算法，第一步遍历生成矩阵G8的列重，只有第8列的列重为1，将g8添加入凿孔向量Np中，将Q(g8)添加入补充冻结集Q(Np)中，并在生成矩阵G8删除第8列及其对应的行；第二步遍历剩余生成矩阵G8的列重，发现有3列的列重为1，即4,6,7，判断其对应列Pe(Q(gi))的大小，发现Pe(Q(g7))最大，因此将g7添加入凿孔向量Np中，将Q(g7)添加入补充冻结集Q(Np)中，并在剩余生成矩阵G8删除第7列及其对应的行；第三步遍历剩余生成矩阵G8的列重，发现有2列的列重为1，即4,6,判断其对应列Pe(Q(gi))的大小，发现Pe(Q(g6))最大，将g6添加入凿孔向量Np中，将Q(g6)添加入补充冻结集Q(Np)中，并在生成矩阵G8删除第6列及其对应的行；到此可以得出凿孔向量Np=[6,7,8]，补充冻结集Q(Np)=[4,6,8]。使用本文算法选出凿孔向量Np及补充冻结集Q(Np)后，再使用高斯近似辅助值选出剩余的冻结位和信息位，在编码后使用凿孔向量Np进行穿刺凿孔，最后在译码时根据冻结位设置的传输值“0”(或“1”)将相应的凿孔位的LLR接收值设置为无穷大值(或者无穷小)即可。

3 性能仿真与分析

本节对提出的基于高斯近似辅助筛选凿孔位的构造算法，在简单的BPSK调制和加性高斯白噪声信道(AWGN)下进行性能仿真。选取Polar母码码长N=1 024，RCSPP码长M=896，码率R=3/4,信息比特位K=672，凿孔向量大小|Np|=N-M=128。译码方法使用SC算法，仿真的总帧数为Ftotal=106。实验仿真的停止条件为错误总帧数大于100帧或者发送帧数达到Ftotal。

图1给出了准均匀凿孔(QUP)方案[7]使用传统缩短算法[8]以及本文提出的构造算法等三种算法下RCSPP码的误码率性能。从图1中可以看出，使用本文算法构造的速率兼容的缩短凿孔极化码的误比特率性能最佳。在BER=10-5时，本文算法相比于文献[8]在误比特率(BER)方面能够获得0.1 dB的性能增益，相比于文献[7]能够获得0.3 dB的性能增益。

图1 不同构造算法下RCSPP码的误码率(BER)性能Fig.1 BER performance of RCSPP code under different construction algorithms

4 结论

本文基于缩短凿孔Polar码，提出一种基于高斯近似辅助筛选凿孔位的构造算法。相比于文献[8]，其在选取凿孔向量和补充冻结集时，没有采用信道的可靠度辅助可能将一些好的极化信道可能会被选入补充冻结集中，影响译码性能。本文算法是在信道的高斯近似值的辅助及|Q(Np)|最小的原则两个限制条件下在Polar码的生成矩阵中选取凿孔向量及补充冻结集，可以在满足|Q(Np)|最小的原则的条件下的同时尽量将坏的极化信道选取到冻结集中，可以对补充冻结集进行改善，从而提升性能。仿真结果表明，基于本文算法得到的RCSPP码相比于准均匀凿孔(QUP)方案[7]及传统缩短算法[8]在误比特率(BER)方面有一定的性能增益。