现代信息理论编码与技术chapter14

1、第十四章 LDPC码陆以勤2008年6月提纲一、历史和特点1.1 历史1.2 特点二、定义和代数结构三、Tanner图四、构造五、译码六、随机LDPC码1.1 历史n1964年Gallager发表Low-Density Check-Parity Code, 证明了LDPC码性能接近于香农限，并提出了构建H矩阵的一种方法，以及两种解码方法和示意性的硬件电路原理图，但是由于当时科技水平有限，硬件条件的限制，LDPC码并没有得到重视和推广。n1981年，Tanner从图的观点提供了对LDPC的阐释，被忽略。n1993年，C.Berrou发明了Turbo码及相关的迭代算法，引起关注。n1996年D.M

2、ac Kay 和R.Neal根据人工智能体系使自己的迭代算法和Pearl置信算法建立的联系，并证明了LDPC码性能和成本都优于Turbo码。1.2 特点n性能优于Turbo码，具有较大的灵活性和较低的差错平底特性（error floors）；n不需要深度交织以获得好的误码性能；n描述简单，对严格理论分析具有可验证性；n译码不基于网格，复杂度低于turbo码，且可实现完全的并行操作，硬件复杂底低，因而适合硬件实现；n吞吐量大，极具高速译码潜力。因此，结合LDPC无线局域网必将取得更好的性能；n欧洲卫星广播系统DVBS52采用；n认为是第四代移动通信的信道编码。提纲一、历史和特点二、定义和代数结构

3、2.1 定义2.2 代数结构三、Tanner图四、构造五、译码六、随机LDPC码2.1 定义定义1：( , )规则（regular)LDPC码定义为具有如下特性的校验矩阵HJXN的零空间：n 每一行含有个1；n 每一列含有 个1；n 任两列之间位置相同的1的个数0，1n N ， J (低密度） (注意，HJXN的各行并不要求独立）密度r = /n = /J2.1 定义定义：( , )规则（regular)LDPC码定义为具有如下特性的校验矩阵HJXN的零空间: n每一行含有个1；n每一列含有 个1；n任两列之间位置相同的1的个数0，1;n N ， J (低密度）0100010110000000

4、01000101100000000100010110000000010001011000000001000101100000000100010110000000010001011100000001000101110000000100010011000000010001101100000001000010110000000100001011000000010000101100000001100010110000000(15,7,5) LDPC码码2.2 代数结构111111111111111111111111111111111111111111111111111111111111Al=h1,h6

5、,h11可用大数可用大数逻辑译码逻辑译码对第对第1位位进行校验进行校验h1h6h112.2 代数结构111111111111111111111111111111111111111111111111111111111111Al=h1,h7,h12可用大数可用大数逻辑译码逻辑译码对第对第2位位进行校验进行校验h1h7h12由此可见，每一个位都有3个校验和对其进行纠错，所以可以纠一个错。一般来说，因为每一列都有 个1，相应的行向量可作为校验和，又因为其他列1的个数最多为1，所以可以构成大数逻辑译码，能纠 / 2个错。提纲一、历史和特点二、定义和代数结构三、Tanner图（二分图）3.1 Tanner

6、图3.2 环的影响四、构造五、译码六、随机LDPC码3.1 Tanner图（二分图）矩阵的图形表示（循环码)1111111111111111111117654321SSSSSSSHV1 V2 V3 V4 V5 V6 V7不包含长度为不包含长度为4的环的环(码元码元)比特节点比特节点,符号节点符号节点（code-bit vertices, symbol nodes)变量点变量点(variable nodes)校验节点校验节点（check nodes)3.2 环的影响含有长为含有长为4的环的环含有长为含有长为6的环的环不能校验（不能校验（x0 x00 xx)和（和（x1x11xx)S2= +v2

7、+v4 S3= +v2 +v5 S4= +v4+v5 提纲一、历史和特点二、定义和代数结构三、Tanner图（二分图）四、构造4.1 Gallager 构造一类码4.2 通过行分裂和列分裂的码构造方法 4.3 有限几何LDPC五、译码六、随机LDPC码4.1 Gallager 构造一类码111111111111111111111111111111111111111111111111111111111111H1 (J1 J1 )H2H1 的列置换的列置换H3H1 的列置换的列置换 (J1=5, =4, =3)构成（构成（20，7，6）码）码4.1 Gallager 构造一类码HHHH.21Gal

8、lager构造一类构造一类LDPC码的方码的方法，但法，但Gallager并没有提供并没有提供H1 的列置换的方法，需要计算机的列置换的方法，需要计算机搜索。搜索。H1 的的列置换列置换H1 的的列置换列置换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分配给gi,2, ,.1111111111111111111111111111 111

9、1111111111111111111111111extHH通过列(行)分裂操作可以拆散长度为4的环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) 称为点(point)，0向量称为原点(origin)。n设a，a0为EG(m,ps)两个线性独立的点， 其中a0（不是原点)，则ps个点组成的集合a+a0: GF(ps)称为EG(m,ps)的一条直线(line)或

10、一维平面（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,ps)共有p(m-1)s(pms-1)/(ps-1)条直线。4.3 有限几何LDPC点点线线HEG =校验矩阵的行对应欧几里德集合的校验矩阵的行对应欧几里德集合的线，线，列对用于欧几里德集合的列对用于欧

11、几里德集合的点点矩阵的元素对应欧几里德集合的点线的关联向量值矩阵的元素对应欧几里德集合的点线的关联向量值(行向量是关联行向量是关联向量）向量）HEG共p(m-1)s(pms-1)/(ps-1)行，n=pms列。由于每条直线只有ps个点，因此行重=ps每一列的总量为 (pms-1)/(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 (其它）其它）提纲一、历史和特点二、定义和代数结构三、Tanner图（二分图）四、构造五、译码5.

12、1 大数逻辑译码5.2 比特翻转译码5.3 加权大数逻辑或加权比特翻转译码5.4 后验概率译码5.5 基于置信度传播的迭代译码 (和积算法）六、随机LDPC码5.1 大数逻辑译码111111111111111111111111111111111111111111111111111111111111Al=h1,h7,h12可用大数可用大数逻辑译码逻辑译码对第对第2位位进行校验进行校验h1h7h12由此可见，每一个位都有3个校验和对其进行纠错，所以可以纠一个错。对于每个比特位置l,H的行向量存在一个行的子集 Al=h1(l), h2(l), h (l) 在该比特位置正交，即Al每一行的第个分量都为

13、1，而其他位置的分量最多只在某一行出现 一般来说，因为每一列都有 个1，相应的行向量可作为校验和，又因为其他列1的个数最多为1，所以可以构成一步大数逻辑可译码，能纠 / 2个错。由于每一列都可找到相应校验和式，不需要循环。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-k,n-2 hn-k,0H= (hn-1, hn-2, , h1,h0 )设e

14、= (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发生错误的位所对应的列发生错误的位所对应的列向量的线性组合向量的线性组合五、线性分组码的译码2例：7，3码， H=101 | 1000111 | 0100110 | 0010011 | 0001s = r HT= ( r6 r5 r4 r3 r2 r1 r0 ) 101 | 1000111 | 0100110 |

15、 0010011 | 0001Tr6 + r4 + r3r6 + r5 + r4 + r2r6 + r5 + r1r5 + r4 + r0=T= （s3 s2 s1 s0) 五、线性分组码的译码3c =(1010011)e =(0100000)r =(1110011)s = r HT = e HT = (0100000) 101 | 1000111 | 0100110 | 0010011 | 0001T=0111Tc =(1010011)e =(1001000)r = (0011011)s = r HT = e HT = (1001000) 101 | 1000111 | 0100110 |

16、0010011 | 0001T=1110T+T1000=(0110)5.2 比特翻转译码算法111111111111111111111111111111111111111111111111111111111111假设假设v2,v3有错，则有错，则s7, s8, s12,s13都都不为不为0，而其它的而其它的sj都为都为0(因此因此f2=f3=2,见见后，后，fj=0,j取取115的其它值的其它值)h1h7h12h8h135.2 比特翻转译码算法比特翻转译码算法n 计算所有奇偶校验和，如果所有的奇偶校验和都和0，则停止译码；n 对于接收序列的每个比特位i，计算包括它的错误奇偶校验方程的个数，记为

17、fi, i= 0,1,n-1 对于上例，f2=f3=2, fj=0, j=1,415n 选取fi大于某个参数 的的比特位，组成集合S;n 将S的比特位翻转；n 重复14步，直至所有的奇偶校验和等于0或者达到最大迭代次数。1. 设计参数 称为门限（threshold),与， ，dmin,和信噪比有关。5.3 加权大数逻辑或加权比特翻转译码接收端匹配滤波器输出的软判决接收序列y=(y0,y0,yn-1)。对于加性高斯白噪声(AWGN)信道，接收符号yl的幅度| yl |是其可靠性的一种简单量度：幅度越大，硬判决数字zl的可靠度就越高。定义 | yj |(l)min min | yi |: 0 i

18、n-1, hj,i =1 将在比特位置l正交的校验和式调整为加权检验和式：根据El修改一步大数逻辑译码：lljSsljljlysE)()(min)(| ) 12(lH111Als1(l)s(l)sj(l)Sl=s1(l), s2(l), sj(l), s(l)）的校验和没有超过半数中为多）的校验和比中为表示1( 0 0,01 ( , 0 , 1lllllSESEe5.4 和积算法（sum-product algorithm, SPA)n是一种基于置信度传播的迭代译码 （iterative decoding algorithm based on belief propagation, IDPB)

19、n一种逐符号、软输入软输出（SISO)的译码算法。n对于每个符号的可靠度的量度可以采用其边缘后验概率、对数似然比或者对应接受符号值。每次译码迭代得到的码符号的可靠度量度的计算结果作为下一次迭代的输入。译码迭代持续进行，直到满足某个特定的停止条件。然后，基于码符号的可靠度量度的计算结果做出硬判决。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

20、,(i) 3,61,(i)q3,30,(i)q3,40,(i)令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)110)1()0()( ,1,)( ,

21、0,)( ,1,)( ,0,)(,10)1( ,)(,)( ,满足条件的归一化算子，选取和是不变的外信息。概率，对每次迭代都是的先验和为迭代前信道给出和其中，iljiljiljiljiljllllllhAhixltxliljixljqqqqvvvppvpppqjltl)1( , 14, 4)1( , 14, 14)(4, 3)( , 14, 3) 1(iiiivpq 1,41,(i-1) 4,41,(i-1)q3,41,(i)1( , 14, 4)1( , 14, 14)(4, 3)( , 14, 3) 1(iiiivpq 1,41,(i-1) 4,41,(i-1)q3,41,(i)令 )(:

22、 )()( ,)( , . ) )(: ,|0(lBtvlBtivtjjtljixljjtjtqlBtvxvsPh hh hh h即给定即给定vl=x(0或或1）和）和B(hj)中其他码比特的可分离的分布中其他码比特的可分离的分布qj,lx,(i): tB(hj)l的条的条件下，校验和件下，校验和sj正确（即正确（即sj =0)的条件概率。的条件概率。(比特节点比特节点vl状态为状态为x和与校验点和与校验点sj中相连的其它比特节点状态已知的条件下，校验和为中相连的其它比特节点状态已知的条件下，校验和为0的概率的概率)。（1）其它满足， , 0) )(: ,( 1) )(: ,|0(jjtljt

23、ljslBtvxvlBtvxvsPh hh h 3,61,(i)q3,30,(i)q3,40,(i)q3,31,(i)q3,41,(i)( , 04, 3)( , 13 , 3)( , 14, 3)( , 03 , 3)( , 14, 3)( , 13 , 34363)( , 04, 3)( , 13 , 34363)( , 14, 3)( , 03 , 34363)( , 04, 3)( , 03 , 34363,)( ,4, 3)( ,3 , 34363)( , 16, 3 )1, 1 , 1|0( )0, 1 , 1|0( )1, 0 , 1|0( )0, 0 , 1|0(), , 1|

24、0(4343iiiiiiiiiiiivviviviqqqqqqvvvsPqqvvvsPqqvvvsPqqvvvsPqqvvvsP 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) ) 1( ,)0()1( , 14, 4)1( , 14, 14)(4, 3)( , 14, 3)1( , 04, 4)1( , 04, 14)(4, 3)( , 04, 3iiiiiiiivpqvpq)( , 04, 3)( , 13 , 3)( , 14, 3)( , 03 , 3)(

25、, 16, 3 iiiiiqqqq ) 1( ,)0()1( , 13 ,7)1( , 13 , 23)(3 , 3)( , 13 , 3)1( , 03 ,7)1( , 03 , 23)(3 , 3)( , 03 , 3iiiiiiiivpqvpqnqj,lx,(i) :在除sj外参与的其它其它校验点提供的信息上，vl的状态为x的置信度。n j,l0,(i):比特节点比特节点vl状态为状态为x和与校验点和与校验点sj中相连的中相连的其它其它比特节点比特节点状态已知的条件下，校验和为状态已知的条件下，校验和为0的概率。的概率。取取其它其它校验点校验点/比特节点：不采用已经输入的信息，避免信息返

26、比特节点：不采用已经输入的信息，避免信息返流，保持信息的独立性，增强迭代效果。流，保持信息的独立性，增强迭代效果。的选取满足条件的先验概率。和为和其中，给出：步，伪后验概率由下式在迭代的第1)|1()|0(10 ),1()0()|()()()(10)1( ,)()(yvPyvPvvvppvpppyxvPililiilllllllAhixljxlillilj得到的得到的 j,lx,(i)用来更新用来更新qj,lx,(i1)。110)1()0(,)1( ,1,)1( ,0,)1(,10)( ,)1(,)1( ,取满足条件的选子的先验概率。归一化因和迭代前信道给出为和其中，iljiljiljllll

27、llhAhixltxliljixljqqvvvppvpppqjlt)1( , 14, 4)1( , 14, 3)1( , 14, 14)(44)() 1()| 1(iiiiivpyvP 1,41,(i-1) 4,41,(i-1) 3,41,(i-1)作为译码结果。，则停止迭代，输出。如果等于然后，计算其它，其中，条件：形成如下向量作为译码基于这一组概率，可以)(1)()()(1)(1)(1)(0)(0, 05 . 0)|1(1),.,(iTiliiiniiizHzyvPzzzzz。的选取满足条件的先验概率。和为和其中，给出：步，伪后验概率由下式在迭代的第1)|1()|0(10 ),1()0()|()()()(10)1( ,)()(yvPyvPvvvppvpppyxvPililiilllllllAhixljxlillilj得到的得到的 j,lx,(i)用来更新用来更新qj,lx,(i1)。110)1()0(,)1( ,1,)1( ,0,)1(,10)( ,)1(,)1( ,取满足条件的选子的先验概率。归一化因和迭代前信道给出为和其中，iljiljiljllllllhAhixltxliljixljqqvvvppvpppqjlt算法：初始化 设定i=0和迭代的最大次数Imax。对于满足hj,l =