（通信与信息系统专业论文）低密度奇偶校验码的混合译码.pdf

中文摘要 摘要：低密度奇偶校验( 1 0 w - d e n s i t yp a r i t y c h e c k ，l d p c ) 码的混合译码结合了软 判决译码和硬判决译码的特点，利用部分信道信息计算硬判决序列的可靠度，实 现性能与复杂度的折衷。与软判决译码相比，现有的混合译码在性能方面尚存一 定差距，这制约了混合译码在高可靠通信方面的应用。所以，在保持较低复杂度 的前提下，设计具有更加接近软判决译码性能的混合译码算法，是非常具有实际 意义的。 首先，提出了改进的加权比特翻转( w e i g h t e db i t f l i p p i n g ，w b f ) 算法。该算 法在计算外信息时，仅考虑不满足的校验方程，而忽略了那些满足的校验方程， 以此达到简化外信息计算，降低译码复杂度的目的。仿真结果表明，改进的w b f 算法与传统的w b f 算法误码性能相当。 其次，利用j a c o b i a n 对数关系式，证明了加权一步大数逻辑( w e i g h t e do n e s t e p m a j o r i t y l o g i c ，w m l g ) 译码的实质就是m a x l o gm a p 译码的一次迭代，并通过仿 真验证了w m l g 译码和l o g m a p 一次迭代译码的性能几乎相同。在此基础上， 将非均匀量化应用于迭代大数逻辑( i t e r a t i v em a j o r i t y 1 0 9 i c ，i m l ) 译码算法，提出 了改进的i m l 译码算法，用非均匀量化代替原算法的均匀量化，降低小信号的量 化噪声。仿真表明，在相同的量化长度下，改进的i m l 算法的误码性能有了显著 提高。 最后，以w m l g 的推导为理论依据，提出了加权迭代一步大数逻辑( w e i g h t e d i t e r a t i v eo s m l g , w i o ) 算法。该算法利用衰减因子校正w m l g 算法中可靠度的 偏差；在计算硬判决比特的外信息时，排除当前比特携带的信息，进一步提高了 外信息计算的精度；并在迭代过程中利用外信息持续更新可靠度。仿真结果表明： 在计算复杂度相当的情况下，w i o 算法的误码性能优于现有的混合译码算法；w l o 算法具有较快的收敛速度，当迭代次数较少时，误码性能与和积算法( s u mp r o d u c t a l g o r i t h m ，s p a ) 几乎相同；在较高信噪比下，w i o 算法未出现s p a 译码算法中的 误码平台效应。此外，针对不同类型的l d p c 码，w i o 算法的衰减因子均具有很 好的鲁棒性，在实际应用中，为便于实现，通常可取衰减因子为o 5 。 关键词：l d p c 码；混合译码算法；加权一步大数逻辑；衰减因子；复杂度 分类号：t n 9 1 1 2 2 ； a bs t r a c t a b s t r a c t ：h y b r i dd e c o d i n gf o rl 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 sc o m b i n e s t h ef e a t u r e so fh a r d d e c i s i o na n ds o f t d e c i s i o nd e c o d i n g i nh y b r i dd e c o d i n g ，r e l i a b i l i t y m e a s u r e so fh a r d d e c i s i o ns e q u e n c ea r eo b t a i n e df r o mp a r t i a lc h a n n e li n f o r m a t i o n t h e r ei s s t i l law i d ep e r f o r m a n c eg a pb e t w e e nh y b r i dd e c o d i n ga n ds o f t - d e c i s i o n d e c o d i n g ，w h i c hh a sb e c o m ea l lo b s t a c l ei nt h o s eh i g l l - r e l i a b l ec o m m u n i c a t i o ns y s t e m s n e w h y b r i dd e c o d i n gw i t hb e t t e rp e r f o r m a n c eb e c o m e sap r a c t i c a lt a s kf o rt h er e s e a r c h f i r s t l y , a ni m p r o v e dw e i g h t e db i t f l i p p i n g ( w b f ) d e c o d i n ga l g o r i t h mi sp r o p o s e d i nt h i sa l g o r i t h m ，o n l yt h eu n s a t i s f i e dc h e c k - s h i l l sa r eu s e dt og e te x t r i n s i ci n f o r m a t i o n o fr e c e i v e ds y m b o l s ，w h i c hr e d u c e sc o m p u t a t i o n a lc o m p l e x i t y s i m u l a t i o nr e s u l t ss h o w t h a te r r o rp e r f o r m a n c e so fi m p r o v e dw b fa r ea l m o s ti d e n t i c a lt oc o n v e n t i o n a lw b e s e c o n d l y , w e i g h t e do n e s t e pm a j o r i t y - l o g i c ( w m l g ) d e c o d i n ga l g o r i t h mi sd e d u c e di n t h ep e r s p e c t i v eo fl o g - m a pd e c o d i n gb yu s i n gj a c o b i a nl o g a r i t h m t h ec o n j e c t u r et h a t w m l gd e c o d i n ga p p r o a c h e sl o g - m a pd e c o d i n gi nt e r m so fe r r o rp e r f o r m a n c ei s v e r i f i e db ys i m u l a t i o n o nt h eb a s i so ft h ee s s e n t i a lo fw m l g a ni m p r o v e di t e r a t i v e m l g ( i m l ) a l g o r i t h m i sp r o p o s e d ，a n di tp r o c e s s e st h er e c e i v e ds e q u e n c eb ya d o p t i n g u n e v e nq u a n t i z a t i o n s i m u l a t i o nr e s u l ti n d i c a t e st h a ti m p r o v e di m la l g o r i t h mc a n o b t a i nb e t t e re r r o rp e r f o r m a n c et h a ni m l f i n a l l y ，aw e i g h t e di t e r a t i v eo s m l g ( w i o ) a l g o r i t h mi sp u tf o r w a r d i nw i oa l g o r i t h m ，c o m p u t a t i o no fr e l i a b i l i t ym e a s u r eo f t h e c h e c k s u mi sr e f i n e db yi n t r o d u c i n ga na t t e n u a t i o nf a c t o ra n dc o m p u t a t i o no fe x t r i n s i c i n f o r m a t i o ni si m p r o v e db yp r e c l u d i n gt h ei n f o r m a t i o no fs y m b o li t s e l f1 n h er e l i a b i l i t y m e a s u r e so fh a r d d e c i s i o ns y m b o l sa l eu p d a t e di ne a c hi t e r a t i o np r o c e s s s i m u l a t i o n r e s u l t ss h o wt h a tw i od e c o d i n ga l g o r i t h mo u t p e r f o r m s a 1 1o t h e rp o p u l a rh y b r i d d e c o d i n ga l g o r i t h m sw i t has l i g h ti n c r e a s ei nc o m p u t a t i o n a lc o m p l e x i t y d u et of a s t e r c o n v e r g e n c es p e e do fw i od e c o d i n g ，e r r o rp e r f o r m a n c e so fl d p c c o d e sd e c o d e dw i t h w i oa n ds p aa l ea l m o s ti d e n t i c a lw i t hi t e r a t i o n sn om o r et h a nf i v e i nc o m p a r e dw i t h s p a ，n oe r r o rf l o o re f f e c tc a nb eo b s e r v e df o rw i oa l g o r i t h mi nh i g hs n rr e g i o n t h e a l g o r i t h m i sr o b u s ti nt e r m so fa t t e n u a t i o nf a c t o r f o ri m p l e m e n t a t i o nr e a s o n ， a t t e n u a t i o nf a c t o rc a nb ec h o s e nt ob e0 5 k e y w o r d s ：l o w - d e n s i t yp a r i t y - c h e c kc o d e s ；h y b r i dd e c o d i n g ；w e i g h t e do n e - s t e p m a j o r i t y - l o g i c ；a t t e n u a t i o nf a c t o r ；c o m p l e x i t y c l a s s n o ：t n 9 1 1 2 2 本论文从最初的论文选题、深入研究到最后的成文，得到了许多老师和同学 的帮助和支持，在此向他们表达谢意。 首先，感谢我的导师张立军老师，本文是在张立军副教授的亲切关怀和悉心 指导下完成的。他严肃的科学态度，严谨的治学精神，精益求精的工作作风，深 深地感染和激励着我。从课题的选择到论文的最终完成，张老师都始终给予我细 心的指导和不懈的支持。感谢张老师在学术理论上的点拨和指引，感谢张老师在 为人师表上的表率作用，在今后的学术或工作生活中，我将以此为榜样，严谨缜 密，广开思路，不断创新。 其次，感谢胡师舜老师还有3 1 5 实验室的各位博士师哥、师姐，他们给了我 无私的帮助和不倦的指导，让我在一个充满温暖和关爱的环境里愉快而顺利地完 成了学业。特别要感谢胡老师，她的认真负责、勤勤恳恳的工作作风和对学生的 真挚关爱使我们从学习、做课题到最后的论文答辩准备工作得以顺利完成的重要 支持力量。 感谢宋紫溪、黄捷、张宇、王婷、卢怡、霍红艳等同学对我两年多来的研究 生学习和生活期间给我的无微不至的关心和帮助，和你们的融洽相处使我有了一 个难忘的生活经历，特别要感谢的是宋紫溪、黄捷同学，作为同门，他们在论文 的研究工作和学术问题的讨论上，给予了很大的帮助，使我能更投入的完成论文。 感谢我的家人，尤其是我的妈妈，你们的关心和鼓励是我前进的动力，是我 永远的、强大的后盾支撑，你们的健康快乐是我的最大心愿。 最后，向所有关心我、帮助我的人们表示衷心的感谢! 1 引言 g a l l a g e r 在1 9 6 2 年首次提出了低密度奇偶校验( 1 0 w - d e n s i t yp a r i t y c h e c k 。 l d p c ) 码【l 】，并于1 9 6 3 年发表在他的博士论文t 2 1 。由于当时的硬件条件的限制， 加之r e e d s o l o m o n 码的出现【3 】，l d p c 码被忽视了2 0 多年。1 9 8 1 年t a n n e r 从图 的观点对l d p c 码进行全新的阐释【4 5 】，上世纪九十年代，m a c k a y 和n e a l 等人又 重新发现了l d p c 码【6 , 7 1 。 和t u r b o 码一样【3 , 8 - 1 1 】，l d p c 码也具有接近香农限的性能。采用置信度传播迭 代译码的长l d p c 码已被证实能够获得距离香农限0 0 0 4 5d b 的误码性能【1 2 1 。l d p c 码被认为是迄今为止性能最好的码，是当今信道编码领域令人瞩目的研究热点， 近几年国际上对l d p c 码的理论研究以及工程应用等都已取得重要进展。基于 l d p c 码的优异性能，l d p c 码被广泛应用于光通信、卫星通信、第四代移动通信 系统、高速与甚高速数字用户线、光和磁记录系统等f 1 3 】。l d p c 码的研究主要包括 码构造、编译码、l d p c 码性能分析及应用掣1 3 。1 舯。其中，l d p c 码的高效译码算 法是一大研究热点【2 2 3 l 】。 1 1l d p c 码的译码算法分类 对同样的l d p c 码来说，采用不同的译码算法可以获得不同的误码性能。优 秀的译码算法可以获得很好的误码性能，反之，采用普通的译码算法，误码性能 则表现一般。对于l d p c 码的构造来说，选择何种译码算法是非常重要的，因为 通过好的稳定的译码算法的误码性能的分析，我们才可以很明显的看出构造的 l d p c 码的好坏，但是译码性能的改善通常是伴随着译码算法复杂度的增加。如何 设计高效的译码算法是一个相当关键的问题。 l d p c 码的译码算法包括比特翻转( b i t f l i p p i n g ，b f ) 算法【1 3 ，i5 1 、一步大数逻 辑( o n e s t e pm a j o r i t y 1 0 9 i c ，o s m l g ) 译码算法【1 3 , 1 9 , 2 0 】、加权比特翻转( w e i g h t e db f , w b f ) 算法【1 3 ，2 1 2 2 捌、加权o s m l g ( w e i g h t e do s m l g , w m l g ) 译码算法1 1 3 1 9 1 、 和积译码算法( s u m p r o d u c ta l g o r i t h m ，s p a ) 等【1 3 j 5 ；2 6 1 。根据信道信息利用率的不 同，可将这些译码算法归为以下三大类。 1 1 1硬判决译码 硬判决译码将接收的实数序列先通过解调器进行解调，再进行硬判决，得到 硬判决0 ，1 序列，最后将得到的硬判决序列输送到硬判决译码器进行译码。这种方 式的计算复杂度固然很低，但是硬判决操作会损失掉大部分的信道信息，导致信 道信息利用率很低，硬判决译码的信道信息利用率和译码复杂度是三大类译码中 最低的。从量化译码的角度来考虑，硬判决译码可以看成是l 比特量化译码，只 利用了信道信息的符号信息，没有考虑接收信号的幅度信息，损失掉了大部分的 信道信息，导致误码性能较差。 常见的硬判决译码算法有b f 算法和o s m l g 算法【1 3 1 。b f 算法最早是由 g a l l a g e r 提出的【2 1 ，该算法是一种典型的硬判决译码算法，译码原理可表述如下【3 】： 若在传输过程中发生了错误，部分校验方程会得不到满足，对应的校验和会等于1 。 在不满足的校验方程中，若包含某些比特的方程数超过某个门限值，则改变这些 比特的取值。利用这些新的取值重新计算校验方程，重复该过程直到所有的校验 方程都得到满足或达到最大迭代次数。但这种b f 算法需要设置门限值，若门限值 设置的过低，太多比特会被翻转，导致大量的译码错误；若门限值设置过高，则 不会改变任何比特。从上述描述可以看出，b f 算法是一种迭代的硬判决译码算法， 在每次迭代译码过程中，通过翻转部分比特来不断更新硬判决序列，新的硬判决 序列作为下一次迭代的输入，最终达到正确译码的目的。 针对需要设置门限值的问题，s l 协在论文【1 5 】中提出简化的比特翻转算法， 该算法不必设置门限值。因为对硬判决序列中的每个码比特而言，都有一定数量 的校验方程参与校验该比特，所以每个码比特都对应存在一个整数值，等于包含 该码比特的不满足的校验方程的个数。选取对应不满足校验方程数最多的比特进 行翻转，会引起不满足的校验方程数发生变化，通过迭代处理，直到所有的校验 方程均得到满足或达到最大迭代次数。本论文的实际仿真中涉及到的b f 算法，都 是采用s l i i l 的这种简单实用的译码算法【1 3 , 1 5 】。 b f 算法的最大缺点是不能进行并行译码，译码复杂度较o s m l g 算法也有很 大提高。但b f 算法的迭代译码处理，使得误码性能较o s m l g 算法有很大提高。 相比之下，o s m l g 译码算法仅是迭代一次的操作过程，o s m l g 算法针对硬判决 序列的各个码比特，计算其参与的不满足的校验方程的个数，当不满足的校验方 程个数超过一半时，则认为该比特的硬判决结果不可靠，需对该硬判决比特进行 翻转，而那些不满足的校验方程个数未超过一半的比特，则不需要翻转，通过上 述处理得到的新的硬判决序列作为译码输出结果。o s m l g 算法可看作是并行的仅 迭代一次的b f 过程，其误码性能较b f 算法有一定差距，但o s m l g 算法的最大 优点是可以实现并行译码，译码复杂度是所有硬判决译码算法中最低的，实际应 用中可采用逻辑组合电路来实现【l3 1 。 2 1 1 2软判决译码 与硬判决译码的1 比特量化相比，软判决译码可以看成是无穷比特量化译码， 它充分利用接收的信道信息( 软信息) ，信道信息利用率得到了极大的提高，软判 决译码利用的信道信息不仅包括信道信息的符号，也包括信道信息的幅度值。信 道信息的充分利用，极大地提高了译码性能，使得译码可以迭代进行，充分挖掘 接收的信道信息，最终获得出色的误码性能。软判决译码的信道信息利用率和译 码复杂度是三大类译码中最高的。 最常用的软判决译码算法是和积译码算法，又称置信传播( b e l i e f p r o p a g a t i o n , b p ) 算法d 3 2 6 ，该算法适用于噪声独立的二进制传输信道，如无记忆的二进制对 称信道( b i n a r ys y m m e t r i cc h a n n e l ，b s c ) 、二进制输入实数输出的高斯信道【3 2 1 。采 用s p a 可获得非常接近香农限的译码性能【1 3 , 1 4 1 。 s p a 算法中消息的传递形式是对数似然比( 1 0 9 1 i k e l i h o o dr a t i o ，l l r ) ，在迭代 过程中，每次在变量节点按照求和规则更新节点的信息，在校验节点按照t a n h 规 则更新节点的信息，直至译码结束或所有的校验方程得到满足。s p a 算法具有接 近香农限的优秀误码性能，但由于每次迭代更新过程中需要进行大量的实数运算， 译码复杂度很高，而造成这种现象的原因主要是校验节点的t a n h 规则的迭代更新 需要大量的实数乘法运算，计算过程非常复杂0 3 , 2 6 。 为了简化校验节点的信息更新计算，人们提出很多简化的s p a 算法，其中最 著名的是最小和译码算法【1 3 , 1 6 。该算法在处理校验节点和变量节点的信息更新时， 只需要进行实数比较和实数加法运算，对于校验节点来说，进行信息的迭代更新 只需找到参与该校验方程的所有变量节点的幅度的最小值和次最小值，大大简化 了校验节点的信息计算。对于a w g n 传输信道来说，使用最小和译码算法的另一 个好处是译码器不需要估计信道参数。但由于最小和译码算法对幅度的估计过于 乐观，导致校验节点更新信息的幅度值比s p a 算法中的真实值偏大，为此人们提 出两种校正偏差的方法，一种方法是引进衰减因子进行校正，另外一种方法是采 用最小幅度值减去一个固定的常实数来进行补偿【1 6 1 。 i 1 3混合译码 与上述的硬判决译码和软判决译码相比，混合译码结合了软判决译码和硬判 决译码的特点，是一类基于可靠度的译码算法，它在硬判决译码的基础上，利用 部分信道信息进行可靠度的计算。在三大类译码中，混合译码的信道信息利用率 低于软判决译码，但高于硬判决译码。在混合译码中，其变量节点的可靠度的更 新计算，和s p a 译码算法类似，是通过求和运算进行的，并且在每次迭代过程中 不断更新变量节点的可靠度，挖掘更多可靠的信息，以达到正确译码的目的。但 是混合译码的校验节点的可靠度衡量在每次迭代过程中基本都是不变的，这样可 以在一定程度上降低计算复杂度，实现译码复杂度和误码性能之间的折衷。 常用的混合译码算法有w b f 译码算法和w m l g 译码算法【1 3 , 1 5 , 2 2 , 2 5 1 ，在w b f 算法中，变量节点的可靠度计算是将参与校验该节点的所有校验方程的可靠度进 行求和，由于校验方程的情况可分为：满足的和不满足的，相应的可靠度衡量的 符号分为：负号和正号，即变量节点的可靠度计算等价为一部分正实数与一部分 负实数的相加求和。在译码的迭代过程中，利用上一次迭代过程中获得的新的硬 判决序列，得到校验和的新情况，即部分校验方程的可靠度的符号会发生改变， 这样各变量节点就获得了新的可靠度，通过更新变量节点的可靠度，不断挖掘可 靠的译码信息，不断进行硬判决序列的更新，迭代过程不断进行，直到所有的校 验方程都得到满足或达到最大迭代次数。在w b f 算法的译码过程中，每次迭代都 选取对应可靠度最大的变量节点进行翻转，得到的新的硬判决序列作为下一次迭 代的输入。 相比之下，w m l g 译码算法的各个变量节点的可靠度的计算是参与校验该节 点的所有校验方程提供的外信息相加求和。当该硬判决比特的可靠度大于0 ，则翻 转该比特；反之，当该硬判决比特的可靠度小于或等于o ，不翻转，最后得到的新 的硬判决序列作为译码结果输出。w m l g 译码仅是迭代1 次的操作过程，信息挖 掘很不充分，但w m l g 译码算法最大的特点是并行译码，在迭代次数为1 次的时 候，w m l g 译码算法的误码性能远远优于w b f 译码算法1 ，这主要归功于w m l g 算法的并行译码，使得译码收敛速度较快。 1 2 研究现状 l d p c 码在经过数十年的沉寂后，随着计算机能力的增强和相关理论的发展， 取代t u r b o 码的趋势是很明显的，研究l p d c 码的学术意义、商业价值以及对通 信领域相关技术发展的推动作用都是巨大的，近几年来，国际上对l d p c 码的理 论研究都已取得重大的进展，在基础应用、工程应用方面的研究正在全方位的开 展【1 3 】o l d p c 码的高效译码算法作为研究的热点之一，其混合译码算法由于结合了软 判决译码和硬判决译码的特点，大量的编码工作人员致力于新型混合译码算法的 1 参见第二章中的圈2 2 4 设计，探索如何在复杂度和误码性能之间进行取舍，达到以相对较低的译码复杂 度来获得好的误码性能的目标【2 3 2 4 2 5 ，2 7 1 。 现有的混合译码算法，如j i a n gm i n g 等提出的改进的w b f ( i m p r o v e dw b f ， i m w b f ) 算法【25 。、g u of e n g 等提出的基于可靠率的w b f ( r e l i a b i l i t y r a t i ob a s e dw b f , r w b f ) 算法【3 3 1 、c h e n 等提出的加权迭代o s m l g ( w e i g h t e di t e r a t i v eo s m l g , w i m l ) 算法【27 1 、h u a n gq i n 等提出的迭代o s m l g ( i t e r a t i v eo s m l g , i m l ) 算法 z 3 2 4 1 ，都在一定程度上改善了混合译码的性能。与软判决译码相比，上述混合译 码虽在一定程度上降低了译码复杂度，但误码性能也下降很多。 i m w b f 算法和r w b f 算法是针对w b f 算法进行的改进，与传统w b f 算法 相比，i m w b f 算法中硬判决序列的各个码比特的外信息的计算，排除了该比特自 身携带的信息，并且在精确的外信息基础上引入当前比特的幅度的加权项，得到 的信息作为该比特的可靠度衡量，在每次迭代过程中，选取对应可靠度最大的比 特进行翻转，得到的新的硬判决序列作为下一次迭代的输入【2 5 1 。i m w b f 算法提高 了外信息的计算精度，比特是否翻转由两部分取值共同决定：校验方程提供的外 信息、该比特自身的幅度信息的加权值，误码性能较w b f 算法有很大的提高， i m w b f 算法是目前w b f 类算法中比较优秀的译码算法，它以很小的译码复杂度 的增加获得非常好的误码性能。而r w b f 算法在计算硬判决序列的各个码比特的 外信息时，不是按照w b f 算法那样，采用参与各个校验方程的码比特的幅度最小 值作为校验方程的可靠衡量，而是综合考虑参与校验方程的所有码比特对该方程 取值的影响，利用当前比特的幅度除以参与校验方程的所有比特的幅度最大值作 为该比特的可靠率1 3 引。r w b f 算法虽然也在一定程度上获得了性能的改善，但由 于译码过程中需要大量的实数除法运算，该算法的计算复杂度太高。 w i m l 算法和i m l 算法在迭代译码之前，还需要进行繁琐的参数优化，比如 w i m l 译码算法需要进行修正项因子和最大幅度的设置，i m l 算法由于涉及均匀 量化的操作，需要进行量化间隔和量化级数的设置【2 3 4 矧。 w i m l 算法在译码迭代前需要通过仿真确定修正因子，根据硬判决比特的接 收值的符号来判定修正项的取值，如果当前比特的接收幅度值大于0 ，则修正项等 于接收的幅度值加上修正因子；反之，如果当前比特的接收幅度值小于或等于0 ， 则修正项等于接收的幅度值减去修正因子，w i m l 算法在译码的迭代过程中，不 断计算新的外信息，用来更新上一次迭代过程中硬判决比特的可靠度。在每次迭 代译码结束进行判决时，参与判决的部分是当前更新后的可靠度与修正项之和， 如果该实数值大于0 ，则当前比特判为l ，反之，如果该实数值小于或等于0 ，则 该硬判决比特判为0 。将得到的新的硬判决序列作为下一次迭代的输入，迭代过程 不断进行，直到所有的校验方程都得到满足或达到最大迭代次数【2 7 1 。 5 w i m l 算法通过实数的加法运算，不断更新可靠度，不断深入挖掘可靠的译 码信息，译码结果不断趋于正确。相比之下，i m l 算法的译码复杂度下降很多， 性能也比w i m l 算法优秀，i m l 算法在译码复杂度和误码性能之间取得了很好的 折衷，是性能比较优秀的一种混合译码算法。i m l 算法在迭代过程中没有涉及实 数加法或实数乘法运算，只涉及到整数运算，译码复杂度大为降低，i m l 算法的 特点是在迭代进行前，需要将接收的信道信息进行均匀量化【2 3 , 2 4 1 ，得到的量化值 作为硬判决比特的可靠度的初始化。在译码迭代过程中，计算包含当前比特的所 有校验方程提供给该比特的外信息，利用外信息不断更新该比特的可靠度，根据 更新后的可靠度的符号来判定硬判决比特的取值，如果可靠度取值大于0 ，则当前 比特判为l ，反之，如果当前比特的可靠度取值小于或等于0 ，则当前比特判为0 ， 得到的新的硬判决序列作为下一次迭代的输入，迭代更新不断进行，直到所有校 验方程都得到满足或达到最大迭代次数。 w i m l 算法和i m l 算法针对不同的l d p c 码，在译码迭代进行前均需要进行 参数的优化，普适性不是很好，而且在较低的迭代次数下，误码性能较软判决译 码算法的差距还是很大的。因此混合译码算法还是有很大的研究空间的，如何在 译码复杂度和误码性能之间取得良好的折衷还是一个很值得深入探索的问题。 1 3 内容与创新 针对混合译码算法的研究现状，本论文主要是关于l d p c 码的混合译码算法 的设计。 首先提出改进的w b f 算法，该改进算法是从降低译码复杂度的角度展开的， 因为在传统的w b f 译码算法中，各个硬判决比特的可靠度的计算是考虑参与校验 该比特的所有校验方程的情况，即一部分正实数与一部分负实数的相加求和得到 可靠度，改进的w b f 算法是只考虑不满足的校验方程的情况，即各个硬判决比特 的可靠度的计算仅是一部分正实数的相加求和，在每次的迭代过程中选取可靠度 最大所对应的比特进行翻转，得到的新的硬判决序列作为下一次迭代过程的输入。 该迭代过程持续不断地进行，直到所有的校验方程都得到满足或达到最大迭代次 数。与传统的w b f 译码算法相比，该简化版本的误码性能曲线与传统的w b f 算 法相当接近，说明简化的w b f 算法的误码性能与传统的w b f 算法性能相当，而 且改进的w b f 算法的计算复杂度较传统的w b f 算法有一定的降低。 其次，在对w m l g 算法的最初认识中，发现可以从一种新的角度推导w m l g 算法，即根据l o g m a p 译码，采用j a c o b i a n 对数关系式，推导w m l g 译码，证 明了w m l g 算法等价于m a x 1 0 9m a p 译码的一次迭代，并且从仿真实验的角度验 6 证了w m l g 算法和l o g m a p 一次迭代译码的性能几乎相同，进一步证实了w m l g 和m a x 1 0 9m a p 一次迭代的等价性。 将上述推导作为理论依据，尝试在传统的w m l g 算法上做文章，提出了基于 非均匀量化的i m l 算法。i m l 算法是一种改进的o s m l g 算法 2 3 8 4 ，该算法基于 o s m l g 算法的正交校验方程，在译码函数中引入部分信道信息，在译码复杂度和 误码性能之间取得很好的折衷。该算法的最大特点是将接收的实数序列进行均匀 量化处理。但在实际的传输信道中，接收信号的分布并不是服从均匀分布的，在 量化过程中，小信号受量化间隔的影响比较大，为了提高小信号的量化精度，借 鉴非均匀量化来处理接收的信道信息，使得量化误差较均匀量化处理有所减小。 与i m l 算法相比，改进的i m l 算法的不同之处在于迭代译码进行前，各个硬 判决比特的可靠度的初始化是采用非均匀量化来处理接收信号的幅度，量化间隔 分别设为。和，且二者需满足a ， a ，。 最后，本文提出加权迭代的o s m l g ( w e i g h t e di t e m t i v eo s m l g ；w i o ) 算法， 该算法是一种并行的迭代译码过程，迭代不仅仅是一种算法，更是一种重要思想， 在一次次的迭代处理过程中，可以充分挖掘潜在的信息，改善由于判决造成的信 息丢失。通过w m l g 算法的推导过程可看出，采用参与该校验方程的所有比特的 幅度最小值作为校验方程的可靠衡量比真实值偏大，可引进衰减因子来校正校验 方程的可靠衡量。此外，计算包含该比特的所有校验方程提供给该比特的外信息 时，应当排除该比特自身携带的信息，这样更进一步提高外信息计算的精确度。 在迭代过程中，利用上一次迭代过程中获得的新的硬判决序列作为新一次迭代的 输入，硬判决序列的各个硬判决比特的可靠度的更新是在上一次迭代过程中的可 靠度的基础上，加上新一次迭代中计算的新的外信息，这样不断迭代，不断进行 可靠度的更新，不断获取更多的潜在信息，直到所有的校验方程都得到满足或达 到译码的最大迭代次数。 1 4相关符号及其定义 在本章及以后的各章节中，介绍译码算法时，我们均采用以下假设：考虑由 满足行列限制，大小为加r 的稀疏校验矩阵h 的零空间给出的l d p c 码c 。校验 矩阵h 的结构特性定义如下【1 3 】：( 1 ) 每一行含有p 个l ；( 2 ) 每一列含有y 个l ； ( 3 ) 任何两行或两列之间位置相同的1 的个数不超过1 ，该性质称为h 矩阵的行 列限制；( 4 ) 与码长和h 矩阵的行数相比，p 和y 都较小。也就是说矩阵中很少 一部分元素非零，其余大部分元素都是零元素，h 中的1 的密度很小，校验矩阵h 称为低密度奇偶校验矩阵。l d p c 码的名字来源正是因为其校验矩阵是稀疏矩阵。 7 根据低密度奇偶校验矩阵h 的行列性质可知，在h 矩阵中找不到四个角都是1 的 矩形，即稀疏校验矩阵h 的零空间对应的l d p c 码的t a n n e r 图中不会出现长度为 4 的环。 令h 0 , ，一l 表示h 矩阵的行，其中h ，= ( 。o ，忍f ，i ，如，川) 是二元伽罗华域 g f ( 2 ) h 的一个玎维向量。对于0 f 朋和0 j 刀，定义下面两个索引集合【2 3 】： n i = j ：0 j ，l ，h l ，= 1 ( 1 1 ) m ，= f ：0 f ( 1 2 ) 集合，中的元素表示矩阵h 的第f 行h i 中元素“1 ”的位置，即参与第f 个校验方 程的所有比特的集合，集合m ，中的元素表示矩阵h 的第，列中元素“1 的位置， 即参与校验第，比特的所有校验方程的集合。由集合的定义可知，集合，的势为 p ，等于h 的行重，集合m ，的势为y ，等于h 的列重。根据h 矩阵的行列限制， 可以看出，对于0 m ，i 九集合f 和，至多有一个公共元素，即表明h 矩阵任意两行之间位置相同的“l 的个数不超过1 ；对于0 j f ， 刀，j j ，集 合m ，和m ，至多有一个公共元素，即表明h 矩阵任意两列之间位置相同的“1 的个数也不超过1 ，说明任意两个比特同时参与的校验方程至多为1 个。 令，= ( v o ，v l ，i ，一一1 ) 表示c 中的一个码字，假设传输采用b p s k 调制d 2 1 ，这 时码字序列可表示为( 2 v o 一1 ，2 v l - 1 , - - , 2 v 一一l - i ) ，经过二进制高斯信道传输，接收 序列可表示为y = ( y o , y i 一，y 川) ，接收序列y 的序列值是实数值，其中 y ，= ( 2 v j 一1 ) + q ，0 歹 “。7 硬判决序列z 的校正子s = ( 而，s 2 ，s 肘) = z h7 1 ，其中校正子的第f 个分量的 计算可表示为1 3 洲 毛= z = z - f ， ( 1 4 ) ，= o 根据集合。的定义，第f 个校验和量的计算又可表示为 毛= z - ，。h i 。， ( 1 5 ) j e n t 对于0 ， 万，定义校验和的子集， s j = “= z h f ：i m ， ( 1 6 ) 集合q 包含了参与校验第，比特z - ，的所有校验和，i s j i = 厂。除比特乃外，其余比 特至多被s ，中的一个校验和校验，这y 个校验和称为比特z ，的正交校验和【1 3 1 。 8 1 5章节安排 本文的主要研究内容是l d p c 码的混合译码。第一章概述，介绍当前l d p c 码的发展前景，简要介绍了l d p c 码三大类译码的原理，阐述了进行混合译码算 法研究的可操作性及必要性。第二章到第五章的内容是详细介绍混合译码算法的 改进过程以及新算法的提出过程。有关w b f 算法的改进是在第二章进行描述的， 首先进行了传统w b f 算法的介绍与分析，进而提出w b f 算法的改进算法。在进 行了w b f 算法的分析、改进之后，我们尝试利用w m l g 译码算法的并行译码优 势进行设计，第三章首先介绍关于w m l g 算法的最初认识，然后从新的角度推导 w m l g 算法，为后面章节中关于w m l g 算法的改进及新算法的提出提供了一定 的理论依据。第四章是从w m l g 算法的角度进行混合译码算法的初步改进设计， 提出了基于非均匀量化的i m l 算法。w i o 算法的具体实现是在第五章进行描述的， 并从仿真实验的角度验证w i o 算法在译码复杂度、误码性能、收敛速度、错误平 台等方面的优势。第六章是本文的结论部分。 9 2 改进的w b f 译码算法 本章是从混合译码一w b f 译码算法的角度展开，在对传统的w b f 算法以及 i m w b f 算法进行详细分析之后，提出我们的改进算法。 2 1w b f 译码算法 与b f 译码算法相比，w b f 译码算法利用信道信息来处理可靠度的计算，信 道信息的利用率较硬判决译码有很大提高，在译码复杂度上虽有一定的提高，但 译码性能有很大改善，是最常用的混合译码算法之一。 w b f 算法的核心处理是对各个码比特计算它们的外信息e ， e j = ( 2 墨一1 溉 ( 2 1 ) i e m j 其中办= m l 。n j e n i l y ，i ，唬是参与第f 个校验方程的所有硬p j 决比特的幅度最小值。 从物理意义上讲，当谚越大，说明参与s ，的硬判决比特的估计越可靠，得到满足 的概率就越大；反之，当识越小，说明参与s 的硬判决比特的估计越不可靠，岛不 满足的概率越大。这是由于对数似然比l o g p ( y ，iv ，= 1 ) p ( y ，iv ，= o ) 】正比于接收 符号的幅度i y 小接收实数序列y 的各个接收符号y ，的幅度可看作对应的硬判决序 列z 中的硬判决比特z ，的可靠度量。接收幅度陟，i 越大，则y ，对应的硬判决估计越 可靠。因此么可看作校验方程s ；的一种可靠度量。w b f 译码算法的详细操作步骤 如下所示 1 3 , 1 5 2 6 】： 初始化：设置最大迭代次数为j r m 救，迭代次数k = 0 。 1 计算硬判决序列z 的校验和，j = ( 两，s 2 ，s 历) = z h 7 。如果s = 0 ，停止译码， 将当前的硬判决序列作为译码结果输出即可；反之，如果s 0 ，说明在传输过程 中发生错误，接着进行第2 步。 2 根据式( 2 1 ) 计算硬判决序列z 的各个码比特的可靠度e ，进行第3 步。 3 对于0 ， 以，选取对应e ，最大的比特位，记为集合s 。 4 将集合s 中的比特翻转，若存在多个满足厂，最大的比特，需同时翻转这些比特。 k4 - - - k + l ，重复第l 步到第3 步，直到所有的校验方程都得到满足或达到最大迭 代次数k = ，。，。 在w b f 算法中，计算办时，若第j 个接收实数值y ，的幅度是最小的，即i y ，i 最 小，则根据式( 2 1 ) 计算的e ，是不准确的，因为在信息传递的过程中，由校验方 程提供给该码比特的外信息的计算应排除该比特自身所携带的信息。 1 0 在上述的w b f 算法的介绍中，同一个校验方程传递给参与该校验方程的各个 码比特的信息是一样的，都等于参与该校验方程的所有比特的幅度最小值，而j i a n g m i n g 提出的i m w b f 算法【2 5 1 ，同一个校验和传递给不同码比特的可靠度量是不同 的，表示为识，对于幅度最小的码比特来说，计算参与校验该比特的校验方程的 可靠度么，应排除该比特自身携带的信息【2 5 1 。 办，= m i n ，e n i ，i y ，i ( 2 2 ) 在计算硬判决比特z ，的可靠度时，集合s ，中的所有校验方程提供的外信息是不包 含当前比特自身携带的信道信息的。在实际译码中，应当考虑该比特自身的幅度 信息，为此，i m w b f 算法在设计各个硬判决比特的可靠度计算公式时，在校验方 程提供的外信息的基础上，引入关于该比特自身幅度信息的加权项。 定义硬判决比特z ，的可靠度衡量的计算， 目，= ( 2 岛一1 溉。，一s l y _ ，l ( 2 3 ) i e m j 可靠度e j 芦包括两部分：q ，。的第一部分求和公式( 2 s ，一1 ) 以，_ ，是参与校验乃的 所有校验方程传递给z ，的可靠度，该可靠度的计算排除了比特z ，自身的信息，e ，。 的第