LDPC码实现及性能研究

1、信息系统工程设计课程报告LDPC码实现及性能研究里斯本时间2016年10月14号凌晨3GPP RAN1会议确定5G将使用LDPC码作为移动宽带（eMBB ）业务数据信息的长宿块编谄方案。在问世53年之后,LDPC终于被主流移动通信系统跳。故而我们对LDPC码的编码理论进行了研究整理。本报告主要对LDPC码的整体实现进行仿真，包括校验矩阵生成、信道编码、译码各个部分，并在不同的码长、码率条件下分析验证了其实际误码性能。一课题背景1信道编码在移动通信中，由于存在干扰和衰落，信号在传输过程中会出现差错，所以 需要对数字信号采用纠、检错技术，即纠、检错编码技术，以增强数据在信道中传输时抵御各种干扰的能

2、力，提高系统的可靠生对要在信道中传送的数字信号 进行的纠、检错编码就是信道编码。信道编码是为了降低误码转口提高数字通信的可靠性而采取的编码。信道编码之 所以能够检出和校正接收比特流中的差错，是因为加入一些冗余比特，把几个比 特上携带的信息扩散到更多的比特上。为此付出的代价是必须传送比该信息所需 要的更多的比特。传统的信号编码有汉明码、BCH码、RS码和卷积码。目前应用较广的有Rirbo 码，以及5G即将使用的LDPC码,还有具有应用潜力的Polar码等。不同的信 道编码，其编译码方法也有所不同，性能也有所差异。2LDPC码从 1964 年 Gallager 发表的LowDensity Chec

3、k-Parity Code一文标志着 LDPC码的诞生，在文章中，他证明了 LDPC码性能接近于香农极限，同时在文 章中也提出了构建H矩阵的一种方法，以及两种解码方法和示意性的硬件电路 扇里图，但是由于当时科技水平有限,硬件条件的限制，LDPC码并没有得到重 视和推广。直到1996年D.Mac Kay和R.Neal证明了 LDPC码性能和成本都优 于TWbo码，LDPC码才有进入人们的视野，掀起了一番研究的献。随后学术 界对LDPC投入了大量的关注，对编码矩阵构造、i圣码算法优化等关键技术展开其中比较关键的研究突破包括：高通的Thomas J. Richardson提出的Multi-Edge构

4、造方法可以灵活的得到不同速率LDPC码，非常适合通信系统的递增冗余（IR-HARQ ）技术；再加上LDPC的并行i圣码可以大幅度降低LDPC码 的解码时间和复杂度，LDPC从理论进入通信系统的障碍被全部扫清了。现在，LDPC码被公认为是性能最接近香农极限的信道编码之一。方法描述LDPC码实际是一种线性分组码，即分为固定长度的码组，每一组内k个信息位被编为n位码组长度，而（m=n-k ）个监督位被加到信息位之后形成新码以 实现检错与纠错，记为。冰）码。当分组码的信息码元与监督码元之间的关系为线 性关系时,这种分组码就称为线性分组码。因此LDPC的编码关键就在于从k 比特的信息到长度为n比特的码组

5、上的映射关系，通常由一个对应的校验矩阵H 来表示。LDPC码的主要特点在于其校验矩阵，的稀疏性，此种特性使得LDPC 码具有更好的易实现性。LDPC码的具体实现首先需要校验矩阵”的设计，随后根据“阵即可相应地 生成编码序列完成编码过程；通过信道传输之后对接收到的信号进行相应地译码, 判决出原有信息位。每一部分的具体原理与过程在下文详细阐述。1校验矩阵生成1.1基本校验矩阵的生成LDPC码作为一种线性分组码，可由其校验矩阵”阵唯T角定。而由于LDPC 码”矩阵的稀疏特性，矩阵中三港元素很少，因此每一LDPC码所对应的H阵又 可由相应的二分图表示，称为该码的Tanner图。Taimer图中的变量(

6、比特)节 点对应至H矩阵中的每一列，也即对应LDPC码的每一码比特；Taimer图中的校 验节点分别对应到H矩阵的每一行，也即对应LDPC码中的校验比特。两类节点 之间的连接情况对应H矩阵中元素的取值：若第i个校验节点与第j个变量节点之间存在函妾，则代表“矩阵的(ij)个元素取值为1 ；若无函妾则对应元素为零图二.1与图二.2分别是一个Q6,8)LDPC码的“阵与Tarnier图。0 0 0 0 0 0I 0 0 1 0 0 .0 01100 0 10 0 00 0 00 0 00 0 11 0 00 1 00 0 0 0 11100 0 0 1 0 0 0 00 0 10 0 0 0 0 1

7、0 0 10 10 000100000 0 00 0 01 1 00 0 11 0 00 1 00 0 00 0 10 0 00 0 00 0 01 1 11 0 00 1 00 0 10 0 021/19图错误！文档中没有指定样式的文字。.1 (16,8)LDPC码H阵Bit Node图错误！文档中没有指定样式的文字。.2(16.8)LDPC码Taimer在码长较长的情况下，LDPC码的H矩阵会十分庞大。因此通常将H矩阵分 块表示：完整的，矩阵视作由多个Z*Z的子矩阵生成,原始的“矩阵即可由一个 mb X3的基本矩阵”b表示（mb =，兀b =；）,从中每一元素对应一个Z*Z子 矩阵，Z被称

8、为扩展因子。其中准循环LDPC码（QCLDPC ）较为常用，其特 点在于每T矩阵为全零方阵或单位阵向右循环移位得到的置换矩阵，因此各子 矩阵都可由循环移位的位数表示，H阵所需存储空间极大减小。另外子矩阵可由 循环移位得到，也更易于硬件实现。12可变速率的校验矩阵设计传统的LDPC码中，每一H阵都分别对应一个码率与码长。而在对不同的码 率、码长的要求越来越多的情况下，这种对需要对不同要求分别设计不同H阵的 方法较为繁琐。因此1中提出了一种可兼容不同码率与码长的H阵设计方案，这 种兼容性主要通过嵌套的基本矩阵（图）与可变的扩展因子Z实现。121嵌套的基本图基本矩阵（图）由是嵌套的子图的集合，即可从

9、该集合中最大的基本图中截 取部分形成新的基本图以应对不同码长、码率要求。其中每一子图由一相对高码 率的核心'图与IR-HARQ扩展构成：核心图由包括2个打孔节点的信息位与校验 位构成，其中校验位结构与802.1111标准中类似；IR-HARQ扩展由核心图中比 牛苗A步校验生成。子图构成的集合设定最大/最小信息比特数与最大/最交验比中撼，即并由 此可计算出该基本矩阵可实现的码长与码率范围。12.2可变的扩展因子扩展因子Z可由不同码长、码率要求取不同的值，取值集合被分为不同的 群组，相同群组内的Z取值对应的扩展子矩阵移位情况相同。因此,由可变的基本矩卜车与扩展因子Z的不同取值，可实现不同码

10、长与码 率M LDPC校验矩阵2LDPC码编码算法2.1 直接编码算法直接编码方法的大致思路是：利用高斯消去法将M * N的校验矩阵H变换成 "'=P I,因为校验矩阵”的不确定，所以在变换过程中可能会涉及到初等行列变凰 如果进行了初等行列变换，则同时要记录下这些行列变换信息。如果校验 矩阵”满足线性相关的,将会删去相关的行，那么这种情况下，LDPC码的码率 由该校验矩阵确定，其值将大于1 - K/ N ；然后，根据系统形式的校验矩阵H' = P I,得到其对应的生成矩阵 G = I P7。如果在生成系统形式的校验矩阵的过程中没有进行初等行列变换, 则有“=0 ,否则

11、”* 0 ,而对于将校验矩阵H进行行列变换的依据则是 根据记录之前记录下的行列变换信息。最后，m为信息序列，则编码后的序列为c = m . G。需要说明的是，如果 在生成系统形式的校验矩阵的过程中进行了初等行列变换，则需要使用进行过相 应的初等行列变换的校验矩阵”进行译码。上面思路基本适用于对任意结构的LDPC码进行编码彳导到的编码复杂度往 往与码长成正比。由于这种编码算法的计算复杂度过于庞大，且会占用过大的存储空间。因此，不适合于硬仰实现，这也是早期阻碍LDPC码发展的原因之一由于LDPC码的码长n很大,同时很多性能优良的LDPC码都是采用随机 方式构造的，这就导致使用上述方法得到生成矩B轮

12、的运算量很大。为降低编码 复杂度，现在已发展出多种已经简化的编码方法，而下面将讨论的这种编码算法 就被视为一种高效的LDPC码编码算法,而且应用广泛。2.2 基于校验矩阵的编码算法传统的直接编码适用于任意结构的LDPC码，但缺点在于编码过于复杂。RU算法是一种可解决该问期的有效算法，主要思想是利用校验形矩阵具有的稀疏性来尽量减轻编码的运算量也这种算法为了能得到一个近似下三角矩阵，会依靠行列置换来改变校验矩阵H ,这么变换的好处就在于原来矩阵所具有的稀疏性会被保留。如图二3所示：通过等中方法将原来矩阵分成六个分块的稀疏矩阵，图中显示的G尽可能小。图错误！文档中没有指定样式的文字。3校验矩阵分斛示

13、意图现在假设信源s的长度是K = NM ,并且 =（S,P1，P2）被编码成码字向量,其中匕、P2都定义成校验向量，长度分别是：G和M - G。具体编码步骤如下:首先对M * N维矩阵H做行、列变换，得到H矩阵的形式为：A B TC D E 计算信源向量的上校正子Z=Ast(2)找出第二个校验向量的临时值，使得上校正子为零P2X = T-Iz(3)接着计算向量的下校正子Zs =C5t -EP?a(4)首先要做的就是准备求第一个检验向量Pi。由矩阵(该矩阵必须可逆)F = -ET -IB +D来求逆矩阵，该计算完成一次的复杂度。(G2 ),这个逆矩阵是一个G*G维高密度矩阵。现在假设第一个校验向

14、量pJ=_F-%(5)接着放弃临时检验性向量，但是要找出新的有效地且符合条件的上校正 子(可以在线性时间完成)：Zc = Za+BPi1(6)接着求解出上面提到的P2的值，同样必须使上校正子满足全为零(利用 回代算法在线性时间内求出pF =上述RU算法，利用了校验矩阵的稀疏性，适用于任1可基于稀疏校验矩阵的 编码。整个编码流程的示意图如下：要错误！文档中没有指定样式的文字。4 RU编码算法漏呈图3 LDPC码译码算法3.1 BP算法BP算法（Belief Propagation Algoritlun ）是一类较重要的消息传递算法，该 算法经常用在人工智能等领域中。算法中各个节点之间传递的信息是

15、概率或置信 信息，例如由变量节点V传递给校验节点S的信息是M取某些特定值的概率信 息，该信息的具体取值依赖于M的观测值和其他所有与V1相连的校验节点（q 除外）在上一轮迭代中传递给后的置信信息，同样的，由q传递给V1的信息也 是9取某些特定值的概率信息 该信息的取值依赖于其他所有与q相连的变量节 点（M除外）在上一轮迭代中传递给的置信信息冷3.1.1 概率域上的BP算法现在给出信道为高斯白噪声信道（AWGN, AdditiveWliiten Gaussian Noise ），噪声方差表示为。2 ,调制方式为BPSK、概率域上的LDPC码的和积译码算法。其中，码元g £0,1,调制符号

16、为=l-2g ,输出%=芍 + % C (-8, +8)。在接收到情况下，4 = d&= b)的先验概率记为p;(d)= p°(%= d| % )在概 率域上，我们用p：(d)表示第k次迭燥个变量节点的可信度，即第k次迭代时 4 = d的概率；r±(d)表示 = d的第k次迭代时，由j传递给Y的信息；埼(d) 表示' =d的第k次迭代时，由传递给%的信息；A(n)表示变量节点乂所对应 的校验式集合；B(m)表示校验式j所对应的变量节点集合。概率域的算法如下:初始化：迭代次数k = l若假定发送序列先验等概pKu-lbpKulXO.S ,则同时变量节点向校验节

17、点传递初始信息，d(d)=P：(d),Cj£A(%)第一步，检验k是否大于最大迭代次数Max ,如果是，结束这帧的译码，否 则继续；第二步，更新变量节点信息：第n个校验节点收集除了第j个以外的变量节 点传递来的信息心，然后再传递给与其相连的第j个变量节点，更新变量节点为 0或1的概率。由校验节点c1专递给变量节点V,的概率信息为：1一 n (Iq-)3加小)J,ie B(m)一1+ Fl (>2q£(l).(I)z JJ第三步，每个变量节点收集与它相连的校脸节点的概率信息，更新对校验节 点的可信度。计算每个变量节点工上的诚(d);p：(d)=*(d)njT(d)jeA

18、inj其中。为概率归T七因子，保证p：(i)+p：(T) = L在获得第k次迭代每个 变量节点的概率域上的可信度后，可以做硬判决得到一个尝试性的译码输出序列 vko第四步,更新校验节点信息：计算每一个变量节点的后验概率4(d);二/照pj£A(n)1 JU x /(T)=，i，j£A(n)rjn (T)其中夕为酶归T七因子，保证(1)4-(-1)=1。第五步，对每个变量节点4 ,根据p：(d)做硬判决，得到一个输出序列vk , 若P：>0.5则输出为1 ,否则为0 ；如果Vk使得所有校验式满足,则将Vk作为 译码输出，并结束译码，否则k=k+l,跳转到第一步。对数域上

19、的BP算法用LR)表示第k次迭代的对数似然比1«匕(%(_) , L(d)表示第k次迭代的对数似然比In,L(p：)表示第k次迭代的对数似然比111pg)/定义:L(O=a(O(O其中,a（q）=啊（L（q：m），"q"）Tq;定义:0(x) = -lntanh加也如exp(x)-l对数域的BP算法如下:初始化：迭代次数k = l ;对L（*赋初值，L（q）=L（p°）；L（口毋力第一步，检验k是否大于最大迭代次数Max ,如果是,结束这帧的译码,否 则继续；第二步,更新变量节点的对数似然比信息：计算每一个L（亡）；L（r-）=f n x （o）第三步，

20、计算每个变量节点4上的L（p：）；L（P：）=L（琮）+ZL（r）jeAjn）第四步，更近校验节点的对数似然比信息：计算每一个L（）；L&）=L（p：）-L&T）,i£B（m）第五步，对每个变量节点”，根据L（p力做硬判决，得到一个输出序列V、； 若L（p：）大于0 ,则输出为1 ,否则为0 ；如果V、使得所有校验式满足，则将丫卜 作为译码输出，并结束浮码，否则，k=k+l,跳转到第一步。无论是概率域的BP算法还是对数域的BP算法，它们所需要的存储量基本 是相同的，因为LDPC码校验矩阵的稀疏性，两种算法所要的存储量都和码长成 线性关系。在运算复杂度方面，概率域的BP

21、算法需要做大量的乘法运算，而对 数域上BP算法只需要做加法运算，对于对数运算，在定点化实现的时候，可以 通过查表获得。由此可见，对数域的算法利于硬件实现，而概率域的算法适合于 浮点仿真的计算。3.2最小和(Min Sum )算法在对数域的BP译码算法中，对数似然比沿着变量节点和校验节点之间的连 线进行传递，从而在每次译码迭代中提供了关于变量节点的判决信息。但该译码 算法存在以下问题：(1)在每次迭代过程中，大量使用了浮点型运算，由其是采用了很多的浮点 型对数和逐攵运算；(2)由丁在每一次迭彳弋过程中，都要对全部比特和校验信息进行il算，因此， 导致该译码算法的复杂度较高巴为了降低LDPC码的译

22、码算法,我们使用最小和算法实现LDPC码的译码 工作。最小和算法和BP算法相类似，在对数域的BP算法中，定义了 3(x) = -ln tan£x)=帑"'。该国数满足"(x)=y>(x)即 ddx)=x , 因此对于。£。伍(q；m)，可以通过某种近似简化计算，通过>(x)的曲线 可以知道，当X在趋向于0的充分小的去建立,0（x）的上升速度很快,所以, Z。仍（q；m）几乎完全由处q*）中最小的一个值决定最终取值。jeBlmlU/ Z 一minD /L（4）a 11 2（q） min。阵）jeBdniUy jeBimiU在计算L（ p

23、：）和L（* ）的时候，因为后面的计算只需要对这些数据做求最小 值的计算，所以对于高斯白噪声信道的方差人也可以简化掉。L（ p：）=L（*）=yn，j£ A（n）另外L（p：）和L（）这两个变量的更新算法，和对数域BP算法中的更新基 本相同。Min-Sum算法迭代的葡呈图如图二.5所示。其结构基本和BP算法相似， 只是在迭代译码的过程中只有加法和比较大小的运算，运算量和存储量都要比 BP算法N导多，很适合硬件实现。图错误！文档中没有指定样式的文字.5 Mm-Sum译码算法流程图三仿真实验1仿真场景本实验考虑AWGN信道、BPSK调制方式，对LDPC码编译码进行仿真, 验证不同码长与码

24、率下的误码性能，并与Drbo码进行比较。考虑编码部分，由于可变码率的校验矩阵设计在应对不同码长、码率要求时， 除确定扩展因子Z值与截取适当的基本图之外，还需进行灵活地打孔与速率匹 配过程较为复杂，因此本实验中我们依然采用了 802.111】标准中的校验矩阵回，即却码长为648,1296,1944 ；支持的码率为1/22/3,3/4,5/6.木咫居标豁出的基本 矩阵比及相应的扩展因子Z得出校验矩阵”,进而得出生成矩阵G并完成编码。译码部分，采用Min-Sum算法迭代实现，复杂度相较其余BP算法更低。本次仿真首先在固定码率为1/2的条件下，对648、1296、1944三种码长的LDPC码的误码性能

25、分析；其次在固定码长为1296与1944的条#下，对四种不同码率的LDPC码的误码性能进行分析。2仿真结果与分析2.1比较不同码长的误码性能10°CC. LU CO-I-M = 648 =M = 1296 7 = 1944II-上一-一t+ 十*4-4+CodeLength1010310d10 0.20.40.60.811.21.41.6Eb/N0图错误！文档中没有指定样式的文字 .6码率为1/2 ,不同码长下的误码率由图三所示，误码率整体随信噪比增加而降低。而码长越长，误码性能越好。另外，在信噪比较低时，不同码长的误码性能差异不大，当信噪比提升到一定程度时不同码长的误码率差距越来越大，码长的影响更明显。2.2比较不同码率的误码性能10°£ io2 8-I R=1/2 ：I R=2/3 :I R=W4 .R=96.r=10*103Coderate00.511.522.533.544.55图错误！文档中没有指定