混合多核极化码指数的收敛性.pdf

Advances in Applied Mathematics 应用数学进展应用数学进展,2024,13(1),47-54 Published Online January 2024 in Hans.https:/www.hanspub.org/journal/aam https:/doi.org/10.12677/aam.2024.131006 文章引用文章引用:王彤,金小雨,杨卫华.混合多核极化码指数的收敛性J.应用数学进展,2024,13(1):47-54.DOI:10.12677/aam.2024.131006 混合多核极化码指数的收敛性混合多核极化码指数的收敛性 王王 彤，彤，金小雨，金小雨，杨卫华杨卫华*太原理工大学数学学院，山西 太原 收稿日期：2023年12月10日；录用日期：2024年1月5日；发布日期：2024年1月10日 摘摘 要要 混合多核极化码存在极化现象且有良好的极化性能。极化码对应的极化矩阵的指数是度量极化码性能的混合多核极化码存在极化现象且有良好的极化性能。极化码对应的极化矩阵的指数是度量极化码性能的重要指标，因此本文主要研究混合多核极化码的指数。本文将多核极化码部分距离的表达式进行拓展，重要指标，因此本文主要研究混合多核极化码的指数。本文将多核极化码部分距离的表达式进行拓展，得到混合多核极化码部分距离，根据极化码部分距离和指数的关系推导出了混合多核极化码指数的表达得到混合多核极化码部分距离，根据极化码部分距离和指数的关系推导出了混合多核极化码指数的表达式，即混合多核极化码指数可以表示为其组成矩阵的线性组合，并得到了混合多核极化码指数的上下界；式，即混合多核极化码指数可以表示为其组成矩阵的线性组合，并得到了混合多核极化码指数的上下界；然后基于混合多核极化码的极化现象，提出了一种特殊的混合多核极化码的矩阵选择规则，证明了在这然后基于混合多核极化码的极化现象，提出了一种特殊的混合多核极化码的矩阵选择规则，证明了在这种矩阵选择规则下产生的混合多核极化码的指数是收敛且与信道容量种矩阵选择规则下产生的混合多核极化码的指数是收敛且与信道容量相关；最后应用本文得出的定理，相关；最后应用本文得出的定理，对一些已有的实验图像和猜想进行了解释。对一些已有的实验图像和猜想进行了解释。关键词关键词 混合多核极化码，指数，收敛性混合多核极化码，指数，收敛性 Convergence of Hybrid Multi-Kernel Polar Codes Exponent Tong Wang,Xiaoyu Jin,Weihua Yang*School of Mathematics,Taiyuan University of Technology,Taiyuan Shanxi Received:Dec.10th,2023;accepted:Jan.5th,2024;published:Jan.10th,2024 Abstract Hybrid multi-kernel polar codes are polarized and have good polarization performance.The ex-ponent of the polarization matrix corresponding to the polar code is an important metric to measure the performance of the polar codes,so this paper focuses on the exponent of the hybrid multi-kernel polar codes.In this paper,we extend the expression of partial distance of multi-kernel polar codes *通讯作者。王彤 等 DOI:10.12677/aam.2024.131006 48 应用数学进展 to obtain the expression of partial distance of hybrid multi-kernel polar codes,and the expression of exponent of hybrid multi-kernel polar codes is derived based on the relationship between par-tial distance and exponent of polar codes,which can be expressed as a linear combination of its constituent matrices,and the upper and lower bounds of exponent of hybrid multi-kernel polar code are obtained.Then,based on the polarization phenomenon of hybrid multi-kernel polar codes,a special matrix selection rule for hybrid multi-kernel polar codes is proposed,and it is proved that the exponent of hybrid multi-kernel polar codes generated under this matrix selection rule is convergent and channel capacity dependent.Finally the theorems derived in this paper are applied to explain some existing experimental images and conjectures.Keywords Hybrid Multi-Kernel Polar Codes,Exponent,Convergence Copyright 2024 by author(s)and Hans Publishers Inc.This work is licensed under the Creative Commons Attribution International License(CC BY 4.0).http:/creativecommons.org/licenses/by/4.0/1.引言引言 ARIKAN 教授提出的传统极化码是首个理论上被证明能够实现信道容量的信道编码1。传统极化码 的码长为2nN=，生成矩阵是n=GF(F为极化变换的核)，其中1011=F，表示克罗内克积。ARIKAN 教授还提出信道极化现象是一种普遍存在的现象，即对于ll()2l 的核lG也会产生信道极化现象2。为了提升传统极化码码长的灵活性，许多文章提出了不同码长的极化码构造，如线性与非线性二进制的核3，极化码的多核构造4，打孔极化码5 6以及缩短极化码7等。将传统极化码生成矩阵中的F替换为iill极化矩阵ilG就得到了码长为1 2nl ll?多核极化码，其生成矩阵为12nlll=GGGG?。多核极化码除了适用于不同的码长外，在错误率性能方面还优于使用打孔和缩短过程得到的极化码4。为了进一步提高极化性，混合多核极化码8在多核极化码的基础上，根据不同的虚拟信道的性能选择不同的组成矩阵。因此，混合多核极化码是局部最优的，有更好的性能。同时，信道极化率9是在 SC 译码下极化码的一个度量块错误率的重要指标。极化码的极化率也被叫做对应极化矩阵的指数，根据极化码指数的计算公式得到传统极化码的指数为()0.5nE=F，多核极 化码的指数为()()1211 2logininllllilnEEl ll=GGGG?10。本文我们的目标是得到混合多核极化码指数的表达式，以推导出某些混合多核极化码指数的收敛性，并将这些理论应用于已有的实验中。2.基础知识基础知识 2.1.混合多核极化码混合多核极化码 为了提高多核极化码的错误性能，混合多核极化码根据虚拟信道的不同性能在极化的每一阶段选择不同的生成矩阵。如图 1 所示，我们在混合多核极化码的每一极化阶段根据信道容量选择极化矩阵。令G是一个ll的极化矩阵，()1,2,iil=G?是iill的极化矩阵，HG是一个混合矩阵，即 Open AccessOpen Access王彤 等 DOI:10.12677/aam.2024.131006 49 应用数学进展 1,11,21,1,11,21,112,12,22,2,12,22,22,1,2,1,2,:iiiiiilllliHlll llllll laaaaaaaaaaaaaaaaaa=GGGGGG?.(1)则矩阵G和HG的类克罗内克积11定义如下：1122:Hll=GGGGG.(2)混合多核极化码的生成矩阵11为()()()()123nnHHH=GGGGG?。Figure 1.Hybrid multi-kernel polar codes construction 图图 1.混合多核极化码的构造 2.2.指数指数 将极化现象应用于混合多核极化码，得到如下引理。引理引理 1(混合多核极化码的极化性混合多核极化码的极化性12)：令 W 是任意二进制输入离散无记忆信道(B-DMC)，信道容量()01I W，混合多核极化码的生成矩阵为()()()()123nnHHH=GGGGG?。当混合多核极化码的码长N 趋于无穷时，信道容量趋于 1 虚拟信道占所有虚拟信道的比例为()I W；信道容量趋于 0 的虚拟信道占所有虚拟信道的比例为()1I W。定义定义 1(指数指数2)：令 W 是任意二进制输入离散无记忆信道(B-DMC)，信道容量()01I W，ll矩阵G的指数()E G满足以下条件：1)对于任意一个定值()EG，inflim21nlnnPr Z=。指数()E G也叫做极化率，是一种在 SC 译码下测量极化码的块错误率的一种方式。指数()E G 王彤 等 DOI:10.12677/aam.2024.131006 50 应用数学进展 由的部分距离计算得到。定义定义 2(部分距离部分距离2)：令TTT1,l=Ggg?为ll极化矩阵，G的部分距离为()()()1,2,DDDDl=GGGG?，()()12,1,2,1HiiilDidil+=Ggggg?，(3)()(),HlDld=Gg 0，(4)其中1212,iiliilspan+=gggggg?，Tig是行向量ig的转置，(),Hda b是向量a和向量b的汉明距离，()(),min,HHdd=caa c，0是1 l的零向量。引理引理 2(部分距离与指数的关系部分距离与指数的关系2)：令G是一个ll极化矩阵且G的部分距离为()()()1,2,DDDDl=GGGG?，则G的指数()()11loglliEDil=GG (5)3.主要结论主要结论 这部分展示了本文的主要结论，即在一种特殊的选择方式下混合多核极化码的指数是收敛的。3.1.混合多核极化码指数的表达式混合多核极化码指数的表达式 根据引理 2，我们可以通过部分距离与指数的关系计算指数。因此，为了得到混合多核极化码的指数的表达式我们先写出混合多核极化码的部分距离。引理引理 3(类克罗内克积的部分距离类克罗内克积的部分距离2)：令()()()1,2,DDDDl=GGGG?是极化矩阵G的部分距离，HG是 由iill的 极 化 矩 阵()1,2,iil=G?组 成 的 混 合 矩 阵，HDG是HG部 分 距 离 序 列，即12,HlDDDD=GGGG?。则混合多核极化码生成矩阵HGG的部分距离()()()()121,2,lHDDDDDDl D=GGGGGGGG?.(6)定理定理 1：令()()()()123nnHHH=GGGGG?为混合多核极化码的生成矩阵，()ijG是极化过程中第 i 阶段的第 j 个矩阵，则()()()11 2logiinnilnEEl ll=GG?，(7)其中()()()()1 2111 211il lliijjiEEl ll=GG?，()2,in=?，即混合多核极化码极化过程中第 i 阶段的所有组成矩阵指数的平均值。证明证明：该定理的证明主要运用了数学归纳法。1)当2n=时，()()()()2222121,HlDDDD=GGGG?，(8)()()()()()()()111111,2,DDDDl=GGGG?.(9)根据引理 3，王彤 等 DOI:10.12677/aam.2024.131006 51 应用数学进展 ()()()()()()()()11212211211,lHDDDDDlD=GGGGGGG?，(10)令1ilxr=?，则()2DiG是()()()1211xDxD+GG的第 r 项，()()()()()12211xDiDxDr+=+GGG，(11)因为()()()()1111111loglliEDil=GG，(12)()()()()()22222121log1jljliEDijll=GG，(13)则()()()()()()()()()()()()()()()()()()1 21 221 2121 211 2121 21 2111212211 211 211 221111 21 2121 21 21log1log11log1log1loglogloglogxxl ll lil ll lil ll ll liljjllllEDil lDxDrl lDxDrl lEEll ll lEEl ll l+=+=+=+=+GGGGGGGGGG (14)2)假设结论对于1n成立，即()()()1111 21logiinnilnEEl ll=GG?.(15)3)当kn=时，则()()()()()()1 21 21111 2111 21 21loglognnnl llnjnjnnnnHl llnlnEEl llEEl lll ll=+GGGGG?.(16)将(16)式带入(15)式并化简，我们得到()()()()()()()()()121211 21 21 21 2loglogloglognininnilnlnlnlnEEEEEl lll lll lll ll=+=GGGGG?.(17)注注：若在混合多核极化码极化过程的第()2,i in=?阶段选择相同的组成矩阵，就得到了多核极化码指数的表达式，这与文献10中得到的结果相同。若给出了组成矩阵中的指数最大和指数最小的矩阵，根据以下推论我们可以得到混合多核极化码的指数()nE G介于其组成矩阵的最大指数和最小指数之间。王彤 等 DOI:10.12677/aam.2024.131006 52 应用数学进展 推论推论 1：令()()()()123nnHHH=GGGGG?是混合多核极化码的生成矩阵，若LG为混合多核极化码组成矩阵中指数最大的矩阵，SG为混合多核极化码组成矩阵中指数最小的矩阵，则()()()SnLEEEGGG.(18)证明证明：首先证明右边的不等式。根据(7)式，()()()()()()()()()()()()1212121 21 21 2121 21 21 21 21 21 21 21 21 212loglogloglogloglog111loglogloglogloglognnnnnnnnlnlnlnLLLlnlnlnLlnlnlnLl lll lll llEEEEl lll lll llEEEl lll lll llEl lll lll llEll=+=+=+GGGGGGGGG?()nLlE=G (19)重复以上步骤，就得到了左边的不等式，此处不再赘述。根据引理 1，当混合多核极化码的码长趋于无穷时，虚拟信道中信道容量接近 1 的虚拟信道占所有虚拟信道的比例为()I W，信道容量接近 0 的虚拟信道占所有信道的比例为()1I W。根据这个特点，我们提出一种矩阵选择规则：信道容量接近 1 的虚拟信道选择极化矩阵xG，信道容量接近 0 的虚拟信道选择极化矩阵yG，剩余的虚拟信道可以选择任意极化矩阵。接下来我们证明在这种选择规则下生成的混合多核极化码的指数是收敛的且与信道容量相关。3.2.混合多核极化码指数的收敛性混合多核极化码指数的收敛性 定理定理 2：令()()()()123nnHHH=GGGGG?是混合多核极化码的生成矩阵，W(B-DMC)为二进制输入离散无记忆信道，信道容量()01I W。当n 时，若根据以上规则选择组成矩阵，则()()()()()()lim1nxynEI W EI WE=+GGG.(20)证明证明：令 k 为一个固定的足够的大的正整数，根据以上矩阵选择规则，在第 k 阶段，有()()1 2kl llI W?个虚拟信道选择极化矩阵xG；有()()()1 21kl llI W?个虚拟信道选择极化矩阵yG。由定理 1 中()()kE G的定义，()()()()()()()lim1kxykEI W EI WE=+GGG。我们将等式(7)分成两部分，第一部分是等式的前 k 项；第二部分是等式的1k+项及其后所有项，根据上一段分析，等式第二部分中的每一项都接近于()()()()()1xyI W EI WE+GG。当 n 不断增加时，由于 k 是固定值且第一部分的()()iE G的系数不断减少，则第一部分()()iE G的系数和递减。根据(7)式，可以明显看出等式中所有()()iE G的系数和为 1，当n 时，第一部分的系数和趋近于 0，那么第二部分()()iE G的系数和趋近 1。因此，第一部分的和趋近于 0，第二部分和趋近于()()()()()1xyI W EI WE+GG。因此()()()()()()lim1nxynEI W EI WE=+GGG。推论推论 2：令 W 是二进制擦除信道(BEC)且为其擦除概率，混合多核极化码的生成矩阵为()()()()123nnHHH=GGGGG?。当n 时，如果根据以上规则选择组成矩阵，()()()()lim1nxynEEE=+GGG.(21)证明证明：对于任意的二进制擦除信道(BEC)W 有()1I W=，显然等式(21)成立。王彤 等 DOI:10.12677/aam.2024.131006 53 应用数学进展 4.数值分析数值分析 最后，我们给出码长为3nN=的混合多核极化码的例子。令G是一个NN极化矩阵，W 是二进制擦除信道(BEC)且信道容量为，()()1iNWiN 是由G生成的第 i 个虚拟信道，()()iNZ W是()iNW的巴氏参数。我们用文献11中的构造方法。令 33100100110,010101111xy=GG，(22)则码长为3nN=的混合多核极化码的生成矩阵为()()()()1233333nnHHHH=GGGGG?，(23)其中()()()()11233,1:iiiiHiGGGinG=对于113ij，(24)根据虚拟信道的信道容量，()ijG取3xG或3yG：当()0,0.5，取3xG；当()0.5,1，取3yG；当0.5=，取3xG或3yG。通过计算，()30.42062xEG，()30.33333yEG根据推论 2 和(23)式，混合多核极化码的指数收敛为()()()()33lim1nxynEEE=+GGG.(25)当0.5=，指数收敛为()()()3312xyEE+GG。Figure 2.Exponents of hybrid multi-kernels polar codes 图图 2.混合多核极化码的指数 王彤 等 DOI:10.12677/aam.2024.131006 54 应用数学进展 图 2 为文献11中模拟码长为()34,6,8,10nNn=时混合多核极化码的指数图像。在图中我们可以观察到，指数会在某些值处出现突变。产生这些突变有两个原因：一是当初始信道的擦除概率为 0.5 时，在第一阶段无法确定对应的组成矩阵；二是在极化过程中的其他阶段出现的擦除概率为 0.5 的虚拟信道时无法确定对应的组成矩阵。当n 时，这些突变会消失。由于信道极化，当 n 足够大时，擦除概率为 0.5 的虚拟信道非常少。因此不管这些信道取3xG或者3yG，对于()nE G的取值几乎没有影响，即()()()()33lim1nxynEEE=+GGG。根据(25)式，在图 2 中，当n 时，混合多核极化码的指数应该为一条过点()0,0.42062和()1,0.33333的直线。5.总结总结 极化码的指数是度量极化码性能的重要指标，为了探究混合多核极化码的指数的相关性质，本文得到了混合多核极化码指数的表达式，即混合多核极化码指数可以表示为其组成矩阵的线性组合并且提出了一种特殊的矩阵选择规则，证明了在这种选择规则下混合多核极化码的指数是收敛的。文献11对混合多核极化码的指数进行了仿真，得到了一类混合多核极化码指数的图像，并针对图像提出了一些猜想。本文将推导出的定理运用到文献11的实验中，解释了图像产生突变的原因，预测了当极化码码长趋于无穷时的图像走向，证实了其猜想。参考文献参考文献 1 Arikan,E.(2009)Channel Polarization:A Method for Constructing Capacity Achieving Codes for Symmetric Bi-nary-Input Memoryless Channels.IEEE Transactions on Information Theory,55,3051-3073.https:/doi.org/10.1109/TIT.2009.2021379 2 Korada,S.B.,Sasoglu,E.and Urbanke,R.(2010)Polar Codes:Characterization of Exponent,Bounds,and Construc-tions.IEEE Transactions on Information Theory,56,6253-6264.https:/doi.org/10.1109/TIT.2010.2080990 3 Lin,H.P.,Lin,S.and Abdel-Ghaffar,K.A.S.(2015)Linear and Nonlinear Binary Kernels of Polar Codes of Small Dimensions with Maximum Exponents.IEEE Transactions on Information Theory,61,5253-5270.https:/doi.org/10.1109/TIT.2015.2469298 4 Gabry,F.,Bioglio,V.,Land,I.,et al.(2017)Multi-Kernel Construction of Polar Codes.2017 IEEE International Conference on Communications Workshops(ICC Workshops),Paris,21-25 May 2017,761-765.https:/doi.org/10.1109/ICCW.2017.7962750 5 Niu,K.,Chen,K.and Lin,J.R.(2013)Beyond Turbo Codes:Rate-compatible Punctured Polar Codes.2013 IEEE In-ternational Conference on Communications(ICC),Budapest,9-13 June 2013,3423-3427.https:/doi.org/10.1109/ICC.2013.6655078 6 Zhang,L.,Zhang,Z.Y.,Wang,X.B.,et al.(2014)On the Puncturing Patterns for Punctured Polar Codes.2014 IEEE International Symposium on Information Theory(ISIT),Hawaii,29 June-4 July 2014,121-125.https:/doi.org/10.1109/ISIT.2014.6874807 7 Wang,R.X.and Liu R.K.(2014)A Novel Puncturing Scheme for Polar Codes.IEEE Communications Letters,18,2081-2084.https:/doi.org/10.1109/LCOMM.2014.2364845 8 Cheng,L.,Zhou,W.and Zhang,L.J.(2019)Hybrid Multi-Kernel Construction of Polar Codes.2019 IEEE 89th Vehi-cular Technology Conference(VTC2019-Spring),Kuala Lumpur,28 April-1 May 2019,1-5.https:/doi.org/10.1109/VTCSpring.2019.8746303 9 Arikan,E.and Telatar,E.(2009)On the Rate of Channel Polarization.2009 IEEE International Symposium on Infor-mation Theory,Seoul,28 June-3 July 2009,1493-1495.https:/doi.org/10.1109/ISIT.2009.5205856 10 Lee,M.-K.and Yang,K.(2014)The Exponent of a Polarizing Matrix Constructed from The Kronecker Product.De-signs Codes Cryptography,70,313-322.https:/doi.org/10.1007/s10623-012-9689-z 11 Cheng,L.,Zhang,L.J.and Sun,Q.(2018)Exponents of Hybrid Multi-Kernel Polar Codes.2018 IEEE 10th Interna-tional Symposium on Turbo Codes&Iterative Information Processing(ISTC),Hong Kong,3-7 December 2018,1-5.https:/doi.org/10.1109/ISTC.2018.8625322 12 宋睿,徐铭,唐元生.混合多核极化码的极化性极化性J.广西师范大学学报(自然科学版),2021,39(3):69-82.