一种基于串行消除列表的多比特翻转译码算法.pdf

第43卷第3期2023年5月DOI:10.13954/ki.hdu.2023.03.008杭州电子科技大学学报（自然科学版）Journal of Hangzhou Dianzi University(Natural Sciences)Vol.43 No.3May2023一种基于串行消除列表的多比特翻转译码算法张旭，刘顺兰，李正杰（杭州电子科技大学电子信息学院，浙江杭州310 0 18)摘要：极化码拥有很好的编译码性能，已成为5G控制信道的标准编码方案，但中短码时，其性能不够优异。为此，提出一种基于串行消除列表的多比特翻转译码算法。首先，用串行抵消译码算法进行译码，选出对数似然比绝对值较小即可靠性较小的信息位索引集合；然后，对索引集合中对应的信息位进行多比特翻转；最后，对所有信息进行串行抵消列表译码，得到信息源序列的估计值。仿真结果表明，在高斯信道下，码长为512，码率为0.5时，提出算法的误块率为10-3时，性能优于其他同类算法。关键词：极化码；串行抵消译码算法；多比特翻转；串行抵消列表译码算法中图分类号：TN911.22文献标志码：A文章编号：10 0 1-9 146（2 0 2 3)0 3-0 0 55-0 60引言极化码 1是首个被证明可以达到信道容量的纠错码，具有较低的编译码复杂度，被第三代合作伙伴计划（3rdGenerationPartnershipProject，3G PP）确定为5GeMBB场景下控制信道编码方案，成功人选5G标准。极化码的码长越趋近于无穷，其极化效果越好。但是，在中短码长情况下，极化效果较差。为了提高极化码的纠错效果，Arikenl提出一种串行抵消译码（Successive Cancellation，SC)算法，但在有限码长情况下，性能并不理想；于是，Tal等L2提出一种串行抵消列表译码（SuccessiveCancellationListDecoding,SCL)算法，通过增加列表数量来扩大译码的路径，提升了译码性能。SCL译码算法是目前最常用的译码方法。为了进一步降低极化码的误码率，提高极化码的译码性能，Niu等 3 提出一种循环允余校验(Cyclic Redundancy Check,CRC)级联Polar的 SCL译码（CRC Aided SCL,CA-SCL)算法，在SCL的译码列表中挑选出正确的译码结果，保证译码的准确性;Elkelesh等 4 设计了一种置信传播列表译码器,其译码性能与常用的SCL译码器相似。文献 5 将比特翻转原理应用到极化码的SC译码算法中，提出一种串行抵消翻转（Successive CancellationFilp，SCF)译码算法，在SC译码错误时，通过比特翻转进行矫正，但只能纠正1位错误。于是，动态SCF算法 6 、分段SCF算法 7-8 被相继提出。同样，SCL算法也可应用比特翻转，文献 9 提出一种串行抵消列表比特翻转（SuccessiveCancellation Listbit-Flip，SC LF)译码算法，性能得到较大提升，但也只能纠正1位错误。为了更好地提升误块率性能，崔建明等 10 1结合比特翻转与分段原理，提出一种分段CRC辅助极化码SCL比特翻转译码算法；袁建国等 11 为了兼顾译码算法的性能与复杂度，提出一种快速串行抵消列表翻转（Fast SuccessiveCancellationListFlip，FSCLF)译码算法，通过引人信息比特结点和单奇偶校验（Single-Parity-Check，SPC)结点来降低译码复杂度，提高了译码性能。受 SCF译码算法的启发，本文结合SCF译码与SCL译码，提出一种基于串行消除列表的多比特翻转译码算法。收稿日期：2 0 2 2-0 4-0 6基金项目：国家自然科学基金资助项目（NU1809201）；浙江省自然科学基金资助项目（LY010013）作者简介：张旭（19 9 7 一），男，研究方向：极化码编译。E-mail：159 9 8 42 7 17 q q.c o m。通信作者：刘顺兰，教授，研究方向：信息与信号处理、无线通信。E-mail:。56杭州电子科技大学学报（自然科学版）2023年1极化码原理1.1极化码极化码是一种运用信道极化理论的信道编码方式，与其他信道编码技术最大的不同在于极化码可以进行信道极化，并利用信道极化产生的极化现象进行信息传输。当极化码的码长不断增大并趋于无穷时，其各个子信道逐渐呈现两极分化现象，一部分信道容量趋近于1，另一部分趋近于0。在传输信息时，可以选择可靠度较高即信道容量趋近于1的信道进行信息传输，剩下的信道作为冻结位。极化码可表示为（N,K，A，u），N表示极化码的码长，K表示信息位的长度，A表示信息位比特的集合，其补集A表示固定子信道的索引集合，其上标c为补集符号，uA表示冻结比特序列 12 ，根据极化码的编码原理，编码后的码字为：aY=uiGN式中，G为极化码的生成矩阵，G=BF，其中F表示克罗内克积，F=的位反转置换矩阵；u=（u i，u 2，u s，u n）为信源序列，由u和u表示，其中ua为信息比特序列，通常设为0。可将式(1)改写为：(2)式中,G（A)为由A中元素对应的行构成的G的子矩阵,G（A）为由A中元素对应的行构成的G的子矩阵，表示模2 加。在得到码字ai后，对进行二进制相移键控（BinaryPhase ShiftKeying，BPSK)调制，再经信道W的传输，在信道的输出端接收到=（y,，），y 经过译码后得到u的估计值=（ui，u2,usin）,u;为第i个译码比特。1.2SC 和 SCL 译码SC译码是最基本译码算法。译码过程中，如果u；是1个冻结比特，则直接译码=ui，如果u；是1个信息比特，先计算每个信道的对数似然比（LogLikelihoodRadio，LLR），定义为：(3)W(y,ui-1|1)再根据LLR值对信息位进行硬判决，得到：0iEA且L(y,ui-1)0u;=人1iEA且L(yN,ui-1)0iEAc式(3)可表示为：Li-1(y,a-2)=(L%e(y a*a),L2(y/2+1 i),2i2式中，.2 和i-分别为i的奇数位估计序列和偶数位估计序列。令=L/2（y/2,i-2 i-2),b=L2（y N/2+1,i-),则式(5)和式(6)表示如下:(1+ea+6ea+eL&(yN,ui-1)=g(a,b,u,)=(-1)a+b式中，u,E(0,1)。SC算法根据式（7)和式（8)计算得到每个节点的LLR后，再根据式（4)对每个信息比特进行判决，得到译码结果。但是，这种方法是串行译码，容易出现错误传播。在SC算法基础上，SCL译码算法同时保留L条SC译码路径，进行并行译码，每条路径都是根据路径度量(PathMetric，PM)13 筛选得到的，其表达式为：(1)B为一个NXNCN=uAGN(A)uAGN(A)W(yi,ui-lo)L(yN,ui-l)=lnL&i-1)(yi,azi-2)=f(a,b)=ln(4)(5)(6)(7)(8)第3期式中，l为译码器的第1条路径（1 lL），s 门为第1条译码路径中第k个比特估计值,L为第1条路径的对数似然比。SCL算法只保留P最小的L条译码路径。1.3SCF译码在SC译码过程中，受信道中噪声或之前错误判决的影响，编码序列容易产生错误，第1个错误判决比特往往由信道噪声引起，所以，重新判断译码错误的判决位尤为重要。为此，Afisiadis等5提出了串行抵消翻转SCF译码算法，其算法流程如图1所示，其中uV为每次重新进行SC译码后输出的结果。图中模块“选出判决出错位置集合”的方法如下：比较SC译码得到的对数似然比绝对值V，其值越小，对应的节点值越不可靠。在第1次SC译码失败后，把得到的V值进行升序排列,取前T个值作为出错位置集合，其中T为翻转比特的个数。张旭，等：一种基于串行消除列表的多比特翻转译码算法PpM=In(1+e-(-2a,)L%)i E(1,2,N)k-157(9)SC译码YCRC校验NY译码成功，输出u选出判决出错位置集合J在集合中选出一位进行翻转，再次进行SC译码YNCRC校验NiT译码失败图1SCF译码算法流程图2基于串行消除列表的多比特翻转译码算法虽然SCF译码算法的性能优于SC译码算法，但每次只能对其中1位不可靠信息位进行翻转，不能进行多位翻转，译码性能提升有限。所以，在SCF译码算法的基础上,本文提出一种基于串行消除列表的多比特翻转译码算法，在编码时，将极化码作为内码进行编码，CRC码作为外码进行校验，极化码编码采用高斯构造方法。本文算法的译码流程如图2 所示。(1)对信道输出端接收到的信号yY进行SC译码，得到每个信息位码字的对数似然比绝对值V。（2)对SC译码后的序列进行CRC校验，通过则输出译码结果V，否则执行下一步。（3)对每个码字的V值进行升序排列，并取前T个最小V值所对应的信息位索引作为翻转集合，其中T表示选取翻转集合元素的个数，=（w1，2，W）表示翻转集合，w;表示翻转集合中第i位元素。(4)对所有信息位进行SCL译码,并判断L条译码路径中是否有路径通过CRC校验，如果有则结束译码，否则选取翻转集合中下一位元素，重新进行SCL译码，直到有路径通过校验；如果T次尝试均不成功，则执行下一步。58杭州电子科技大学学报（自然科学版）2023年SC译码对SC译码得到的NCRC校验LLR的绝对值进行升序排列Y译码成功输出(5)从=（1，2，WT)中依次选取V值较小的2 位进行翻转，再进行SCL译码，译码结果若未通过CRC校验，则重新选取翻转位进行SCL译码。若通过校验，则输出译码结果。当所有尝试均未通过CRC校验，则译码失败。3仿真实验与分析在MATLAB平台上，加性高斯白噪声（AdditiveWhite GaussianNoise，A WG N）信道下，采用BPSK调制方式进行仿真实验。极化码的码率为0.5，蒙特卡罗仿真次数为10 0 0 0 次。码长N为512,SCL的列表宽度L为4，选取不同翻转集合个数T，采用本文提出的基于串行消除列表的多比特翻转译码算法进行仿真，得到误块率(Block ErrorRate,BLER)如图3所示。从图3可以看出，在相同信噪比情况下，T值越大，误块率越小。当T为码长512 的1/8，即T=64时，误块率的提升几乎达到极限，说明T对译码性能的提升有一定的影响。码长N为512，码率为0.5，T为6 4，选取不同列表宽度L，采用本文算法进行仿真，得到误块率如图4所示。10010-110-2选取1位元素选取前T位作进行翻转并为翻转集合0进行SCL译码Y译码失败图2 基于多比特翻转的串行消除列表译码算法流程.T4.-*.T8-T-16-G T=32冷-T=64一T-128NCRC校验YN所有元素都完成翻转10010-110-2YiTN依次选取2 位元素进行翻转并进行SCL译码NCRC校验Y.L=2*L=4-G L=8-L=1610-310-310-40.5图3不同T值下，本文算法的误块率从图4可以看出，随着L的增大，误块率随之变小。列表宽度L为4，翻转集合元素的个数T为8，选取不同码长N，采用本文算法进行仿真，得到误块率如图5所示。10-41.01.5信噪比/dB2.02.53.00.5图4不同L值下，本文算法的误块率1.01.5信噪比/dB2.02.53.0第3期从图5可以看出，随着码长N的增大，误块率随之变小，性能越来越优，当误块率为10-3时，相比于码长为2 56，本文算法在码长为512 时获得了大约0.1dB的增益。列表宽度L为4，翻转集合元素的个数T为码长的1/8，选取不同码长N，采用本文算法进行仿真，得到误块率如图6 所示。10010-1张旭，等：一种基于串行消除列表的多比特翻转译码算法-N=128N=256-*N=-51259100-N=512+N-128-*-N=25610-110-210-2米10-310-40.5图5不同N值下，本文算法的误块率从图6 可以看出，随着N的增加，误块率随之变小，当误块率为10-3时，相比于码长为2 56，码长为512时获得了大约0.2 dB的增益。码长N为512,列表宽度L为4，翻转集合元素的个数T为6 4时，分别采用本文算法、SC译码算法、SCL译码算法、文献5中SCF译码算法、文献9中SCLF译码算法、文献3中CA-SCL译码算法进行仿真，得到6 种算法的误块率如图7 所示。10-310-41.01.5信噪比/dB2.02.51003.00.5图6 不同N值且T为码长的1/8 下，本文算法的误块率1.01.5信噪比/dB2.02.53.010-1Q10-2+.SC译码10-3-GSCF译码T=64-SCL译码L-4SCLF译码L=4T=64本文建议方法L=4T-6410-40.5图7不同算法的误块率对比从图7 可以看出，当误块率为10-3时，本文算法的误块率最小，相较于SCF译码算法、SCL译码算法、CA-SCL译码算法、SCLF译码算法、SC译码算法分别获得了0.7 0 dB,0.90dB,0.65dB，0.6 0 d B，1.50 dB的增益。4结束语为了进一步提高极化码在中短码长下的译码性能，本文在SCF译码算法的基础上，提出一种基于串行消除列表的多比特翻转译码算法。当SC译码发生错误时，根据SC译码得到的对数似然比绝对值选出翻转集合，并对其进行多比特翻转。但是，本文只是在AWGN信道下进行了仿真实验，后续将在其他通信环境下展开进一步研究。1.01.5信噪比/dB2.02.53.03.560参考文献1J ARIKEN E.Channel polarization:a method for constructing capacity achieving codes for symmetric binary-inputmemoryless channelsJJ.IEEE Transactions on Information Theory,2009,55(7):3051-3073.2 TALI,VARDY A.List decoding of polar codesJJ.IEEE Transactions on Information Theory,2015,61(5):2213-2226.3J NIU K,CHEN K.CRC-aided decoding of polar codesLJJ.IEEE Communications Letters:a Publication of the IEEECommunications Society,2012,16(10):1668-1671.4 ELKELESH A,EBADA M,CAMMERER S,et al.Belief propagation list decoding of polar codesJJ.IEEECommunications Letters,2018,22(8):1536-1539.5J AFISIADIS O,BALATSOUKAS S A,BURG A P.A low-complexity improved successive cancellation decoder forpolar codesCJ/Asilomar Conference on Signals,Systems and Computers,Pacific Grove,CA,USA,2014:2116-2120.6J CHANDESRIS L,SAVIN V,DECLERCQ D.Dynamic-SCFlip decoding of polar codesJJ.IEEE Transactions onCommunications,2017,66(6):2333-2345.7 ERCAN F,CONDO C.Partitioned successive-cancellation flip decoding of polar codesC/IEEE InternationalConference on Communications(ICC),2018:1-6.8 FANG Y,LI J P,LV Y S.Improved segmented SC-flip decoding of polar codes based on gaussian approximationCJ/2019 4th International Conference on Smart and Sustainable Technologies,(Spli Tech).Split,Croatia,2019:1-5.9J YU Y R,PAN Z W,LIU N.Successive cancellation list bit-flip decoder for polar codesCJ/1oth InternationalConference on Wireless Communications and Signal Processing(WCSP),IEEE,Hangzhou,China,2018:1-6.10 崔建明，王庆祥，张小军，等.分段CRC辅助极化码SCL比特翻转译码算法J.现代电子技术，2 0 2 1，44（7)：6-10.11袁建国，王露，梁棚，等.一种基于比特翻转的极化码FSCLF译码算法J.半导体光电，2 0 2 1，42（2）：2 95-30 0.12 Dai L Y,Huang L,Bai Y H,et al.CRC-aided belief propagation with permutated graphs decoding of polar codesCJ/2020 IEEE 3rd International Conference on Electronic Information and Communication Technology(ICEICT).IEEE,Shenzhen,China,2020:445-448.13J BALATSOUKAS S A,BASTANI P M,BURG A.LLR-based successive cancellation list decoding of polar codesJ.IEEE Transactions on Signal Processing,2014,63(19):5165-5179.杭州电子科技大学学报（自然科学版）2023年A successive cancellation list decoding algorithm based on multi-bit flipZHANG Xu,LIU Shunlan,LI Zhengjie(School of Electronic Information,Hangzhou Dianzi University,Hangzhou Zhejiang 310018,China)Abstract:Polar codes have good coding and decoding performance and have become the standardcoding scheme for 5G control channels,but its performance is not excellent enough in short andmedium code.Therefore,a multi-bit flip decoding algorithm based on successive cancellation listdecoding is proposed.Firstly,use the successive cancellation decoding algorithm to decode.If thedecoding result passes the CRC check,the decoding is ended;otherwise,in the decoding process,theset of information bit indexes with a small log-likelihood ratio(which is of less reliability)is selected.Then,the corresponding information bits in the set are multi-bit flipped.Finally,all the informationis decoded by successive cancellation list decoding.The simulation results show that when the codelength is 512,the code rate is 0.5 in Gaussian channel and the block error rate is 10-3,our proposedalgorithm is better than other similar ones.Key words:polar codes;successive cancellation decoding algorithm;multi-bit flip;successive cancellation listdecoding algorithm