纠错LDPC的原理讲解

G的维数巨大，G一般也并不稀疏。比如一个（10000，5000）LDPC码，P矩阵将是5000×5000矩阵。假设“1”的密度是0.5，编码所作的运算也有0.5×(5000×5000)=12.5×106次（注：H在系统化之前是稀疏矩阵，系统化后不一定。若H在系统化后是稀疏矩阵，G是稀疏的）简化编码的方法之一是利用代数或几何途径来设计LDPC码，使之能用移位寄存电路实现编码.LDPC码的迭代译码一般线性分组码的译码方法：当C是码字时，有CHT=0对于BSC信道,R=CE,其中E是差错矢量。译码器的任务是要找出E，把它加到接收码上C=RE。译码算法一般是基于线性代数，运算量随码长指数上升。LDPC码通常采用基于图的译码算法，比如1.和-积(Sum-product)算法（用在基于一般图的编码）2.MAP(BCJR)算法（用在基于网格图的编码）3.消息传递(Messagepassing)算法（用在基于二分图的码）消息传递(MessagePassing)算法是一种最大似然(ML-Maximumlikelihood)译码定义似然度L=似然度与硬判决的关系ĉi=约束条件CHT=0“消息传递”的内容是取“1”或“0”的概率(似然度)，与MAP(BCJR)算法中的外信息(extrinsicinformation)类似。“消息传递”分两个阶段，第一阶段是比特节点的概率，第二阶段是校验节点的概率，上述过程中，假设后验(posterior)概率互相独立Pr[ci=1|r]Pr[ci=0|r]1如L>10如L<1算法所用符号定义qij－从比特节点ci传递到校验节点fj的消息rji－从校验节点fj传递到比特节点ci的消息Rj={i:hji=1}-H矩阵第j行中,值为1的元素所在的列号的集合Rj\i={i:hji=1}\{i}-集合Rj中扣除了列号i后剩余的集合Ci={j:hji=1}-H矩阵第i列中,值为1的元素所在的行号的集合Ci\j={j:hji=1}\{j}-集合Ci中扣除了行号j后剩余的集合pi=Pr(ci=1|ri)－收码ri条件下,发码ci=1的概率比如H＝11100000R2={0,3,6},00011100R2\3={0,6}10010010C4={1,3},01001001C4\3={1}f0f0f2c0c1c2c0q00q10q20r00r20计算仅涉及到H矩阵的非零元素，即i,j，符合hij=1的项1.初值qij(0)=1-pi=Pr(ci=0|ri)=1/(1+)qij(1)=pi=Pr(ci=1|ri)=1/(1+)2.迭代上半轮rji(0)=rji(1)=1-rji(0)3.迭代下半轮qij(0)=kij(1-pi)这里，kij的选择应能保证qij(1)=kijpiqij(0)+qij(1)=14.软判决Qi(0)=ki(1-pi)Qi(1)=kipi这里，ki选择得使约束条件Qi(0)+Qi(1)=1成立5.硬判决ci=如果CHT=0或迭代次数超限，算法结束。否则，进入2开始新一轮迭代。1如果Qi(1)>00其它MessagePassing算法的特点MessagePassing算法存在着一种译码门限现象。当信道的信噪比低于该门限时，译码后的误码率能够任意的趋于0，而当信噪比高于门限时，译码后的误码率将不能够趋于0。算法工作在二分图模型上，在图中没有圈的条件下，算法的输出结果将精确地成为码字比特的后验概率，在图中有圈的条件下，经过一定次数的迭代后，圈中节点接收到的信息与节点的信道输出信息不再是相互独立的，导致算法译码性能的下降。信度传递(BeliefPropagation)算法若MP算法中译码器的输入（信道输出）符号集和所译信息码符号集相同，都为实数集R，且适当选择信息映射函数，MP算法就成了BP算法。信度传递算法BP是MP的一个子类，归于最大对数似然译码(MaximumLog-likelihood)之列。令消息比特为xi，校验比特为yi，定义:条件概率Pr[xi=0|yi]和Pr[xi=1|yi]满足Pr[xi=0|yi]+Pr[xi=1|yi]=1(1)似然比L(xi)=(2)条件似然比L(xi|yi)=(3)对数条件似然比lnL(xi|yi)=ln(4)Pr[xi=0]Pr[xi=1]Pr[xi=0|yi]Pr[xi=1|yi]Pr[xi=0|yi]Pr[xi=1|yi]设xi是二进制硬判决值而yi是模拟随机变量，利用式(1)Pr[x1=0|y1]＝1-Pr[x1=1|y1]的关系，可知2Pr[x1=0|y1]-1=-{2Pr[x1=1|y1]-1}(5)2Pr[x2=0|y2]-1=-{2Pr[x2=1|y2]-1}这里2Pr[x1=0|y1]-1是对Pr[x1=0|y1]的移位扩展Pr[x1=0|y1]以0.5为中心，取值范围[0,1]而2Pr[x1=0|y1]-1以0为中心，取值范围[-1,1]2Pr[x1=0|y1]-1的正负号是xi硬判决依据。在xi等概的条件下,由贝叶斯，有L(xi|yi)=L(yi|xi)若校验比特y是独立的随机变量，应有lnL(xi|y1,y2,…,yd)=lnL(xi|yi)(6)似然度的绝对和相对量值：2Pr[x1=0|y1]-1是似然度的绝对量值，而条件似然比L(xi|yi)是似然度的相对量值。似然度的绝对与相对量值间存在着确定的关系。从绝对量值推相对量值的关系式是L(xi|yi)==(7)从相对量值推绝对量值的关系式：两边乘（1-Pr[xi=0|yi]）后整理，可得Pr[xi=0|yi]=即2Pr[xi=0|yi]-1=-1==tanh(li/2)(8)这里li是对数条件似然比，li=lnL(xi|yi),tanh(x)=Pr[xi=0|yi]Pr[xi=1|yi]Pr[xi=0|yi]1-Pr[xi=0|yi]L(xi|yi)1+L(xi|yi)L(xi|yi)-1L(xi|yi)+1ex–e-xex+e-x2L(xi|yi)1+L(xi|yi)令li是对数条件似然比li=lnL(xi|yi)(9)则条件似然比L(xi|yi)=eli(10)由(8)式，条件概率2Pr[xi=0|yi]-1====tanh(li/2)(11)(11)式两边乘以L(xi|yi)+1后整理，可改写(10)条件似然比为L(xi|yi)=(12)以及改写(9)对数条件似然比为li=lnL(xi|yi)=ln(13)eli–1eli+1L(xi|yi)-1L(xi|yi)+1eli/2–e-li/2eli/2+e-li/21+tanh(li/2)1-tanh(li/2)1+tanh(li/2)1-tanh(li/2)多位判决的联合概率两位判决的联合概率应为2Pr[x1=0,x2=0|y1y2]-1=2Pr[x1=1,x2=1|y1y2]-1=2Pr[x1x2=0|y1y2]-1=tanh(l1/2)tanh(l2/2)，式中代表模2加。以此类推，多位判决的联合概率(绝对似然度)应为2Pr[x1…xm=0|y1y2…ym]-1={2Pr[xi=0|yi]-1}=tanh(li/2)(14)(7)式两边乘(Li+1)后整理可得Li=或取对数lnLi=ln1+tanh(li/2)1-tanh(li/2)1+tanh(li/2)1-tanh(li/2)图结构对码性能的影响二分图中环的存在是我们对迭代译码过程进行准确概率分析的一个障碍，并且图中的环越短，分析过程也将越早被迫中断。观察下图所示某校验矩阵的二分图片断： 图中有一个长度为4的环（用粗线条表示），迭代4次就可能发生信息反馈。如果构造校验矩阵时使得任两列之间重叠的1最多只有一个，那么就可以消除长度为4的环。LDPC码H矩阵的任意两列间至多只能有一个‘1’在同一行。这是因为：两个“1”在同行将导致Tanner图上的一个4节闭环(4-cycle),如图所示H=11100000000111001001011001001001校验节点(行）f0f1f2f3fjci比特节点(列)c0c1c2c3c4c5c6c7............比特节点校验节点二分图中存在最小长度为6的环，码的最小距离有可能为3，纠错能力小于2。在构码时，如何消除短长度环，提高环的平均长度是需要着重考虑的问题。为了定量研究二分图中的环，引入了术语“girth”（围长）。二分图girth指图中最短闭环的围长。例如：某个二分图有长度为6、8、10、12和长度更长的圈，其中最短者为6，则该二分图的girth为6。全图有全图的girth，节点也有节点的girth。某节点的girth(thegirthatnode)指经过节点的最短闭环的围长。例如，经过某节点有长度为8、10、12和更长的环，则该节点的girth为8。定义比特节点girth的分布（girthdistribution）等于girth为某值的比特节点占整个变量节点的比例，即g(l)=围长为l的比特节点数/比特节点总数这里，l=2,4,…,lm,l一定是偶数，最大值是lm。定义girth的平均值为，编码研究很大一部分在于如何取得高girth值。LDPC码校验矩阵的构造方法Gallager的构造方法MacKay的构造方法超轻（Urltra-Light）构造法非正则码的构造LDPC码的译码MessagePassing算法BSC信道译码软判决译码BEC信道译码并行译码算法基于迭代可靠性的译码算法LDPC码的实现LDPC码可以用DSP，FPGA，模拟的VLSI和ASIC等硬件来实现，有很多文献都谈到了这些实现。其中，Flarion公司[20]开发了LDPC编码/译码产品，称为Vector-LDPC。采用FPGA实现，主频100MHz，码率0.9，编码器利用64k逻辑门和13kB存储器时，用户数据速率可以达到1.9Gbps；译码器使用320k逻辑门和38kB存储器时，用户数据速率为384Mbps。采用ASIC实现，译码器可工作在10Gbps。LDPC码的应用LDPC码有很好的应用前景，将在深空通信、光纤通信、卫星通信、磁/光/全息存储、移动和固定无线通信、电缆调制/解调器和数字用户线（DSL）中得到广泛应用。尤其需要指出的，因为LDPC码具有比turbo码更简单有效地译码，并可线性时间编码，和更好的性能，它必然将成为下一代高速移动通信系统4G的纠错编码方案。数字电视地面广播传输系统帧结构、信道编码和调制（GB20600-2006）发送端原理框图扰码FEC编码复用星座映射与交织系统信息帧体数据处理组帧帧头基带后处理正交上变频数据入射频出数字电视地面广播传输系统帧结构、信道编码和调制（GB20600-2006）4.4编码与调制4.4.1扰码生成多项式G(x)=1+x14+x15LFSR(linearfeedbackshiftregister)的初相100101010000000DDDDDDDDDDDDDDDPN序列输出4.4.2前向纠错BCH+LDPCFEC码参数BCH(762,752)由本原BCH(1023,1013)码缩短而成。在扰码输出的752比特前加261比特0后进行BCH(1023,1013)编码，然后去除前261个0，形成762比特的缩短BCH(762,752)码生成多项式是GBCH(x)=1+x3+x100.860167488码率30.645127488码率20.430087488码率1编码效率信息比特块长(bit)编号LDPC（7493,3048）码的生成矩阵是其中I是b×b阶单位阵，0是b×b阶零阵生成子矩阵Gij和校验矩阵的定义分别见此的附录A和Bk、c、b的参数有三种1.码率0.4，b=127,k=24,c=35先由4个BCH(762,752)码和LDPC(7493,3048)构成级联码，然后删除LDPC(7493,3048)码校验位的前5位，码长变为7488，信息位752×4=3008.2.码率0.6，b=127,k=36,c=23先由6个BCH(762,752)码和LDPC(7493,4572)构成级联码，然后删除LDPC(7493,3048)码校验位的前5位，码长变为7488，信息位752×6=4512.3.码率0.8，b=127,k=48,c=11先由8个BCH(762,752)码和LDPC(7493,6096)构成级联码，然后删除LDPC(7493,3048)码校验位的前5位，码长变为7488，信息位752×8=6016.4.4.3符号星座映射5种星座可选：64-QAM、32-QAM、16-QAM、4-QAM和4QAM-NR先进入比特为低位（LSB-leastsignificantbit），比如（b5b4b3b2b1b0）中的b0是先进入的比特。映射时将输入比特分为同相（实坐标）和正交（虚坐标）两部分，按格雷（循环）码的规律排列，相邻两码间仅变化一位，首位区分正负。比如3位格雷码的顺序是000,001,011,010,110,111,101,100星座已作归一化处理，5种不同星座的平均功率是相同的 ╵ ╵╵╵╵╵╵╵-7-5-3-11357–7–5–3–1–-1–-3–-5–-7000000000110000010000011001110000111000101000100001000001010001001001011001111000001001100001101011100011000011110011010011011011001011101011111010000010110010010010011010001010100010101010111110100110000110110110010110011110001110101110111111100111000111110111010111011111001111101111111101100101000101110101010101011101001101101101111100100100000100110100010100011100001100101100111Bit顺序b5b4b3b2b1b0同相b2b1b0正交b5b4b364－QAM映射 ╵ ╵╵╵╵╵-7.5-4.5-1.51.54.57.5–7.5–4.5–1.5–-1.5–-4.5–-7.51100110001101011110101001000010010110000110000110101000000000010010100111000110001010000100011010110111100111001011000110011110010110100111111011100111011111111Bit顺序b4b3b2b1b032－QAM映射╵╵╵╵-6-226–6–2–-2–-616－QAM映射Bit顺序b3b2b1b0同相b1b0正交b4b30000001000110001010001100111010111001110111111011000101010111001╵╵-4.54.5–4.5–-4.54－QAM映射Bit顺序b1b0同相b0正交b1100111004QAM-NR映射NR-NordstromRobinson准正交q完