LDPC码

1LDPC码编码性能仿真目录第一章LDPC码简介1.1LDPC码分类.............................................................21.2LDPC码编码方法.........................................................31.2.1二进制LDPC码的编码...................................................31.2.2基于高斯消去的编码....................................................41.2.3基于近似下三角矩阵的编码............................................41.2.4循环码的编码........................................................51.3LDPC码的译码方法.......................................................5参考文献.....................................................................6第二章LDPC码的仿真实现2.1实验内容................................................................82.2实验过程................................................................82.3LDPC编码方法...........................................................82.3.1校验矩阵的构造........................................................82.3.2编码算法..............................................................82.4LDPC译码方法...........................................................92.4.1消息传递算法..........................................................92.4.2置信传播算法........................................................102.4.3置信传播算法........................................................102.4.4比特翻转译码算法.....................................................102.5编程思路...............................................................102.6实验结果及分析.........................................................11参考文献....................................................................12第三章卷积码的仿真实现3.1实验内容...............................................................133.2实验过程...............................................................133.3实验原理...............................................................133.3.1卷积码编码原理.....................................................133.3.2卷积码译码方法.....................................................143.4编程思路...............................................................153.5实验结果及分析.........................................................153.6卷积码性能和LDPC码比较................................................16参考文献....................................................................17总结.......................................................................182第一章LDPC简介1993年，DMacKay、MNeal等人对Gallager在1963年提出的一类具有稀疏校验矩阵的线性分组码（linearblockcodes）重新研究，发现LDPC码具有逼近香农限的优异性能，并且具有译码复杂度低、可并行译码以及译码错误的可测性等特点，从而成为了信道编码理论新的研究热点。一方面，Mckey和Luby提出的非正则码将LDPC码的概念推广——非正则LDPC码的性能是目前已知的最接近香农极限的码。另一方面，Richard和Urbank不仅提出了一种新的编码算法，也在很大程度上改善了随机构造LDPC码编码上的巨大的运算需求和存储量需求。同时还发明了密度演讲理论，此理论能够有效分析出一大类LDPC译码算法的译码门限。近年来，对LDPC码不断地深入研究与改进，使得LDPC码在众多领域得到了广泛的应用。1.1LDPC码的分类LDPC码有多种分类方法[1]。①按照LDPC码稀疏矩阵中每行或每列1的个数是否一样，可分为规则码和不规则码；②按照LDPC码稀疏矩阵中元素如何取值可分为二进制码（二元LDPC码）和高阶有限域GF（q）（q=2m）码（非二元LDPC码）；③按照LDPC码稀疏矩阵中非0元素位置如何构造可分为随机码和结构型（代数和组合型）；④按照LDPC码稀疏矩阵中元素如何约束可分为LDPC分组码、LDPC卷积码和广义LDPC码等。LDPC码本质上是一种线性分组码，它通过一个生成矩阵G将信息序列映射成码字序列，转换成被传输的码字S，即有S=GTT[2]。对于生成矩阵G，完全等效地存在一个稀疏校验矩阵H，所有码字序列C构成了H的零空间，HCT=0[2]，即分组码是一组线性校验方程的解，每一行对应一个校验方程，每一列对应码字的一位。设k个向量为：g1=[g11g12…g1,kg1,k+1…g1,n]g2=[g21g22…g2,kg2,k+1…g2,n]gk=[gk1gk2…gk,kgk,k+1…gk,n]任何码字都可以由这些基的线性组合生成。即：3G=如果信息序列u=[u1u2…uk]是由k个信息码元组成的信息组，则其编码后的码字为：C=uG=[u1u2…uk]1.2LDPC码编码方法下面介绍LDPC规则码的编码方法。所谓LDPC规则码，是指其校验矩阵每一行和每一列的“1”的个数是相同的，分别为q和p；其Tanner图中比特节点的度和校验节点的度分别对应着一个固定值，通常用（n，p，q）表示，其中n表示码长，p表示信息节点的度，q表示校验节点的度。因稀疏校验矩阵非零元素的随机排列和稀疏性直接影响着编码和译码的复杂度和LDPC码的性能，反应在二分图上对编码性能的影响就是图中的环的长度，所以LDPC码在编码中最主要的就是构造一个高性能的稀疏校验矩阵，由稀疏校验矩阵我们可以很容易求得生成矩阵G。目前LDPC码编码方法主要有：二进制LDPC码的编码、基于高斯消去的编码、基于近似下三角矩阵的编码与循环码的编码。1.2.1二进制LDPC码的编码其基本思想是通过构造单位矩阵确定稀疏校验矩阵每一行和每一列的“1”值。一个码长为n在GF（2）域上的LDPC码的稀疏校验矩阵Hm*你可以表示为H（n，p，q）应当满足如下定量和定性要求。①矩阵每行非零元素个数为q，每列非零元素个数为p，qp≥3,m/n=q/p。②任意两行或者任意两列的相叠非零元素个数不大于1，即不能出现四线循环，如果出现，对于稀疏校验矩阵来说，就不一定是满秩的，因为在编码过程中会用到逆矩阵，如果稀疏校验矩阵中的某一部分不能保证满秩，则在编码过程中就会受到很大影响，甚至出现不能进行编码的现象。③非零元素的位置按行或按列尽量随机排列，且分布稀疏。④分组长度尽量长（如大于103）。⑤某个子矩阵的逆矩阵存在（在GF（2）域）。为了满足以上条件，对于1的分布及个数的满足采用先以对角线满足个数，再把小块的稀疏矩阵随机打乱，来进行构造。其步骤如下：①首先进行校验矩阵的布局设计，设a1，a2,a3为3个长为n/2的全1矢量，使a2在4主对角线位置，a1在对角线下距离1的位置，a3在对角线上距离为2的位置。②每一矢量在大小为n/2方阵的次对角线上布局剩下的剩余部分，可折叠往上分布，任意两行或两列1相重叠的个数不大于1，这样得出的线是平行的。③再将3条全1矢量按列或按行随机置换，满足随机性。排列虽随机，因是初等变换，不改变矩阵的秩，能满足求逆要求。（a）（b）（c）图1对角线法的示意图（b）（C）为随机排列后的矩阵1.2.2基于高斯消去的编码[2]将编码后的码字x分成两部分x=（s，p），其中s代表系统比特，p代表校验比特，则系统编码可分为以下两个步骤：①将要传输的N-M个信息比特直接赋值给系统s；②对于第i（i=1,2，…M）个校验比特pi可通过后向递推得到，pi=Sj+pj。1.2.3基于近似下三角矩阵的编码图2近似下三角矩阵＝[2]5令x=（s，p1，p2），s代表系统比特，p1与p2代表校验比特，长度分别为g和M-g，可以通过下式分别递推出两部分校验比特。[3]通过前人分析可以求解p1的运算量为O（N+g2），p2的运算量O（N）。由上面对该简化得编码算法的运算量分析可知，只要使g的值尽量小就可以接近线性的编码复杂度。1.2.4循环码的编码所谓循环码是指如果一个（n，k）线性分组码C，如果C中的每一个码字的每一个循环移位都是C中的码字，则C是一个循环码。在循环码中，存在唯一一个次数为n-k的码多项式g（x）=1+g1x+g2x2+…gn-k-1xn-k-1+xn-k，使得循环码中其他的码多项式都是g（x）与另外一个多项式的乘积，即v（x）=u（x）g（x）[4]。循环码可以由g（x）确定，称为码的生成多项式。如果循环码的生成多项式为g（x），则由其得到的k个多项式g（x），xg（x），x2g（x）,…xk-1g（x）是线性无关的，因此得到的循环矩阵为：G=设待编码的消息数据为m=(m0,m1,…,mk-1),相应的消息多项式为m（x）=m0+m1x+…+mk-1xk-1。则循环码的步骤如下：①用xn-k乘以消息多项式m（x）；②用生成多项式g（x）除xn-km(x)得到余式b（x）(校验位多项式)；③构成码字多项式c（x）=xn-km（x）+b（x）；1.3LDPC码的译码方法LDPC码编码是在通信系统的发送端进行的，在接收端进行相应的译码。LDPC码的译码算法研究主要集中在基于概率（软消息）的置信传播（BeliefPropagation）迭代译码算法（简称BP算法）[5][6]和基于校验矩阵和统计迭代的比特翻转（BitFlipping）译码算法（简称BF算法）上。BF算法属于硬判决译码算法，其译