资源描述
#,密码学概述,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,#,密码学概述,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,单击此处编辑母版标题样式,#,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,规则码,(N,p,q),定义为具有如下特性的校验矩阵,H,MXN,的零空间：,每一行含有,q,个,1,；,每一列含有,p,个,1,；,任两行（列）之间位置相同的,1,的个数,不大于,1,即,0,，,1,q,N,，,p,q2,m/n=p/q,。,(2),任意两行（列）位置相同非零元素的个数不大于,1.,(3),非零元素个数尽量随机排列，且分布稀疏。,(4),某个矩阵的逆矩阵存在（在二元域上存在,）,对角线法,思想：对于,1,的分布及个数的满足采用先以对角线满足个数，再把小块的稀疏矩阵随机打乱,以规则码,H(8,3,4),为例,矩阵的行数为,6,，先进行矩阵布局设计，设,a,b,c,为三个长为,8,的全,1,矢量，使,a,在左边方阵主对角线下距离,1,的位置，,b,在主对角线位置，,c,在上距离为,2,的位置。每一矢量的剩余部分，折断往上分布，适当调整使任意两行、列相重叠的个数不大于,1,，如图,(a),。然后可以对矩阵的行或列随机排序（都是初等变换）得到图,(b),所示,LDPC,系统码的编码,一般,系统线性分组码的编码,C=mG=m mP,一般,编码方法用于,LDPC,码会产生的,问题,G,的维数巨大，,G,一般也并不稀疏。比如一个（,10000,，,5000,）,LDPC,码，,P,矩阵将是,50005000,矩阵。,假设“,1”,的密度是,0.5,，编码所作的运算也有,0.5,(50005000)=12.510,6,次（,注：,H,在系统化之前是稀疏矩阵，系统化后,不一定。）,简化,编码的方法之一是利用代数或几何途径来设计,LDPC,码,.,近似下三角矩阵编码,交换行和列,可以将,H,转化成一个近似下三角矩阵,g,T,B,C,D,E,A,0,n-m,m-g,g,m-g,保证,T,是可逆的,将变换后的矩阵,H,左乘,其中,I,是单位矩阵，得到,设编码码字,，其中,t,为信息位，,为检验位。,注意两点：,g,应当尽可能的小，,0.02746n,；保证,可逆。,LDPC,编码方法的研究：,如何利用校验矩阵的稀疏性有效的进行编码，其目的是使编码复杂度随码长呈线性增长。上述近似下三角方法的复杂度近似为：,LDPC,译码,Gallager,概率译码算法,BP,算法,硬判决：对信道的输出作出是,0,还是,1,的判决。,软判决：不作出,01,判决，只输出有关信息，如,0,、,1,的后验概率。,软判决译码算法：对信道输出的软判决序列进行译码的算法就叫软判决译码算法。,Gallager,概率译码算法和,BP,算法都是软判决译码算法。其目的都是利用码字中其他所有比特的信息来修正该比特的后验概率，就可能得到该比特的最佳后验概率，然后判决它为,0,或,1,。,Gallager,概率译码算法,对码字的某一比特，包含它的校验方程可能不止一个，这些校验方程的其他比特又可能包含在更多的校验方程之中。为表示这种关系，引入,校验集合树,概念,。,d,(1,1),(1,2),根节点,d,表示比特,d,，和,d,相连的每一条边表示包含,d,的一个校验方程，如,Gallager,概率译码算法,其中,S,表示包含,d,的所有校验方程成立这一事件,令,Gallager,概率译码算法,证明,：,我们先证以下结论,考虑关于,t,的,m,次多项式,Gallager,概率译码算法,由二项式分布知道 的系数正是序列中包含,i,个,1,的概率。再考虑：,差别仅在于其 的奇次幂系数是负的。把两多项式相加，然后令,t=1,，并除以,2,，就得到 序列中包含偶数个,1,的概率是,：,Gallager,概率译码算法,同理，可以得到序列中包含奇数个,1,的概率为,根据条件概率定义有,Gallager,概率译码算法,当 ，包含,d,的,j,个校验方程成立的条件是每个校验方程中其余,k-1,个比特中含有偶数个,1,，由前面的公式有：,Gallager,概率译码算法,同理有,代入即得,Gallager,概率译码算法,概率译码算法：,对每一比特，给出校验集合树，利用公式从顶层开始逐层计算各节点后验概率，直到求出根节点的后验概率，然后判决该比特是,0,还是,1,。,BP,算法,符号的定义：,BP,算法,BP,算法,BP,算法,BP,算法,BP,算法,迭代译码算法的变种：,上述算法表示不够简单，采用很多相乘运算，且要分别计算,0,和,1,的概率，所以在此基础上对消息的表达式有很多变种，使得算法表述更洁且更利于实现（对数似然比表示的,BP,算法,）,谢谢,!,
展开阅读全文