LDPC码全面介绍ppt

密码学概述LDPC码（LowDensityParityCheckCode）李风光LDPC简介LDPC规则码的对角线构造方法Gallager概率译码算法LDPC编码BP算法LDPC历史1960年，由Gallager提出。但是由于计算复杂度超出当时的计算能力，LDPC码被人们所遗忘。1981年，Tanner提出编码的图形结构表示方法，这为LDPC解码算法的简化奠定了基础，促进了LDPC的复苏。1996年，MacKay和Neal重新发现LDPC码，并指出LDPC的优秀性能可以逼近Shannon极限。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规则码的对角线构造方法一个码长为n在上的LDPC码的稀疏检验矩阵H可以表示为H（n,p,q）应当满足如下要求：(1)矩阵每行非零元素个数为q，每列为p,pq2,m/n=p/q。(2)任意两行（列）位置相同非零元素的个数不大于1.(3)非零元素个数尽量随机排列，且分布稀疏。(4)某个矩阵的逆矩阵存在（在二元域上存在）2GF对角线法思想：对于1的分布及个数的满足采用先以对角线满足个数，再把小块的稀疏矩阵随机打乱以规则码H(8,3,4)为例矩阵的行数为6，先进行矩阵布局设计，设a,b,c为三个长为8的全1矢量，使a在左边方阵主对角线下距离1的位置，b在主对角线位置，c在上距离为2的位置。每一矢量的剩余部分，折断往上分布，适当调整使任意两行、列相重叠的个数不大于1，如图(a)。然后可以对矩阵的行或列随机排序（都是初等变换）得到图(b)所示101001101101000101101010001101010101101010001101a101001010111001011001100100100110100111000111001b100000000100000000100000000100000000100000000100a100000001100000001100000001100000001100000001100a101000001101000001101000001101000001101000001101aLDPC系统码的编码一般系统线性分组码的编码C=mG=[m¦mP]一般编码方法用于LDPC码会产生的问题G的维数巨大，G一般也并不稀疏。比如一个（10000，5000）LDPC码，P矩阵将是5000×5000矩阵。假设“1”的密度是0.5，编码所作的运算也有0.5×(5000×5000)=12.5×106次（注：H在系统化之前是稀疏矩阵，系统化后不一定。）简化编码的方法之一是利用代数或几何途径来设计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编码方法的研究：如何利用校验矩阵的稀疏性有效的进行编码，其目的是使编码复杂度随码长呈线性增长。上述近似下三角方法的复杂度近似为：2nOgLDPC译码Gallager概率译码算法BP算法硬判决：对信道的输出作出是0还是1的判决。软判决：不作出01判决，只输出有关信息，如0、1的后验概率。软判决译码算法：对信道输出的软判决序列进行译码的算法就叫软判决译码算法。Gallager概率译码算法和BP算法都是软判决译码算法。其目的都是利用码字中其他所有比特的信息来修正该比特的后验概率，就可能得到该比特的最佳后验概率，然后判决它为0或1。Gallager概率译码算法对码字的某一比特，包含它的校验方程可能不止一个，这些校验方程的其他比特又可能包含在更多的校验方程之中。为表示这种关系，引入校验集合树概念。d(1,1)(1,2)根节点d表示比特d，和d相连的每一条边表示包含d的一个校验方程，如11120dcccGallager概率译码算法其中S表示包含d的所有校验方程成立这一事件令1|ddPPcydd 1ilPl表示的校验集合树第一层中包含的第i个校验方程的第个比特为的概率，那么有：111111120|,11|,112kjilddlkiddillPPcySPPcySPPd1|,dPcyS如何求比特的最佳后验概率？Gallager概率译码算法证明：我们先证以下结论m  1llPlm一个长为的相互独立的二进制序列，其中第个比特为1的概率为，那么序列中包含偶数个1的概率是11122mllevenPP考虑关于t的m次多项式11mlllftPPtGallager概率译码算法由二项式分布知道的系数正是序列中包含i个1的概率。再考虑：it11mlllgtPPt差别仅在于其的奇次幂系数是负的。把两多项式相加，然后令t=1，并除以2，就得到序列中包含偶数个1的概率是：it11111211222mmmlllllllevenPPPPPGallager概率译码算法同理，可以得到序列中包含奇数个1的概率为111212mlloddevenPPP根据条件概率定义有0|,0,,1|,1,,ddddPcySPcySPcySPcyS[][0|][|0,][][1|][|1,]ddddPyPcyPScyPyPcyPScyGallager概率译码算法|0,1|1,ddddPScyPPPScy当，包含d的j个校验方程成立的条件是每个校验方程中其余k-1个比特中含有偶数个1，由前面的公式有：0dc111112|0,2kljldlPPScyGallager概率译码算法同理有111112|1,2kljldlPPScy代入即得111111120|,11|,112kjilddlkiddillPPcySPPcySPPGallager概率译码算法概率译码算法：对每一比特，给出校验集合树，利用公式从顶层开始逐层计算各节点后验概率，直到求出根节点的后验概率，然后判决该比特是0还是1。11|,0.50dddcPcySc若其他BP算法符号的定义：:1mllmlLmLmxH设表示与校验节点s相连的所有变量节点x的集合即:1lmmmlMlMlsH设表示与变量节点x相连的所有校验节点s的集合即\0,1xmlxmllximllmlmqMlmxxxqxsqixs，表示基于接收信号并根据校验节点集合得出的的概率，，可以认为，表示第次迭代是向传递的信时向息传递的信息BP算法'':\sxxmllmlmxmlmlximlmlrxxqlLmlrisrxsx，表示，并给定其他比特的一组概率时，校验节点对应的方程成立的概率，，表示第次迭可以看作是向传递的信息代时向传递的信息'''0,1,\0,12iimlmllLmlimlqqr'''0,1,\1,12iimlmllLmlimlqqrBP算法1,00,01111(1),1mlmllmlllqfqff对所有满足H的m,l执行以下步骤初始化：，为信道得到的概率''''''0,1,0,1,\\0,1,1122iiiimlmlmlmllLmllLmliimlmlqqqqrr(2)校验节点信息更新：，''''0,10,1,11,01\\0,11,1(3)1iiiimlmllmlmllmlmlmMlmmMlmiimlmlmlqaprqapraqq变量节点信息更新：其中是一个使的值。BP算法0,10,1,10,010,11,1(4)1iiiilllmllllmlmMlmMliilllqaprqapraqq计算后验概率其中为使成立的值。0,1(5)0.5,0,11,20,illTqxlnxx比特判决：若则判反之为，。若H或者迭代次数到达最大值，则结束迭代，输出；否则转到第二步继续迭代。BP算法1s2s3s4s1x2x3x4x5x6x7x8x1110001121111211(1),qqfqqf初始化0101013355770101011111313151(2),,2ffffff计算rr,rr,rBP算法0001110111111211111121111111(3)(1qafrqafraqq计算为使的值)00011101111121111121111(4)(1qarrqarraqq计算为使的值)0111(5)0.50,10lTqxxxHx若则反之计算出所有后成立则结束，否则回到(2)。迭代译码算法的变种：上述算法表示不够简单，采用很多相乘运算，且要分别计算0和1的概率，所以在此基础上对消息的表达式有很多变种，使得算法表述更洁且更利于实现（对数似然比表示的BP算法）谢谢!