ldpc码的编译码算法研究本科毕业论文(编辑修改稿)

ldpc码的编译码算法研究本科毕业论文(编辑修改稿)内容摘要：

TC s E 1 T（ T As ） O（ n） 稀疏矩阵和向量相乘 向量的减法运算 1TC s EF   1 T（ T A s ） O（ n） 矩阵的求逆运 算 高密度矩阵和向量相乘 表 3． 2 计算 2Tp 的复杂度 操 作 复 杂 度 备 注 A Ts O（ n） 稀疏矩阵和向量相乘 1TBP O（ n） 稀疏矩阵和向量相乘 A Ts + 1TBP O（ n） 稀疏矩阵和向量相乘 向量的加法运算 1T (A Ts + 1TBP ) O（ n） 稀疏矩阵和向量相乘 10 例 一个 (12,3,6)LDPC 码的校验矩阵如下： 将列重新按下序排列： 1， 2， 3， 4， 5， 6， 7， 10， 11， 12， 8， 9 得到一个g =2 的近似下三角矩阵为 用高斯消元法消去矩阵 E ，得到 可以看到 1 11U E T B + D = 11  矩阵 U 是奇异矩阵 ，这种奇异性可以通过交换列 5， 8 来消除。 于是最终列的排序为： 1， 2， 3， 4， 10， 6， 7， 5， 11， 12， 8， 9。 对应的等价矩阵为 11 假设待编码的信息比特为 s = (1 0 0 0 0 0)，按照上述步骤计算：  TTA s 1 1 0 1  T1 TT A s 1 1 0 0   T1 TT A s 0 0  TTCs 0 0   T 1 T T E T A s C s 0 1         T 1 1 T T T1U E T A s + C s 0 1 = P  根据得到的 1p 计算 2p  TT1B p = 0 1 0 0  TTT 1A s B p 1 0 0 1         T1 T T T12T A s B p 1 0 1 0 = p  因此编码得到的码字为    12s p p 1 0 0 0 0 0 0 1 1 0 1 0 将上述码字代入式（ ）进行检验，得到 HcT = 0，因此满足校验方程。 上述有效编码方法，利用了校验矩阵的稀疏性，适用于任何基于稀疏校验矩阵的编码。 4 LDPC码的译码 概述 LDPC码具有良好性能的重要原因之一是 LDPC码采用了基于置信传播的迭 代译码算法，这是一种迭代概率译码算法，是 LDPC 码与传统纠错码的重要区别。 MP算法集 信息传递 (Message Propagation， MP)算法是最主要的一类 LDPC 码译码算法，它具有严格的数学结构和良好的性能，使用它能对译码性能做定量分析。 LDPC 码译码算法中很多种都可以被归结到信息传递 算法集中。 信息传递算法的主要思想就是通过在变量节点和校验节点之间来回传递概率似然值，最终找到正确的码字。 这一过程在 Tanner 图上可以直观的表示出来，信息在 Tanner 图中沿着连接变量节点和校验节点的边双向传递。 变量节点接收 12 与它相连接的校验节点送来的节点信息，然后根据这些信息计算出反馈给各校验节点的信息。 校验节点开始接收与它相连接的变量节点送来的节点信息，然后根据这些信息计算出反馈给各变量节点的信息，如此往复形成迭代。 每次迭代结束后，对每个变量节点做判决，得出一个码字，再通过校验矩阵验证码字正确性。 如果译 码成功，则译码结束；否则继续迭代，直到达到预先设定的最大迭代次数。 信息传递算法为了保证传递信息的独立性，每个节点接收的信息都是从除自身之外的其他节点而来。 但是由于现实中所使用的码长都是有限的，使得节点不可能永远收到与自身无关的信息，即存在环的影响。 以一个行重为 cd ，列重为 vd的正则 LDPC 码为例，当前迭代周期中某一变量节点送来的信息直接来自 vd1。 个校验节点， 而这些校验节点所送来的信息又来自与各自相连的以 cd 一 1个变量节点在上一迭代周期中送出的值，如下图所示的树状图表示它们之间的关系。 因此，在 LDPC 码译码过程中环对译码的影响是不容忽视的。 图 节点树 LDPC 码有很多种译码方法，本质上大都是基于 Tanner 图的信息传递译码算 法。 根据信息迭代过程中传送消息的不同形式，可以将 LDPC 的译码方法分为硬 判决译码和软判决译码。 如果在译码过程中传送的信息是比特值，称之 为硬判决 译码，如 BF 算法，它具有较低的译码复杂度，易于工程实现。 但是与软判决译码相比，硬判决译码在性能上要损失约 23dB；如果在译码过程中传送的信息是与后验概率相关的信息，称之为软判决译码，如置信传播译码算法。 虽然软判决算法译码复杂度较高，但可以获得更好的译码准确性，比硬判决译码具有更大的编码增益。 在 AWGN 信道中，它比硬判决译码要多 2dB 左右的软判决增益，而在衰落信道中，软判决增益超过 5dB。 硬判决译码可以看成是 l 比特量化译码， 13 而软判决译码可以看成无穷多比特量化译码。 主要的硬判决译码算法有比特翻转算法 (BF)、加权的比特翻转算法 (WBF)等；软译码算法主要有置信传播算法(BeliefPropagation)、简化的最小和算法 (Minsum)、归一化最小和算法 (Normalized Min． Sum)、偏移量最小和算法 (OffsetMin． sum)等。 硬判决译码算法 比特翻转算法 Gallager 在其论文中提出了硬判决译码算法，该算法是一种比较简单而且容易理解的译码算法，它对运算量和存储量的要求都很低，但是其性能相对比较差。 比特翻转算法 (Bit Flipping Algorithm)可看成是置信传播算法的简化形式，而加权位翻转译码算法是在 BF 算法的基础上加上硬判决译码系数，其性能较比特翻转译码算法有一定程度的提高 比特翻转算法 (Bit Flipping Algorithm)是 Gallager在其论文中提出的被命名为 Gallager 硬判决的译码算法。 设码字 c= 0 1 N1c c ... c， ， ， 为发送序列，经 BPSK 调制为序 列 x= 0 1 N1c c ... c， ， ， ，  iix 2c 1， 0 i N1 ，  0 1 N1r r r ... r ， ， ， 为接收的实数向量序列，由实数序列可以得到硬判决二元向量序列z=( 0 1 N 1z z z， ， ... ， )： iii1 r 0z 0 r 0  ， 当 时， 当 时 （ 41） 由此得到码字伴随式 s=（ 0 1 2 J 1s s s s， ， ， ... ，） = TzH ，若 js0 ，则说明接收向量 满足第 j 个校验方程；若 s=0，则表示接收向量满足所有校验方程，接收码字 z 正 确，译码成功；若伴随式为非全“ 0”向量时，接收序列 z 有错误，此时则需计算出每个码元不满足校验方程的个数 f= 0 1 N1f f f， ， ... ， =sH，搜索 f中的最大值，翻转对应位置的码元 jz。 再重复上述的过程，直到译码成功后达到最大迭代次数。 BF 译码算法步骤如下： (1)根据硬判决二元向量序列得到码字 的伴随式 s，判断 s 是否为全“ 0”，如果为全“ 0”，则译码成功，否则转 (2)； (2)计算 f，并找出其最大值 jf =max{f}，翻转对应位置的码元 jz ； 14 (3)将得到的新的向量序列代替原向量，转 (1)，如满足伴随式全为“ 0”，译码成功，跳出，否则重复上述步骤，直到达到最大迭代次数。 由于校验矩阵为稀疏矩阵，而且一般为随机构成，所以参与每个校验方程的比特很少，且这些比特在码字上分布很分散，那么任一校验方程所含的 比特要么 无错，要么以很高概率的只有一个比特错误， BF 算法就可以有效地进行纠错。 即使某一校验方程发生多于一个错误，纠错仍可以进行。 但是相对的牺牲的就是译码性能，所以下面对于硬判决译码算法提出了一种加权硬判决译码算法，它是在 BF 算法基础上进行了一定的改进，在性能上有了一定的提高。 加权比特翻转译码算法 在译码接收端通过添加一些可信信息将可以提高 BF 算法的纠错性能。 那么，加权比特翻转译码 (WBF)算法就是在选择需要翻转的变量节点的时候，将每一个码字中不满足校验方程个数最多的码元的信道输出信息作为该判决 式的权重信息。 设译码器接收端的输入信息为  0 1 1, , . . . ,Ny y y y x w  ，其中 0 1 1, , ...,Nx x x x 是经过调制后的信息，  0 1 1w , ,..., Nw w w  为加性高斯白噪声。  mnH= H  为校验矩阵，    mnN m n H 1： 表示与校验节点 m 相连的变量节点，    mnm n m H 1： 表示与变量节点刀相连的校验节点。 因此， WBF 算法的一般步骤如 下，其中 m=0， 1， ⋯， M－ 1， n=0， 1， ⋯， N－ 1： (1)根据硬判决二元向量序列 z 得到码字的伴随式为 s，判断 s 是否为全“ 0”， 如果为全“ 0”，则译码成功，否则转 (2)； (2)计算 iminy {min y } ： 0iN－ 1， n∈ N(m)； (3)对于 n=0， 1， ⋯， N－ 1，计算 n m M ( ) m inE = (2 1)nmsy  ，并找出其中最大的值 max{ }jnEE ，翻转对应位置的 jz ； (4)将得到的新的向量序列代替原向量，转 (1)，如满足伴随式全为“ 0”，译码成功，跳出，否则重复上述步骤，直到达到最大迭代次数。 加权译码算法是通过软判决译码算法和附加信息来计算加权校验信息 E，这 种算法虽然比单纯的 BF 算法在复杂度上有了增加，但是却具有更好的译码性能。 15 5 AWGN 信道下 LDPC码的性能仿真 仿真软件简介（ matlabamp。 simulink） MATLAB 软件 MATLAB 在数学类科技应用软件中在 数值计算 方面首屈一指。 MATLAB 可以进行 矩阵 运算、绘制函数和数据、实现算法、创建用户界面、连 接其他编程语言的程序等，主要应用于工程计算、控制设计、信号处理与通讯、 图像处理 、 信号检测 、金融建模设计与分析等领域。 MATLAB 的基本数据单位是矩阵，它的指令表达式与数学、工程中常用的形式十分相似，故用 MATLAB 来解算问题要比用 C， FORTRAN 等语言完成相同的事情简捷得多，并且 mathwork 也吸收了像Maple 等软件的优点 ,使 MATLAB 成为一个强大的数学软件。 MATLAB 包括拥有数百个内部函数的主包和三十几种工具包。 工具包又可以分为功能性工具包和学科工具包。 功能 工具包用来扩充 MATLAB 的符号计算，可视化建模仿真，文字处理及实时控制等功能。 学科工具包是专业性比较 强的工具包，控制工具包，信号处理工具包，通信工具包等都属于此类。 开放性使MATLAB 广受用户欢迎。 除内部函数外，所有 MATLAB 主包文件和各种工具包都是可读可修改的文件，用户通过对源程序的修改或加入自己编写程序构造新的专用工具包。 其中的 Communication Toolbox—— 通讯工具 箱与 Signal Processing Toolbox—— 信号处理工具箱 等在通信方面得到很多应用。 Simulink 仿真 软件 近年来，由于问题域的扩展和仿真支持技术的发展，系统仿真方法学致力与更自然地抽象事物的属性特征，寻求使模型研究者更自然地参与仿真活动的方法。 在这些探索的推动下， MATHWORKS 公司推出的 Simulink 提供了一个系统级的建模与动态仿真的图形用户环境，并且利用 MATLAB 在科学计算上的天然优势，建立起了一个从设计构思到最终要求的可视化桥梁，它的模块化，可以很方便的创建和维护一个完整的模型评估不同的算法和结构并验证系统性能 仿真与结果分析 仿真中采用的信道都是二进制输入的加性高斯白噪声信道，采用的 调制方式都是基带 BPSK调制。 一般在仿真中要获得较低的误比特率需要大量的数据帧，而在码长较长时大量的数据帧的计算要花费很多时间，因此只选定了一些码长相 16 对较短的规则 LDPC码进行了仿真。 而由于受码长和仿真数据量的限制使得仿真得到的性能结果较 LDPC码所能够达到的性能指标有一定的差距。 仿真中所用的是规则的 LDPC码，其校验矩阵使用 Gallager的随机构造的方法生成，具有固定的列重和行重。 由于在编码二分图中长度为 4的圈的存在会导致 LDPC码的误码率性能变得很差，因此构造的校验矩阵在编程上考虑了消除长度为 4的圈。 仿真中选用了码率为 1/2和 2/3，码长分别为 4 9 20 408和 816五种码长的 LDPC码娜l。