LDPC码全面介绍.ppt

1、1,LDPC码 （ Low Density Parity Check Code ）,李风光,LDPC简介,LDPC规则码的对角线构造方法,Gallager概率译码算法,LDPC编码,BP算法,LDPC历史,1960年，由Gallager提出。但是由于计算复杂度超出当时的计算能力，LDPC码被人们所遗忘。 1981年，Tanner提出编码的图形结构表示方法，这为LDPC解码算法的简化奠定了基础，促进了LDPC的复苏。 1996年，MacKay和Neal重新发现LDPC码，并指出LDPC的优秀性能可以逼近Shannon极限。LDPC重新进入大家的视野，并受到广泛重视。,定义,定义：LDPC规则码(

2、N,p,q)定义为具有如下特性的校验矩阵HMXN的零空间： 每一行含有q个1； 每一列含有p 个1； 任两行（列）之间位置相同的1的个数不大于1即0，1 q N ，p2,m/n=p/q。 (2)任意两行（列）位置相同非零元素的个数不大于1. (3)非零元素个数尽量随机排列，且分布稀疏。 (4)某个矩阵的逆矩阵存在（在二元域上存在）,对角线法,思想：对于1的分布及个数的满足采用先以对角线满足个数，再把小块的稀疏矩阵随机打乱,以规则码H(8,3,4)为例,矩阵的行数为6，先进行矩阵布局设计，设a,b,c为三个长为8的全1矢量，使a在左边方阵主对角线下距离1的位置，b在主对角线位置，c在上距离为2的

3、位置。每一矢量的剩余部分，折断往上分布，适当调整使任意两行、列相重叠的个数不大于1，如图(a)。然后可以对矩阵的行或列随机排序（都是初等变换）得到图(b)所示,LDPC系统码的编码,一般系统线性分组码的编码 C = mG = m mP 一般编码方法用于 LDPC码会产生的问题 G的维数巨大，G一般也并不稀疏。比如一个（10000，5000） LDPC码，P矩阵将是50005000矩阵。假设“1”的密度是0.5，编码所作的运算也有 0.5(50005000)=12.5106 次（注：H在系统化之前是稀疏矩阵，系统化后不一定。） 简化编码的方法之一是利用代数或几何途径来设计LDPC码.,近似下三角

4、矩阵编码,交换行和列可以将H转化成一个近似下三角矩阵,g,保证T是可逆的,将变换后的矩阵H左乘 其中I是单位矩阵，得到,设编码码字 ，其中t为信息位， 为检验位。,注意两点：g应当尽可能的小，0.02746n；保证 可逆。,LDPC编码方法的研究： 如何利用校验矩阵的稀疏性有效的进行编码，其目的是使编码复杂度随码长呈线性增长。上述近似下三角方法的复杂度近似为：,LDPC译码,Gallager概率译码算法,BP算法,硬判决：对信道的输出作出是0还是1的判决。 软判决：不作出01判决，只输出有关信息，如0、1的后验概率。,软判决译码算法：对信道输出的软判决序列进行译码的算法就叫软判决译码算法。,G

5、allager概率译码算法和BP算法都是软判决译码算法。其目的都是利用码字中其他所有比特的信息来修正该比特的后验概率，就可能得到该比特的最佳后验概率，然后判决它为0或1。,Gallager概率译码算法,对码字的某一比特，包含它的校验方程可能不止一个，这些校验方程的其他比特又可能包含在更多的校验方程之中。为表示这种关系，引入校验集合树概念。,(1,1),(1,2),根节点d表示比特d，和d相连的每一条边表示包含d的一个校验方程，如,Gallager概率译码算法,其中S表示包含d的所有校验方程成立这一事件,令,Gallager概率译码算法,证明：我们先证以下结论,考虑关于t的m次多项式,Galla

6、ger概率译码算法,由二项式分布知道 的系数正是序列中包含i个1的概率。再考虑：,差别仅在于其 的奇次幂系数是负的。把两多项式相加，然后令t=1，并除以2 ，就得到 序列中包含偶数个1的概率是：,Gallager概率译码算法,同理，可以得到序列中包含奇数个1的概率为,根据条件概率定义有,Gallager概率译码算法,当 ，包含d的j个校验方程成立的条件是每个校验方程中其余k-1个比特中含有偶数个1，由前面的公式有：,Gallager概率译码算法,同理有,代入即得,Gallager概率译码算法,概率译码算法： 对每一比特，给出校验集合树，利用公式从顶层开始逐层计算各节点后验概率，直到求出根节点的后验概率，然后判决该比特是0还是1。,BP算法,符号的定义：,BP算法,BP算法,BP算法,BP算法,BP算法,