（通信与信息系统专业论文）基于ieee80216e协议的ldpc码编译码算法的研究.pdf

摘要 目前，l d p c ( 低密度奇偶校验码) 码以其优越的性能在通信系统中得到了越 来越多的应用，其中如何构造优良的实用型好码，以及寻找软判决译码算法中的 快速译码算法成为了人们研究的重点。本文以i e e e 8 0 2 1 6 e 协议规定的l d p c 码为 基础，以降低编码复杂度，减少译码时延实现快速译码为目标，研究i e e e 8 0 2 1 6 e 系统使用的l d p c 码的编译码算法。 i e e e 8 0 2 1 6 e 协议规定的l d p c 码是以准循环l d p c 码为基础构成的，其校验 矩阵分别是由单位矩阵，单位矩阵的循环移位阵和零矩阵组成。本文针对这种分 块矩阵的特点，给出了块状码( b l o c k l d p c 码) 的编码方案，并构造了不同码长 和码率的码字，给出了不同信道下各自码字性能仿真的对比。在译码方面，本文 在传统的l d p c 码译码算法( l l rb p 算法) 的基础上，给出了二维修正的 a p p b a s e d 译码算法，并针对不同信噪比下不同的性能改善，给出了分信噪比选取 可变因数对的思想，提高了译码的有效性，改进了目前常用译码算法速度快但性 能不足的状况。本文通过仿真给出了采用不同译码算法及不同调制方式时，多种 码长和码率的码字的性能对比曲线，分析了各种算法的复杂度和性能的基础上证 明了本文所译码算法是可靠有效的，最后结合本文中l d p c 码校验矩阵的特殊性 给出了一种译码器设计的思路，并分析了这种半并行结构的译码器在逻辑资源使 用和运算速度方面的优越性。 关键词：低密度奇偶校验码、块状码、二维修正的a p p b a s e d 算法、译码器 a b s t r a c t n o w , l d p c ( l o w - d e n s i t yp a r i t y - c h e c k ) c o d e sh a v eb e e na p p l i e dt om a n y c o m m u n i c a t i o ns y s t e m sf o rt h eg o o dp e r f o r m a n c et on e a rs h a n n o nl i m i t h o wt o c o n s t r u c tu t i l i t yg o o dc o d e sa n dt of i n da ne f f i c i e n td e c o d i n ga l g o r i t h mb e c a m et h e r e s e a r c hh o ts p o t s w i t ha i m so fr e d u c i n gt h e c o m p l e x i t y o fe n c o d i n ga n d i m p l e m e n t i n gal d p cd e c o d e rw i t l ls h o r t - d e c o d e r - l a t e n c y , t h i st h e s i sw o r k sa tt h e d e s i g no fe n c o d i n ga n dd e c o d i n ga l g o r i t h m so fl d p cc o d e so n t h eb a s eo f i e e e 8 0 2 1 6 ep r o t o c 0 1 i nt h ei e e e 8 0 2 1 6 es y s t e mw eu s eq c - l d p cc o d e st oc o n s t r u c tt h ehm a t r i x ( p a r i t yc h e c km a t r i x ) w h i c hi sc o m p o n e n to fz e r om a t r i x e s ，i d e n t i t ym a t r i x e sa n dt h e c i r c l e s h i f tm a t r i x e so fi d e n t i t ym a t r i x e s w i t hc o n s i d e r a t i o no ft h et r a i to ft h i sk i n do f b l o c km a t r i x e s ，t h i st h e s i sd e s i g n sa ne n c o d i n ga l g o r i t h m sa n dc o n s t r u c t sc o d e sd i f f e ri n r a t ea n dl e n g t h f o rd e c o d i n ga l g o r i t h m s ，a f t e rr e s e a r c ht h et r a d i t i o n a ld e c o d i n g a l g o r i t h m so fl d p cc o d e s l l rb pa l g o r i t h m s t h i st h e s i sp u t sf o r w a r da np l a n a r m o d i f i e da p p b a s e da l g o r i t h m sa n dw i t hc o n s i d e r a t i o no fd i f f e r e n tp e r f o r m a n c e i m p r o v e du n d e rd i f f e r e n ts n i lp r e s e n ta na l t e r a b l ef a c t o rs e l e c t i n gt h o u g h t t h i sp l a n a r m o d i f i e da l g o r i t h m si m p r o v e dt h ev a l i d i t yo fd e c o d i n g ，a m e l i o r a t e dt h es t a t u so f t r a d i t i o n a lb p b a s e da l g o r i t h m sw h i c ha r es p e e d i n e s sb u tl a c k i n go np e r f o r m a n c e f o rd i f f e r e n td e c o d i n ga l g o r i t h m s ，t h i st h e s i sp r e s i d e n t sm a n ys i m u l a t i n gr e s u l t s i n c l u d e so fd i f f e r e n td e c o d i n ga l g o r i t h m sw i t l lt h es a m ec o d e t h es a m ed e c o d i n g a l g o r i t h m s 、析t l lc o d e sd i f f e ri nc o d el e n g t ho rr a t e a n da l s os i m u l a t i o n su n d e rd i f f e r e n t m o d u l a t i o n s a f t e rd e e p l yr e s e a r c ho nt h ep e r f o r m a n c ea n dc o m p l e x i t yo ft h e s e d e c o d i n ga l g o r i t h m s ，t h e r ec o m e st h ec o n c l u s i o nd e n o t e st h a tt h i sk i n dl d p cc o d eo f e n c o d i n ga n dd e c o d i n ga l g o r i t h m sp r e s e n t e di nt h i st h e s i si sg o o df o rt h ei e e e 8 0 2 16 e s y s t e m i nt h el a s tp l a c e ，t h i st h e s i sp r o v i d e dat r a i no ft h o u g h to nt h ed e s i g no fd e c o d e r w i t hm u c hc o n s i d e r a t i o no ft h ed i s t i n c t i v e n e s st h ehm a t r i xp r o v i d e d ，a n da l s oa n a l y z e d t h ea d v a n t a g e so ns a v i n gl o g i c a lr e s o u r c e sa n do p e r a t i n gs p e e d k e yw o r d ：l d p c b l o c kl d p cp l a n a rm o d i f i e da p p - b a s e da l g o r i t h m s d e c o d e r 西安电子科技大学 学位论文独创性( 或创新性) 声明 本人声明所呈交的论文是我个人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特另t l d i 以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果；也不包含为获得西安电子科技大学或 其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做 的任何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： 日期：趁：么：丝 西安电子科技大学 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印或其它复制手段保存论文。( 保密的论文 在解密后遵守此规定) 本学位论文属于保密在一年解密后适用本授权书。 本人签名：巫塑丝土 导师签名： 日期：丝夕：多：胆 日期：丝! ! ：蔓：! 兰 第一章绪论 第一章绪论 通信的目的是把对方不知道的消息及时可靠地传送给对方，如何在数据源功率 和带宽有限、系统复杂性和设备造价尽可能小的条件下实现尽可能准确的信息传 输，即使信息传输误码率最小，是通信系统设计中最关心的问题。由于l d p c 码 有很好的抗衰落性和较高的编码增益，在i e e e 8 0 2 1 6 e 系统实际应用中，接收机在 较低的信噪比情况下仍然可以维持较低的误码率，从而使覆盖范围得到提升，本 文主要研究l d p c 码在i e e e 8 0 2 1 6 e 物理层中的编译码方案。 1 1 纠错码的理论基础 1 9 4 8 年s h a n n o n 开创性的论文“am a t h e m m i c a lt h e o r yo f c o m m u n i c a t i o n ”1 3 j ， 首次阐明了有扰信道中实现可靠通信的方法，并提出了著名的有扰信道编码定理： 即对任意一个平稳离散无记忆有噪声的信源，都有一个固定的信道容量( 记做c ) ， 只要信息的传输率低于信道容量，就必然存在一种编码方法，采用最大似然译码 的算法使得信息出现差错的概率随码长的增加趋于任意小；反之，当信息传输速 率超过信道容量时，则不存在这样的编码方法。这就是著名的信道编码定理，给 出了特定信道上信息传输速率的上确界。同时，s h a n n o n 给出了高斯白噪声信道下， 信道容量的表达式： p c = 朋0 9 2 1 + 蒜m 7 s ) ( 1 - 1 ) 其中，只= e 。t 是信号功率，e 。是信号能量，丁是分组码信号的持续时间， 即信号宽度；形是信道所能提供的带宽，0 是单位频带上的噪声功率，只w 是 单位频带上的信号功率，只( 聊v 0 ) 是信噪比。 s h a n n o n 的信息论奠定了现代纠错码的理论基础，其定理中指出的纠错码能够 有效纠错时所需的最小比特信噪比，我们称之为s h a n n o n 限，这是我们评价一种 编码方案和译码算法性能的一个重要标准。 s h a n n o n 在信道编码定理的证明中引用了三个基本条件，即： 1 ) 采用随机编码方式； 2 ) 码字长度趋于无穷大； 3 ) 译码采用最佳的最大似然译码。 但具体采用什么样的信道编译码方法才能使信道的信息传输速率r 逼近信道 容量c ，s h a n n o n 并没有给出一个标准的答案。因此，自s h a n n o n 提出了著名的有 2 基于i e e e 8 0 2 】6 e 协议的l d p c 码编译码算法的研究 扰信道编码定理以来，编码研究者们一直致力于寻找性能上尽可能接近s h a n n o n 极限，而编码复杂度又较低的可实现的信道编码方案。 我们用好坏和实用性来评价一种码。在给定信道中，能够以任意小的错误概 率实现任意小信道容量的非零速率通信，我们称这样的码为好码，否则为坏码； 而实用码，是指在给定信道中，能够在时间和空间复杂度可以接受的情况下完成 编码和译码，这样的码就称为实用码。 五十多年来，人们构造实用好码的探索基本上是按照s h a n n o n 所引用的基本 条件的后两条为核心展开的，但到目前为止，研究实用好码的构造方法仍有很广 阔的空间。 1 2 纠错码发展历程 纠错码从构造方法上可以分为分组码和卷积码两大类，以下介绍几种重要的 纠错码。 1 ) 最早的纠错码线性分组码 线性分组码是发展最早的一类纠错码【4 】。它以代数中的群、域、环理论和有关 的几何理论为基础，利用各种代数几何方法设计好的纠错码，如汉明码、b c h 码、 r s 码( 多进制b c h 码、代数几何码) 、g o l a y 码、g o p p a 码( 有理分式码) 等等。这 些码的编译码设备不太复杂，特别是结构简单的b c h 码【5 】，在通信系统中应用极 其广泛，但是除了g o p p a 码和代数几何码存在个别渐进好码外，其它码均不是好 码，分组码的译码主要采用基于代数的硬判决译码。 2 ) 卷积码 卷积码在编码过程中引入了寄存器，增加了码元之间的相关性，在相同复杂 度的条件下可以获得比分组码更高的编码增益；缺点是分析和设计的复杂性高， 例如，采用v i t e r b i 译码方法的卷积码是好码但不是实用码，其译码复杂度随约束 长度的增加呈指数增加；而采用序列译码的卷积码是实用码，其复杂程度与约束 长度无关，但是在可靠传输时速率只能到信道的截止速率( c u t o f fr a t e ) r 0 】( 这个 速率一直被认为是差错控制码性能的实际极限) ，并不能接近信道容量。卷积码具 有动态格图结构，可以用有限状态机来描述其状态，由于缺乏有效的理论研究工 具，目前对卷积码的有效研究成果不是很多，其中性能好的卷积码的构造方法主 要是借助于计算机搜索来获得。卷积码一般采用概率译码，由于译码算法简单、 实用且易于实现，卷积码被广泛应用于实际系统中。 3 ) 级联码 级联码是通过内码和外码级联而来的，基本思想是通过级联构造长码来提高 纠错码的纠错能力【6 】。例如内码选用卷积码，外码选用r s 码的级联码，在d v b t 第一章绪论 3 系统中得以使用，选择合适的码进行级联可以获得接近信道容量的性能，同时还 能降低实现时的复杂度，更接近实用型好码，1 9 8 2 年欧洲的u n g e r b o e c k 和日本的 i m a i 分别独立地提出了具有扩展频带特性的编码与调制相结合的思想，提高了频 带利用率。 4 ) t u 曲0 码 上述这些编码技术都对信道编码的设计和发展产生了重大影响，但是其增益 与s h a n n o n 理论极限始终都存在2 - 3 d b 左右的差距，而s h a n n o n 限仅是理论上的 极限，实际是不可能达到的。而实际能达到的最大速率就是在t u r b o 码提出以前一 直被认为是差错控制码性能的实际极限的信道截止速率( c u t o f f r a t e ) 。 t u r b o 码巧妙地将卷积码和随机交织器结合起来 7 1 ，实现了随机编码的思想， 同时采用软输出迭代译码来逼近最大似然译码。b e r r o u 等人使用约束长度为5 的 子码，长度为6 5 5 3 5 的交织器，码率为1 2 的t u r b o 码，经过1 8 次迭代译码之后， 在a w g n 信道上，采用b p s k 调制，当最0 0 7 d b 时的误比特率b e r 1 0 一， 达到了近s h a n n o n 限的性能。t u r b o 码是一种实用好码，成为了编码界的热点，同 时其迭代译码思想在均衡、多用户检测等各方面得到了广泛应用，并成为第三代 移动通信标准c d m a 2 0 0 0 和w c d m a 中的信道编码方案。t u r b o 码也存在其缺点： 由于交织器的存在，其译码复杂度相对较大，译码时延较长；由于低码重码字的 原因，在高信噪比是存在错误平台现象。t u r b o 码的提出更新了编码理论研究的一 些概念和方法：编码理论的研究从早期的基于代数结构的构造与译码方法，变成 了现在主要是基于概率的软判决译码方法；编码方案的比较也由以前的相互比较 过渡到了现在大多与s h a n n o n 限进行比较；t u r b o 码的提出具有里程碑的意义。 随着对t u r b o 码的深入研究，人们重新发现g a l l a g e r 早在1 9 6 2 年提出的低密 度奇偶校验码( l o w d e n s i t yp a r i t y c h e c kc o d e s ，简称l d p c 码) 也是一种具有渐 进性的非常好码，它在中长码长时的性能优于t u r b o 码，且译码复杂度更低，并且 不存在由于交织器的引入带来的译码时延等问题，成为信道编码理论研究的热点。 1 3l d p c 码的研究现状 1 3 1l d p c 码编译码方法的研究 g a l l a g e r 早在1 9 6 2 年提出的低密度校验码( l d p c 码，也称g a l l a g e r 码) 也 是一个好码，经过迭代译码可以获得随码长长度指数降低的比特错误概率，但是 由于当时的计算机仿真水平有限，l d p c 码并未受到充分的重视。 1 9 8 1 年，t a n n e r 提出的一种规范的图码表示法【8 1 对l d p c 码的再发现有着重 4 基于i e e e 8 0 2 16 e 协议的l d p c 码编译码算法的研究 要意义，这种t a n n e r 图法把码校验约束建立在局部码元集合上的t a n n e r 图。通过 分析最小和( m i n s u m ) 与和积( s u m p r o d u c t ) 两种消息传递算法，证明了基于有 限无环t a n n e r 图时，最小和算法准确实现了最小码字错误概率的最佳最大似然译 码，和积算法实现了最小符号错误概率的后验概率算法。 在译码算法的研究方面，首先m a c k a y 等人总结前人的工作，在论文【9 】中详细 地论述了l d p c 码的理论和实际性能，证明了l d p c 码是一种实用好码，推广了 g a l l a g e r 提出的概率迭代译码算法，论述了实用译码方法和积算法( s u m p r o d u c t 算法，也称置信传播算法叫e l i e fp r o p a g a t i o n 算法、消息传递算法一 m e s s a g ep a s s i n g 算法) 的详细实现方法，极大地推动了l d p c 码的发展，成为l d p c 码发展中的一个里程碑。f o s s o r i e r 对低复杂度的b p 算法作了进一步的研究1 3 1 1 ，提 出了b p b a s e d 算法；为了改善b p b a s e d 算法因为校验节点上的简化处理而造成 的性能损失，j c h e n 提出了两种改进的算法1 3 5 j ：采用归一化的近似最佳b p b a s e d 算法( 亦称n o r m a l i z e db p b a s e d 算法) 和通过降低可靠性值来改善外附信息精度 的o f f s e tb p b a s e d 算法。 在性能研究方面，自m a c k a y 等重新发现l d p c 码后，对多元域的l d p c 码进 行了深入研究，发现多元域的l d p c 码比二元域的码有更好的性能，且编码阶数 越高，性能越好；人们的进一步研究表明，非正则l d p c 码的性能要优于正则码： 采用优化度序列设计的非正则t a n n e r 图被用于构造l d p c 码，称为非规则码，这 种基于非规则双向图的l d p c 长码性能可以优于1 、曲。码，且这样的码的性能可 以非常接近s h a n n o n 限，例如，在二进制输入a w g n 信道下，设计的码率1 2 、 码长l o7 的非规则l d p c 码在错误概率1 0 。6 时离s h a n n o n 限仅0 0 0 4 5 d b 1 0 1 。这是 迄今为止发现的性能最接近s h a n n o n 限的信道编码。另外l d p c 码具有良好的距 离特性，小的译码错误概率和较低的译码复杂度，而且适当码长( 比如大于2 0 0 ) 时，不存在误码平台，其码率容易调整，实验结果中的错误几乎均为可以检测错 误，。 近几年来，r i c h a r d s o n 等人利用密度进化理论来测度l d p c 码的性能，并指出 译码信息的迭代传递过程中存在着译码性能阀值现象，即当信噪比大于译码阀值 时，迭代译码的误码率将收敛于某个值。r i c h a r d s o n 等人的进一步研究证明有限随 机有环图的译码阀值可以逼近无环图的译码阀值。通过建立在无环图上的密度进 化理论，可以精确的计算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 码的优化设计。c h u n g 等人通过对密 度进化理论的研究，进一步提出了应用高斯逼近原理来简化译码阀值计算和收敛 性分析，从而使测度l d p c 码性能的模型由多参数动态系统的密度进化理论模型 第一章绪论 5 简化为单一参数动态系统的高斯逼近模型。 1 3 2l d p c 码的理论研究热点和待解决问题 对于l d p c 码的理论研究主要集中在校验矩阵的构造和度的优化、编译码算 法的优化、迭代译码性能的分析等方面。构造方面主要有随机构造和代数构造。 随机构造的码，码长和码率灵活，在长码长时性能较好，但短码时会引入较多围 长短的环，影响码字的性能；而代数构造的码编译码方法相对简单，且设计优良 的l d p c 码译码性能相对较好。度优化方面，主要是根据不同系统的要求，利用 如线性规划、密度进化、e x i t 图等工具优化设计l d p c 码的度分布，进而生成校 验矩阵。因为l d p c 码的编码复杂度比较高，近年来大量的研究集中在了如何简 化l d p c 码的编码复杂度上，例如可以采用简单的移位寄存器构造准循环码 ( q c l d p c ) ，以及基于矩阵分解的循环置换矩阵构造方法，例如欧式几何法和投 影几何法。l d p c 码迭代译码的性能一直是l d p c 码编译码技术研究的热点和关键 点，例如在码长无穷长、不存在短环路的情况下，采用高斯逼近、密度进化或者 e x i t 等分析方法，可以精确地分析出l d p c 码的理论极限。 目前存在的问题是：1 ，l d p c 码的编码问题，l d p c 码的产生取决于其校验 矩阵，其编码运算复杂度很高，实现起来资源占用量大，寻找高速同时节约资源 的编码方案是一个重要研究方向；2 ，l d p c 码的译码算法分为硬判决译码和软判 决译码两种，其中硬判决译码计算复杂度很低但性能不够理想，而软判决译码性 能要远远好于硬判决，但复杂度又很高。尽管以及由很多译码算法提出，但寻找 一种性能优良，译码运算量又低的软判决算法仍然是研究的热点问题；3 ，多元域 上的l d p c 码性能远好于二元域l d p c 码，但其运算复杂度与阶数成指数级增加 关系，一旦找到低复杂度的编译码方法，多元域的l d p c 码将具有更好的实用性； 4 ，找到一种合适的分析方法来研究l d p c 码的性能也是一个重要课题。本论文主 要围绕前两个问题展开，主要是研究8 0 2 1 6 e 系统规定的构造特殊的l d p c 码的性 能，改进编码器的设计，以减少资源消耗；另外在研究现有译码算法的基础上， 本文提出一种不仅译码速度快，复杂度低，且性能也较之现有算法有可观改进的 译码算法。 众多研究成果表明，l d p c 码是一类性能优异的好码，比t u r b o 码在技术上更 有优势，更能适应未来系统高速数据传输和高性能的要求。由于其提出时间较晚， l d p c 码己与第三代移动通信标准失之交臂，但基于l d p c 编码的方案极有可能成 为第四代移动通信系统的应用方案i l ，目前基于l d p c 码的研究在各通信领域方 兴未艾，例如移动和固定无线通信、深空通信、光纤通信、卫星通信和磁光全息 存储等领域的应用。 6 基于i e e e 8 0 2 16 e 协议的l d p c 码编译码算法的研究 1 4 论文主要工作及内容安排 无线城域网( w i m a x ) 是一种新兴的宽带无线接入技术，提供面向互联网的 高速连接，它的另一个名字就是8 0 2 1 6 。这项技术起点高，采用了代表了未来通 信技术发展方向的o f d m o f d m a 、a s s 、m i m o 等先进技术，尤其是随着d s p 芯片技术的发展，快速傅里叶变换反变换技术的引入，无线城域网的技术越来越 成熟，应用更加广泛。在无线城域网系统中，纠错编码是必不可少的。 本文的编码方案遵照i e e e 8 0 2 1 6 e 协议的规定，采用一种块编码的方法，给出 具体的编码算法；译码算法方面，目前软判决译码算法是l d p c 码译码算法研究 的重点，本文的工作主要集中在如何降低运算量的同时又能保持良好的译码性能 上。本文在详细论述了现有的几种主要译码算法的基础上，讨论了一种基于l l r b p ( 对数域b p ) 算法的简化译码算法，这种算法增加了码元信息之间的相关性，降 低了译码的复杂度，使快速译码得以进一步的实现，且相对于目前的简化译码算 法，本算法的性能也有不小的改善。 第一章为绪论，首先简要介绍了纠错码的相关知识，尤其是l d p c 的发展历 程和研究现状，然后根据i e e e 8 0 2 1 6 e 的系统要求确定了本文的研究任务，明确了 所要进行的工作； 第二章详细介绍l d p c 码的构造方法和分类，以及l d p c 码的最小码重分布； 第三章介绍l d p c 码的基本编码方法以及i e e e 8 0 2 1 6 e 系统使用的编码方法， 给出了1 2 码率l d p c 码的具体构造方法，测试并分析了这种构造的l d p c 码与随 机构造的l d p c 码在同等译码条件下性能的差别，介绍了编码器核心模块的设计 方法，给出了一种节省硬件资源的串行编码方法和一种高效的矩阵存储方法； 第四章详细论述l d p c 码的几种主要的软判决译码算法，并以此为基础给出 了一种改进的对数域b p ( b e l i e f p r o p a g a t i o n ) 译码算法一二维修正的a p p b a s e d 算法，讨论了算法的原理、设计步骤，分析了各种译码算法的复杂度，首先对比 采用单一修正因子和不采用任何修正因子时的性能，接下来同时采用两个修正因 子进行性能仿真，与现有经典算法对比，并且提出了分信噪比动态选取修正因数 的方法，充分体现了选择不同的修正因子对性能的不同影响，最终找到最优的修 正因数对的选取，体现了本算法的性能优于现有的l l rb p 改进算法，且复杂度远 低于b p 算法。同时本文给出了在q a m 等多种调制方式下，高斯白噪声信道和瑞 利信道下不同译码方式的仿真图，显示了在不同信道下二维修正的a p p b a s e d 译 码算法的性能。最后结合8 0 2 1 6 e 系统中规定的l d p c 码校验矩阵具有分块性这一 特点，给出了一种高效率的译码器设计方法，通过分析校验矩阵的特点和详细介 绍译码器的设计思路，给出了具体的设计结构图，很清晰地说明了了这种设计方 法的优势。 第五章总结全文，并对下一步工作进行展望。 第二章l d p c 码的基本原理 7 第二章l d p c 码的基本原理 低密度奇偶校验码( l d p c ：l o wd e n s i t yp a r i t yc h e c k ) 码，是基于稀疏校验 矩阵的线性分组码。所谓稀疏是指其校验矩阵中非零元素的个数小于矩阵元素总 数的一半；当稀疏矩阵的非零元素随着矩阵元素的增加而减小时，这个矩阵就是 非常稀疏了，l d p c 码的校验矩阵正是这样一种非常稀疏矩阵。这使得l d p c 码的 译码复杂度与码长呈线性关系，使其长码的应用成为可能。 2 1 线性分组码 线性分组码是分组码中最重要的一类码，是研究各种码字的基础1 13 1 。特别是 生成矩阵g 和校验矩阵日，其中后者与码字纠错能力之间有着重要的关系。本节 讨论线性分组码的重要概念，如g 矩阵和日矩阵、码重和码距、系统码等。 通常用( 玎，七) 表示一个线性分组码，也就是将信息划成k 个码元为一段( 称信 息组) ，通过编码器变成长为靠个码元的组。这”码元称为码字( 码组) ，冗余的刀一k 个码元为校验位，其产生方式仅与本组的k 个信息位有关，而与其他组的信息位无 关，译码时也仅仅利用本组码元，这种码称为线性分组码，码率，= k n 。二元线 性分组码必须满足如下两个条件： 1 ) 码字集合中的任意两个码字经过模2 加之后得到的结果仍然是码字集合 中的一个码字； 2 ) 码字集合包含有全零码字。 显然，在二进制情况下每个码元的取值只有0 和1 两种，则一个( ”，七) 码共有2 个码字。 长的数组共有2 ”组，这2 ”个n 维数组构成了g f ( 2 ) 域( 本论文只研究二 元域的l d p c 码，所以对q 2 的情况不做讨论) 上的g 维线性空间。 2 1 1 生成矩阵和校验矩阵 线性分组码的编码过程可以描述为一个信息矢量s 和一个矩阵相乘的结果： c = s xg ( 2 1 ) 其中g 是生成矩阵，有k 个刀维矢量 岛，l ，g k - 1 ) r 构成；s 是信息序列 ，而，s k _ ) ；c 是编码得到的 维编码输出 c o ，q ，巳一， ，其中矢量与矩阵的乘 法是在二元域g f ( 2 ) 上进行的。 根据式( 2 1 ) ，码字c 可以表示为 8 基于i e e e 8 0 2 16 e 协议的l d p c 码编译码算法的研究 c = s o g o + 岛g l + + & 一l xg k 一1 ( 2 - 2 ) 对应每一个k r 的生成矩阵g ，存在一个( 1 - 七) ，z 的矩阵日，g 的行和日的 行正交，即g h r = 0 ，h7 是日的转置矩阵，0 是一个kx ( n k ) 的全零矩阵，称日 为校验矩阵。很容易证明码字和校验矩阵满足以下关系： 啊：l啊。 红： l 吃。 mom 红柑) 2l 政柑加 q e m 巳 = 0 ( 2 - 3 ) 简写为：田r = 0 或者h c r = 0 。 如果生成矩阵g 经过有限的行运算和列置换后，转化成g - - el ，】的形式，其 中尸是kx ( 聆一k ) 维矩阵，为k xk 的单位矩阵。这时，生成的码字前k 位是信息 位，余下的( 刀一k ) 位是校验位。 线性分组码可以由其校验矩阵或者生成矩阵唯一确定。 2 1 2 系统码 系统码可以定义如下：若信息组以不变的形式在码组的任意k 位( 通常在最前 面) 出现，那么这样的码称为系统码，否则称为非系统码。系统码可用如下框图 直观的表示： 图2 1 系统码框图 也可以用矩阵的形式表示，将线性分组码的生成矩阵g 变换成如下形式 g = 【只( 柑) iik。k】(2-4) 其中，p 是生成矩阵的校验阵列，厶。是单位矩阵。同样道理，校验矩阵的系 统形式为： h = 训柑) lp k 女) 】 ( 2 5 ) 利用系统形式的校验矩阵可以很容易地求出系统码。 2 1 3 码距和码重 两个码字x = x l x 2 人x n ，】，= m 班人儿之间的汉明码距定义为两个码字对应码 元不相同的位数，用d ( x ，n 表示，例如：x = 1 0 1 0 1 ，y = 1 0 0 1 0 ，则d ( x ，y ) = 3 第二章l d p c 码的基本原理 9 码字x = x ，x 2 l 矗的汉明重量，是指码字中非零码元的位数，用w ( x ) 表示。 一组码字c 包括若干码字 q ，c 2 ，巳) ，所有这些码字相互间码距的最小的数值， 称为该码组的最小码距d ： d = m h a d ( c ：，c ，) = m i i l 形( c ：一c ，) ，i , j 1 ，2 ，l ，f j ( 2 - 6 ) 最小码距d ，表明了分组码抗干扰能力的大小。d 越大，码的抗干扰能力越强， 在同一种译码方法下最小码距大的码字译码错误概率越小。因此，通常用最小码 距来分析码的检错纠错能力。 2 1 4 线性分组码的译码 由于线性分组码可以由校验矩阵或生成矩阵唯一确定，所以只要找到了日矩 阵或者g 矩阵就解决了编码问题。编码后的码字在传输过程中经过信道受到干扰 可能出错，那么在接收端就要考虑检错和纠错，这就是译码问题。 线性分组码常用一种代数译码来进行译码，称为伴随式译码。如果发送码字 为c = q ，c 2 ，巳) ，经过信道后接收序列为，= ，r 2 ， ，最大似然译码( m l d ) 是在码集合c 中找到使似然函数p ( r 旧) 最大的q 作为发送码字c 的估计。对离散 无记忆信道，似然函数表示为乘积形式： l _ p ( ，iq ) = i jp ( r jc i j ) ( 2 - 7 ) 此时可以采用对数似然准则，最佳译码为： d = a r g cm a x e l o g p ( r jf 勺) ( 2 - 8 ) 。f j = i 一般m l d 译码需要g 个求和运算，同时需要找到具有最大对数似然函数的 码字，其运算复杂度随码字长度的增加呈指数形式增加，是不可实现的。但是， 中等码长或更长码长的一面可以采用一些次最佳算法来逼近m l d 译码。 利用码字之间的汉明距离也可以进行译码，即选择与接收矢量r 距离a ( r ，c ，) 最 小的c i 作为c 的估计，称为最小汉明距离译码。 接收矢量可以表示为，= c + e ，e 是g f ( q ) 上的矢量称为码字c 的错误图样， 描述了码字在传输过程中发生错误的情况。当e = o 时，没有错误。当g = 2 时，由 于a ( r ，e ) = w t ( r ，c ，) = w t ( e ) 最小意味着e 的重量最小。在所有的错误图样中找到最 小重量的一个，从r 中减去e ，即可得到最小距离译码。将接收矢量进行校验，有 r h 丁= ( f ，+ e ) h r = e h r 。由此，定义s = r h r = 讲7 1 为接收矢量，的伴随式，含有 接收矢量的全部信息。显然，若e = 0 s = 0 ，没有错误，= c ；若e 0 ，s 0 则发 生错误，如果能从s 得到e ，则由c = ，一e 可恢复发送的码字。可见，s 仅与e 有关， 1 0 基于i e e e s 0 2 1 6 e 协议的l d p c 码编译码算法的研究 反映了信道干扰的情况，与发送的码字无关。 由上述的讨论可以得知，译码的一般步骤为： 1 ) 计算接收矢量的伴随式； 2 ) 找到对应的错误图样； 3 ) 通过c = ，一e 实现译码。 值得注意的是，若错误图样e 本身是一个码字时，s = 0 ，此时的错误不能被 发现，也无法纠正，为不可检测错误模式。 2 2l d p c 码简介 通常用( n ，七) 的形式来表示l d p c 码。在1 9 6 2 年g a l l a g e r 关于l d p c 码的定 义中，表示为( ”，k ) 的l d p c 码的奇偶校验矩阵有以下结构特征： 1 ) 每行有k 个l ( k 为定值，k 又称行的权重，其它元素为0 ) ； 2 ) 每列有，个1 ( ，为定值，又称行的权重，其它元素为0 ) ； 3 ) 任意两行( 列) 具有共同“l “的位置个数不超过1 ； 4 ) k 和，与日的列数和行数相比是很小的。 l d p c 码可以由其校验矩阵日唯一定义，日矩阵的每一行对应一个校验方程， 每一列对应码字的一位。例如： h = 2 2 1t a n n e r 图 t a n n e r 于1 9 8 1 年提出了l d p c 码的图形表示法，t a n n e r 图由两类节点组成， 表达了码字比特和校验方程的校验位之问的关系。如图2 2 所示，上面的一行节点 v 1 、u 、v 4 和k 是变量节点，可以认为是一个码字中的一个比特对应于校验矩 阵中的一列；下面的一行的节点g 、c 2 、c 3 和c 4 是校验节点，分别表示一个校验方 程，对应于校验矩阵的一行。当码字中某比特出现在某一校验方程中，即校验矩 阵中相应的位置为“1 ”时，图2 2 中的上下节点之间存在连线，这条线被称为两 端节点的相邻边，相邻边两端的节点被称为相邻点。每个节点相邻的边数称为该 节点的度数。 l d p c 码有正则码和非正则码两类，正则l d p c 码的校验矩阵具有相同的行重 叻 二 l o o o o o = = = = = “所国印印 + + + + + 以靠像瑰白 + + + + + 以彩玖旬 + + + + + 仍自以o “ o 0 o 1 1 o o l o l o 0 1 1 0 0 l 0 o 1 0 1 o 1 o o 1 1 o o 1 0 0 o 1 l o o 1 o 1 o 1 o 0 l 1 o o o 第二章l d p c 码的基本原理 和列重；非正则l d p c 码的校验矩阵行重和列重不同。非正则码和正则码同样可 以通过上下节点度数是否相同来定义。 v lv 2v 3 v 4v 5 h = 1l00 0 o1101 01o11 1011l 图2 2 校验矩阵及其t a n n e r 图表不 上图所给出的就是非规则l d p c 码的校验矩阵及t a n n e r 图，可以看出k ，k 和 圪各有两条边，其余变量节点各有3 条边；c l 校验节点有2 条边，c ，和g 有3 条 边，c 。有四条边，也就是具有5 个变量节点和4 个校验节点。 译码信息就是通过边来传递的，从t a n n e r 图可以直观的看出，变量节点的度 越多，它从校验节点得到的信息越多，那么就能越准确地判断出它的正确值，因 此信息节点最好有高的度数。相反的，从校验节点来看，校验节点的度数越高， 它可能发送给变量节点的错误信息就越多，因此，它的度数最好比较低，这两个 矛盾的要求必须折中处理。 从译码的角度来看，非正则码的性能要优于正则l d p c 码，尤其是已经证明 了，构造优良的非正则l d p c 码在性能上已经很好的逼近s h a n n o n 限了，是因为， 如果选择非正则t a n n e r 图的话，在平衡上述矛盾的两项要求的时候将有更大的选 择范围。事实上，性能的改进源自于变量节点度数的变化，具有高度数的信息节 点迅速得到它们的正确值，接着就能提供更为正确的信息给度数稍低的节点。非 正则t a n n e r 图的构造正是导致了这种波状效应，度数最高的节点首先得到它们的 正确值，接着是度数稍低的节点，然后是度数更低的节点，如此不断继续下去。 以下给出规则l d p c 码与非规则l d p c 码的性能对比图。 1 2 基于i e e e 8 0 2 1 6 e 协议的l d p c 码编译码算法的研究 静 謇 蝼 图2 3规则l d p c 码与非规则l d p c 码性能对比图( n = 1 00 0 0 ) 从图2 3 可见，规则l d p c 码与非规则l d p c 码的误码率都随着s n r 的增加 下降，当s n r 到达一定值时，规则码的误码率出现陡降区( w a t e r f a l l ) ，误码率迅 速降低。在此之前，非规则码的性能要优于规则码，在此之后，非规则码的误码 率曲线变化缓慢，存在错误平台现象。这是因为规则码的变量节点的度数是4 ，而 非规则码中存在度数为2 的节点，l d p c 码的度分布对码字的性能有着至关重要的 影响，接下来的一节将对度分布做简要介绍。 2 2 2 度分布 对于每一个l d p c 码组，其每一个码都可以由校验矩阵或t a n n e r 图唯一确定， 这两者是等价的。而一个l d p c 码的集合可以相应的用码生成函数或度数分布表 示【2 0 1 。 设最大变量节点的