（通信与信息系统专业论文）脉冲噪声信道下基于高阶调制的ldpc码译码算法研究.pdf

上海师范大学硕士学位论文缩略词 3 g a w g n a r q b p b e r b e c b s c b f b p s k g s n r l d p c l l r l p l s m a p m p s k o f d m q a m s o v a s a s s p a u m 咿 v l s l 缩略词 3 “g e n e r a t i o n a d d i t i v e m i t eg a u s s i a nn o i s e a u t o m a t i cr e p e a tr e q u e s t b e l i e f p r o p a g a t i o n b i te r r o rr a t e b i n a r ye r a s u r ec h a n n e b i n a r ys y m m e t r yc h a n n e l b i tf l i p p i n g b i n a r yp h a s es h i f tk e y i n g g e o m e t r i c a ls i g n a l - t o - n o i s er a t i o l o w - d e n s i t yp a r i t yc h e c k ( l d p c ) c o d e s l o g - l i k e l yr a t i o l i n e a rp r o g r a m m i n g l e a s ts q u a r e m a x i m u map o s t e r i o dp r o b a b i l i t y m - - a r yp h a s e s h i f tk e y i n g o r t h o g o n a lf r e q u e n c yd i v i s i o nm u l t i p l e q u a d r a t u r ea m p l i t u d em o d u l a t i o n s o f t - o u t p u tv i t e r b ia l g o d t h r n s y m m e t r ya l p h a - s t a b l e s u m - p r o d u c ta l g o r i t h m u n i f o r m l ym o s tp o w e r f u l v e 巧l a r g es c a l ei n t e g r a t e d 3 9 第三代无线通信系统 加性高斯白噪声 重传反馈方式 置信度传播 误码率 二元删余信道 如二元对称信道 比特翻转 二进制相移键控 几何信噪比 低密度奇偶校验码 对数似然比 线性规化 最小二乘法 最大后验概率 m 元移相键控 正交频分复用 正交幅度调制 软输出v i t e r b i 算法 口平稳对称 和积算法 最大噪声功率归一化 超大规模集成电路 论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文中除 了特别加以标注和致谢的地方外，不包含其他人或机构已经发表或撰写过的研究 成果。其他同志对本研究的启发和所做的贡献均已在论文中做了明确的声明并表 示了谢意。 作者签名：黑0 峪同期：莎68 论文使用授权声明 n 7 | 本人完全了解上海师范大学有关保留、使用学位论文的规定，即：学校有权 保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的全部或部 分内容，可以采用影印、缩印或其它手段保存论文。保密的论文在解密后遵守此 规定。 作者签名浆导师签名： 日期 弘护r 7 论文题目t 脉冲噪声信道下基于高阶调制的l d p c 码译码算法研究 学科专业：通信与信息系统 学位申请人t 吴樱 指导教师：李莉 脉冲噪声信道下基于高阶调制的l d p c 码译码算法研究 摘要 本文的目标是对l d p c 码在加性脉冲噪声信道下的差错控制性能进行研究，论文主要工 作包括t 首先介绍了l d p c 码基本原理、规则l d p c 码的构造方式和译码算法； 提出t b p 算法的一种简化的线性拟合算法，采用此算法后在不影响误码性能的情况下， 既能降低复杂度，又能使硬件实现变得更加容易： 本文还对在二元a w g n ( 加性白高斯噪声) 环境下规贝j j l d p c 码与t u r b o 码的性能进行了 仿真分析，通过误码性能和译码复杂度两方面的比较，证明了规贝j j l d p c 码在中短帧传输下的 优异性能，这对l d p c 码投入实际应用具有重要的意义； 研究了l d i ) c 码在加性脉冲噪声信道中的l d p c 码的译码算法及其性能。l d p c 码在加性 脉冲噪声信道中使用b p 译码算法时，信道初始化消息没有闭式解，计算非常困难。通过分 析a w g n 信道下初始化消息的计算过程，提出用最小二乘测度计算信道初始化消息，从而简 化了标准b p 译码算法。由于脉冲信道所具有的特点，基于最小二乘测度的简化译码算法会 出现错误限底( e r r o rf l o o r ) 现象，因而提出用更具鲁棒性的h u b e r 钡u 度来计算信道初始化消 息。从仿真结果来看，在噪声符合蝴布的脉冲信道上，中等长度( 码长n = 5 1 4 4 ) 的规贝j j l d p c 码具有良好的误码性能。 最后介绍了加性脉冲噪声信道下基于高阶调制的软解调算法，并针对4 q a m ，1 6 q a m 的 b p 简化算法进行了性能仿真，仿真结果表明采用高阶调制的简化译码算法在降低了译码复 杂度的同时可实现高速率数据的可靠传输。 关键词：低密度奇偶校验码，置信度传播算法，脉冲加性噪声信道，q a m 调制 t i t l e ：as t u d yo fd e c o d i n ga l g o r i t h mf o rl d p cc o d e sb a s e do nh i 【曲o r d e rm o d u l a t i o no v e r i n p u l s i v en o i s ec h a n n e l s m a j o r ：t e l e c o m m u n i c a t i o na n di n f o r m a t i o ns y s t e m a p p l i c a n t ：w uy i n g t u t o r ：l i l i a s t u d yo fd e c o d i n ga l g o r i t h mf o rl d p cc o d e s b a s e do n h i g ho r d e rm o d u l a t i o no v e ri n p u l s i v en o i s ec h a n n e l s a b s t r a c t i nt h i s p a p e r , t h ed e c o d i n ga n dp e r f o r m a n c eo fl o w - d e n s i t yp a r i t y c h e c k ( l d p c )c o d e si sd i s c u s s e df o ra d d i t i v ei m p u l s en o i s ec h a n n e l s n l em a i nc o n t e n t s c a l lb es u m m a r i z e da sf o l l o w s ： 1 1 1 i sp a p e ri n t r o d u c e st h ep r i n c i p l e so fl d p cc o d e s ，i n c l u d i n gt h ee n c o d i n g s c h e m ec o d e sa n d d e c o d i n gs c h e m e al i n e a rc a l i b r a t i o no fb p d e c o d i n ga l g o r i t h mi sp u tf o r w a r dw h i c hc a ns i m p l i f y c a l c u l a t i o nc o m p l e x i t ya n dm a k eh a r d w a r ec o n v e n i e n tw i t h o u tn e g a t i v ee f f e c to nt h e p e r f o r m a n c eo fa l g o r i t h mp r o c e s s t h e nt h ep e r f o r m a n c ef o rr e g u l a rl d p cc o d e so na w g nc h a n n e li ss i m u l a t e d ，n l ea c t u a la d v a n t a g e so fr e g u l a rl d p cc o d e su n d e rt h es h o r ta n dm i d d l ef r a m e sc a i l b ev e r i f i e dt h r o u g hc o m p a r i s o n 、析1t u r b oc o d e s b pd e c o d i n ga l g o r i t h mi sd i s c u s s e df o ra d d i t i v ei m p u l s en o i s ec h a n n e l s w h e n b p a l g o r i t h mi su s e df o ra d d i t i v ei m p u l s en o i s ec h a n n e l s ，t h ei n i t i a lc h a n n e ll o g l i k e l y r a t i o ( l l r ) m e s s a g e sh a v en oc l o s ee x p r e s s i o n , a n dm o r e o v e r , c o m p u t a t i o no ft h e i n i t i a lc h a n n e ll l ri sv e r yd i f f i c u l t b yr e e x a m i n e dt h ec o m p u t a t i o no ft h ei n i t i a l c h a n n e ll l r m e s s a g e sf o ra w g nc h a n n e l s ，l e a s ts q u a r e ( l s ) m e t r i ci sp r o p o s e dt o c o m p u t et h ei n i t i a ll l rm e s s a g e sf o ri m p u l s en o i s ec h a n n e l s ，a n dt h ed e c o d i n g a l g o r i t h mi ss i m p l i f i e d s i n c et h ec h a r a c t e r i s t i c so fi m p u l s en o i s e ，b pa l g o r i t h m 谢t 1 1 2 l sm e t r i co c c u r se r r o rf l o o r i no r d e rt od i s s o l v et h i sp r o b l e m ，a n o t h e rr o b u s tm e t r i c ， i e ，h u b e rm e t r i ci si n t r o d u c e dt oc o m p u t et h ei n i t i a ll l rm e s s a g e s s i m u l a t i o n r e s u l to fb pa l g o r i t h mb a s e dh u b e rm e t r i c a c h i e v e sg o o dp e r f o r m a n c e f i n a l l y , t h eh i g ho r d e rs o f td e m o d u l a t i o na l g o r i t h m sb a s e do na d d i t i v ei m p u l s e n o i s ec h a n n e l sw e r ei n t r o d u c e d t h e nt h eb pa l g o r i t h m sw e r ep r e s e n t e db a s e do n l l i 出o r d e rs o f td e m o d u l a t i o n , s u c ha s4 q a m ，16 q a m s i m u l a t i o nr e s u l ts h o w st h a t t h ec o d e d - m o d u l a t i o n a l g o r i t h m s c a nw o r k r e l i a b l y i n h i 曲s p e e dd i g i t a l c o m m u n i c a t i o n k e yw o r d s ：l o w - d e n s i t yp a r i t yc h e e k ( l d p c ) c o d e s ，b e l i e fp r o p a g a t i o n ， a d d i t i v ei m p u l s en o i s ec h a n n e l s ，q u a d r a t u r ea m p l i t u d em o d u l a t i o n 3 上海师范大学硕士学位论文 第一章绪论 第一章绪论 本章首先简要介绍数字通信系统，然后概述低密度校验码发展和研究现状，：最后介绍本 文的课题来源和论文内容安排。 1 1 数字通信系统 通信系统的基本目的在于将信息由信源高效、可靠、有时还需安全地传送到信宿。有扰 通信信道中的噪声会不可避免地对传输信息产生不同程度的干扰，从而可能降低通信可靠 性。所以通信系统设计的核心问题就是在存在随机噪声的信道中如何克服干扰，解决系统的 有效性与可靠性之间的矛盾。一般地，通信系统的可靠性用误比特率( b e r ) 来衡量，其有 效性则用信息传输速率r 比特信道符号来衡量。早期的人们普遍认为：通信系统的可靠性 与有效性之间是一对不可调和的矛盾，一方的改善总是以牺牲另一方为代价，并指出当功率 受限时，在有扰通信信道上实现任意小错误概率的信息传输的唯一途径就是把信息传输速率 降低至零。s h a n n o n 信息和编码理论的奠基性论文“通信的数学理论”于1 9 4 8 年发表之后 乜1 ，改变了这一观点。他首次阐明了在有扰信道上实现可靠通信的方法，指出实现有效而可 靠地信息传输的途径就是通过编码。根据s h a n n o n 的信息理论，数字通信系统的基本组成 如图1 1 所示。 图1 - 1 数字通信系统模型 s h a n n o n 的信息理论从通信系统的整体最佳化来研究信息的传输和处理。比特是一 种通用的信息表示形式，它本身并不依赖于信源或信道特征。这就允许我们分别设计图卜1 所示的两个阶段的信息处理，即信源编码和信道编码。s h a n n o n 不失最佳性地证明了这种分 离性羽。 6 上海师范大学硕士学位论文第一章绪论 1 2 低密度校验码的提出、发展和现状 l d p c 码最早是由麻省理工学院的r gg a l l a g , r 于1 9 6 3 年发明的嘲。在其博士论文 中，g a l l a g e r 提出了规则l d p c 码的构造方法、编译码算法以及最小汉明距离分析和译码算 法的性能分析。由于当时的条件限制，编译码器的硬件实现几乎是不可能的：同时，因为没 有足够计算能力的计算机，所以精确细致的仿真也不能实施，g a l l a g e r 只能给出高于1 0 q 的 误码率。由于这些原因，尽管l d p c 码有很好的纠错能力，但仍然被人们忽略了3 0 多年。 现在看来，文献h 1 和文献啼1 的最大成就可能是提出了一种全新的译码器，展现了一种全新的 译码思想。这种译码器主要有三个显著特征： 译码算法的计算复杂度随码长n 的增加而线性的增加。 是一种软判决( s o 俳s e c i s i o n ) 译码算法。 是一种迭代译码算法，具有全并行结构。 t a n n e r 提出的用二分图( 又称为t a n n e r 图) 来分析奇偶校验码的思想哺3 对l d p c 码的发 展也起到了很重要的作用。我们可以用二分图代替校验矩阵来表示l d p c 码，从而可以从 图论的角度来分析l d p c 码的距离特性和性能限。 t u r b o 码的发明口1 让人们重新意识到了l d p c 码。上世纪9 0 年代后期，m a c k a y ，n e a l 等人重新发现了l d p c 码吲。通过大量的仿真，m a c k a y 等人表明：和t u r b o 码一样，l d p c 码也具有接近香农限的性质。 m a c k a y ，l u b y 提出的不规则l d p c 码悖1 伽将l d p c 码的概念推广。不规则l d p c 码的 性能不仅优于规则l d p c 码，甚至还优于t u r b o 码的性能，是目前己知的最接近香农限的 码。r i c h a r d s o n 和u r b a n k 也为l d p c 码的发展做出了巨大的贡献。首先，他们提出了一 种新的编码算法n 刳，在很大程度上减轻了随机构造的l d p c 码在编码上的巨大运算量需求 和存储量需求。其次，他们发明了密度进化理论引，能够有效的分析出一大类l d p c 译码 算法的性能限，仿真结果表明，这是一个非常紧的性能限。最后，密度进化理论还可以用于 指导不规则l d p c 码的设计n 引，以获得尽可能优秀的性能。 7 上海师范大学硕士学位论文第一章绪论 k o u 和l i n 等人从代数、几何理论着手，用确定性算法构造出了性能也很好的l d p c 码。 这一类l d p c 码一般都是规则码，和随机构造的规则l d p c 码相比较，尽管性能上有很小 的损失，但是以下几个方面的优点使得这一类l d p c 码非常受关注： 具有严谨的数学结构，构造和性能分析更加精确，甚至最小汉明距离的准确计算都 是可能的。 和随机构造的l d p c 码相比，具有更低的错误限底，可以应用于有线通信、深空通 信以及磁盘存储工业等对误码率要求更加苛刻的场合。 可以具有循环( c y c l i c ) 或者准循环( q u a s i c y c l i c ) 的结构，极大的减低编码 复杂度，也为译码提供了更加方便的选择。 工业界也已经有l d p c 编译码芯片问世。其中，处于领先地位的f l a r i o n 公司推出的 基于a s i c 的v e c t o r - l d p c 解决方案使用了约2 6 0 万门，内存为1 9 0 k b ，最高可以支持5 0 0 0 0 的码长，0 9 的码率，最大迭代次数为1 0 ，译码器可以达到l o g b p s 的吞吐量，其性能已经 非常接近香农限，可以满足目前大多数通信业务的需求。a h a 公司、d i g i t a lf o u n t a i n 公司 也都推出了自己的编译码解决方案。和另一种近s h a n n o n 限的码一t u r b o 码相比较，l d p c 码主要有以下几个优势： l d p c 码的译码算法，是一种基于稀疏矩阵的并行迭代译码算法，运算量要低于 t u r b o 码译码算法，并且由于结构并行的特点，在硬件实现上比较容易。因此在大容量通信 应用中，l d p c 码更具有优势。 l d p c 码的码率可以任意构造，有更大的灵活性。而t u r b o 码只能通过打孔来达到 高码率，这样打孔图案的选择就需要十分慎重的考虑，否则会造成性能上较大的损失。 ( 爹l d p c 码具有更低的错误限底，可以应用于有线通信、深空通信以及磁盘存储工业 等对误码率要求更加苛刻的场合。而t u r b o 码的错误限底在1 0 量级上，应用于类似场合中， 一般需要和外码级联才能达到要求。 8 上海师范大学硕士学位论文第一章绪论 l d p c 码是上个世纪六十年代发明的，现在在理论和概念上不再有什么秘密，因此在 知识产权和专利上不再有麻烦。这一点给进入通信领域较晚的国家和公司，提供了一个很好 的发展机会。 译码算法的好坏决定了能否最大程度地发挥码本身具备的这种纠错潜力，译码算法的复 杂度决定了工程实现可行的l d p c 码的各种译码算法。 l d p c 码有很多种译码方法，本质上大都是基于t a n n e r 图的消息迭代译码算法。根据消 息迭代过程中传送消息的不同形式，可以将l d p c 的译码方法分为硬判决译码和软判决译 码。 如果在译码过程中传送的消息是比特值，称之为硬判决译码；如果在译码过程中传送的 消息是与后验概率相关的消息，称之为软判决译码，有时也称为和积译码算法。硬判决译码 计算比较简单，但性能稍差；软判决译码计算比较复杂，但性能较好。为了平衡性能和计算 复杂度，可以将两者结合使用，称为混合译码算法。根据消息迭代过程中传送的消息是否进 行了量化及量化所使用的比特数，我们可以将译码方法分为无量化译码和量化译码。硬判决 译码可以看成是l 比特量化译码，软判决译码可以看成无穷多比特量化译码，而混合译码可 以看成变比特量化译码。从量化译码的角度看，硬判决译码和软判决译码属于同一类译码方 法，已有研究表明，可以用3 比特量化取得和和积译码算法非常接近的性能。目前主要的硬 判译码算法有一步大数逻辑译码算法( m l g ) ，o a l l a g e r 提出的比特翻转算法( b f ) ，加权的 大数逻辑译码算法( 眦l g ) ，加权的比特翻转算法( 1 b f ) 以及一些对以上几种算法作改进的 算法如i w b f 等硬判译码算法；软译码算法主要有迭代结构的置信传播算法( b p ) ( 有时也称 之为和积算法( s p a ) ) ，以及基于标准b p 算法，对信息进行部分处理，降低译码复杂度的译 码算法，如u m pb p - b a s e d 算法( m i n - s u m 算法) ，n o r m l i z e db p - b a s e d 算法，还有基于最 优化理论的译码算法如线性规化算法( l p ) 。g a l l a g e r 曾给出了2 种l d p c 码的迭代译码算 法：硬判决和软判决算法。d j c m a c k a y 和c p h e s k e t h n 5 1 研究了l d p c 码采用b e l i e f 传播算 法译码并假定某个噪声电平时，译码性能随实际噪声变化的敏感程度，得出了实际与假定噪 声失配对译码性能影响的函数关系。 目前，对l d p c 码的研究己取得了许多重要的成果，但仍然存在着一些需要进一步研究 的问题，主要包括以下五个方面： l d p c 码在有环图模型上的性能分析。现有l d p c 码的理论分析都是基于无环图上 9 上海师范大学硕士学位论文第一章绪论 的，能否找到有效的理论分析工具直接对有环图上的l d p c 码进行描述和分析是一个值得 研究的问题；同时，对和积译码算法在有环图上的收敛条件和稳定性，小环路对迭代译码的 影响，寻找能有效减少小环路的l d p c 码构造方法等问题也具有重要意义。 ( d t a n n e r 图的代数构造方法。目前t a n n e r 图采用随机生成的方法，虽然s p i e l m a n 等证 明了随机t a n n e r 图所构造的l d p c 码是大概率的渐进好码，但无法有效地控制码的性能。 能否找到一种代数方法来构造t a n n e r 图，从而精确地控制l d p c 码的汉明距离、距离谱以 及图模型的参数，准确地预测迭代译码的性能和计算译码闽值的大小；应用简便的代数方法 来优化非规则l d p c 码的度序列，以提高l d p c 码性能等问题对l d p c 码的研究是非常重 要的。 ( d l d p c 码在复杂信道中的性能研究。自从t u r b o 码出现以来，大量的文章讨论了t u r b o 码在复杂信道中的性能，取得了丰富的成果，而对l d p c 码的研究却很少虽然m a c k a y 和 m c e l i e c 曾分别预测l d p c 码在突发错误信道和衰落信道以及非对称信道具有优异的性能， 但目前在这方面的研究极为有限。 ( dl d p c 码迭代译码算法的改进。虽然最小和算法与和积算法具有复杂度低、译码速 度快、可并行译码等优点，但仍可对译码算法做以下几方面的改进：在不降低或不明显降低 译码性能的情况下，通过降低输入变量和译码中间变量的状态复杂度，进一步地降低译码复 杂度；改进信息传递的方式，加快迭代译码的收敛速度，减少译码的迭代次数；寻找与t o r n a d o 码相似的具有线性复杂度的迭代译码算法等。 ( d l d p c 码的应用研究，主要包括：利用大规模集成电路，硬件实现l d p c 码编译码器 的研究；l d p c 码和t u r b o 码。码组合编码方法的研究：利用l d p c 码良好的无误译性能，研 究l d p c 码在串行级连混合a r q 中的性能；以及l d p c 码与空时( s p a c e - t i m e ) 码、o f d m 相 结合的研究等。 1 0 上海师范大学硕士学位论文第一章绪论 1 3 本论文的主要研究内容及其意义 1 3 1 研究的目的和意义 随着移动通信的快速发展，用户数量的急剧增长及多媒体业务的不断涌现，一个新型的 具有巨大容量的和多媒体接入能力的移动通信系统成为人们的期待目标，因此第三代移动通 信( 3 g ) 应运而生。3 g 标准的设计目标是3 8 4 k b p s 的步行通信速率和2 m 的室内通信速率， 在业务上引入更多的多媒体业务。尽管3 g 的设计目标是提供具有多媒体接入能力的无线通 信手段，但是3 g 所能提供的通信带宽并不能满足人们不断增长的需求，且在用户容量上也 存在着很大的不足。为了解决3 g 系统中的不足，需要研制一套容量更大，频谱利用率更高 的系统，即目前正在讨论的b 3 g 4 g 通信系统。为了达到高速移动下的可靠通信，有必要采 用各类优秀的信道编码技术，分集技术，接收检测技术等。 纠错码的设计是保证数据可靠传输的一个重要组成部分，因为它可以检测并纠正信号传 输过程中引入的错误。在信道编码方面，l d p c 码在新一代移动通信超3 g 中有着很大的用武 之地，因为l d p c 码本身即有抗突发差错的特性：不需要引入交织器，避免了可能带来的时延： 可以实行完全并行的操作：便于硬件实现：吞吐量大：极具高速译码的潜力：它不仅具有接近 s h a n n o n 限的优异性能，同时由于在码的构造，译码方法上的相关成果的获得使得l d p c 码在信 道条件较差的无线移动通信中展现出了巨大的应用前景，非常适合于在未来的移动通信系统 中实现。 l d p c 码的优异性能及其在信息可靠传输中的良好应用前景( 例如光通信、卫星通信、 深空通信、第4 代移动通信系统、高速与甚高速率数字用户线、光和磁记录系统等) ，已引 起世界各国学术界和i t 业界的高度重视，成为当今信道编码领域最瞩目的研究热点。 l d p c 码在许多情况下将取代t u r b o 码的趋势已很明显，研究l d p c 码的学术意义、商业 价值和对i t ( 特别是通信) 领域相关技术发展的推动作用是巨大的。近几年国际上对l d p c 码的理论研究已取得重要进展，在应用基础乃至工程应用和v l s i ( 超大规模集成电路) 实现 方面的研究亦正在全方位开展。 上海师范大学硕士学位论文 第一章绪论 1 3 2 本论文内容安排 本论文采用理论分析和仿真相结合的方法，对l d p c 码的理论进行了深入研究，取得了 一些成果。全文共六章，其章节安排如下： 第一章阐述l d p c 码的发展和现状并介绍课题来源以及本文的内容安排。 第二章系统地阐述规则l d p c 码的构造，编码原理。 第三章介绍l d p c 码的迭代译码b p 算法，并在b p 算法的基础上提出一种简化的线性 拟合算法；同时为了检验l d p c 码和b p 译码算法的实际性能，分别对加性高斯信道( a w g n ) 下的l d p c 码和t u r b o 码的性能进行了仿真。 第四章首先介绍服从s a s 分布的加性脉冲噪声信道模型，并研究l d p c 码在这一类服从 s a s 分布的加性脉冲噪声信道上的译码方法，最后对基于h u b e r 测度的简化的译码算法进行 性能仿真。 第五章研究在加性脉冲噪声信道中高阶q a m 调制的l d p c 码译码算法，并采用 b p s k , 4 q a m , 1 6 q a m 调制的l d p c 码的简化的译码算法在脉冲信道参数a = 1 5 下进行性能 仿真。 进。 第六章对论文进行简要的总结，并展望了论文的后续工作以及未来可以进行的提高和改 1 2 上海师范大学硕士学位论文第二章l d p c 码的编码原理 第二章l d p c 码的编码原理 本章将对论文研究所涉及的l d p c 码基本理论加以介绍，由于基础理论内容广泛，这里 主要针对规则l d p c 码的构造，编码原理进行介绍。 2 1l d p c 码的基础 g f l l a g e r 在1 9 6 2 年引入了一种基于低密度校验矩阵的纠错编码，这种码有以下特性： ( 1 ) 将随机排列和简单的校验码结合在一起构造了一种有效的低复杂度的码来模拟随机 码。 ( 2 ) 使用迭代的译码技术，先验信息和对信道的观测都被用于计算后验概率和新的先验 信息。 2 1 1l d p c 码的定义 l d p c 码是一种基于稀疏校验矩阵何的线性码。一个( n j 0 - - - 进制的l d p c 码可用一个与 其相对应的校验矩阵日来表示。其中j 矩阵是m x n 且满秩的，相对应的l d p c 码长为n ， 校验位为必信息位为k = - m ，码率为r = k n o 一个二进制向量c = ( c ，c 2 ，钳) ，当且仅 当h x c = o 时，才是一个码字。g f l l a g e r 在o f ( 2 ) e 定义了l d p c 规则码( ，p ，力，其中， h 矩阵每列中“1 ”的个数称为列重p ，每行中“l ”的个数称为行重) ，也称为l d p c ( 户，) ，) 码。具有奇偶校验矩阵日的l d p c 码可用两种节点( 可变节点和校验节点) 组成二分图来 表示。每个码比特是一个可变节点，而每个奇偶校验矩阵的每一行表示一个校验节点。 图2 1 是一个码长为6 ，校验矩阵中行重和列重都为3 的l d p c 规则码( 6 ，3 ，3 ) 的码 字的二分图，上面是可变节点，下面为校验节点； 圈( c y c l e ) ：由变量节点、校验节点和边首尾相连组成的闭合环路； g i r t h 的定义：码字二分图中最短圈的圈长； 图中粗线构成了一个长度为6 的圈，如果没有长度为4 的圈，那么这个图的最小圈长，即 g i r t h ，就是6 ； 给出一个码的校验矩阵后，可以用m a oy o n g y i 6 1 提出的搜索方法得到该l d p c 码的g i r t h 及其分布。 1 3 上海师范人学硕士学位论文 第二章l d p c 码的编码原理 2 2l d p c 码的构造 图2 1( 6 ，3 ，3 ) 码字的二分图 2 2 1g a l l a g e r 的规则l d p c 码的构造 在g a l l a g e r 最初的工作中，给出了( p ，) ，) 规则码的构造方法，这是一种随机的构造方 法：对于码长为的( p ，) ，) 规则码，将校验矩阵按行水平的分割为p 个相同大小的子矩阵， 每个子矩阵的任一列都只包含一个1 。第一个子矩阵以预定的方式构造，如可以用递减的形 式包含所有的l ，矩阵的第f 行所有的1 都分布在第o 1 ) ，十l 到f 7 列。其它下面的歹1 个子矩阵都是第一个子矩阵的随机排列。这种构造方法可如式2 1 表示： 凰为矩阵，校验矩阵砌式2 2 构造： h = = 鼠 砭喊) 喊) ( 2 1 ) ( 2 2 ) 这里万为矩阵日d 的列置换。上面日矩阵的第一个子矩阵为日d ，也可以用凰的任一置 换代替，得到式2 3 更加对称的构造方法： 1 4 上海师范大学硕士学位论文第二章l d p c 码的编码原理 h - - - 巧嘱) 呢噶) 喊) ( 2 3 ) g a l l a g e r 经过推导得出了下面的结论：给定一个规则码系列，如果其校验矩阵的列重 量为某个给定的p ，满却3 ，且可任意选择码长，那么该编码是一个好码，也就 是说当给定通信信道的时候，存在某个低于信道容量的最大信息传递速率，使得当通信 速率低于该速率时，当该码系列中编码的码长足够大时，以之进行通信能够使误码概率 任意的低。如果码系列中编码的列重量p ，不固定，允许任意的选择，那么该编码是一 个最佳码。也就是说对于任意信道都存在这样的分组码系列，使得任意以低于信 道容量的速率进行的通信的误码率都能够任意的小。 图2 2 ：为g a l l a g e r 构造的一个( 2 0 ，3 ，4 ) 的校验矩阵日： 图2 2 ( 2 0 ，3 ，4 ) 码 2 2 2m a c k a y 的规则l d p c 码的构造方式 m a c k a y i l 7 】的思想提出了自己的构造方案，当日矩阵中出现长为4 的圈时，会导致在迭 代译码时，变量节点和校验节点难以获得有效的外部消息。为了避免出现长为4 的圈，m a c k a y 采取的方法就是构造时要保证任意列之间的位置相同的l 的个数不大于l 。一般规则的 l d p c 码的校验矩阵具有恒定的行重和列重。 c i a ：这种方法是最基本的一种构造方法，它要求保证固定列重为p ，而行的重量尽可能 1 5 上海师范人学硕士学位论文第二章l d p c 码的编码原理 均匀的保持为) ，。按照此方法构造的一个列权重为3 ，行权重为6 的l d p c ( 3 ，6 ) 码。如图2 - 3 所示。 c - 2 a ：将矩阵中有m 2 列的列重量置为2 ，这里 仁校验位数通常采用两个朋陀m 2 的 单位矩阵上下叠放。剩余的列依然保持c 1 a 的构造方法。如图2 4 所示。 o 八 u 入 。 入 图2 - 3c 1 a 构造方式图2 - 4c 2 a 构造方式 2 3l d p c 码的编码 假设矩阵脚 勺所有行都是线性无关的。矩阵行的线性无关性由其生成算法保证，如果行 不是线性无关的，那么矩阵的生成算法应该能够检测到行相关性并重新运行直至生成一满足 行线性无关的校验矩阵，也可消去矩阵肿的冗余行。假设矩阵日劫l ， ( 雠的奇偶校验矩阵。 根据定义，相应的编码满足方程：h x t = 0 t 最直接地得到系统编码的方法是：首先将h 矩阵用高斯消去法化成下三角形式，图2 5 所 不。卜_ 生兰一 图2 - 5 基于高斯消去的直接编码方法 将矢量分为系统比特部分s ，s 矸删，和校验比特部加，p 卵埘，这样辄= ( 埘。然后： 1 6 上海师范大学硕士学位论文第二章l d p c 码的编码原理 i ) 将s 用个希望进行编码的信息比特填充。 i i ) 用回代法确定 外校验比特。 对于该编码方案的复杂性，将矩阵h 转化成下三角形式所需的高斯消去法需d 向次预处 理。由于经高斯消去法预处理的稀疏矩阵不再是稀疏的，没有有效利用l d p c 码校验矩阵地 稀疏性，实际的编码过程需d 向刁次运算，也且p l d p c 码最直接的编码方案具有二次方的时间 复杂度。 在改善编码复杂度问题上，许多入进行了研究研究。例如t j r i c h a r d s o n 和& l u r b a n k e 在文献【1 8 】中进行了改善l d p c 编码复杂度的研究，在这种编码方案下，仅仅对编码的校验矩 阵进行一些重排的预处理，就能使编码的时间复杂度在绝大多数情况下都是相当可控的甚至 具有线性时间复杂度。例如，对一个码长为刀的( 3 ，6 ) 正则码，编码的复杂度表面上看起来是 阶的，但是实际所需的操作不超过0 0 1 7 2 n 2 + d 例。由于这极小的常量因子，即使对大的 码长，编码器也是实际可操作的。 1 7 上海师范大学硕士学位论文第三章l d p c 码的译码算法 第三章l d p c 码的译码算法 自从l d p c 码被重新认识发现其性能非常接近s h a n n o n 限后引起许多学者对此编码的 研究，其中基于置信度传播( b e l i e fp r o p a g a t i o n ，b p ) 译码算法表现出了优异性能，但b p 算法中节点更新的计算很复杂，对于实际的应用是很困难的。本章介绍了l d p c 码的迭代译 码算法b p 算法，并在b p 算法的基础上提出了一种简化的线性拟合算法，此算法可以降低 译码复杂度又能使硬件实现变得更加容易；为了检验l d p c 码和b p 译码算法的实际性能，本 文对加性高斯信道下的l d p c 码的性能进行了仿真。 3 1 对数似然比域内的b p 算法( l l r - b p ) 假设l d p c 码编码器的输出序列协七 经过二进制调制 u k = 2x k - 1 ) 后，输入高斯信 道，在译码器的输入端得到序列杪七) ，y k = s k + g k ，其中玎七为白噪声。 所有的外部消息由对数似然比( l l r ) 的形式表示，变量上表示外部信息，随机变量u 的 二进制l l r 值定义为： 三仰黼 ( 3 1 ) 此对数似然比量度可以解释为：三f ，的正负号用来判别随机变量u 为0 还是l ，其绝对值表 示取o 和1 的置信度，8 p l ( u ) 绝对值越大说明为0 或1 可能性越大，在不致混淆的情况下，同构 空间 o ，1 和 一1 ，+ 1 ) 在文中可等价使用。 此外，定义了厶。( 翰) 表示变量节点输出到校验节点置信度，么一( ) 表示校验节点输 出到变量节点置信度。 译码算法如下： 初始化：根据信道模型和采用的调制方式，初始化信道对数似然比； 迭代过程： ( 1 ) 校验节点更新：对于每个校验节点m ，对连接到校验节点的每个边，计算从校验节点 8 上海师范大学硕士学位论文第三章l d p c 码的译码算法 到比特节点传递的外部消息： 么一( ) = 2 t a n h 1 兀姗办叫，( ) 2 ( 3 2 ) h e n ( “) ( 2 ) 变量节点更新：对于每个校验节点疗，对连接到比特节点的每个边，计算从比特节点 到校验节点传递的外部消息： r 彳胛。( ) = ( 蝴卜 ： 么。一( ) ( 3 3 ) 肌j ( 肘) 、脚 对每个刀，计算 枞) = 三( ) + 么一( ) m e n ( m ) ( 3 4 ) ( 3 ) 尝试判决：如果厶( ) 1 0 ，则x = 1 ，如果厶( 蝴) 0 ，则x = 0 。如果xx = 0 ，则译码 停止，译码器输出x 。否则，继续执行迭代过程。如果达到设置的最大迭代次数，还未 找到满足的码字，则宣告译码失败。 3 2 改进的线性拟合译码算法 目前关于l d p c 码的译码简化有了一定的研究，为应用于实时的通信系统提供科学依 据，本小节从考虑b p 译码算法更具有实用角度出发，对其进行了改进。 3 2 1 译码算法分析与改进 ( 既p i ) 是节点比特的概率密度，可以变换度量p = p o p i 和m = 科尸，) ，且 m = 钮( 1 + ( 1 - a p ) 】 a p = ( e ”1 ) ( p ”+ 1 ) = m n h ( m 2 ) ( 3 5 ) ( 3 6 ) 对于上节中的译码迭代过程为了直观便于理解我们可相应的变换成： d c 一1 ( 1 ) 校验节点的更新：t a n h ( u 2 ) = 兀t a n h ( 吁2 ) ( 3 7 ) j = l 1 9 上海师范大学硕士学位论文第三章l d p c 码的译码算法 以一l ( 2 ) 变量节点的更新：1 ，= 砌+ “， i = l c 3 ，尝试判决：# = s g n ( 喜甜 ( 3 8 ) ( 3 9 ) 其中，每个节点相连的边数，称为该节点的度。校验比特节点的度用盔，变量节点的 度用磊表示。 坳( i = 1 ，2 ，3 ，, i v ) 表示变量x j 的所有巩个邻居校验节点传递的的消息，劬表 示变量x 的初始消息。 译码算法的复杂性主要是由于校验节点更新的双曲正切函数造成的，为了简化计算，对 校验节点的更新，即t a n h ( u 2 ) = ( e x p ( u ) - 1 ) ( e x p ( u ) + 1 ) ，可以取对数，并将其分解为符号和 绝对值两个部分，表示为序偶形式： ( 姆s g n ( t a n h ( u 2 ) ) ，一姆s g n ( 1