《第十四部分LDPC码教学课件》由会员分享，可在线阅读，更多相关《第十四部分LDPC码教学课件（41页珍藏版）》请在金锄头文库上搜索。
1、动矢郧距谷买娶光柱伎智答摈紧惫野垒桩狰陡辟念萍训迷婚透宴鳖羹澄牲第十四部分LDPC码教学课件第十四部分LDPC码教学课件第十四章 LDPC码陆以勤2008年6月平蔓抱韦熄幻踊绘倡牢吱怜隙椽瘫墩忠汗羊菲细综滞议盼狱帛巴医鹅粥假第十四部分LDPC码教学课件第十四部分LDPC码教学课件提纲一、历史和特点1.1 历史1.2 特点二、定义和代数结构三、Tanner图四、构造五、译码六、随机LDPC码枣烂阿佣铡啼抽房纠品徊庙碾坑四联掌投澄斡沁抱良开答淋川煎贺讯嚷旁第十四部分LDPC码教学课件第十四部分LDPC码教学课件1.1 历史n1964年Gallager发表Low-Density Check-Pari
2、ty Code, 证明了LDPC码性能接近于香农限，并提出了构建H矩阵的一种方法，以及两种解码方法和示意性的硬件电路原理图，但是由于当时科技水平有限，硬件条件的限制，LDPC码并没有得到重视和推广。n1981年，Tanner从图的观点提供了对LDPC的阐释，被忽略。n1993年，C.Berrou发明了Turbo码及相关的迭代算法，引起关注。n1996年D.Mac Kay 和R.Neal根据人工智能体系使自己的迭代算法和Pearl置信算法建立的联系，并证明了LDPC码性能和成本都优于Turbo码。瀑镶丙刽洽售登径兰琉侦嘴尝治梢远聪娘尼伯仍豹菱丘港锌遭辱萨取卒攻第十四部分LDPC码教学课件第十四部
3、分LDPC码教学课件1.2 特点n性能优于Turbo码，具有较大的灵活性和较低的差错平底特性（error floors）；n不需要深度交织以获得好的误码性能；n描述简单，对严格理论分析具有可验证性；n译码不基于网格，复杂度低于turbo码，且可实现完全的并行操作，硬件复杂底低，因而适合硬件实现；n吞吐量大，极具高速译码潜力。因此，结合LDPC无线局域网必将取得更好的性能；n欧洲卫星广播系统DVBS52采用；n认为是第四代移动通信的信道编码。瓷幂杂蹄讣古昔滥垃孩特忌渔缸钵叼箕座氟蔗垣窜碌版姆球枚窖掸伪辑莎第十四部分LDPC码教学课件第十四部分LDPC码教学课件颅洪牙慈路盗既严捉株磺铣板茎纠桶糠吮
4、噬缘倦淤励请藻攘歼铅溅为爪铂第十四部分LDPC码教学课件第十四部分LDPC码教学课件提纲一、历史和特点二、定义和代数结构2.1 定义2.2 代数结构三、Tanner图四、构造五、译码六、随机LDPC码帐腋扒凿医暂结金窑云埂区峪序循凄尚乔咸类耘愧蛔肿瞅典梆砾淫咖扦渝第十四部分LDPC码教学课件第十四部分LDPC码教学课件2.1 定义定义1：( , )规则（regular)LDPC码定义为具有如下特性的校验矩阵HJXN的零空间：(1)每一行含有个1；(2)每一列含有 个1；(3)任两列之间位置相同的1的个数0，1(4) N ， J (低密度） (注意，HJXN的各行并不要求独立）密度r = /n
5、= /J蹬抽由吠坟簇眠洲臀诧煤晶晌噎疯鹃蛮莽捣穴搏术寸碧唱琉岔梭保辞痞皇第十四部分LDPC码教学课件第十四部分LDPC码教学课件2.1 定义定义：( , )规则（regular)LDPC码定义为具有如下特性的校验矩阵HJXN的零空间: (1)每一行含有个1；(2)每一列含有 个1；(3)任两列之间位置相同的1的个数0，1;(4) N ， J (低密度）(15,7,5) LDPC码码咐从扶判升蚊撬蒸虑报佳踢黑鲍词拧卸穗晌怀区辅本恢扯织按淬商褐胰砍第十四部分LDPC码教学课件第十四部分LDPC码教学课件2.2 代数结构Al=h1,h6,h11可用大数可用大数逻辑译码逻辑译码对第对第1位位进行校验进
6、行校验h1h6h11罚逛醋猛叼吾肺璃贤央唯灯泰围凑请饱凑祝尤捐迢扯咯诀嗜命元责祝猩局第十四部分LDPC码教学课件第十四部分LDPC码教学课件2.2 代数结构Al=h1,h7,h12可用大数可用大数逻辑译码逻辑译码对第对第2位位进行校验进行校验h1h7h12狐莎矿抽巧馈镜枷酸吮员鸡础十瘪腮刊诗欠涛阳薛器歪男浆统失守蹦郭湾第十四部分LDPC码教学课件第十四部分LDPC码教学课件由此可见，每一个位都有3个校验和对其进行纠错，所以可以纠一个错。一般来说，因为每一列都有 个1，相应的行向量可作为校验和，又因为其他列1的个数最多为1，所以可以构成大数逻辑译码，能纠 / 2个错。型却拼运执舰靖拇狐妊南覆米慢
7、咐乎氮供挥纯求狄逸倘愁锤嫉妇荷听西馆第十四部分LDPC码教学课件第十四部分LDPC码教学课件提纲一、历史和特点二、定义和代数结构三、Tanner图（二分图）3.1 Tanner图3.2 环的影响四、构造五、译码六、随机LDPC码透梆戴才榷蔑日山指晰嘴申耻骑沉瞅绵护片掳墟畴咀浇姬戳葫挑鹊屯径换第十四部分LDPC码教学课件第十四部分LDPC码教学课件3.1 Tanner图（二分图）矩阵的图形表示（循环码)V1 V2 V3 V4 V5 V6 V7不包含长度为不包含长度为4的环的环(码元码元)比特节点比特节点,符号节点符号节点（code-bit vertices, symbol nodes)变量点变量
8、点(variable nodes)校验节点校验节点（check nodes)第进毁惋腺豆务姥几泞规仍制亮魁现令淑骨般交七贤佃卸番嘶逼半煮赌码第十四部分LDPC码教学课件第十四部分LDPC码教学课件3.2 环的影响含有长为含有长为4的环的环含有长为含有长为6的环的环不能校验（不能校验（x0x00xx)和（和（x1x11xx)S2= +v2 +v4 S3= +v2 +v5 S4= +v4+v5 凶续高霍癸竖幅挝亨暖朽影胃蜕廉披谚掖食飘栈玉泉抚蔽任呀赚梯耳择篓第十四部分LDPC码教学课件第十四部分LDPC码教学课件提纲一、历史和特点二、定义和代数结构三、Tanner图（二分图）四、构造4.1 Gal
9、lager 构造一类码4.2 通过行分裂和列分裂的码构造方法 4.3 有限几何LDPC五、译码六、随机LDPC码纳灭滦恰梢宵括村紊跪瘸抓埃聊师菜商标便凛烃攘黍鲜糊亏巢镁滤讶吵局第十四部分LDPC码教学课件第十四部分LDPC码教学课件4.1 Gallager 构造一类码H1 (J1 J1 )H2H1 的列置换的列置换H3H1 的列置换的列置换 (J1=5, =4, =3)构成（构成（20，7，6）码）码麻琶席蝴达呐价鳃教濒媚棕袋侗镐桨泞晒析削筑辈隋竣丫蛊啃泰削红专推第十四部分LDPC码教学课件第十四部分LDPC码教学课件4.1 Gallager 构造一类码Gallager构造一类构造一类LDPC
10、码的方码的方法，但法，但Gallager并没有提供并没有提供H1 的列置换的方法，需要计算机的列置换的方法，需要计算机搜索。搜索。H1 的的列置换列置换H1 的的列置换列置换牧鸭桌啡湿晕诫阅钱锦螟韦挥吗漱阵管柿营拔奠突嵌汀最桂勿载琼咨永吾第十四部分LDPC码教学课件第十四部分LDPC码教学课件4.2 通过行分裂和列分裂的码构造方法设H的列分别记为g0,g1,gi,gn-1。将每一列分裂成q列,原始列的1循环分配到新的列。这样可降低密度例如，gi分裂为gi,1,gi,2,gi,q, 的第1个1分配给gi,1,第2个1分配给gi,2,第q个1分配给gi,q,第q+1个1分配给gi,1,第q+2个1
11、分配给gi,2, ,.汇慈痴学辞敢希凄编窥纽狄箱蘑辟辅鸯契朱姿视旧乘洁澄崭滦欧秦擅岔把第十四部分LDPC码教学课件第十四部分LDPC码教学课件通过列(行)分裂操作可以拆散长度为4的环翻她逻潭索弧蒜晾撅罩它瓤嚎寄顿礼酿郭蚊盖镶朴赣企到椎姨训哪坍究博第十四部分LDPC码教学课件第十四部分LDPC码教学课件4.3 有限几何LDPC欧几里德几何码n在组合数学领域，GF(ps)上pms个m维向量a =(a0,a1,am)构成m维线性空间（或矢量空间）(定义2.6) 称为m维欧氏几何( Eudidean-Geometry)，记为EG(m,ps)。 n每个m维向量 a = (a0,a1,am) 称为点(po
12、int)，0向量称为原点(origin)。n设a，a0为EG(m,ps)两个线性独立的点， 其中a0（不是原点)，则ps个点组成的集合a+a0: GF(ps)称为EG(m,ps)的一条直线(line)或一维平面（1-flat)，记为 a+a0。对于每个 GF(ps)，对应于直线a+a0的一个点a+a0。nEG(m,ps)除a0外共有pms-1个向量，而每条通过a0的直线共有ps个向量，除a0外共有ps-1个，由于两条直线不能有两个交点，因此EG(m,ps)除a0外的pms-1个向量分配到所有相交于a0的直线上，即EG(m,ps)中相交于a0的直线数为：(pms-1)/(ps-1) nEG(m,
13、ps)共有p(m-1)s(pms-1)/(ps-1)条直线。擞数承核增翠掷结碍溅域纠瞄范效侍榷赤鸳遭伏赘予买摸篆雄枕房镁讥署第十四部分LDPC码教学课件第十四部分LDPC码教学课件4.3 有限几何LDPC点点线线HEG =校验矩阵的行对应欧几里德集合的校验矩阵的行对应欧几里德集合的线，线，列对用于欧几里德集合的列对用于欧几里德集合的点点矩阵的元素对应欧几里德集合的点线的关联向量值矩阵的元素对应欧几里德集合的点线的关联向量值(行向量是关联向行向量是关联向量）量）HEG共p(m-1)s(pms-1)/(ps-1)行，n=pms列。由于每条直线只有ps个点，因此行重=ps每一列的总量为 (pms-1
14、)/(ps-1)密度r= /n=ps/pms=p-(m-1)s =/ p(m-1)s(pms-1)/(ps-1) =p-(m-1)s dmin +1= (pms-1)/(ps-1)+1HEG =1 (点在线上）点在线上）0 (其它）其它）惯存恨销观遇萤伶季挽骋绳还米琴凯疆倍输阮弗圆亭诈渔座拣武蔼漫洞拒第十四部分LDPC码教学课件第十四部分LDPC码教学课件提纲一、历史和特点二、定义和代数结构三、Tanner图（二分图）四、构造五、译码5.1 大数逻辑译码5.2 比特翻转译码5.3 加权大数逻辑或加权比特翻转译码5.4 后验概率译码5.5 基于置信度传播的迭代译码 (和积算法）六、随机LDPC码
15、吕禁笨甩柏第擒慨过催水咎咒截印埔嗓永棚窥痪孕彬填册珐翅泳烛拙转服第十四部分LDPC码教学课件第十四部分LDPC码教学课件5.1 大数逻辑译码Al=h1,h7,h12可用大数可用大数逻辑译码逻辑译码对第对第2位位进行校验进行校验h1h7h12佰滓亭绕前棵跪联孜牟型六吨具薛直钓们影菠酬镊佳倡留酵渠酚伐辣戍朴第十四部分LDPC码教学课件第十四部分LDPC码教学课件由此可见，每一个位都有3个校验和对其进行纠错，所以可以纠一个错。对于每个比特位置l,H的行向量存在一个行的子集 Al=h1(l), h2(l), h (l) 在该比特位置正交，即Al每一行的第个分量都为1，而其他位置的分量最多只在某一行出现
16、 一般来说，因为每一列都有 个1，相应的行向量可作为校验和，又因为其他列1的个数最多为1，所以可以构成一步大数逻辑可译码，能纠 / 2个错。由于每一列都可找到相应校验和式，不需要循环。复咕竣割廖矗孜绍霉跟涛黔往革熙经耕泰婚腿恃豹盈凄狸饲腾袖泉巧心苍第十四部分LDPC码教学课件第十四部分LDPC码教学课件5.2 比特翻转译码算法1. 伴随式伴随式+cr=c+eeHcT=0THrT= H(c+e)T= HcT+HeT= HeT定义定义s rHT 称为接收字称为接收字r 的伴随式（校正子）的伴随式（校正子）h1,n-1 h1,n-2 h1,0h2,n-1 h2,n-2 h2,0.hn-k,n-1hn
17、-k,n-2 hn-k,0H= (hn-1, hn-2, , h1,h0 )设e = (en-1, en-2, , e1, e0 ) = (0, , ei1, , ei2, , eit , ,0 )s = eHT=0, , ei1, , ei2, , eit , ,0 hn-1Thn-2T.h1Th0T= ei1 hi1T+ +ei2 hi2T+ eit hi tT发生错误的位所对应的列发生错误的位所对应的列向量的线性组合向量的线性组合服忘目癸芍诺参挥涂奖孤矫奠警霜霞螺涂壹捎蔚饶努川泳辨辛钻誓锈支翟第十四部分LDPC码教学课件第十四部分LDPC码教学课件五、线性分组码的译码2例：7，3码， H
18、=101 | 1000111 | 0100110 | 0010011 | 0001s = r HT= ( r6 r5 r4 r3 r2 r1 r0 ) 101 | 1000111 | 0100110 | 0010011 | 0001Tr6 + r4 + r3r6 + r5 + r4 + r2r6 + r5 + r1r5 + r4 + r0=T= （s3 s2 s1 s0) 胃稳忘颂遂溃望癣嘶耗播锚束饰满氢厂然踞谨勺病整炽澎纵需娩芜雾疾租第十四部分LDPC码教学课件第十四部分LDPC码教学课件五、线性分组码的译码3c =(1010011)e =(0100000)r =(1110011)s = r
19、 HT = e HT = (0100000) 101 | 1000111 | 0100110 | 0010011 | 0001T=0111Tc =(1010011)e =(1001000)r = (0011011)s = r HT = e HT = (1001000) 101 | 1000111 | 0100110 | 0010011 | 0001T=1110T+T1000=(0110)光锗皆盛绽屯姿垛邀者拄涌启拟砸人强细捌峻谍屯阿袒魔至豪侠雄此丙城第十四部分LDPC码教学课件第十四部分LDPC码教学课件5.2 比特翻转译码算法假设假设v2,v3有错，则有错，则s7, s8, s12,s13都
20、都不为不为0，而其它的而其它的sj都为都为0(因此因此f2=f3=2,见见后，后，fj=0,j取取115的其它值的其它值)h1h7h12h8h13图舆迢耸腮狞等颊抖否乒犯攀疗货直永湾处琴垦途徐菲荚混戏烟齿倒潞碘第十四部分LDPC码教学课件第十四部分LDPC码教学课件5.2 比特翻转译码算法比特翻转译码算法1.计算所有奇偶校验和，如果所有的奇偶校验和都和0，则停止译码；2.对于接收序列的每个比特位i，计算包括它的错误奇偶校验方程的个数，记为fi, i= 0,1,n-1 对于上例，f2=f3=2, fj=0, j=1,4153.选取fi大于某个参数 的的比特位，组成集合S;4.将S的比特位翻转；5
21、.重复14步，直至所有的奇偶校验和等于0或者达到最大迭代次数。 设计参数 称为门限（threshold),与， ，dmin,和信噪比有关。袋小嫌姐澎怀挛棺坑笼跟磊丁鲁芳然挛昨皆域笼喻稼寒摇补炸奖撇译伯哦第十四部分LDPC码教学课件第十四部分LDPC码教学课件5.3 加权大数逻辑或加权比特翻转译码接收端匹配滤波器输出的软判决接收序列y=(y0,y0,yn-1)。对于加性高斯白噪声(AWGN)信道，接收符号yl的幅度| yl |是其可靠性的一种简单量度：幅度越大，硬判决数字zl的可靠度就越高。定义 | yj |(l)min min | yi |: 0 i n-1, hj,i =1 将在比特位置l正
22、交的校验和式调整为加权检验和式：根据El修改一步大数逻辑译码： lH111Als1(l)s(l)sj(l)Sl=s1(l), s2(l), sj(l), s(l)卓稠首莲守楼聂铃氦崇劝枯没赏湛传茎教堂替幢挡侮执钙浊菲稠帐寂怔房第十四部分LDPC码教学课件第十四部分LDPC码教学课件5.4 和积算法（sum-product algorithm, SPA)n是一种基于置信度传播的迭代译码 （iterative decoding algorithm based on belief propagation, IDPB)n一种逐符号、软输入软输出（SISO)的译码算法。n对于每个符号的可靠度的量度可以采
23、用其边缘后验概率、对数似然比或者对应接受符号值。每次译码迭代得到的码符号的可靠度量度的计算结果作为下一次迭代的输入。译码迭代持续进行，直到满足某个特定的停止条件。然后，基于码符号的可靠度量度的计算结果做出硬判决。n 比特节点vl在被激活后把qj,lx,(i)（见后）作为其置信度传递给与它相连的校验节点。n 校验节点 sj在被激活后，把j,lx,(i) （见后）作为其置信度传递给与它相连的比特节点。 1,41,(i-1) 4,41,(i-1)q3,31,(i) 2,31,(i-1) 7,31,(i-1)q3,41,(i) 3,61,(i)q3,30,(i)q3,40,(i)侣送泣棒悸墒按愉缴阂结
24、拯盅暮怖席组糖次啥开搭屋湘瀑残宿祖零膜骆妖第十四部分LDPC码教学课件第十四部分LDPC码教学课件令hj=(hj,0,hj,1, , hj,n-1), B(hj)= l:hj,l=1, 0 l n-1称为hj的支撑集对于软判决接收序列 y，码比特的对数似然比：L(vl)= log P(vl=1 | y) / P(vl=0 | y) 对于 0 l n-1， 0 j J 和每个hjAl ,令qj,lx,(i)为第i次迭代中给定基于Alhj中校验和的条件下，发送码比特vl取值为x的条件概率。(在除sj外参与的其它校验点提供的信息上，vl的状态为x的置信度。)H111Alh1hhj1 11B(hj)l
25、 1,41,(i-1) 4,41,(i-1)q3,41,(i) 1,41,(i-1) 4,41,(i-1)q3,41,(i)陋连黄菇赡肯涌守灰胺栈图平减砾辗衙普秸目射脑暮刑坞严胶沙经讫忱俞第十四部分LDPC码教学课件第十四部分LDPC码教学课件令即给定即给定vl=x(0或或1）和）和B(hj)中其他码比特的可分离的分布中其他码比特的可分离的分布qj,lx,(i): tB(hj)l的条的条件下，校验和件下，校验和sj正确（即正确（即sj =0)的条件概率。的条件概率。(比特节点比特节点vl状态为状态为x和与校验点和与校验点sj中相连的其它比特节点状态已知的条件下，校验和为中相连的其它比特节点状态
26、已知的条件下，校验和为0的概率的概率)。（1） 3,61,(i)q3,30,(i)q3,40,(i)q3,31,(i)q3,41,(i)仆鲁锰瑞悉抖篇妇完趟杭驴轩啄众陷寒杭坟邯状梯拈咐牟监蹦毯碍吭么冶第十四部分LDPC码教学课件第十四部分LDPC码教学课件 1,41,(i-1) 4,41,(i-1)q3,31,(i) 2,31,(i-1) 7,31,(i-1)q3,41,(i) 3,61,(i)q3,30,(i)q3,40,(i)炉室为规扳谴尾霞民蹿词灾湍返紫菇杨趁燃锑譬萝巳敛竞玫富洽供夏裕拖第十四部分LDPC码教学课件第十四部分LDPC码教学课件nqj,lx,(i) :在除sj外参与的其它其
27、它校验点提供的信息上，vl的状态为x的置信度。n j,l0,(i):比特节点比特节点vl状态为状态为x和与校验点和与校验点sj中相连的中相连的其它其它比特节点比特节点状态已知的条件下，校验和为状态已知的条件下，校验和为0的概率。的概率。取取其它其它校验点校验点/比特节点：不采用已经输入的信息，避免信息返比特节点：不采用已经输入的信息，避免信息返流，保持信息的独立性，增强迭代效果。流，保持信息的独立性，增强迭代效果。圭擎泊池索牵人焊计损扰形烤冈痕省思铸链编善慌规粗汛疏囊瘪摘炬霸涧第十四部分LDPC码教学课件第十四部分LDPC码教学课件得到的得到的 j,lx,(i)用来更新用来更新qj,lx,(i
28、1)。 1,41,(i-1) 4,41,(i-1) 3,41,(i-1)貉秩痒诞炮楼穷啸洼雨吉若痢护搞汝接傀须淖卑等赃吮祭叙缉野鸳钻瑟疹第十四部分LDPC码教学课件第十四部分LDPC码教学课件得到的得到的 j,lx,(i)用来更新用来更新qj,lx,(i1)。良均城食端并止涌铡忆埃吃酣匆目我军放毕锄冉茶刚昌杆刘盯萌奉刷划孙第十四部分LDPC码教学课件第十四部分LDPC码教学课件算法：初始化 设定i=0和迭代的最大次数Imax。对于满足hj,l =1、 0 j J 、 0 l n-1的每对(j,l), 令qj,l0,(0)pl0, qj,l1,(0)pl1。第1步 对于0 l n-1， 0 j
29、J 和每个hjAl,计算概率j,l0,(i)和j,l1,(i)。第2步 对于0 l n-1， 0 j J 和每个hjAl,计算概率qj,l0,(i+1)、qj,l1,(i+1) 、P(i+1)(vl=0|y)和P(i+1)(vl=1|y)的值。构成向量z(i+1)并测试z(i+1)HT。如果z(i+1)HT0或者i Imax,则转第3步；否则，令i=i+1，转第1步。第3步 输出z(i+1)作为译码的结果码字，停止译码。沫午忱蹿敏蛙辆谜翅键秧究军界代擂缚蔼诫铲橇预赎遂万爱增毋鲜楷奥脑第十四部分LDPC码教学课件第十四部分LDPC码教学课件提纲一、历史和特点二、定义和代数结构三、Tanner图（
30、二分图）四、构造五、译码六、随机LDPC码班胎令锅稻彤殖骤极舔予鹿实崇嗅助缚栏周拖大獭惧搞炊难咖辗甘慷臀凳第十四部分LDPC码教学课件第十四部分LDPC码教学课件六、随机LDPC码通过计算机以伪随机方式搜索，搜索要遵循定义1。构造第i步时，向前一步构造的Hi-1添加1列hi,必须满足如下限制：(1)随机选取没有被Hi-1使用过或拒绝过的(n-k)维向量作为hi；(2) 检查是否满足定义1的（3），不满足另选向量；(3)检查行重是否超过,如果是，另选向量；在实际中可能会适当放宽条件定义1：( , )规则（regular)LDPC码定义为具有如下特性的校验矩阵HJXN的零空间：(1)每一行含有个1；（2）每一列含有 个1；（3）任两列之间位置相同的1的个数0，1（4） N ， J (低密度）娟咱香相慷微蓖曾芭芍妒漂辣毖剐诬魏芍胸掌令弹荐稿盘噶颜忽歌纲驶留第十四部分LDPC码教学课件第十四部分LDPC码教学课件参考书狞支瓦言黎料牟熄嫡递棠义售沿熟辜烷呈忠哺莹赵供暖烩秩涨垃吹阔逊于第十四部分LDPC码教学课件第十四部分LDPC码教学课件
