（通信与信息系统专业论文）基于动态消息调度的ldpc码及数字喷泉码改进译码算法研究.pdf

西南交通大学硕士研究生学位论文第1 页 摘要 随着无线通信的飞速发展，高速率的数据传输以及多媒体业务的急速增多，在提高 信息传输效率的基础上，如何保证通信过程的可靠性显得尤为重要，这对纠错编码提出 了更高的要求。低密度奇偶校验码( l d p c ) 具有逼近香农极限的纠错性能，且有描述方便、 易理论分析和译码简单的特点，适合硬件实现；数字喷泉码作为一种无固定码率码，可 以根据信道的实时状况，自适应地匹配编码方案。置信传播( b p ) 译码是l d p c 码和数字 喷泉码两种编码的基本译码算法，但传统的b p 译码算法，不能充分利用信息传递过程 中的更新信息。基于置信传播的动态译码算法，为实现每次信息传递提供更多的置信度 提供了一个有效的途径，近来吸引了大量的学者对其进一步的研究。 论文首先简要介绍了l d p c 码和l t 码的基本概念，包括码字的表示、特性以及编 码过程，接着详细介绍了两种码字通用的迭代译码算法，即b p 译码算法的原理和译码 流程。在此基础上，论文分析和讨论了影响b p 译码算法的关键因素，分析了消息调度 对b p 译码算法的影响。接着，论文详细分析了基于残差的置信传播动态的消息调度算 法，并结合t a n n e r 图详尽分析了基于残差的r b p 、n w r b p 和v c r b p 三种动态消息 调度算法的具体调度过程，讨论了每种调度算法的特点，阐释了相关消息调度克服陷阱 集的过程，采用仿真研究的方法，分析并讨论了不同的动态消息调度策略对l d p c 码及 l t 码译码性能的影响。 论文针对l d p c 码和l t 码的相关仿真研究分析表明，动态消息调度对基于置信传 播的迭代译码算法的改进高度依赖于编码构造。一般来说，对于中、短码长的码字，如 果码字的t a n n e r 图中变量节点和校验节点的度数分布相对均匀，且无大量度为1 的节点 以及过多的四环时，采用基于动态消息调度的b p 译码算法可以显著提高译码性能；对 于度分布极度不均匀或四环过多的中、短码长码字，或者度分布为1 的节点过多时，采 用基于动态消息调度对b p 译码算法的改进并不明显。此外，论文的分析结果说明，在 实际系统应用时，应结合编码结构，合理选择相关消息调度机制以充分发挥基于动态消 息调度的改进译码算法所能带来的潜在的性能改进。 关键词：l d p c 码；置信传播：动态调度算法；l t 码；t a n n e r 图 西南交通大学硕士研究生学位论文第l i 页 a b s t r a c t w i t ht h er a p i dd e v e l o p m e n to fw i r e l e s sc o m m u n i c a t i o n , h i g h - s p e e dd a t at r a n s m i s s i o na n d m u l t i m e d i as e v i c e si n c r e a s er a p i d l y t h e r e f o r e ，h o wt oe n s u r et h er e l i a b i l i t yo fc o m m u n i c a t i o n p r o c e s si sp a r t i c u l a r l yi m p o r t a n to nt h eb a s i so fi n f o r m a t i o nt r a n s m i t t e d , a n dn e e dh i g h e r d e m a n do nt h ee r r o r - c o r r e c t i n gc o d e s l 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 a na p p r o a c h t h es h a n n o nl i m i te r r o rc o r r e c t i o np e r f o r m a n c e ，w h i c hi sd e s c r i b e dc o n v e n i e n t l ya n de a s y t h e o r e t i c a l a n a l y s i sa s w e l la s d e c o d i n g m e a n w h i l e ，i ti sq u i t es u i t a b l ef o rh a r d w a r e i m p l e m e n t a t i o n o nt h eo t h e rh a n d , d i g i t a lf o u n t a i nc o d ea sa ne f f i c i e n tr a t e l e s sc o d e s ，i tc a n a d a p t i v em a t c h i n ge n c o d i n gs c h e m e ，a c c o r d i n gt oc h a n n e ls t a t u sf r o mt i m et ot i m e b e l i e f p r o p a g a t i o n ( b p ) a l g o r i t h mi sd e c o d i n gb a s i so ft h e s et w oc o d e s h o w e v e r , c o n v e n t i o n a lb p c a r l tp a s st h el a t e s tu p d a t e dm e s s a g et oa d j a c e n te d g e s t h e nb a s e do nt h ei n f o r m e dd y n a m i c s c h e d u l i n g ( i d s ) f o rb pd e c o d i n g , t h e r ei s m o r ec o n f i d e n c em e s s a g ef o re v e r ym e s s a g e p a s s i n g i nt h i sp a p e r , f i r s tb r i e f l yi n t r o d u c et h eb a s i cc o n c e p t so fl d p cc o d e sa n dl tc o d e s ， i n c l u d i n gr e p r e s e n t a t i o n s ，f e a t u r ea n de n c o d i n gp r o c e s s i n g t h e nd e t a i l e di t e m t i v ed e c o d i n g a l g o r i t h mi sd e s c r i b e d ，t h a ti sp r i n c i p l ea n dp r o c e s so fb pa l g o r i t h m o nt h i sb a s i s ，a n a l y z e t w ok e yf a c t o r sa f f e c t i n gt h eb pd e c o d i n ga l g o r i t h m , a sw e l la si n f o r m e dd y n a m i cs c h e d u l e s ( i d s ) n e x t ，d i s c u s sa n da n a l y z et h es p e c i f i cp r o c e s so fb pd e c o d i n ga l g o r i t h mb a s e do n r e s i d u a lv a l u eo fi d s o nt h i sb a s i s ，c o m b i n e dt ot a n n e rg r a g h , m a i n l yi n t r o d u c et h r e e a l g o r i t h m ，i n c l u d i n g r e s i d u a lb e l i e fp r o p a g a t i o n ( r b p ) a n dn o d e - w i s er e s i d u a lb e l i e f p r o p a g a t i o n ( m y r j 3 p ) ，w h i c hb a s e do nt h ed i f f e r e n c e sb e t w e e nt h ev a l u eo ft h ec h e c kn o d e s t ov a r i a b l en o d e sm e s s a g eb e f o r ea n da f t e ra nu p d a t e ，v a r i a b l en o d e st oc h e c kn o d e sr e s i d u a l b e l i e fp r o p a g a t i o n ( v c r b p ) ，w h i c hb a s e do nt h eh ed i f f e r e n c e sb e t w e e nt h ev a l u eo ft h e v a r i a b l en o d e st oc h e e kn o d e sm e s s a g eb e f o r ea n da f t e ra nu p d a t e m o r e o v e r , d i s c u s st h e c h a r a c t e r i s t i c so fe a c hs c h e d u l i n ga l g o r i t h m , a n de x p o u n dp r o c e s st h a tt h er e l e v a n ti d s s t r a t e g i e so v e r c o m e t r a p p i n gs e t s ”b ys i m u l a t i o ns t u d y ，a n a l y z ea n dc o m p a r et h ed e c o d i n g p e r f o r m a n c e0 1 1d i f f e r e n ti d ss t r a t e g i e sa f f e c t i n go nl d p cc o d e sa n dl tc o d e s s i m u l a t i o ns t u d ya n a l y s i s ，a c c o r d i n gt ol d p ca n dl tc o d e s ，s h o wt h a tt h ep e r f o r m a n c ef o r t h eb p d e c o d i n ga l g o r i t h mo ni d sc a l lb ei m p r o v e d h o w e v e r , i td e p e n do nc o d i n gc o n s t r u c t s g e n e r a l l ys p e a k i n g , i fac o d e w o r di sm e d i u ma n ds h o r t , a n dd e g r e ed i s t r i b u t i o nr e l a t i v e l y u n i f o r mi n t h et a n n e rg r a p h , a n dt h e r ei s1 1 0l a r g en u m b e ro fv a r i a b l en o d e sw i 廿1o n ed e g r e ea s w e l la sg i r t h , t h e nt h eb pd e c o d i n go ni d sc a ns i g n i f i c a n t l yi m p r o v ed e c o d i n gp e r f o r m a n c e 西南交通大学硕士研究生学位论文 第1 ii 页 o t h e r w i s e ，i f ae o d e w o r di sm e d i u ma n ds h o r t , t h ep e r f o r m a n c ei m p r o v e m e n ti sn o ts i g n i f i c a n t s ot h ep a p e r so fa n a l y s i sr e s u l t si n d i c a t et h a t , i np r a c t i c e ，c o m b i n e dw i t ht h ec o d i n gs t r u c t u r e ， b er e a s o n a b l et oc h o o s ei m p r o v e db pd e c o d i n ga l g o r i t h mo ni d ss t r a t e g i e s ，i no r d e rt og i v e f u l lp l a yt ot h er o l eo fl d st h a tc a nb r i n gp o t e n t i a lp e r f o r m a n c ei m p r o v e m e n t s 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 e kc o d e s ；l u b yt r a n s f o r mc o d e s ，b e l i e fp r o p a g a t i o n a l g o r i t h m ；i n f o r m e dd y n a m i cs c h e d u l i n g ；l u b y t r a n s f o r mc o d e s ；t a n n e rg r a p h 西南交通大学硕士研究生学位论文第1 页 第1 章绪论 随着科技的不断进步和生活水平的大幅提高，人们对于通信的需求量以及通信质量 的要求日益增长。下一代移动通信系统( s y s t e mb e y o n di m t 2 0 0 0 ) 要支持低速用户 1 0 0 m b i t s ，高速用户1 g b i t s 1 1 。除了采用m i m o 和o f d m 等高效无线传输技术有效利 用移动通信系统有限的频谱资源之外，如何保证高速数据传输系统的传输可靠性能也同 样面临严峻的挑战。通信的目的在于把信息及时、可靠并有效地传递到信宿。但是在通 信过程中，信息传递的可靠性和有效性通常是相互矛盾的。信息的可靠传输往往面临噪 声、干扰和信道衰落等多重因素的影响。因此，通信系统设计的一个核心问题就是如何 在有噪声干扰的情况下，采用有效的信道编译码技术支撑稳定可靠的信息传递。 信道编码的目的是提高通信系统传输的可靠性，克服通信过程中各种噪声和不确定 的干扰。纠错编码作为信道编码，发展至今已有5 0 多年的历史，主要经历了以下四个发 展阶段。 第一阶段，1 9 5 0 年，汉b j ( h a m m i n g ) 提出了汉明码【8 】。在随后的十多年时间里，学 者提出了多种有效的编解码的方法，其中广为人知的就是b c h 码和r s 码。不过较为遗 憾的是r o b e r tg a l l a g e r 在其博士论文中所提出的低密度奇偶校验码，即l d p c 码 ( l o w d e n s i t yp a r i t y - c h e e kc o d e s ) 在当时由于受实现条件等限制，并没有引起足够的重视 【】4 】，直到3 0 年后才重新被世人发现是一类性能极其优异的纠错编译码方案。 第二阶段，进入2 0 世纪7 0 年代，纠错编码经历了一个飞速发展的时期，主要表现 在：采用软判决译码算法解决了卷积码的译码难题【9 】；提出了一大类不展宽频带的编码 调制方法；第一次提出了级联编码的思想。 第三阶段，到了2 0 世纪8 0 年代，人们开始从代数角度来分析纠错编码，利用代数 的曲线特性构造出一类代数几何码，使得先前赋予码字的很多重要参数具有了全新的几 何意义，如码重、汉明距离掣1 0 ，1 1 1 。本文中所采用的迭代译码思想也在这个时期出现， 目前应用非常广泛。 第四阶段，自从2 0 世纪9 0 年代发展至今，纠错编码的发展进入了一个空前繁荣的 阶段。首先是编码理论的研究热点发生重大变革，由代数转向稀疏几何编码。喷泉码就 是在这个阶段由m l u b y 提出。其次，t u r b o 码编译码方案的提出【1 2 】是一个重大突破， 将两个并行级联的卷积码作为一个t u r b o 码，利用软判决迭代译码表现出非常好的性能， 距离香农极限仅0 7 d b 。再次，l d p c 码又重新得到学者的重视【1 3 】，研究表明其性能也 可有效接近香农极限。实质上这两种码皆可与图论结合起来，译码都采用迭代译码的基 本思想。 西南交通大学硕士研究生学位论文第2 页 1 1l d p c 码和数字喷泉码的发展历程与现状 l d p c 码是一种线性分组码，该编码在有噪的高速数据传输信道以及存储信道下， 其性能接近香农极限。l d p c 码最早是在1 9 6 0 年，由r o b e r tg a l l a g e r 毛e 其博士论文中提出 【1 4 】。不过在接下去的3 5 年时间里，一直未得到世人的充分重视。值得一提的是，t a n n e r 在1 9 8 1 年的一项研究中，构造了l d p c 码，并且与图论结合起来研究l d p c 码，也就是现 在俗称的t 锄e r 图( 也作二分图) 1 5 】。直到2 0 世纪9 0 年代中期，l d p c 码随着m a c k a y 、l u b y 和其他一些学者的关注 1 6 , 1 7 , 1 8 】，被“再次发现”。研究结果表明，l d p c 码的低密度校验特 性为其带来了良好的编码特性，l d p c 编译码领域所取得的研究进展也是近年来信息和 编码领域中的最为重要的标志型成果之一。 对于非规则l d p c 码，特别是经过良好设计并具有优异的参数分布特性的l d p c 码， 采用基于置信传播( b p 。b e l i e fp r o p a g a t i o n ) 的迭代译码机制，其性能甚至超过了t u r b o 码 冽。已有理论研究结果表明，在二进制高斯噪声信道( b i - a w g n ，b i n a r yi n p u ta d d i t i v e w h i t eg a u s s i a nn o i s e ) 下，一个码率为1 2 、码长达到1o7 的非规则l d p c 码距离香农限仅 0 0 0 4 5 d b ，误码率达到lo - o ，这也是迄今为止所发现的最接近香农理论限的可实现纠错 编译码方案【1 9 1 。虽然l d p c 码晚于t u r b o 码出现，错过了3 g 无线移动通信标准制订的时间， 但因其在技术上的优势，更适合未来宽带无线通信系统高速数据传输对高可靠信道编译 码的要求，已被包括i e e e8 0 2 1 6 e 标准【2 l 】等多种通信系统所采纳，而且l d p c 编译码方案 极有可能为4 g 通信标准所采用。 围绕l d p c 编译码技术的相关研究工作一直是信道编码领域的研究热点，研究成果 颇多。在大量的l d p c 编译码算法的研究工作中，有关于l d p c 码的改进译码算法的研 究工作近年来引起了编码界广泛的关注。针对l d p c 码编码构造与性能分析的相关研究 结果表明，影响l d p c 码性能的关键因素是u ) p c 码t a n n e r 图中环的存在以及各节点的 度分布【4 5 斯】。具体来说，长码受码构造所存在的环的影响较小，而受到度分布的好坏的 影响很大，但是在中长码时，度分布和环的影响同时影响着编码性能。通常情况下，为 了提高和改善l d p c 码性能，会从编码构造方向入手，在编码过程中，精细选择好的度 分布，并消除校验矩阵中的四环。但是，如果对于编码结构已经固定，或者在一些将实 际的通信问题等效转换为l d p c 编码处理的场景，例如自适应网络协作编码a n c c ( 。 a d a p t i v en e t w o r kc o d e dc o o p e r a t i o n ) 6 ，由于编码约束已经确定，为了改善l d p c 码性 能，可以考虑从译码算法入手，寻求提高和改善译码性能的有效方法。 在l d p c 译码过程中，当译码失败时，该错误变量节点在t a n n e r 图中要么是孤立的， 要么是落在某些短环中。显然，如何克服短环以及度分布对b p 迭代译码算法的影响是 改进l d p c 译码性能的关键所在。在实际的b p 迭代译码过程中，对于那些难于收敛的 变量节点，往往需要足够多的外信息时才能正确译码，对于容易收敛的变量节点，则只 西南交通大学硕士研究生学位论文第3 页 需要提供少量的外信息即可正确译码。标准的b p 译码算法的一次迭代过程中，变量节 点和校验节点是交替更新各自的置信消息，并将收集到的最新信息传递给其相邻的校验 或变量节点。但传统的b p 译码算法中这种消息的更新顺序是不加任何选择和甄别，即 标准b p 译码算法采用的是一种洪泛( f l o o d i n g ) 的消息更新策略。而近年来的研究结果表 明，合理调度节点的消息更新的顺序，可以使得难收敛的变量节点能够优先接收到相关 外信息，从而加快整个译码过程收敛速度，进而达到促进迭代译码收敛，提升译码性能 的效果一蜘。 根据b p 迭代译码过程中节点的不同调度顺序，大致可以将b p 译码算法中的消息调度 分为洪泛调度( 巨p f l o o d i n g ) 策略、串行调度策略以及动态调度策略 4 0 l ，其中前者是标准 l d p c 译码所默认的消息更新与调度策略。目前常用的串行消息调度策略为非动态标准 串行调度策略s s s ( s t a n d a r ds e q u e n t i a ls c h e d u l i n g ) ，而常用的动态消息调度策略为基于残 差的信任传播策略r b p ( r e s i d u a lb e l i e fp r o p a g a t i o n ) t 郾1 1 。本文的主要研究内容正是在分 析和比较现有的各类消息调度策略的基础上，重点分析不同的消息调度策略对l d p c 译 码性能的影响，并在此基础上，研究具有更好收敛特性和译码性能的改进l d p c 译码算 法。 另一方面，在很多通信系统中，信道的某些特性发送端事先并不完全掌握，而且数 据在传输过程中，信道可能随时都在发生变化，比如删除信道的删除概率、高斯信道的 噪声方差，衰落信道的衰落系数等等。自适应编码是适应动态信道的一种有效的编码手 段，但自适应编码需要了解信道的实时状况，以便找到能有效匹配实时信道的编码方案。 喷泉码编译码算法简单，更重要的是，喷泉码可以在发送端不知道信道状态信息的条件 下，根据信道条件自适应地调整编码码率，这种独有的码率无关性使得喷泉码较之其他 码率固定的编码，更适合用做协作通信的编码方案。实际的喷泉码编码构造包括l u b y t r a n s f o r m ( ( l t ) 碉j t 2 2 1 ，2 0 0 6 年，在l t 码的基础上，由s h o k r o l l a h i 提出了性能更优的r a p t e r 码1 2 3 1 。喷泉码除了可以应用于删除信道之外，最新的研究结果表明，在a w g n 信道和 衰落信道条件下，喷泉码也表现出了良好的性制冽 2 5 】。从提出喷泉码的思想到发展至今， 数字喷泉码的研究热点主要包括如何优化度分布【2 6 1 、优化喷泉码的编译码技术，在保障 喷泉码性能的同时，简化喷泉码的编码构造。一般而言，在无线通信环境下应用数字喷 泉码接收端采用需要采用类似l d p c 码的b p 译码算法，采用基于t a n n e r 码图的迭代译 码算法，而由于喷泉码的编码构造不同于l d p c 码，在编码构造时系统是按照特定的度 分布在确定系统编码矩阵，这使得喷泉码在采用b p 迭代译码算法往往面临短圈等不利 因素。如何借鉴l d p c 码迭代译码中的动态消息调度，克服喷泉码编码构造对软判决迭 代译码的不利影响，这是论文研究的第二个背景和动机。 西南交通大学硕士研究生学位论文第4 页 1 2 论文研究目的和研究内容 随着近年来l d p c 码研究的不断发展与进步，相对于t u r b o 码，l d p c 码具有诸如 可以采用结构化的构造、描述方法简单，支持并行迭代译码，实现复杂度低，性能好等 优势，将是未来的宽带无线通信系统中信道编码的重要选择；喷泉码的无码率特性，编 译码复杂度低，不需要反馈，适合应用到诸多通信环境；针对目前l d p c 码及喷泉码编 译码仍然存在的问题，特别是在给定编码构造的条件下，如何进步改进基于b p 算法的 译码性能，相关研究成果无论是在理论上，还是考虑其在未来的实际通信系统中的应用 都是非常重要和极有意义的。 1 )论文围绕基于置信传播的b p 译码算法展开相关研究工作，论文在概述l d p c 编码理论的基础上，重点围绕译码算法分析设计以及结合仿真结果的性能分析等。论文 的主要内容包括：论文简要介绍了l d p c 码和l t 码的基本概念，包括码字的表示、特 性以及编码过程，接着详细介绍了两种码字通用的迭代译码算法，即b p 译码算法的原 理和译码流程，分析和讨论了影响b p 译码算法的关键因素。 2 )论文详细分析了非动态的异步调度算法过程，以此为契机，引出动态的消息调 度译码算法。围绕着动态的消息调度算法，先介绍了动态消息调度算法的机理基于 残差的置信传播；然后结合t a n n e r 图，从现象到本质的分析了动态消息调度算法的具体 调度过程；再根据残差计算方法的不同以及调度过程中的顺序不同，重点介绍了三种调 度算法r e s i d u a lb e l i e fp r o p a g a t i o n ( r b p ) 、n o d e - w i s e r b p f n w r b p ) 和v a r i a b l et oc h e e k r b p ( v c - r b p ) 的调度过程，并结合t a n n e r 图，讨论了每种调度算法的特点，以及分析 各调度算法克服陷阱集的过程；最后，对以上几种不同的译码算法，基于l d p c 码，在 a w g n 信道中进行性能仿真，通过对比不同的仿真性能曲线，验证了基于动态消息调度 策略的迭代译码性能优于基于非动态消息调度策略的迭代译码性能，收敛速度更快；此 外，论文通过仿真研究，分析和比较了不同的动态消息调度策略对l d p c 译码性能的影 响。 3 )论文结合l t 码的t a n n e r 图，动态消息调度算法同样适用于l t 码的软判决译 码；最后，通过对比不同算法的译码仿真结果图，验证了基于动态消息调度策略的译码 算法可以在一定范围内有效提升l t 码的软判决译码性能。但论文的分析也发现，基于 动态消息调度策略的改进译码算法应用与l t 码时存在着门限效应，即当信道条件超过 某个信噪比门限值时，改进迭代译码算法难以迸一步改善l t 码的译码性能。 4 )论文结合相关仿真验证，分析了基于动态的消息调度机制改善l d p c 码以及l t 码译码性能的根本原因。研究表明，采用动态的消息调度策略可以在一定程度上克服“陷 阱集”的问题。针对不同的调度算法，论文结合t a n n e r 图，分析了各类动态消息调度算 法克服“陷阱集”的具体过程。论文的分析表明，由于l t 码编码构造与l d p c 编码的不 同，基于动态消息调度的b p 译码算法并不能完全解决由于l t 码编码构造所带来的大量 西南交通大学硕士研究生学位论文第5 页 的四线循环和度为1 的节点给译码性能所带来的影响，单纯的通过动态消息调度对译码 性能的提升并不显著。 论文的分析表明：基于动态消息调度的b p 译码算法并不适合任何编码构造。一般 来说，对于中、短码长的码字，如果码字的t a n n e r 图中变量节点和校验节点的度数分布 相对均匀，且无大量度为l 的节点以及过多的四环时，采用基于动态消息调度的b p 译 码算法可以显著提高译码性能；对于长码长的码字以及度分布极度不均匀或四环过多的 中、短码长码字，或者度分布为l 的节点过多时，采用基于动态消息调度对b p 译码算 法的改进并不明显。另一方面，动态消息调度将各个节点的并行洪泛消息传递改为串行， 或部分串行的传递过程将增加译码计算时延。为了充分发挥基于动态消息调度的改进译 码算法所能带来的潜在的性能改进，在实际系统应用时，应结合编码结构、合理选择相 关消息调度机制。 1 3 论文结构安排 本文的研究内容主要是基于二进制l d p c 码以及l t 码的置信传播动态消息调度的 算法问题。整篇文章将从基础的编译码算法介绍入手，由浅入深，具体结构安排如下： 第一章，绪论，简单介绍数字通信系统的基本概念，l d p c 码以及喷泉码的发展历 程与现状，本文的研究动机、研究方法和所期望达到的目的。 第二章，简要介绍线性分组码的概念，l d p c 码及喷泉码的编码译码原理，重点介 绍基于b p 的迭代译码算法，并分析影响b p 译码性能的两个关键因素。 第三章，从介绍非动态的异步消息更新算法( s s s ) ，到动态调度消息更新算法( r b p ) ， 详细分析了动态调度消息更新算法的原理，重点介绍三种动态调度算法的更新过程，最 后对l d p c 码基于动态调度消息译码算法性能进行仿真，并对比标准b p 译码以及s s s 更新算法，详细分析和比较三种动态调度算法的特点。 第四章，介绍l t 码可以采用b p 译码的背景，同时结合l d p c 码中b p 算法所采用 的动态消息调度算法，采用合理的过渡机制，将动态的消息调度算法应用于l t 码中。 通过l t 码在各种译码算法下的性能仿真曲线，分析和对比l t 码的译码性能，根据第三 章和第四章的仿真结果，分析各动态调度算法的特点，并总结出动态消息调度算法适用 的范围。 论文最后对全文工作进行总结，并对动态消息调度的可行的研究方向进行了展望。 西南交通大学硕士研究生学位论文第6 页 第2 章l d p c 码和l t 码 分组码表示信道在编码过程中，对长度为k 的信息序列之后，按一定规则加上长度 为刀一k 的校验序列，共同组成一个码长为n 的码字。如果这n k 个校验序列的生产 仅与该组的k 个信息位相关，与其他组的信息不相关，并且在译码过程中，仅限于利用 本组的码元序列，具有这种性质的码称为分组码，通常用( n ，k ) 表示该分组码的集合。 本文所研究的两种码均为线性分组码，是分组码中非常重要的一类码，是讨论各种码的 基础【2 7 1 。码长为n 的分组码c 里有曰七个码字，当且仅当q 庀个码字构成g f ( c 7 r ) 上所有 n 维向量组成的向量空间f 的k 维子空间时，该分组码 ，z ，尼】，称为线性分组码，其中 叮1 c f ，k 称为分组码c 的维数。如果不作特别说明，本文中所分析的线性分组码皆 叮 为二元线性分组码对于( 刀，k ) 线性分组码，h 为其校验矩阵，g 为生成矩阵， c = ( c 1 ，c 2 ，q ) 是码字空间的一个码字，u = ( u 1 ，u 2 ，u k ) ，则有以下关系： h c 。= 0 砬扭。= 0 - c = u g g h r = 0 或册r = 0 2 1l d p c 码概述 ( 2 1 ) ( 2 - 2 ) ( 2 3 ) l d p c 码的编译码过程基于二分图，接下来首先介绍l d p c 码的表示方法，然后介 绍l d p c 码的描述和分类以及构造等基本概念。 2 1 1l d p c 码的表示 矩阵表不 尽管l d p c 码的码字符号集可以是非二进制元素集，为了简单方便，仅考虑二进制 l d p c 码。由于l d p c 码是线性编码，在g f ( 2 ) 上，码字c 是一种( ，z ，k ) 分组码，其中 码长为，z ，信息序列长度为k 。这样，我们可以把信息序列b = g l ，9 2 ，g k - 1 通过 c = u g 映射( 其中u = u 1 ，u 2 ，u 七- 1 ) ，而称g 为一个n k 维的生成矩阵，它的 行就是信息序列 g ， 。码字c 的生成矩阵g 中的( 咒一七) 维的列向量对于所有信息序 列x e 都有x g l = 0 ，其中，生成矩阵g 的列向量b 上= h o ，吃一纠) 。所 以，对于任意c c ，对于所有f 都有c 矿= 0 。在c 日上= 0 中，h 是一个( ，z 一后) n 维的校验矩阵，它的行是向量 红 ，而且与其生成矩阵垂直。之所以称校验矩阵h 为 奇偶校验矩阵式因为它的行m = n k 在接收码字时可以区分奇偶校验。 低密度奇偶校验编码是一种线性编码，并且其校验矩阵h 中1 的密度很低。对于规 西南交通大学硕士研究生学位论文第7 页 则l d p c 码，要求校验矩阵h 的每列重彬，每行重为w ，而且w r = 彬( 刀耽) 。通 1 ， 常情况，每列的列重m k s 将理想孤子函数p ( i ) 与鲁棒孤子分布f ( f ) 相加并且进行归一化，得到表达式如下： = ( 户( f ) + 攻f ) ) ( 2 1 9 ) f ( 垆继学业，江1 ，2 ，k ( 2 - 2 0 ) p 这就是鲁棒孤子分布函数。为了在迭代译码过程中，满足每次迭代时，都有 s - c l o g 。( 七回j j 个度为1 的编码符号出现，再引入两个常数参量c 和万， c 一般取 小于l 的正数。若要求在接收端至少以1 一万的概率译码成功，则必须要求接收到的编码 。 西南交通大学硕士研究生学位论文第1 3 页 符号数满足关系式刀= 七。该分布的优点是：接收端可以采用最小的编码符号数量来恢 复所有原始编码符号。 实际中，虽然鲁棒孤子分布函数应用起来稳定性高于理想孤子分布，但是实现起来 复杂度太高，尤其是对于a w g n 信道，因此一般采用一些简化的分布来替代，如文献f 3 2 】 采用了如下的弱化的鲁棒孤子分布，见式( 2 2 1 ) 。 q ( x ) = 0 0 0 8 x + 0 4 9 3 x 2 + o 16 6 x 3 + o 0 7 3 x 4 + o 0 8 3 x 5 + o 0 5 6 x 8 + o 0 3 7 x 9 + o 0 5 6 x 1 9 + o 0 2 5 x 6 5 + o 0 0 3 x 6 6 ( 2 2 1 ) 2 3l l rb p 算法的消息更新策略 l d p c 码和l t 码在b i a w g n 上和b e c 信道中都可采用软判决的迭代译码算法， 二者的区别在于喷泉码基于伪校验矩阵，l d p c 码的校验矩阵是物理意义上实际存在的， 有关l t 码的软判决译码的具体实施过程中第四章会详细介绍。下面具体介绍u rb p 算法的更新过程【r 7 1 。 l l rb p 算法是和积译码算法( s p a ) 的似然比表示形式。基于t a n n e r 图，b p 译码算 法一次完整的迭代过程为：首先t a n n e r 图中所有校验节点收集从其相邻的变量节点信 息，处理结束后，再利用已更新的所有校验节点的信息更新所有变量节点信息，最后每 个变量节点利用收集到的信息进行判决。如此反复，直至译码成功或者到达最大迭代次 数。 先介绍相关符号。 m ：表示通过信道传输后接收到的码元； 1 ，：表示与校验节点，相连的所有变量节点的集合： ，f ：表示除f 外与与校验节点，相连的变量节点的集合；， q ：表示与变量节点f 相连的校验节点的集合； q ：表示除，外与变量节点i 相连的校验节点集合； m ，( 一f ) ：表示来自与校验节点相关的除变量节点k 外所有变量节点的信息； 心( 一_ ，) ：表示来自与变量节点相关的除校验节点c ，外所有校验节点的信息； 霉= v r ( v , = 1 i 以) ； s ：表示与变量节点相连的校验节点q 的校验方程成立的事件； q a ( b ) = p r ( v = 6i 墨，乃，犯( 朋，这里6 o ，1 ) ，表示除第，个校验节点外其他 校验节点提供信息条件下第f 个信息比特m = b 的概率； r j , ( b ) = p r ( 校验方程c ，成立i k = 6 ，m ，( 一f ) ，这里6 o ，1 ) ，表示第i 个信息比特 m = b 的条件下，第，个校验方程满足的概率。 下面结合图2 - 4 ，解释说明q a ( o ) 的具体计算方法。根据定义， 西南交通大学硕士研究生学位论文第14 页 q f j ( o ) 2p r ( v f2 0i 儿，墨，m 。( ，) ) = ( 1 一只) p r ( sc f = 0 ，咒，蜂( ，) ) p r ( s ，) ( 2 - 2 2 ) = ( 1 一鼻) 兀“o ) j e q v ( 2 - 2 2 ) 式中第二个等式使用了两次贝叶斯准则，由q u ( 0 ) = p r ( v t = 0y t ，s ，m 。( 一朋推 导得出q o ( 0 ) = ( 1 一只) p “sv = o ，y t ，哆( 朋p r ( s ，) ，( 2 2 2 ) 式中第三个等式利用了相互 独立条件，由幻( o ) = p “v = oy , ，墨，m 。( 一) ) 推导出劬( o ) = 巧( 1 一鼻) 1 - if j i ( o ) 的形式。 ，ec ， 同理可得 q g j ( 1 ) = 鼻n “1 ) ( 2 - 2 3 ) j e c ，j 归一化常数的选择是为了保证勤( o ) + ( 1 ) = 1 。 图2 - 4 信息传递半迭代用于计算( 6 ) 的说明图 为了推导( 6 ) 的表达式，需要利用以下引理。 引理1 ：对于二进制序y l ja = ( a l , - - ，a 村) ，其中p r ( a ，= 1 ) = p i ，那么序列口中包含偶 数个1 的概率是： 1 m 去+ 9 r i ( 1 2 b ) ( 2 - 2 4 ) lli = 1 再根据关系b = q ，g ( 1 ) 和图2 _ 4 ，可见 r j i ( 0 ) = i 1 + i 1h ( 1 - 2 q r j ( 1 ) ) ( 2 2 5 ) 二 厶f ! u 这是因为如果此处k = 0 ，那么信息比特集 u ：f n 中必须包含偶数个1 才能保 证该校验方程的和为0 的条件满足。同理可得 r ，t ( 1 ) = 1 一r j , ( o ) ( 2 - 2 6 ) 西南交通大学硕士研究生学位论文第15 页 q u 0 ) 图2 - 5 信息传递半迭代用于计算，= ：f ( 6 ) 的说明图 本文所有迭代译码算法的仿真环境都是在b i a w g n 信道环境下，接着看该算法的 初始化设置。 首先我们令x t = l - 2 v i 为第i 次传输的二进制值。当v = o n ，五= 1 ， h = l 时，薯= 一1 。后面用x i 代替v j 。第i 个接收样本表示为只= 薯+ n i ，其中，n i 相互独 立，而且为正态分布( o ，o - 2 ) 。这样，我们很容易可以得出 p r ( x ；= x i 咒) = 1 + e x p ( - 2 y x 扩) 1 ( 2 - 2 7 ) 其中工 1 ) 根据前面的计算过程，乘法计算过多，为了降低译码的复杂度，以及增强结果的稳 定性，采用对数域的迭代译码算法( l l rb p ) ，具体过程如下： 首先定义下面的对数似然比l l r s ： 地。g c 等帮j 陋2 8 ， 地) - l 。g 器 ( 2 - 2 9 ) h 。g ( 等 陋3 。， 三c q i ) = l o g ( 器j 亿3 ， 在b i a w g n 信道下初始化为： l ( q f j ) = 三( v ) = 2 y t 仃2 ( 2 - 3 2 ) 经过变化后，最终可以得到校验节点的更新信息表示： t a i l l l ( i 1 三( 像) ) = nt a n h ( + l ( q 吖) ) ( 2 - 3 3 ) 西南交通大学硕士研究生学位论文第1 6 页 变量节点的更新信息表示： ( 劬) = ( h ) + l ( r j ，) ( 2 3 4 ) 变量节点收集到的所有u r 的总和表示： 三( q ) = 三( m ) + 三( 珞) ( 2 - 3 5 ) l l rb p 算法的主要步骤如下： 1 ) 初始化：利用信道接收到的信息初始化变量节点似然比信息l ( 只) ，这样，设定 变量节点传向校验节点的初始化信息为： l ( q o ) = 三( b ) = 2 乃矿 ( 2 - 3 6 ) 2 1 迭代处理过程： 校验节点消息处理，如图2 4 。图中箭头的方向表示了信息传递的方向，该 图展示了信息l ( h ) 从校验节点c ，传向变量节点u 的过程。传递到信息节点 m 的信息，是校验节点c ，已经除去u 以后的其它相邻变量节点处获得的所有 外信息。该过程利用的是下式： t a i