纠错LDPC

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,LDPC,码,1,LDPC,（,低密度校验）码,（,Low Density Parity Check,）,基本思路：,校验矩阵是稀疏矩阵，极长码。只对“,1”,迭代,Turbo,译码,LDPC,码,历史,Robert,Gallager,1960,年在,MIT Ph. D.,论文中提出，但由于,1.,计算量大,2.,RS,码的引入,3.,RS,卷积码被认为是最佳搭配,因此该码被忽视了几十年,MacKay (1999),和,Richardson/Urbanke(1998),重新发现了该码的优点和利用方式,.,2,逼近,Shannon,限，例如,在,二元输入的,AWGN,信道,，,码率,1/2,的,非正则,(,Irregular),LDPC,码可具有,离香农限,不到,0.06,dB,的性能,;,计算机仿真结果表明，最好的非正则,LDPC,码,(,长度为,10,6,),可获得在,BER=10,-6,时仅偏离容量,0,13,dB,的性能，优于迄今所知道的最佳,turbo,码,(,Richardson,2001),当码长为,10,7,、,R=1/2,时，性能距,香农,限只差,0.0045,dB,的次数分布对已经找到,.,(,Chung,2001),纠码字差错,block error,的性能好,差错平台,error floor,低(,误码率随信噪比的增加而下降减速甚至不再下降，称为,error floor,现象）,最小距离正比于码长,译码复杂度与码长,是线性关系,适合并行译码运算,LDPC,码性能,3,线性分组码基础,可用一个生成矩阵,G,或,校验矩阵,H,来,描述,The structure,纠错能力由最小距离,d,mi,n,决定。,最小距离,d,mi,n,等于,生成矩阵,G,中最轻行的重量,最小距离,d,mi,n,也等于,校验矩阵,H,的秩加,1,比如,(7, 4),汉明码,G,=,H,=,非稀疏矩阵,码字和校验矩阵的关系：,CH,T,=0,或,HC,T,=0,1 0 0 0 1 1 1,0 1 0 0 1 1 0,0 0 1 0 1 0 1,0 0 0 1 0 1 1,1 1 1 0 1 0 0,1 1 0 1 0 1 0,1 0 1 1 0 0 1,4,LDPC,码结构特点,(1),说(,n,k,),分组码校验,矩阵,H (,n-k,行,n,列),是稀疏矩阵,，指其每行每列只有极少个“,1”,而,最小距离,d,mi,n,又,较大。,正则（规则）的,LDPC,码:,指,H,矩阵每列,(,column),有同样,w,c,个“,1”,，,每行,(,row),有同样,w,r,个“,1”,，且,=,这里,m,=,n-k,，,w,c,m,，,w,r,1,0 如,L ,0,0,其它,23,Message Passing,算法的特点,Message Passing,算法存在着一种译码门限现象。当信道的信噪比低于该门限时，译码后的误码率能够任意的趋于,0,，而当信噪比高于门限时，译码后的误码率将不能够趋于,0,。,算法工作在二分图模型上 ，在图中没有圈的条件下，算法的输出结果将精确地成为码字比特的后验概率，在图中有圈的条件下，经过一定次数的迭代后，圈中节点接收到的信息与节点的信道输出信息不再是相互独立的，导致算法译码性能的下降。,24,信度传递,(,Belief Propagation),算法,若,MP,算法中译码器的输入（信道输出）符号集 和所译信息码符号集相同，都为实数集,R，,且适当选择信息映射函数，,MP,算法就成了,BP,算法,。,信度传递算法,BP,是,MP,的一个子类,，归于最大对数似然译码,(,Maximum Log-likelihood),之列。,令消息比特为,x,i,，,校验,比特为,y,i,，,定义,:,条件概率,Pr,x,i,=0|,y,i,和,Pr,x,i,=1|,y,i,满足,Pr,x,i,=0|,y,i, +Pr,x,i,=1|,y,i, = 1 (1),似然比,L(,x,i,),= (2),条件似然比,L(,x,i,|,y,i,),= (3),对数条件似然比,ln,L(,x,i,|,y,i,),=,ln,(4),Pr,x,i,= 0,Pr,x,i,= 1,Pr,x,i,=0 |,y,i,Pr,x,i,=1 |,y,i,Pr,x,i,=0 |,y,i,Pr,x,i,=1 |,y,i,25,设,x,i,是,二进制硬判决值而,y,i,是,模拟随机变量，,利用式,(1),Pr,x,1,=0|,y,1, 1-Pr,x,1,=1|,y,1,的关系，可知,2,Pr,x,1,=0|,y,1,-1 = - 2Pr,x,1,=1|,y,1,-1 ,(5),2Pr,x,2,=0|,y,2,-1 = - 2Pr,x,2,=1|,y,2,-1 ,这里,2,Pr,x,1,=0|,y,1,-1,是对,Pr,x,1,=0|,y,1,的,移位扩展,Pr,x,1,=0|,y,1,以,0.5,为中心，取值范围, 0 ,1,而,2,Pr,x,1,=0|,y,1,-1,以,0,为中心，取值范围, -1,1,2,Pr,x,1,=0|,y,1,-1,的正负号是,x,i,硬判决依据。,在,x,i,等概的条件下,由贝叶斯公式，有,L(,x,i,|,y,i,),=,L(,y,i,|,x,i,),若校验比特,y,是独立的随机变量，应有,ln,L(,x,i,|,y,1,y,2, ,y,d,) =,ln,L(,x,i,|,y,i,),(6),26,似然度的绝对和相对量值：,2,Pr,x,1,=0 |,y,1,-1,是似然度的绝对量值， 而,条件似然比,L(,x,i,|,y,i,),是,似然度的,相对,量值。,似然度的绝对,与相对量值间存在着确定的,关系。,从绝对,量值推相对量值的关系式是,L(,x,i,|,y,i,) = =,(7),从,相对量值推,绝对,量值的关系式：,两边乘（,1-,Pr,x,i,=0|,y,i,）,后,整理，可得,Pr,x,i,=0 |,y,i,=,即,2,Pr,x,i,=0|,y,i,-1= -1= =,tanh,(,l,i,/2),(8),这里,l,i,是,对数条件似然比,，,l,i,=,lnL,(,x,i,|,y,i,),tanh,(,x,) =,Pr,x,i,=0 |,y,i,Pr,x,i,=1 |,y,i,Pr,x,i,=0 |,y,i,1-Pr,x,i,=0|,y,i,L,(,x,i,|,y,i,),1+L,(,x,i,|,y,i,),L,(,x,i,|,y,i,),-1,L,(,x,i,|,y,i,),+1,e,x, e,-,x,e,x,+ e,-,x,2,L,(,x,i,|,y,i,),1+L,(,x,i,|,y,i,),27,令,l,i,是,对数条件似然比,l,i,=,lnL,(,x,i,|,y,i,),(9),则,条件似然比,L,(,x,i,|,y,i,) =,e,li,(10),由(8),式，条件概率,2,Pr,x,i,=0|,y,i,-1= = = =tanh(,l,i,/2),(11),(11),式两边乘以,L,(,x,i,|,y,i,),+1,后,整理，可改写,(10),条件似然比为,L,(,x,i,|,y,i,) =,(12),以及改写,(9),对数条件似然比为,l,i,=,lnL,(,x,i,|,y,i,) =,ln,(13),e,li,1,e,li,+1,L,(,x,i,|,y,i,),-1,L,(,x,i,|,y,i,),+1,e,li/2,e,-,li/2,e,li/2,+,e,-,li/2,1+,tanh(,l,i,/2),1-,tanh,(,l,i,/2),1+,tanh(,l,i,/2),1-,tanh,(,l,i,/2),28,多位判决的联合概率,两位判决的联合概率应为,2,Pr,x,1,=0,x,2,=0 |,y,1,y,2,-1= 2Pr,x,1,=1,x,2,=1 |,y,1,y,2,-1,=2Pr,x,1,x,2,=0 |,y,1,y,2,-1 = tanh(,l,1,/2),tanh(,l,2,/2) ，,式中代表模,2,加。,以此类推，多位判决的联合概率,(,绝对似然度,),应为,2,Pr,x,1,x,m,=0|,y,1,y,2,y,m,-1,= 2Pr,x,i,=0|,y,i,-1 =,tanh,(,l,i,/2),(14),(7),式,两边乘,(,L,i,+1),后整理可得,L,i,=,或,取对数,lnL,i,=,ln,1+tanh(,l,i,/2),1-tanh(,l,i,/2),1+tanh(,l,i,/2),1-tanh(,l,i,/2),29,图结构对码性能的影响,二分图中环的存在是我们对迭代译码过程进行准确概率分析的一个障碍，并且图中的环越短，分析过程也将越早被迫中断。观察下图所示某校验矩阵的二分图片断：,图中有一个长度为,4,的环（用粗线条表示），迭代,4,次就可能发生信息反馈。,如果构造校验矩阵时使得任两列之间重叠的,1,最多只有一个，那么就可以消除长度为,4,的环。,30,LDPC,码,H,矩阵的任意两列间至多只能有一个,1,在,同一行。这是因为：两个“,1”,在同行将导致,Tanner,图上的一个,4,节闭环,(4-,cycle),如图所示,H=,1 1 1 0 0 0 0 0,0 0 0,1,1,1,0 0,1 0 0,1,0,1,1 0,0 1 0 0 1 0 0 1,校验节点,(,行）,f,0,f,1,f,2,f,3,f,j,c,i,比特节点,(列),c,0,c,1,c,2,c,3,c,4,c,5,c,6,c,7,31,.,.,.,.,比特节点,校验节点,二分图中存在最小长度为,6,的环，码的最小距离有可能为,3,，,纠错能力小于,2,。,在构码时，如何消除短长度环，提高环的平均长度是需要着重考虑的问题。,为了定量研究二分图中的环，引入了术语“,girth”（,围长）,。二分图,girth,指图中最短闭环的围长。例如：某个二分图有长度为,6,、,8,、,10,、,12,和长度更长的圈，其中最短者为,6,，则该二分图的,girth,为,6,。,32,全图有全图的,girth，,节点也有节点的,girth。,某节点的,girth(the girth at node ),指经过节点的最短闭环的围长。例如，经过某节点有长度为,8,、,10,、,12,和更长的环，则该节点的,girth,为,8,。,定义比特节点,girth,的,分布（,girth distribution,）,等于,girth,为某值的,比特节点占整个变量节点的比例，即,g(,l,)=,围长为,l,的,比特节点数,/,比特节点总数,这里，,l =,2,4,l,m,l,一定是偶数，最大值是,l,m,。,定义,girth,的平均值为，,编码研究很大一部分在于如何取得高,girth,值。,33,LDPC,码校验矩阵的构造方法,Gallager,的构造方法,MacKay,的构造方法,超轻（,Urltra,-Light）,构造法,非正则码的构造,34,LDPC,码的译码,Message Passing,算法,BSC,信道译码,软判决译码,BEC,信道译码,并行译码算法,基于迭代可靠性的译码算法,35,LDPC,码的实现,LDPC,码可以用,DSP,，,FPGA,，,模拟的,VLSI,和,ASIC,等硬件来实现，有很多文献都谈到了这些实现方案。其中，,Flarion,公司,20,开发了,LDPC,编码,/,译码产品，称为,Vector-LDPC,。,采用,FPGA,实现，主频,100,MHz,，,码率,0.9,，编码器利用,64,k,逻辑门和,13,kB,存储器时，用户数据速率可以达到,1.9,Gbps,；,译码器使用,320,k,逻辑门和,38,kB,存储器时，用户数据速率为,384,Mbps,。,采用,ASIC,实现，译码器可工作在,10,Gbps,。,36,LDPC,码的应用,LDPC,码有很好的应用前景，将在深空通信、光纤通信、卫星通信、磁,/,光,/,全息存储、移动和固定无线通信、电缆调制,/,解调器和数字用户线（,DSL,）,中得到广泛应用。尤其需要指出的，因为,LDPC,码具有比,turbo,码更简单有效地译码，并可线性时间编码，和更好的性能，它必然将成为下一代高速移动通信系统,4,G,的纠错编码方案。,37,数字电视地面广播传输系统帧结构、信道编码和调制,（,GB20600-2006）,发送端原理框图,扰码,FEC,编码,复,用,星座,映射与,交织,系统信息,帧体,数据处理,组,帧,帧头,基带,后处理,正交上变频,数据入,射频出,38,数字电视地面广播传输系统帧结构、信道编码和调制,（,GB20600-2006）,4.4,编码与调制,4.4.1,扰码,生成多项式,G(x)=1+,x,14,+,x,15,LFSR(,linear feedback shift register,),的初相100101010000000,D,D,D,D,D,D,D,D,D,D,D,D,D,D,D,PN,序列输出,39,4.4.2,前向纠错,BCH+LDPC,FEC,码参数,BCH(762,752),由本原,BCH(1023,1013),码缩短而成。,在扰码输出的,752,比特前加,261,比特,0,后进行,BCH(1023,1013),编码，然后去除前,261,个,0,，形成,762,比特的缩短,BCH(762,752),码,生成多项式是,G,BCH,(,x,)=1+,x,3,+,x,10,编号,块,长(,bit),信息比特,编码效率,码率1,7488,3008,0.4,码率2,7488,4512,0.6,码率3,7488,6016,0.8,40,LDPC,（7493,3048）,码的生成矩阵是,其中,I,是,bb,阶单位阵，,0是,bb,阶零阵,生成子矩阵,G,ij,和校验矩阵的定义分别见,此标准的附录,A,和,B,k、c、b,的参数有三种,41,1.码率0.4，,b=127,k=24,c=35,先由4个,BCH(762,752),码和,LDPC(7493,3048),构成级联码，然后删除,LDPC(7493,3048),码校验位的前5位，码长变为7488，信息位7524=3008.,2. 码率0.6，,b=127,k=36,c=23,先由6个,BCH(762,752),码和,LDPC(7493,4572),构成级联码，然后删除,LDPC(7493,3048),码校验位的前5位，码长变为7488，信息位7526=4512.,3. 码率0.8，,b=127,k=48,c=11,先由8个,BCH(762,752),码和,LDPC(7493,6096),构成级联码，然后删除,LDPC(7493,3048),码校验位的前5位，码长变为7488，信息位7528=6016.,42,4.4.3,符号星座映射,5种星座可选：64-,QAM、32 -QAM、16 -QAM、 4-QAM,和4,QAM-NR,先进入比特为低位（,LSB-least significant bit），,比如（,b,5,b,4,b,3,b,2,b,1,b,0,）,中的,b,0,是,先进入的比特。,映射时将输入比特分为同相（实坐标）和正交（虚坐标）两部分，按格雷（循环）码的规律排列，相邻两码间仅变化一位，首位区分正负。,比如3位格雷码的顺序是,000,001,011,010,110,111,101,100,星座已作归一化处理，5种不同星座的平均功率是相同的,43, ,-7 -5 -3 -1 1 3 5 7, 7, 5, 3, 1,-1,-3,-5,-7,000000,000110,000010,000011,001110,000111,000101,000100,001000,001010,001001,001011,001111,000001,001100,001101,011100,011000,011110,011010,011011,011001,011101,011111,010000,010110,010010,010011,010001,010100,010101,010111,110100,110000,110110,110010,110011,110001,110101,110111,111100,111000,111110,111010,111011,111001,111101,111111,101100,101000,101110,101010,101011,101001,101101,101111,100100,100000,100110,100010,100011,100001,100101,100111,Bit,顺序,b,5,b,4,b,3,b,2,b,1,b,0,同相,b,2,b,1,b,0,正交,b,5,b,4,b,3,64,QAM,映射,44, ,-7.5 -4.5 -1.5 1.5 4.5 7.5, 7.5, 4.5, 1.5, -1.5, -4.5, -7.5,11001,10001,10101,11101,01001,00001,00101,10000,11000,01101,01000,00000,00100,10100,11100,01100,01010,00010,00110,10110,11110,01110,01011,00011,00111,10010,11010,01111,11011,10011,10111,11111,Bit,顺序,b,4,b,3,b,2,b,1,b,0,32,QAM,映射,45, ,-6 -2 2 6, 6, 2,-2,-6,16,QAM,映射,Bit,顺序,b,3,b,2,b,1,b,0,同相,b,1,b,0,正交,b,4,b,3,0000,0010,0011,0001,0100,0110,0111,0101,1100,1110,1111,1101,1000,1010,1011,1001,46, ,-4.5 4.5, 4.5,-4.5,4,QAM,映射,Bit,顺序,b,1,b,0,同相,b,0,正交,b,1,10,01,11,00,47,4,QAM-NR,映射,NR-Nordstrom Robinson,准正交,48,q,49,完,50,