LDPC码实现及性能研究

信息系统工程设计课程报告LDPC码实现及性能研究2/19前言里斯本时间，2016年10月14号凌晨，3GPPRAN1会议确定5G将使用LDPC码作为移动宽带（eMBB）业务数据信息的长码块编码方案。在问世53年之后，LDPC终于被主流移动通信系统接纳。故而我们对LDPC码的编码理论进行了研究整理。本报告主要对LDPC码的整体实现进行仿真，包括校验矩阵生成、信道编码、译码各个部分，并在不同的码长、码率条件下分析验证了其实际误码性能。一课题背景1信道编码在移动通信中，由于存在干扰和衰落，信号在传输过程中会出现差错，所以需要对数字信号采用纠、检错技术，即纠、检错编码技术，以增强数据在信道中传输时抵御各种干扰的能力，提高系统的可靠性。对要在信道中传送的数字信号进行的纠、检错编码就是信道编码。信道编码是为了降低误码率和提高数字通信的可靠性而采取的编码。信道编码之所以能够检出和校正接收比特流中的差错，是因为加入一些冗余比特，把几个比特上携带的信息扩散到更多的比特上。为此付出的代价是必须传送比该信息所需要的更多的比特。传统的信号编码有汉明码、BCH码、RS码和卷积码。目前应用较广的有Turbo码，以及5G即将使用的LDPC码，还有具有应用潜力的Polar码等。不同的信道编码，其编译码方法也有所不同，性能也有所差异。2LDPC码3/19从1964年Gallager发表的《Low-DensityCheck-ParityCode》一文标志着LDPC码的诞生，在文章中，他证明了LDPC码性能接近于香农极限，同时在文章中也提出了构建H矩阵的一种方法，以及两种解码方法和示意性的硬件电路原理图，但是由于当时科技水平有限，硬件条件的限制，LDPC码并没有得到重视和推广。直到1996年D.MacKay和R.Neal证明了LDPC码性能和成本都优于Turbo码，LDPC码才有进入人们的视野，掀起了一番研究的热潮。随后学术界对LDPC投入了大量的关注，对编码矩阵构造、译码算法优化等关键技术展开研究。其中比较关键的研究突破包括：高通的ThomasJ.Richardson提出的Multi-Edge构造方法可以灵活的得到不同速率LDPC码，非常适合通信系统的递增冗余（IR-HARQ）技术；再加上LDPC的并行译码可以大幅度降低LDPC码的解码时间和复杂度，LDPC从理论进入通信系统的障碍被全部扫清了。现在，LDPC码被公认为是性能最接近香农极限的信道编码之一。方法描述LDPC码实际是一种线性分组码，即分为固定长度的码组，每一组内k个信息位被编为n位码组长度，而（m=n-k）个监督位被加到信息位之后形成新码以实现检错与纠错，记为(n,k)码。当分组码的信息码元与监督码元之间的关系为线性关系时，这种分组码就称为线性分组码。因此LDPC的编码关键就在于从k比特的信息到长度为n比特的码组上的映射关系，通常由一个对应的校验矩阵𝐻来表示。LDPC码的主要特点在于其校验矩阵𝐻的稀疏性，此种特性使得LDPC码具有更好的易实现性。4/19LDPC码的具体实现首先需要校验矩阵𝐻的设计，随后根据𝐻阵即可相应地生成编码序列完成编码过程；通过信道传输之后对接收到的信号进行相应地译码，判决出原有信息位。每一部分的具体原理与过程在下文详细阐述。1校验矩阵生成1.1基本校验矩阵的生成LDPC码作为一种线性分组码，可由其校验矩阵𝐻阵唯一确定。而由于LDPC码𝐻矩阵的稀疏特性，矩阵中非零元素很少，因此每一LDPC码所对应的𝐻阵又可由相应的二分图表示，称为该码的Tanner图。Tanner图中的变量（比特）节点对应至𝐻矩阵中的每一列，也即对应LDPC码的每一码比特；Tanner图中的校验节点分别对应到𝐻矩阵的每一行，也即对应LDPC码中的校验比特。两类节点之间的连接情况对应𝐻矩阵中元素的取值：若第i个校验节点与第j个变量节点之间存在连接，则代表𝐻矩阵的(i,j)个元素取值为1；若无连接则对应元素为零。图二.1与图二.2分别是一个(16,8)LDPC码的𝐻阵与Tanner图。图错误!文档中没有指定样式的文字。.1(16,8)LDPC码H阵图错误!文档中没有指定样式的文字。.2(16,8)LDPC码Tanner5/19图在码长较长的情况下，LDPC码的𝐻矩阵会十分庞大。因此通常将𝐻矩阵分块表示：完整的𝐻矩阵视作由多个Z*Z的子矩阵生成，原始的𝐻矩阵即可由一个𝑚𝑏×𝑛𝑏的基本矩阵𝐻𝑏表示（𝑚𝑏=𝑚𝑧,𝑛𝑏=𝑛𝑧），𝐻𝑏中每一元素对应一个Z*Z子矩阵，Z被称为扩展因子。其中准循环LDPC码（QC-LDPC）较为常用，其特点在于每一子矩阵为全零方阵或单位阵向右循环移位得到的置换矩阵，因此各子矩阵都可由循环移位的位数表示，𝐻阵所需存储空间极大减小。另外子矩阵可由循环移位得到，也更易于硬件实现。1.2可变速率的校验矩阵设计传统的LDPC码中，每一𝐻阵都分别对应一个码率与码长。而在对不同的码率、码长的要求越来越多的情况下，这种对需要对不同要求分别设计不同𝐻阵的方法较为繁琐。因此[1]中提出了一种可兼容不同码率与码长的𝐻阵设计方案，这种兼容性主要通过嵌套的基本矩阵（图）与可变的扩展因子Z实现。1.2.1嵌套的基本图基本矩阵（图）由是嵌套的子图的集合，即可从该集合中最大的基本图中截取部分形成新的基本图以应对不同码长、码率要求。其中每一子图由一相对高码率的核心图与IR-HARQ扩展构成：核心图由包括2个打孔节点的信息位与校验位构成，其中校验位结构与802.11n标准中类似；IR-HARQ扩展由核心图中比特进一步校验生成。子图构成的集合设定最大/最小信息比特数与最大/最小校验比特数，即并由此可计算出该基本矩阵可实现的码长与码率范围。6/191.2.2可变的扩展因子扩展因子Z可由不同码长、码率要求取不同的值，取值集合被分为不同的群组，相同群组内的Z取值对应的扩展子矩阵移位情况相同。因此，由可变的基本矩阵与扩展因子Z的不同取值，可实现不同码长与码率的LDPC校验矩阵。2LDPC码编码算法2.1直接编码算法直接编码方法的大致思路是：利用高斯消去法将M∗N的校验矩阵𝐻变换成𝐻′=[PI]，因为校验矩阵𝐻的不确定，所以在变换过程中可能会涉及到初等行列变换。如果进行了初等行列变换，则同时要记录下这些行列变换信息。如果校验矩阵𝐻满足线性相关的，将会删去相关的行，那么这种情况下，LDPC码的码率由该校验矩阵确定，其值将大于1–K/N；然后，根据系统形式的校验矩阵𝐻′=[PI]，得到其对应的生成矩阵𝐺=[IP𝑇]。如果在生成系统形式的校验矩阵的过程中没有进行初等行列变换，则有𝐻𝐺𝑇=0，否则𝐻𝐺𝑇≠0，而对于将校验矩阵H进行行列变换的依据则是根据记录之前记录下的行列变换信息。最后，𝑚为信息序列，则编码后的序列为𝑐=𝑚⋅𝐺。需要说明的是，如果在生成系统形式的校验矩阵的过程中进行了初等行列变换，则需要使用进行过相应的初等行列变换的校验矩阵𝐻进行译码。上面思路基本适用于对任意结构的LDPC码进行编码，得到的编码复杂度往往与码长成正比。由于这种编码算法的计算复杂度过于庞大，且会占用过大的7/19存储空间。因此，不适合于硬件实现，这也是早期阻碍LDPC码发展的原因之一[2]。由于LDPC码的码长n很大，同时很多性能优良的LDPC码都是采用随机方式构造的，这就导致使用上述方法得到生成矩阵𝐺的运算量很大。为降低编码复杂度，现在已发展出多种已经简化的编码方法，而下面将讨论的这种编码算法就被视为一种高效的LDPC码编码算法，而且应用广泛。2.2基于校验矩阵的编码算法传统的直接编码适用于任意结构的LDPC码，但缺点在于编码过于复杂。RU算法是一种可解决该问题的有效算法，主要思想是利用校验形矩阵具有的稀疏性来尽量减轻编码的运算量[3]。这种算法为了能得到一个近似下三角矩阵，会依靠行列置换来改变校验矩阵𝐻，这么变换的好处就在于原来矩阵所具有的稀疏性会被保留。如图二.3所示：通过某种方法将原来矩阵分成六个分块的稀疏矩阵，图中显示的𝐺尽可能小。图错误!文档中没有指定样式的文字。.3校验矩阵分解示意图现在假设信源𝑠的长度是K=N-M，并且𝑥=(𝑠,𝑃1,𝑃2)被编码成码字向量，其中𝑃1、𝑃2都定义成校验向量，长度分别是：𝐺和𝑀−𝐺。具体编码步骤如下：M-GGNNGM-MACBDTE08/19首先对M∗N维矩阵𝐻做行、列变换，得到𝐻矩阵的形式为：ABTCDE(1)计算信源向量的上校正子=AsTZ(2)找出第二个校验向量的临时值，使得上校正子为零12APTZ(3)接着计算向量的下校正子2TASsZCEP(4)首先要做的就是准备求第一个检验向量𝑃1。由矩阵（该矩阵必须可逆）𝐹=−𝐸𝑇−1𝐵+𝐷来求逆矩阵，该计算完成一次的复杂度𝑂(𝐺2)，这个逆矩阵是一个G*G维高密度矩阵。现在假设第一个校验向量BZFPT11(5)接着放弃临时检验性向量，但是要找出新的有效地且符合条件的上校正子（可以在线性时间完成）：1TcAZZBP(6)接着求解出上面提到的𝑃2的值，同样必须使上校正子满足全为零（利用回代算法在线性时间内求出）。12TcPTZ上述RU算法，利用了校验矩阵的稀疏性，适用于任何基于稀疏校验矩阵的编码。整个编码流程的示意图如下：9/19图错误!文档中没有指定样式的文字。.4RU编码算法流程图3LDPC码译码算法3.1BP算法BP算法（BeliefPropagationAlgorithm）是一类较重要的消息传递算法，该算法经常用在人工智能等领域中。算法中各个节点之间传递的信息是概率或置信信息，例如由变量节点vi传递给校验节点cj的信息是vi取某些特定值的概率信息，该信息的具体取值依赖于vi的观测值和其他所有与vi相连的校验节点（cj除外）在上一轮迭代中传递给vi的置信信息，同样的，由cj传递给vi的信息也是cj取某些特定值的概率信息，该信息的取值依赖于其他所有与cj相连的变量节点（vi除外）在上一轮迭代中传递给的置信信息[4]。3.1.1概率域上的BP算法现在给出信道为高斯白噪声信道（AWGN,AdditiveWhitenGaussianNoise），噪声方差表示为𝜎2，调制方式为BPSK、概率域上的开始编码接受二进制待编码校验比特编码器𝑃1校验比特编码器𝑃2将信息源比特和生成的校验比特合成码字并且最终输出编码结束10/19LDPC码的和积译码算法。其中，码元𝑐𝑗∈{0,1}，调制符号𝓍𝑗=1−2𝑐𝑗，输出𝑦𝑗=𝑥𝑗+𝑛𝑗∈(−∞,+∞)。在接收到𝑦𝑛情况下,()nnxdv=b的先验概率记为00nnnp(d)=p(x=d|y)在概率域上，我们用knp(d)表示第k次迭代某个变量节点的可信度，即第k次迭代时nxd的概率；()kmird表示ixd的第k次迭代时，由mc传递给iv的信息；knjqd表示ixd的第k次迭代时，由nv传递给jc的信息；()An表示变量节点nv所对应的校验式集合；()Bm表示校验式mc所对应的变量节点集合。概率域的算法如下：初始化：迭代次数1k若假定发送序列先验等概110.5nnpxpx，则2202222exp2|11expexp22nnnnnydpxdyyy021|,1,121expnnnnpxdydyd同时变量节点向校验节点传递初始信息，00,njnjnqdpdcAv第一步，检验k是否大于最大迭代次数Max，如果是，结束这帧的译码，否则继续；第二步，更新变量节点信息：第n个校验节点收集除了第j个以外的变量节点传递来的信息njq，然后再传递给与其相连的第j个变量节点，更新变量节点为0或1的概率。由校验节点mc传递给变量节点iv的概率信息为：11/19