《LDPC码和Polar码的基础理论分析》4100字

LDPC码和Polar码的基础理论分析综述目录TOC\o"1-3"\h\u5036LDPC码和Polar码的基础理论分析综述 1160681.1LDPC码的基本理论 1281301.1.1LDPC码的构造 1224101.1.2LDPC码的编码 2238001.1.3LDPC码的译码算法 3202661.1.3和积算法SPA和最小和算法MS 3215211.2Polar码的基本理论 6189681.1.1信道极化 6215671.1.2极化码的编码 9168371.1.3极化码的译码 10本章主要阐述了LDPC码和极化码的基本原理。首先是介绍了关于LDPC码的构造、编码方案以及和积译码算法（SPA）和最小和译码算法（MS），同时给出了两种算法的仿真；接着对信道极化理论和极化码的编码原理、SC译码算法和BP译码算法进行简要的论述，同时给出了极化码在这两种译码算法下的仿真。1.1LDPC码的基本理论LDPC码在检错纠错上以及误码率性能上都有着不错的表现和特性。LDPC码提出以来，直到1996年MacKay和Neal等人提出的利用Tanner图来进行迭代译码，不在受限于当时的硬件发展水平，以及当时数字集成电路的快速发展，才将LDPC码应用到工业界当中，并很大程度上改善了LDPC码的译码性能。当下，LDPC码已经是一种相当成熟的信道编码，已被确认为5GeMBB场景中信息信道的编码方案，并且也广泛应用在各通信领域。1.1.1LDPC码的构造Gallager在其论文中给出一种方法-随机构造法，Gallager码(n,j,k)的构造步骤：将矩阵分割成j个子矩阵，每个矩阵每列仅具有1个。第一子矩阵的一成下降趋势的构成；其他子矩阵由随机列置换从第一子矩阵构成。通过计算机设计可以避免这个缺点，就是该方法不能保证H中没有长度为4的环。Gallager更为关键的是指出这类码有复杂度较低的编码器，主要是其校验比特可以通过校验矩阵或者校验判决式表示为信息比特的方程，因此可以设计一种具有较低复杂度的编码器。1.1.2LDPC码的编码1.1.1.1基于生成矩阵的高斯消元法

高斯消元法:通过对校验矩阵H进行变换，得到生成矩阵G，然后利用公式G∗对于一个(n,k)二进制LDPC码，变为更符合编码的形式，即系统形式，那么这样的校验矩阵为H=[Qm∗k然后根据校验矩阵，当然也可以根据校验判决式，即码字c满足H∗H当且仅当Qm∗k=QPm∗k时上式成立。因此，完全可以通过、、求得编码所需要的系统码生成矩阵1.1.1.2基于校验矩阵的直接编码首先推导出校验矩阵直接编码的等式。将尺寸为(m,n)校验矩阵写成如下形式H=编码后的码字行向量为c码长为n，写成如下形式c由校验公式H得H展开得p若校验矩阵是非奇异的，则H2p高斯消元法适用于任何类型的LDPC码编码。但是缺点是该编码方案不利于硬件的实现，这是由于生成矩阵G破坏了校验矩阵H原有的稀疏特性，大大提升了编码计算复杂度和存储要求。1.1.3LDPC码的译码算法复杂度低的LDPC码的硬判决算法，因此纠错能力也有限，在对要求较低的情形下应用是比较合适的，也较为广泛。而复杂度高的软判决算法更适合于要求较高的通信场景，由于其采用可靠性消息迭代算法，必然是具有更好的误比特率性能的译码，因此广泛应用在高要求通信场景中。本节主要讲述软判决算法和积算法SPA和最小和MS算法。首先了解一下Tanner图的概念，Tanner图上每个校验节点和一个校验方程相对应，每个变量节点和一个编码比特相对应。例如一个H矩阵如下所示;H那么其对应的Tanner图如2-1所示：图2-1LDPC码的Tanner图示例1.1.3和积算法SPA和最小和算法MSGallager在其论文中除了提出了LDPC码的构造方法之外，还提出了一种译码算法，即和积算法（SPA）。在SPA译码器的推导中，其内在的最优准则是基于符号的最大后验概率(MAP)准则。假设接收字y=[y0,y1,…,yn−1]，我们感兴趣的是怎样计算传输码字v=[u0PrAPP的比值(也称似然比，LR):l取在数值上更加稳定的对数似然比LLRL在这里以及之后，我们假定对LLR都取自然对数。Gallager的和积算法如下：（1）初始化：对所有j，根据适当的信道模型，对Lj进行初始化。然后，对所有满足ℎij=1的i,j，令（2）CN更新：对每个CN，计算其往外传递的信息LL然后传递给其相邻的VN。（3）VN更新：对每个VN,计算其往外传递的信息LL然后传递给其相邻的CN。（4）LLR总和：对j=0,1，…，n-1，计算L（5）终止准则：对j=0,1，…，n-1，令v从而得v，如果如果v步骤2中的更新方程可以化为：Lαβ故步骤2重写为：tanh现在介绍更为简单的，也就是复杂度更低的译码算法-最小和译码算法（MS），它们在性能上通常都会有略微的损失。考虑对数域SPA译码中对Li于是最小和简化算法只需要对SPA算法中的第二步进行更换即可（2）CN更新：LMS算法还有一个好处是，是在AWGN信道下，初始化Lj→i对LDPC码的不同译码算法进行仿真，分别比较不同码长下、不同译码算法下LDPC码的误比特率性能,迭代次数为30次，仿真结果如下：图2-2LDPC码的仿真图仿真结果如图所示，其中不管哪种编码，都会有错误平层现象，区别是在LDPC的码率相同的情况下，码长越长则LDPC码的误比特率性能更优，原因是因为其具有更多的冗余位去保护信息部分，有效性降低，可靠性得到提高。在LDPC码的码长和码率都相同的情况下，付出的代价是更高的译码复杂度的BP译码算法相比MS算法，误比特率更低。1.2Polar码的基本理论Arikan在其论文中基于信道极化现象提出了级化码，因级化码具有不错的编译码复杂度和纠错能力，已被应用于5GeMBB场景下控制信道的编码方案。1.1.1信道极化信道的极化利用了递归思想，为了更加清楚地描述该极化过程，在这里首先考虑最简单的信道极化情况。如图2-2所示，针对二进制无记忆信道（B-DMC）信道，信源比特u1,u2在经过信道W传输前，需要经过运算x1=u图2-3信道联合示意图将合并后得到的矢量信道记为W2:X2→Y2，其转移概率为:W2y1,y2∣u1,u图2-4

利用递归方法，当输入向量维数为N时，如图2-4所示，RN表示奇偶交换操作，将输入向量u1N=u图2-5

接下来将信道联合时构造的信道WN分裂成N个比特信道WWN图2-6信道分裂示意图其对应的信道转移概率可以求得W1.1.2极化码的编码极化码编码的编码过程主要概括为以下三个步骤：（1）进行极化信道的可靠性估计（2）比特混合动力-已知的混合通信的冻结住的比特（3）生成矩阵的构成-生成最终极化码码字对极化后的信道进行可靠性估计，从而选择一部分信道传输信息序列、一部分信道传输冻结。对于BEC，Arikan给出的方法是计算巴氏参数：Z巴氏参数Z(WN码长为N的极化码的生成矩阵，可由信道极化理论推得，表达式为：

G其中F⊗n表示对矩阵F=101B其中RN是对单位阵I1.1.3极化码的译码对于极化码的译码，最先提出的是SC译码算法，除此之外，根据极化码的因子图，并行极化的BP译码算法（flooding-BP）也是极化码主流的译码算法之一。本小节主要介绍SC译码算法和BP译码算法。1.1.3.1SC译码算法由于最后的极化码码字由消息比特和冻结比特组成，对比特进行判决前，需要区分当前比特ui是冻结比特还是消息比特。若ui是冻结比特，直接令ui为双方约定的值，若ui是消息比特，假设u其中似然比LNL式中u1i−1&初始值为：LSC译码利用来自信道的向量y1N和u1对u2进行判决，按标号递增的顺序对后面比特依次进行判决，直到完成最后一个比特的判决,从而得到对整个来自信道的序列的估计，故SC译码的译码过程是串行执行的。译码器在对uN进行译码时，需要用到来自信道的接收符号y对其改进后的SCL译码算法的大致思路可以概括为“加比选”，过程与维特比译码有相似的地方，在处理比特时，保留两种可能的取值0或者1，同时计算两种取值情况下各自所对应路径的可靠性度量，当存储的路径数量达到预先设定的阈值时，会对这些路径进行筛选，依据可靠性保留可靠性度量最高的路径，这些路径作为后续译码的候选路径，当对最后一个比特的译码完成之后，在所有的候选路径中选择一条可靠性最高的路径作为最终的译码结果。1.1.3.2BP译码算法一种消息传递译码算法称为BP译码算法，文献阐述[24]极化码的生成矩阵和LDPC码的校验矩阵类似，可以广泛地应用于各种类型的编码，其中BP编码算法也可以类似地应用于极化码的编码算法，并且可靠性消息在图表结构中来回重复。代码长度n＝8的偏振码的系数图如图所示，具有在各阶段追加了n/2个处理单元的多级结构（参照下图）。与极化码编码编码过程相反，在重复循环期间，从右到左逐步地传递可靠消息，并且在消息被传送到左边缘之后，从左到右边缘逐步地传递该擦除。图2-7极化码的因子图‘图2-8极化码的每一级中的处理单元每次迭代传递的消息依然是对数似然比的形式，即：&其中f(当达到最大迭代次数后，更新最左边一级和最右边一级的软信息&然后进行判决：u文献[25]提出利用ui和码字ci的估计值对极化码的迭代过程进行早判决，不必要一直迭代到最大迭代次数，因此可以降低BP译码的时间复杂度以及硬件需求，若满足校验式对极化码在不同的译码算法和不同的码长