LDPC码实现及性能研究解析

《LDPC码实现及性能研究解析》由会员分享，可在线阅读，更多相关《LDPC码实现及性能研究解析（21页珍藏版）》请在装配图网上搜索。

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

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

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

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

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

6、对应的“阵又 可由相应的二分图表示，称为该码的Tanner图。Tanner图中的变量(比特)节 点对应至“矩阵中的每一列，也即对应LDPC码的每一码比特；Tanner图中的校 验节点分别对应到H矩阵的每一行，也即对应LDPC码中的校验I：缩。两类节点 之间的连接情况对应H矩阵中元素的取值：若第i个校验节点与第j个变量节点 之间存在连接，则代表H矩阵的(ij)个元素取值为1 ；若无连接则对应元素为零。 图二.1与图二.2分别是一个(16,8)LDPC码的H阵与Tamiei图。Bit NodeCheck Node图二.2 (16,8)LDPC 码 Taimer 图在码长较长的情况下，LDPC码的“

7、矩阵会十分庞大。因此通常将H矩阵分 块表示：完整的H矩阵视作由多个Z*Z的子矩阵生成，原始的“矩阵即可由一个 mb x队的基本矩阵比表示（频=上，取=乙），比中每一元素对应一个Z*Z子 ZZ矩阵，z被称为扩展因子。其中准循环LDPC码（QC-LDPC ）较为常用，其特 点在于每一子矩阵为全零方阵或单位阵向右循环移位得到的置换矩阵，因此各子 矩阵都可由循环移位的位数表示，H阵所需存储空间极大减小。另外子矩阵可由 循环移位得到，也更易于硬件实现。1.2 可变速率的校验矩阵设计传统的LDPC码中，每一H阵都分别对应一个码率与码长。而在对不同的码 率、码长的要求越来越多的情况下，这种对需要对不同要求分

8、别设计不同“阵的 方法较为繁琐。因此1中提出了一种可兼容不同码率与码长的H阵设计方案，这 种兼容性主要通过嵌套的基本矩阵（图）与可变的扩展因子Z实现。121嵌套的基本图基本矩阵（图）由是嵌套的子图的集合，即可从该集合中最大的基本图中截 取部分形成新的基本图以应对不同码长、码率要求。其中每一子图由一相对高码 率的核心图与IR-HARQ扩展构成：核心图由包括2个打孔节点的信息位与校验 位构成，其中校验位结构与802.1111标准中类似；IR-HARQ扩展由核心图中比 特进一步校验生成。子图构成的集合设定最大,最小信息比特数与最大/最小校验比特数，即并由 此可计算出该基本矩阵可实现的码长与码率范围。

9、1.2.2可变的扩展因子扩展因子z可由不同码长、码率要求取不同的值，取值集合被分为不同的 群组，相同群组内的z取值对应的扩展子矩阵移位情况相同。因此，由可变的基本矩阵与扩展因子Z的不同取值，可实现不同码长与码 率的LDPC校验矩阵。2 LDPC码编码算法2.1 直接编码算法直接编码方法的大致思路是：利用高斯消去法将M*N的校验矩阵”变换成 H'= P I,因为校验矩阵H的不确定，所以在变换过程中可能会涉及到初等行列 变换。如果进行了初等行列变换,则同时要记录下这些行列变换信息。如果校验 矩阵H满足线性相关的，将会删去相关的行，那么这种情况下，LDPC码的码 率由该校验矩阵确定，其值将大

10、于1 - K/ N ；然后，根据系统形式的校验矩阵H' = P I,得到其对应的生成矩阵G = I Pro如果在生成系统形式的校验矩阵的过程中没有进行初等行列变换，则有 HGT = 0,否则HG7丰0 ,而对于将校验矩阵H进行行列变换的依据则是根 据记录之前记录下的行列变换信息。最后,m为信息序列，则编码后的序列为c = m-Go需要说明的是，如果 在生成系统形式的校验矩阵的过程中进行了初等行列变换,则需要使用进行过相 应的初等行列变换的校验矩阵H进行译码。上面思路基本适用于对任意结构的LDPC码进行编码彳导到的编码复杂度 往往与码长成正比。由于这种编码算法的计算复杂度过于庞大，且会占

11、用过大的 存储空间。因此，不适合于硬件实现，这也是早期阻碍LDPC码发展的原因之2o由于LDPC码的码长n很大,同时很多性能优良的LDPC码都是采用随机 方式构造的，这就导致使用上述方法得到生成矩阵G的运算量很大。为降低编 码复杂度，现在已发展出多种已经简化的编码方法，而下面将讨论的这种编码算 法就被视为一种高效的LDPC码编码算法，而且应用广泛。2.2 基于校验矩阵的编码算法传统的直接编码适用于任意结构的LDPC码，但缺点在于编码过于复杂。 RU算法是一种可解决该问题的有效算法，主要思想是利用校验形矩阵具有的稀 疏性来尽量减轻编码的运算量1*这种算法为了能得到一个近似下三角矩阵，会依靠行列置

12、换来改变校验矩阵 H ,这么变换的好处就在于原来矩阵所具有的稀疏性会被保留。如图二.3所示： 通过某种方法将原来矩阵分成六个分块的稀疏矩阵，图中显示的G尽可能小。图二.3校验矩阵分解示意图现在假设信源s的长度是K = N-M ,并且x = (s,Pi ,22 )被编码成码字向量, 其中P、P2都定义成校验向量，长度分别是：G和M - G。具体编码步骤如下：首先对M * N维矩阵”做行、列变换，得到H矩阵的形式为：ABTC D E计算信源向量的上校正子Z=Asr(2)找出第二个校验向量的临时值，使得上校正子为零尸 2、LZ接着计算向量的下校正子Zs = Csr - EP1A(4)首先要做的就是准

13、备求第一个检验向量由矩阵(该矩阵必须可逆)F = -ET 1B + D来求逆矩阵,该计算完成一次的复杂度。(G2 ),这个逆矩阵是一个G*G 维高密度矩阵。现在假设第一个校验向量P； = _ 广接着放弃临时检验性向量，但是要找出新的有效地且符合条件的上校正 子(可以在线性时间完成)：(6)接看求解出上面提到的P2的值，同样必须使上校正子满足全为零(利用 回代算法在线性时间内求出IpF = -Lz上述RU算法，利用了校验矩阵的稀疏性，适用于任基于稀疏校验矩阵的 编码。整个编码流程的示意图如下：图二.4 RU编码算法流程图3 LDPC码译码算法3.1 BP算法BP算法(Belief Propaga

14、tion Algontlun )是一类较重要的消息传递算法，该 算法经常用在人工智能等领域中。算法中各个节点之间传递的信息是概率或置信 信息，例如由变量节点必传递给校验节点q的信息是片取某些特定值的概率信 息，该信息的具体取值依赖于v,的观测值和其他所有与“相连的校验节点(q 除外)在上一轮迭代中传递给"的置信信息，同样的，由q传递给M的信息也 是。取某些特定值的概率信息，该信息的取值依赖于其他所有与q相连的变量节 点(“除外)在上一轮迭代中传递给的置信信息用。3.1.1 概率域上的BP算法现在给出信道为高斯白噪声信道(AWGN, Additive Whiten Gaussian N

15、oise ),噪声方差表示为。2 ,调制方式为BPSK、概率域上的LDPC码的和积译码算法。其中，码元。£0,1,调制符号=1 - 2Cj ,输出乃=%+巧 e (-co,+oo)0在接收到情况下，七=4匕=b)的先验概率记为p：= p°(xn = d I尤)在 概率域上,我们用”表示第k次迭代某个变量节点的可信度，即第k次迭代 时 =4的概率力/)表示 ="的第斤次迭代时，由。传递给匕的信息；或(内 表示A； = d的第k次迭代时，由匕传递给c；的信息；4)表示变量节点v,所对应 的校验式集合；以表示校验式5所对应的变量节点集合。概率域的算法如下:初始化：迭代次

16、数k=1若假定发送序列先验等概p(x”=-l) = (4=1) = 05 ,则同时变量节点向校验节点传递初始信息，q：(d) = P：(d),CjWA(匕)第一步，检验上是否大于最大迭代次数Mg ,如果是，结束这帧的译码，否 则继续；第二步，更新变量节点信息：第个校验节点收集除了第，个以外的变量节 点传递来的信息勾，然后再传递给与其相连的第1个变量节点，更新变量节点为 0或1的概率。由校验节点J传递给变量节点匕的概率信息为：1- n(i-2啕)燎/，如"、8(?)淄（T=1+ n（i-24）219/19第三步，每个变量节点收集与它相连的校验节点的概率信息，更新对校验节点的可信度。计算

17、每个变量节点匕上的“ (d)；:3) = ap0(d)n 限(d)其中。为概率归一化因子，保证p：(l) + p；(_l) = l。在获得第"次迭代每个 变量节点的概率域上的可信度后，可以做硬判决得到一个尝试性的译码输出序列第四步，更新校验节点信息：计算每一个变量节点的后验概率确(d)；或'初 1)或(-1)=4,/“()rjn LU其中?为概率归一化因子，保证力(1)+或(_1)=1。第五步，对每个变量节点匕,，根据做硬判决，得到一个输出序列丫 若p；(l)> 0.5则输出为1 ,否则为0 ；如果H使得所有校验式满足，则将H作为 译码输出，并结束译码，否则攵乂+ 1

18、,劭炼专至IJ第f。对数域上的BP算法用”点)表示第k次迭代的对数似然比In点,L(编)表示第k次迭代的对数似然比m,l(p：)表示第k次迭代的对数似然比中"%-1）定义：L% = a（4”）夕（媒）其中,0（或） = s，g（L（媒），"（点）=脸| ；定义：（1exp（x）+l（p（x） = -n tanh x = In- 2exp（x）-l对数域的BP算法如下：初始化：迭代次数攵=1 ；对L）赋初值，"%；） = "：；）；“球）=嘲=2%第一步，检验上是否大于最大迭代次数族，如果是，结束这帧的译码，否 则继续；第二步，更新变量节点的对数似然比信息

19、：计算每一个“播）;l（点）=n。（端J。z。（尸（力”）第三步,计算每个变量节点为上的L（4）；暖）第四步，更近校验节点的对数似然比信息：计算每一个”力.）；L&） = “4 ）一心（点£ 8（/）第五步，对每个变量节点匕根据乙（片）做硬判决，得到一个输出序列H ； 若以武）大于0,则输出为1 ,否则为0 ；如果V*使得所有校验式满足,则将H 作为译码输出,并结束译码，否则，&=+1,劭林专到第 f。无论是概率域的BP算法还是对数域的BP算法，它们所需要的存储量基本 是相同的，因为LDPC码校验矩阵的稀疏性，两种算法所要的存储量都和码长成 线性关系。在运算复杂度方面

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

21、码的译码算法，我们使用最小和算法实现LDPC码的译码 工作。最小和算法和BP算法相类似,在对数域的BP算法中,定义了 (x) = -ln tanh Lv = In 三出。该函数满足 / (x) = p(x)即 9(Q(x) = x ,2 y exp(x)-l因此对于/ Z。伍*),可以通过某种近似简化计算，通过9(x)的曲线可以知道，当X在趋向于0的充分小的去建立，e（x）的上升速度很快，所以， Z 0（A（皈）几乎完全由网公“）中最小的一个值决定最终取值。/ Z -）" minP（力，JJei?（7W）r）l（瑞卜 II a （或）jminP（或）在计算l（M）和l（4）的时候，因

22、为后面的计算只需要对这些数据做求最小 值的计算，所以对于高斯白噪声信道的方差b?也可以简化掉。L（P；） = L） = yd5）另外“：）和L（力）这两个变量的更新算法，和对数域BP算法中的更新基 本相同。Min-Sum算法迭代的流程图如图二.5所示。其结构基本和BP算法相似， 只是在迭代译码的过程中只有加法和比较大小的运算，运算量和存储量都要比 BP算法小得多，很适合硬件实现。/倒始化，对L(P)；L(qj 赋初值更新校验节点 计算L(r)更新变量节点计算L(q)计算L(p)根据L(p)做出硬判决得到码字V输出码字Vk = k+1图二.5 Mm-Sum译码算法流程图三仿真实验1仿真场景本实验

23、考虑AWGN信道、BPSK调制方式，对LDPC码编译码进行仿真， 3佥证不同码长与码率下的误码性能，并与Turbo码进行比较。考虑编码部分，由于可变码率的校验矩阵设计在应对不同码长、码率要求时, 除确定扩展因子Z值与截取适当的基本图之外，还需进行灵活地打孑疗速率匹 配，过程较为复杂，因此本实验中我们依然采用了 802.1 In标准中的校验矩阵, 即支持码长为648,1296,1944 ；支持的码率为1/2,2/3,3/4,5/6根据标准给出的基本 矩阵儿及相应的扩展因子Z得出校验矩阵H ,进而得出生成矩阵G并完成编码。译码部分，采用Min-Sum算法迭代实现，复杂度相较其余BP算法更低。本次仿

24、真首先在固定码率为1/2的条件下，对648、1296、1944三种码长的 LDPC码的误码性能分析；其次在固定码长为1296与1944的条件下，对四种不 同码率的LDPC码的误码性能进行分析。2仿真结果与分析2.1 比较不同码长的误码性能图三.1码率为1/2 ,不同码长下的误码率由图三.1所示,误码率整体随信噪比增加而降低。而码长越长，误码性能越 好。另外,在信噪比较低时,不同码长的误码性能差异不大，当信噪比提升到一 定程度时不同码长的误码率差距越来越大，码长的影响更明显。2.2 比较不同码率的误码性能图三.2码长为1296 ,不同码率下的误码率图 二.3码长为1944 ,不同码率下的误码率由

25、图中可以明显看出，在两种固定码长情况下，码率的增加均使得误码率显著升高，也即相同码长下误码性能的提高需要通过降低码率来实现，尤其在信噪比较低的情况下。这也反映了传输有效性与可靠性的折中关系。图中还可以看出在码长为1944时误码性能相较于1296码长时更优。本次的仿真实验，首先通过对经典文献和理论的学习，我们对LDPC码有了 大致的了解；随后依照校验矩阵生成、编码算法、译码算法三个部分查找文献资 料，对LDPC码编译码原理进行了更深入的学习，并就各个部分在系统中的衔接 与联系互相交流，实现了整体的编解码过程以及对误码性能的分析验证。本次实验也存在不足之处：由于对可变速率编码中的打孔以及速率匹配部

26、分 理解不够，未能实现兼容多种码率与码长的校验矩阵设计。在之后的学习科研中 可对此内容进行更深入的研究，以完整掌握可变速率编码的实现。参考文献1 “LDPC rate compatible design”, Rl-166388, Qualcomm Iiicoiporated, Gothenburg, Sweden2张晨.高吞吐量LDPC码编码构造及其FPGA实现上海交通 大学,2008.3. "Efficient encoding of low-density parity check codes”, Urbanke T R R, Richardson T.正EE Trans, on Infonn. Theory, 2001, 47(2): 638-656.4尹晓琦. LDPC码编码及译码算法的研究D.南京：南京师范大学,2006.5廖薇，刘锦昌h基于最小和的图效LDPC译码算法D.上海：华东师范 大学,2009.6为EEE 802.1111 Wireless LAN Medium Access Control MAC and Physical Layer PHY specifications”，IEEE 802.11n-D2.0, 2007