LDPC码-zwh

LDPC码（LowDensityParityCheckCode）ByCuz-dreamLDPC简介LDPC编码LDPC码的分类线性分组码简介LDPC译码线性分组码简介主要参数校验矩阵H生成矩阵G信道编码定理每个信道具有确定的信道容量C，对于任何小于C的码率R，存在有速率为R码长为n的分组码及卷积码，若用最大似然译码，则随着码长的增加其译码错误概率p可以任意小。LDPC历史1964年Gallager发表Low-DensityCheck-ParityCode,证明了LDPC码性能接近于香农限，并提出了构建H矩阵的一种方法，以及两种解码方法和示意性的硬件电路原理图，但是由于当时科技水平有限，硬件条件的限制，LDPC码并没有得到重视和推广。1981年，Tanner从图的观点提供了对LDPC的阐释，被忽略。1993年，C.Berrou发明了Turbo码及相关的迭代算法，引起关注。1996年D.MacKay和R.Neal根据人工智能体系使自己的迭代算法和Pearl置信算法建立的联系，并证明了LDPC码性能和成本都优于Turbo码。LDPC特点•性能优于Turbo码，具有较大的灵活性和较低的差错平底特性（errorfloors）；•不需要深度交织以获得好的误码性能；•描述简单，对严格理论分析具有可验证性；•译码不基于网格，复杂度低于turbo码，且可实现完全的并行操作，硬件复杂底低，因而适合硬件实现；•吞吐量大，极具高速译码潜力。因此，结合LDPC无线局域网必将取得更好的性能；•欧洲卫星广播系统DVB－S52采用；•认为是第四代移动通信的信道编码。LDPC码的分类按照校验矩阵列重量分：规则（regular）LDPC码：列重量一致不规则（irregular）LDPC码：列重量不一致按照取值域分：二进制LDPC码：基于GF(2)多进制LDPC码：基于GF(q)(q2)通常情况下，多进制码的性能优于二进制码；同一取值域的LDPC码，不规则码的性能优于规则码。但是复杂度正好相反，规则二进制码最简单，多进制不规则码最为复杂。定义定义：LDPC规则码(N,p,q)定义为具有如下特性的校验矩阵HMXN的零空间：(1)每一行含有q个1；(2)每一列含有p个1；(3)任两行（列）之间位置相同的1的个数不大于1即＝0，1(4)qN，pM(低密度）密度r=q/N=p/M如果各行（列）重量不同，则叫非规则码。Tanner图描述LDPC码基本工具之一是二分图,二分图是一种无向图，基本元素是节点(node)和边(edge)。节点分成两类(class),一条边所连接的两个节点必须分属不同的两类。Tanner图是二分图的具体化。Tanner图里有两类节点:消息比特(messagebit)节点和校验(check)节点，节点间连线表示关联。（n，p，q）=（8，2，4）101010101001010101100110010110011s2s3s4s1x2x3x4x5x6x7x8xLDPC码的构造尽可能大的码距没有短环mindLDPC码的构造LDPC码的构造即校验矩阵的构造：规则码的构造：Gallager的构造方法MacKay的构造方法不规则码的构造：主要是对度分布函数(λ,ρ)的研究12()vdiiixx12()cdiiixx构造过程中要注意消除校验矩阵对应二分图中的短环。LDPC码的编译码原理LDCP码编译码原理：图LDPC码的编译码框图LDPC码的编码◆基于高斯消元的直接编码在获得校验矩阵H后，利用H和G之间的正交性可以用高斯消元法来得到生成矩阵G。LDPC码传统编码算法和一般的线性分组码十分类似，需要求出生成矩阵。若已知长度为k的输入信息向量m，以及k×n的生成矩阵G，码字C就可以容易的得到：C=m×G。从分组码的角度，编码是由稀疏的校验矩阵H通过高斯消元得到生成矩阵G，然后由信息序列和生成矩阵相乘而得。LDPC码的编码◆近似下三角矩阵编码：交换行和列可以将H转化成一个近似下三角矩阵gTBCDEA0n-mm-ggm-g保证T是可逆的将变换后的矩阵H左乘其中I是单位矩阵，得到10IETI110ABTETACETBD设编码码字，其中t为信息位，为检验位。12,,Stpp12,pp1 0,THSETBD根据若可逆。可得1111TTpETBDETACt121TTTPTAtBp注意两点：g应当尽可能的小，0.02746n；保证可逆。1ETBDLDPC译码Gallager提出的译码方法：基于硬判决的树型译码算法基于软判决的迭代译码算法LDPC译码MP算法集LDPC码的译码算法种类很多，其中大部分可以被归结到信息传递(MessagePropagation，MP)算法集中。MP算法是基于二分图结构的译码算法，由于在算法的运行过程中，可靠性信息在二分图的变量节点和校验节点之间来回的传送，因此称为MessagePassing算法。这一类译码算法由于具有良好的性能和严格的数学结构，使得译码性能的定量分析成为可能，因此特别受到关注。Tanner图中的短环会对MP译码算法性能产生很大影响。当二分图无环时，算法译码的性能最好；如果存在环路时，由于多次循环之后无法保证迭代信息的独立，译码的性能会有一定损失。MP算法集中的置信传播(BP)算法是一种软判决迭代译码算法，具有最好的性能。同时，通过一些常用的数学手段，我们可以对BP译码算法作一些简化，从而在一定的性能损失内获得对运算量和存储量需求的降低。BP算法LDPC的译码算法中，最经典的是BeliefPropagation(BP)算法。实际上BP算法也是MP算法的一个特例，是一种软判决的译码算法，该算法中传递的信息是前一级模块软判决输出的概率或似然比，因此是MP算法中最精确，性能最好的一种。LDPC码的优点错误可检测性：基于BP算法的解码过程中，除非超出可检测范围，否则即使超过迭代次数宣布解码失败也不会误解码。并行译码：在解码过程中，无论是校验节点的运算还是信息节点的计算，都是与同层的其他节点无关的。所以如果采用实时性更好的并行译码，弥补LDPC码码长、译码时延大的缺点，将会大大扩展LDPC码的应用领域。LDPC码编译码流程谢谢!