1 引言
2009年,Arikan在其论文中开创性的提出了Polar码[1],这是迄今为止,唯一可以理论上证明可达到任意二进制离散无记忆对称信道容量,并且具有低编译码复杂度的新型高效信道编码技术,因此,Polar码成为近年来最具吸引力的信道编码之一[2- 4]。虽然Polar码在码长趋于无限大时能够达到香农限,但在实际应用中有限码长的Polar码的性能并不理想。如何提高有限码长下的Polar码性能是当前的研究热点,需要从Polar码的构造与译码算法两个方面进行努力。Arikan提出的逐次消除(Successive Cancellation, SC)译码算法[1]对输入的比特进行单路径连续译码,是一种低复杂度的Polar码译码算法。此后,Tal 等人提出了逐次消除列表(Successive Cancellation List, SCL)译码算法[5],该算法在译码的过程中同时保留多条译码路径,用以增加正确译码的可能性。另外,Polar码与不同编码技术的级联方案来改进Polar码的性能,也达到了很好的效果。Guo等人用置信传播(Belief Propagation, BP)译码算法对LDPC码与Polar码级联方案进行了研究,研究表明,该级联码相对于传统的BP译码具有 0.3 dB的增益[6]。Niu等人提出了CRC辅助的Polar码[7],译码时通过CRC校验选择合适的译码路径,Chen等人对CRC的最佳设计进行了探究[8],极大的提高了其纠错性能。Wang等人提出的PC辅助的Polar码[9],在特定的信噪比下使用蒙特卡洛法得到比特信道的错误概率,性能提高的同时导致构造的复杂度严重增加。在研究者的不懈努力下,研究表明,即使与Turbo码和LDPC码相比,Polar码也展示出极大的竞争性[10-12]。Polar码凭借着优异的性能,以及其较低的编译码复杂度,Polar码成功入选5G标准,作为增强移动宽带场景控制信道的编码方案[13]。
在5G标准中,华为公司提出的极化权重(Polarization Weight, PW)方法[14]是一种非常优秀的构造实现方案,该方法的构造方式与具体的信道无关,相对于传统的密度进化[15]和高斯近似[16]方法是一种独立于信噪比、复杂度低的构造方法。CRC辅助的Polar码是学术界研究最成熟的Polar码编码方式,该编码方式被纳入5G控制信道编码方案。CRC辅助的Polar码在译码时相对于SCL译码算法只是添加了CRC校验,针对其译码的过程中没有任何辅助措施来帮助路径度量值进行正确的修剪译码路径,本文使用PW方法进行Polar码的构造,设计出一种新型的级联编码方案,在译码的过程中利用PC比特辅助路径度量值进行译码路径的修剪,用以保证路径选择的可靠性,进而提高其纠错性能,奇偶校验操作简单,在复杂度上没有明显增减。最后基于加性高斯白噪声信道模型,采用BPSK调制对不同的码长、码率的新型级联Polar码进行了实验仿真,仿真结果证明新型级联Polar码具有优异的性能。
2 Polar码的基本原理
2.1 编码原理
Polar码的核心是信道极化,信道极化是指将二进制输入离散无记忆信道W的N个独立的时隙进行相关变换,得到一组前后具有相关性的比特信道,随着N的增大,N个比特信道中一部分会变成信道容量趋于0的纯噪声信道,另一部分变成信道容量趋于1的无噪信道[1]。因此,在极化信道上编码是非常简单的,只需要选择信道容量趋于1的比特信道用来发送信息uA,信道容量趋于0的比特信道发送冻结比特uAC(即收发双方均已知的信息,通常设置为0),即可实现数据的可靠性传输。
Polar码是一种线性分组码,对于码长为N,N=2n,信息长度为K的Polar码编码,设A为{1,2,3,…,N}的一个子集,|A|=K,称A为信息位集,是挑选出K个信道容量较高的比特信道序号。在编码时,首先要将信息比特与冻结比特进行比特混合,将信息比特放置在信息位,其他位置放置冻结比特,得到长度为N混合比特序列
...,uN),然后,
乘以N×N的生成矩阵GN得到编码后的生成序列
...,xN)[1],即:
(1)
GN为N阶生成矩阵,生成矩阵GN表示为:
GN=BNF⊗n
(2)
(2)式中F⊗n表示F的n次克罗内克积,其中
为比特反转矩阵其构造方法如下:
BN=RN(I2⊗BN/2)
(3)
I2、B2均为单位矩阵,RN称为置换矩阵,功能是将奇序元素排列在前,偶序元素排列在后,如:(s1,s2,s3,...,sN)→(s1,s3,s5,...,sN-1,s2,s4,s6,...,sN)。
如:当码长N=4时,G4=B4F⊗2=R4(I2⊗
2.2 译码原理
Polar码的SC译码算法针对接收端的信道输出序列
...,yN)进行译码,得到译码估计序列
...,
代表第i个译码比特,当
是冻结比特位时,可直接得到
否则需要计算对数似然比通过判决函数进行计算:
(4)
对数似然比(Log Likelihood Radio, LLR)的计算公式为式(5),其中,
为已经译码结束的前i-1个译码比特。
(5)
SC译码算法采用单路径局部最优译码算法,当码长为有限长时,性能并不理想,如果前面的译码比特出现错误,将会产生错误传递。Tal等人在SC译码算法的基础上,提出了SCL译码算法[5],设定正整数L, 表示路径搜索宽度,即在译码的过程中可以同时保留L条译码路径,以提高正确译码的可能性。L值越大,Polar码的译码性能越好,越接近最大似然译码的性能限,复杂度也相应的增加。特别地,L=1时,SCL译码算法就是SC译码算法。
3 新型级联Polar码方案
新型级联Polar码的整体方案如图1所示,假设码长为N,信息比特长度为K,CRC校验比特长度为Q,PC校验比特长度为S。编码器由CRC编码器、PC编码器、Polar码编码器三部分组成,译码器是基于SCL译码算法,同时双校验技术加以辅助挑选正确的译码路径。新型级联Polar码在编码时,首先对要发送的信息比特进行CRC编码,本设计中采用长度为6的CRC校验;然后进行PC编码,本设计中采用偶校验编码;最后进行Polar码编码。在译码的过程中,是基于SCL译码算法,通过PC比特辅助路径度量值进行译码路径的修剪,最后选择能通过CRC校验且路径度量值较大的路径译码序列作为最终译码结果。其实,CRC辅助的Polar码的译码和SCL译码原理一样,仅依靠路径度量值进行译码路径的修剪,在译码的过程中没有任何辅助措施帮助路径度量值进行修剪路径,只是添加了CRC校验,用于最后从L条译码路径中挑选出最佳译码路径进行输出。新型级联Polar码新颖之处正是弥补了CRC辅助的Polar码这一缺陷,所添加的PC比特辅助路径度量值进行译码路径的修剪,这是因为PC校验比特的译码是通过前面已经完成译码的比特信息经过奇偶校验运算关系得到,并非通过路径度量值进行译码。若PC比特前的信息比特译码错误,就会导致校验比特译码错误,从而产生对路径度量值的影响使得路径度量值变小,因此在后续的译码过程中会更加容易的挑选出正确的译码路径,提高了其译码可靠性。由于奇偶校验的简单且易于操作,编译码复杂度也没有明显增加。
图1 新型级联Polar码的整体方案
Fig.1 Novel cascaded Polar codes overall scheme
3.1 新型级联Polar码的编码
3.1.1 新型级联Polar码的构造
Polar码的构造就是通过特定的规则进行挑选比特信道,是Polar码编码之前的一个重要环节。PW构造方法基于Polar码生成矩阵的固定行重提出的,用以估计比特信道的可靠性[14],编码时正是通过PW方法挑选出来的可靠性高的比特信道进行传输信息。首先,将比特信道的序号i二进制表示为i
Bn-1Bn-2…B0,其中n=log2N,计算比特信道的重量值Wi,重量计算公式为:
*
(6)
依次计算W0,W1,W2,…,WN-1,并按照WI0≤WI1≤WI2≤…≤WIN-1形式进行升序排序,取其下标得到比特信道序号序列
即为比特信道的可靠性排序,排序的位置越靠后,该比特信道的可靠性就越高。例如:当码长N=16时,n=log2 16=4,当i=5(i0101)时,
新型级联Polar码在构造时,首先,根据上述PW方法得到比特信道的可靠性排序,然后挑选排序靠后的K+Q个可靠性较高的比特信道用来传输信息比特和CRC校验比特,最后从剩下的比特信道中挑选S个可靠性较高的比特信道用来传输PC校验比特,剩余所有的比特信道作为冻结比特传输信道使用。该方法既可以保证信息比特以及CRC校验比特用可靠性高的比特信道进行传输,以保证信息传输的可靠性,PC校验比特不会占用传送信息比特、CRC校验比特的比特信道的同时,还能辅助路径度量值正确译码的作用,这是新型级联Polar码性能优异的根本原因。
3.1.2 新型级联Polar码的编码方法
新型级联Polar码的编码过程大致分为CRC编码、PC编码、比特混合以及Polar码编码四个部分,具体如下:
(1)CRC编码: 信息比特长度为K信息比特序列
经过CRC编码器进行编码,产生Q位CRC校验比特附加在信息比特序列尾部得到生成序列
(2)PC编码:
作为PC编码器的输入,进行PC编码(本文使用偶校验编码)得到PC编码器编码序列
其中,PC编码具体流程图如图2所示;
(3)比特混合: 根据新型级联Polar码的设计方法,将
序列与冻结比特uAc进行比特混合,得到长度为N混合比特序列...,uN);
(4)Polar码编码:乘以N×N的生成矩阵GN,即
编码完成。
图2 PC编码流程图
Fig.2 The pipeline of PC encoding
3.2 新型级联Polar码的译码
新型级联Polar码译码算法是一种双校验技术辅助的SCL译码算法。该算法弥补了CRC辅助的Polar码在译码的过程中仅依靠路径度量值进行译码路径的修剪,没有任何辅助措施帮助路径度量值进行修剪路径的不足。新型级联Polar码正是通过在译码的过程中引入PC比特,PC校验比特的译码是根据已经成功译码得到的信息比特或者CRC校验比特异或运算得到,相当于一类动态的冻结比特。PC校验比特能辅助路径度量值在译码的过程中进行路径选择,这是因为在译码过程中,假如ui是PC校验比特,当其前面的信息比特或者CRC校验比特译码出现错误时,根据奇偶校验关系,PC校验比特会发生错误,从而导致该条译码路径的路径度量值变小,因此会更加容易的挑选出正确的译码路径,从而提高纠错性能。当L条路径均译码结束,需要进行CRC校验,选择最佳的译码路径的译码结果进行输出。新型级联Polar码的译码算法流程图如图3所示。
图3 新型级联Polar码的译码算法流程图
Fig.3 The pipeline of new cascaded Polar codes decoding algorithm
4 仿真结果及性能分析
本文基于加性高斯白噪声信道模型,采用BPSK调制方式,搜索路径宽度L=32,对新型级联Polar码的性能进行仿真,通过计算误码率BER来分析Polar码的性能。图4是码长分别为256,码率为1/6、1/3、1/2时,新型级联Polar码与SC Polar码性能仿真图;图5为码长分别是128、256、512,码率为1/3时,新型级联Polar码与CRC辅助的Polar码性能对比仿真图。
如图4和图5所示,显然,在相同码长、码率的情况下,相对于SC Polar码、CRC辅助的Polar码,新型级联Polar码均展现出其优异的性能。当误码率为10-3,码长为256,码率为1/6时,新型级联Polar码相对于SC Polar码的增益高达约1.5 dB;当误码率为10-6时,码率为1/3时,码长为512的新型级联Polar码比同等码长的CRC辅助的Polar码有0.12 dB的增益。这均表明新型级联Polar码采用双校验技术辅助的SCL译码算法达到了很好的效果,多路径译码的同时以双校验技术进行辅助译码。特别地,新型级联Polar码在译码的过程中弥补了CRC辅助的Polar码仅依靠路径度量值进行译码路径的删剪的这一缺陷,添加了PC比特辅助路径度量值进行译码路径的修剪,用以保证路径选择的可靠性。相对于CRC辅助的Polar码,由于PC校验简单易于操作,其复杂度低,新型级联Polar码在复杂度方面几乎没有增加。
图4 新型级联Polar码与SC Polar码性能对比
Fig.4 Performance comparison between novel cascaded ar codes and SC Polar codes
图5 新型级联Polar码与CRC辅助的Polar码性能对比
Fig.5 Performance comparison between novel cascaded Polar codes and CRC-Polar codes
5 结论
为了进一步提高Polar码在有限码长下的性能,本文提出了一种新型级联Polar码,通过校验技术辅助Polar码进行译码,其中CRC码、PC码作为新型级联Polar码的外码,Polar码作为其内码。在Polar码的构造方面,使用构造上不依赖信噪比且复杂度低的PW构造方法。在译码方面,基于SCL译码算法,加入的PC校验比特能辅助路径度量值在译码过程中进行路径的修剪,CRC校验用于从全部候选译码路径中挑选最优的译码序列并输出。最后对提出的新型级联Polar码进行仿真实验,结果表明新型级联Polar码具有出色的纠错性能,从而为该类新科技在未来的第五代移动通信应用中创造基础条件。
[1] Arikan E. Channel polarization: a method for constructing capacity-achieving codes for symmetric binary-input memoryless channels[J]. IEEE Transactions on Information Theory, 2009, 55(7): 3051-3073.
[2] Hong S N, Hui D, Maric I, et al. Capacity-achieving rate-compatible polar codes[J]. IEEE Transactions on Information Theory, 2017, 63(12): 7620-7632.
[3] Bioglio V, Land I. Polar-code construction of Golay codes[J]. IEEE Communication Letters, 2018, 22(3): 466- 469.
[4] 张孝甜, 赵生妹, 郑宝玉. 无线信道中的Polar码协商[J]. 信号处理, 2018, 34(7): 793-798.
Zhang Xiaotian, Zhao Shengmei, Zheng Baoyu. Key reconciliation using polar code in wireless channel[J]. Journal of Signal Processing, 2018, 34(7): 793-798.(in Chinese)
[5] Tal I, Vardy A. List decoding of polar codes[J]. IEEE Transactions on Information Theory, 2015, 61(5): 2213-2226.
[6] Guo Jing, Qin Minghai, Fabregas A G I, et al. Enhanced belief propagation decoding of polar codes through concatenation[C]∥International Symposium on Information Theory. IEEE, 2014: 2987-2991.
[7] Niu Kai, Chen Kai. CRC-aided decoding of polar codes[J]. IEEE Communications Letters, 2012, 16(10): 1668-1671.
[8] Chen Fengyi, Liu Aijun, Zhang Yingxian, et al. CRC location design for polar codes[J]. IEEE Communications Letters, 2018, 22(11): 2202-2205.
[9] Wang Tao, Qu Daiming, Jiang Tao. Parity-check-concatenated polar codes[J]. IEEE Communications Letters, 2016, 20(12): 2342-2345.
[10] Hui D, Sandberg S, Blankenshi Y, et al. Channel coding in 5G new radio: a tutorial overview and performance comparison with 4G LTE[J]. IEEE Vehicular Technology Magazine, 2018, 13(4): 60- 69.
[11] Sharma A, Salim M, Sharma A, et al. Polar code: the channel code contender for 5G scenarios[C]∥International Conference on Computer. IEEE, 2017: 676- 682.
[12] Trifonov P, Miloslavskaya V. Polar subcodes[J]. IEEE Journal on Selected Areas in Communications, 2016, 34(2): 254-266.
[13] 3GPP.3GPP TS 38.212 v15.0.0-2017, Multiplexing and channel coding (Release 15)[S]. Valbonne: 3GPP, 2017.
[14] Huawei, HiSilicon. Details of the polar code design(R1-1611254)[EB/OL]. https:∥www.3gpp.org/ftp/tsg_ran/ WG1_RL1/TSGR1_87/Docs/, 2016-11- 03.
[15] Mori R, Tanaka T. Performance of polar codes with the construction using density evolution[J]. IEEE Communications Letters, 2009, 13(7): 519-521.
[16] Trifonov P. Efficient design and decoding of polar codes[J]. IEEE Transactions on Communications, 2012, 60(11): 3221-3227.
