LDPC码全面介绍

1、密码学概述密码学概述ldpc码（ low density parity check code ） ldpc简介简介ldpc规则码的对角线构造方法规则码的对角线构造方法gallager概率译码算法概率译码算法ldpc编码编码bp算法算法 ldpc历史历史19601960年，由年，由gallagergallager提出。但是由于计算复杂度提出。但是由于计算复杂度超出当时的计算能力，超出当时的计算能力，ldpcldpc码被人们所遗忘。码被人们所遗忘。19811981年，年，tannertanner提出编码的图形结构表示方法，提出编码的图形结构表示方法，这为这为ldpcldpc解码算法的简化奠定了基础

2、，促进了解码算法的简化奠定了基础，促进了ldpcldpc的复苏。的复苏。19961996年，年，mackaymackay和和nealneal重新发现重新发现ldpcldpc码，并指出码，并指出ldpcldpc的优秀性能可以逼近的优秀性能可以逼近shannonshannon极限。极限。ldpcldpc重新重新进入大家的视野，并受到广泛重视。进入大家的视野，并受到广泛重视。 定义定义 定义：定义：ldpcldpc规则码规则码(n,p,q)(n,p,q)定义为具有如下特性的定义为具有如下特性的校验矩阵校验矩阵h hmxnmxn的零空间：的零空间： 每一行含有每一行含有q q个个1 1； 每一列含有每

3、一列含有p p 个个1 1； 任两行（列）之间位置相同的任两行（列）之间位置相同的1 1的个数的个数 不大于不大于1 1即即 0 0，1 1 q n q n ，p m pq2,m/n=p/qp,pq2,m/n=p/q。(2)(2)任意两行（列）位置相同非零元素的个任意两行（列）位置相同非零元素的个数不大于数不大于1.1.(3)(3)非零元素个数尽量随机排列，且分布稀非零元素个数尽量随机排列，且分布稀疏。疏。(4)(4)某个矩阵的逆矩阵存在（在二元域上存某个矩阵的逆矩阵存在（在二元域上存在在） 2gf 对角线法对角线法思想：对于思想：对于1 1的分布及个数的满足采用先以对角的分布及个数的满足采用

4、先以对角线满足个数，再把小块的稀疏矩阵随机打乱线满足个数，再把小块的稀疏矩阵随机打乱以规则码以规则码h(8,3,4)h(8,3,4)为例为例矩阵的行数为矩阵的行数为6 6，先进行矩阵布局设计，设，先进行矩阵布局设计，设a,b,ca,b,c为三个长为为三个长为8 8的全的全1 1矢量，使矢量，使a a在左边方阵在左边方阵主对角线下距离主对角线下距离1 1的位置，的位置，b b在主对角线位置，在主对角线位置，c c在上距离为在上距离为2 2的位置。每一矢量的剩余部分，的位置。每一矢量的剩余部分，折断往上分布，适当调整使任意两行、列相重折断往上分布，适当调整使任意两行、列相重叠的个数不大于叠的个数不

5、大于1 1，如图，如图(a)(a)。然后可以对矩阵。然后可以对矩阵的行或列随机排序（都是初等变换）得到图的行或列随机排序（都是初等变换）得到图(b)(b)所示所示 101001101101000101101010001101010101101010001101a 101001010111001011001100100100110100111000111001b 100000000100000000100000000100000000100000000100a 100000001100000001100000001100000001100000001100a 101000001101000001

6、101000001101000001101000001101a ldpc系统码的编码系统码的编码n一般系统线性分组码的编码一般系统线性分组码的编码c = mg = m mp c = mg = m mp n一般编码方法用于一般编码方法用于 ldpcldpc码会产生的问题码会产生的问题 g g的的维数巨大，维数巨大，g g一般也并不稀疏。比如一个（一般也并不稀疏。比如一个（1000010000，50005000） ldpcldpc码，码，p p矩阵将是矩阵将是5000500050005000矩阵矩阵。假设。假设“1”1”的密度是的密度是0.50.5，编码所作的运算也有，编码所作的运算也有 0.50

7、.5(5000(50005000)=12.55000)=12.510106 6 次（注：次（注：h h在在系统化之前是稀疏矩阵，系统化后不一定。）系统化之前是稀疏矩阵，系统化后不一定。）n简化编码的方法之一是利用代数或几何途径来简化编码的方法之一是利用代数或几何途径来设计设计ldpcldpc码码. . 近似下三角矩阵编码近似下三角矩阵编码交换行和列交换行和列可以将可以将h h转化成一个近似下三角矩转化成一个近似下三角矩阵阵gtbcdea0n-mm-ggm-g保证t是可逆的 将变换后的矩阵将变换后的矩阵h h左乘左乘 其中其中i i是单位矩阵，得到是单位矩阵，得到10ieti110abtetac

8、et bd 设编码码字设编码码字 ，其中，其中t t为信息位，为信息位， 为检验位。为检验位。12,st p p12,p p10,thset bd根据若可逆。可得 1111ttpet bdetac t 121tttptatbp 注意两点：g应当尽可能的小，0.02746n；保证 可逆。1etbd ldpc编码方法的研究：如何利用校验矩阵的稀疏性有效的进行编码，其目的是使编码复杂度随码长呈线性增长。上述近似下三角方法的复杂度近似为：2nog ldpc译码译码gallager概率译码算法概率译码算法bp算法算法 硬判决：对信道的输出作出是硬判决：对信道的输出作出是0 0还是还是1 1的判决。的判决

9、。软判决：不作出软判决：不作出0101判决，只输出有关信息，如判决，只输出有关信息，如0 0、1 1的后验概率。的后验概率。软判决译码算法：对信道输出的软判决序列软判决译码算法：对信道输出的软判决序列进行译码的算法就叫软判决译码算法。进行译码的算法就叫软判决译码算法。gallagergallager概率译码算法和概率译码算法和bpbp算法都是软判决算法都是软判决译码算法。其目的都是利用码字中其他所有译码算法。其目的都是利用码字中其他所有比特的信息来修正该比特的后验概率，就可比特的信息来修正该比特的后验概率，就可能得到该比特的最佳后验概率，然后判决它能得到该比特的最佳后验概率，然后判决它为为0

10、0或或1 1。 gallager概率译码算法概率译码算法对码字的某一比特，包含它的校验方程可能不对码字的某一比特，包含它的校验方程可能不止一个，这些校验方程的其他比特又可能包含止一个，这些校验方程的其他比特又可能包含在更多的校验方程之中。为表示这种关系，引在更多的校验方程之中。为表示这种关系，引入入校验集合树校验集合树概念概念。d(1,1)(1,2)根节点d表示比特d，和d相连的每一条边表示包含d的一个校验方程，如1 11 20dccc gallager概率译码算法概率译码算法其中其中s s表示包含表示包含d d的所有校验方程成立这一事件的所有校验方程成立这一事件令1|ddpp cy dd1i

11、lpl表示 的校验集合树第一层中包含 的第i个校验方程的第 个比特为 的概率，那么有：111111120| ,11| ,112kjilddlkiddillpp cy spp cy spp d1| ,dp cy s如何求比特 的最佳后验概率？ gallager概率译码算法概率译码算法证明：我们先证以下结论m1llplm 一个长为的相互独立的二进制序列，其中第 个比特为1的概率为，那么序列中包含偶数个1的概率是11122mllevenpp考虑关于t的m次多项式 11mlllftppt gallager概率译码算法概率译码算法由二项式分布知道 的系数正是序列中包含i个1的概率。再考虑：it 11ml

12、llg tppt差别仅在于其 的奇次幂系数是负的。把两多项式相加，然后令t=1，并除以2 ，就得到 序列中包含偶数个1的概率是：it11111211222mmmlllllllevenppppp gallager概率译码算法概率译码算法同理，可以得到序列中包含奇数个同理，可以得到序列中包含奇数个1 1的概率为的概率为111212mlloddevenppp根据条件概率定义有根据条件概率定义有0 |,0,1|,1,ddddp cy sp cy sp cy sp cy s 0| |0, 1| |1, ddddp y p cy p s cyp y p cy p s cy gallager概率译码算法概率

13、译码算法|0,1|1,ddddp s cyppp s cy当当 ，包含，包含d d的的j j个校验方程成立的条件是每个校验个校验方程成立的条件是每个校验方程中其余方程中其余k-1k-1个比特中含有偶数个个比特中含有偶数个1 1，由前面的公式有：，由前面的公式有：0dc 111112|0,2kljldlpp s cy gallager概率译码算法概率译码算法同理有同理有111112|1,2kljldlpp s cy代入即得代入即得111111120| ,11| ,112kjilddlkiddillpp cy spp cy spp gallager概率译码算法概率译码算法概率译码算法：概率译码算法

14、：对每一比特，给出校验集合树，利用公式从顶对每一比特，给出校验集合树，利用公式从顶层开始逐层计算各节点后验概率，直到求出根层开始逐层计算各节点后验概率，直到求出根节点的后验概率，然后判决该比特是节点的后验概率，然后判决该比特是0 0还是还是1 1。11| ,0.50dddcp cy sc若其他 bp算法算法符号的定义： :1mllmll ml mxh设表示与校验节点s 相连的所有变量节点x的集合即 :1lmmmlm lm lsh设表示与变量节点x相连的所有校验节点s 的集合即 0,1xmlxmllx imllmlmqm lmxxxqxsqixs，表示基于接收信号并根据校验节点集合得出的的概率，

15、可以认为，表示第 次迭代是 向传递的信时 向息传递的信息 bp算法算法 :sxxmllmlmxmlmlx imlmlrxxqll mlrisrxsx，表示，并给定其他比特的一组概率时，校验节点对应的方程成立的概率，表示第 次迭可以看作是 向 传递的信息代时 向 传递的信息 0 ,1,0 ,12iim lm lllmlim lqqr 0 ,1,1,12iim lm lllmlim lqqr bp算法算法 1, 00, 01111(1),1mlmllmlllqfqff 对所有满足h的m,l执行以下步骤初始化：， 为信道得到的概率 0,1,0,1,0,1,1122iiiimlmlmlmlll m l

16、ll m liimlmlqqqqrr(2)校验节点信息更新：， 0,10,1,11,010,11,1(3)1iiiimlmllmlmllm lm lmm lmmm lmiimlmlmlqaprqapraqq变量节点信息更新：其中是一个使的值。 bp算法算法 0,10,1,10,010,11,1(4)1iiiilllmllllmlm m lm m liilllqa prqa praqq计算后验概率其中为使成立的值。0,1(5)0.5,0,11,20,illtqxlnxx比特判决：若则判反之为，。若h或者迭代次数到达最大值，则结束迭代，输出 ；否则转到第二步继续迭代。 bp算法算法1s2s3s4s1x2x3x4x5x6x7x8x1110001121111211(1),qqfqqf初始化0101013355770101011111313151(2),2ffffff计算rr ,rr ,r bp算法算法00 011 1011111 1211111 1 21111111(3)(1qa f rqa f r aqq计算为使的值)0001110111 11 2111 11 21111(4