（信号与信息处理专业论文）喷泉码的优化设计.pdf

_ 。一e k ；r n牲一。t#b、二二、 j q硌p 靴 j ； ，奄，j舡、。，i。江0。 41、rj，、 独创性( 或创新性) 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文中不 包含其他人已经发表或撰写过的研究成果，也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名： ! 煞盈堑 日期： 幽! ! ：互! 之 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定，即： 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学。学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘，允许学位论文被查阅和借 阅；学校可以公布学位论文的全部或部分内容，可以允许采用影印、缩印或其它 复制手段保存、汇编学位论文。( 保密的学位论文在解密后遵守此规定) 保密论文注释：本学位论文属于保密在一年解密后适用本授权书。非保密论 文注释：本学位 本人签名： 导师签名： 适用本授权书。 日期： 圳l0 - ；、j1 一_ j ，iit，。，目f0u ：童鼍 北京邮电大学硕士学位论文 喷泉码的优化设计 喷泉码的优化设计 摘要 随着移动通信技术和因特网的迅猛发展，多媒体广播和组播技术 得到了广泛的应用。近年来，喷泉码技术凭借其本身的技术优势被 3 g p p 选为第三代移动通信多媒体广播组播服务( m b m s ) 的组成部 分，并在越来越多的通信领域得到应用和推广。本论文以喷泉码为研 究对象，在喷泉码的度分布、中继系统中的喷泉码、不等差错保护方 案等方面的优化设计进行了研究，为喷泉码的研究和应用做出了一定 的贡献。 论文论述了喷泉码技术的优势特点、发展历程，研究现状及应用 前景，分析了存在的问题；阐述了t o r n a d o 码、l t 码、r a p t o r 码、 3 g p pm b m s 中的喷泉码的基本原理、编译码算法，并指出各自的优 缺点。 由于喷泉码的度分布是影响其编译码性能的关键因素，论文从置 信传播译码算法的角度出发，分析了度分布结构对可译集合大小的影 响，建立了设计喷泉码度分布的模型，以平均误码率最小为目标，采 用差分进化的方式提出了一种喷泉码度分布的优化设计方法。仿真结 果表明，与现有的喷泉码度分布相比，采用设计的度分布构造的喷泉 码具有更低的平均误码率。 论文研究了在协作通信系统中，中继节点对喷泉码度分布的影 响，推导了协作中继系统中的喷泉码的度分布与端到端通信系统中的 度分布的关系，在现有的性能优良的度分布基础上提出了一种适用于 协作通信系统中的喷泉码度分布的设计方法。仿真结果表明，在中继 系统中，与现有的喷泉码相比，我们设计的喷泉码有更好的译码性能。 而在组播系统中，为了提高所有用户的译码性能，可以根据中继情况 选择优化参数。 针对不等差错保护编码方案的具体应用，论文研究了u e p 喷泉 码的实现方法，在此基础上，提出了一种u e p 喷泉码的优化设计方 法；该方法根据译码过程中各部分数据的误码率，通过调整输入符号 的发送概率以提高u e p 喷泉码的整体译码性能。仿真结果表明与传 喷泉码的优化设计 优化设计的u e p 喷泉码具有更好的整体 继不等差错保护 北京邮电大学硕上学位论文 o p t i m i z e dd e s i g no ff o u n t a i nc o d e s 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 ft h ei n t e m e ta n dt h et e c h n o l o g yo f m o b i l ec o m m u n i c a t i o nt e c h n o l o g y , t h et e c h n o l o g yo fb r o a d c a s t i n ga n d m u l t i c a s t i n gt e c h n i q u e si su s e dw i d e l y r e c e n t l y , f o u n t a i nc o d e sa r e a d o p t e db y3 g p pm b m sw i t hi t so w nt e c h n i c a la d v a n t a g e s ，a n da r e a p p l i e da n dp r o m o t e di nm o r ea n dm o r ec o m m u n i c a t i o n sf i e l d f o c u s i n g o nt h ed e s i g n i n gm e t h o do ff o u n t a i nc o d e s ，w em a i n l yr e s e a r c ht h e d e g r e ed i s t r i b u t i o no ff o u n t a i nc o d e s ，t h ef o u n t a i nc o d e sb a s e do n c o l l a b o r a t i v er e l a ys y s t e m sa n dt h eu n e q u a le r r o rp r o t e c t i o nf o u n t a i n c o d e s ，a n dm a k eac e r t a i nc o n t r i b u t i o nt ot h er e s e a r c ha n da p p l i c a t i o no f f o u n t a i nc o d e s f i r s t l y , w ee x p o u n dt h ea d v a n t a g e s ，t h ed e v e l o p m e n t ，t h er e s e a r c h s i t u a t i o na n dt h ea p p l i c a t i o n so ff o u n t a i nc o d e ，a n dp o i n to u tt h ee x i s t e d p r o b l e m s t h e nw es t u d yt h ee n c o d i n ga n dd e c o d i n ga l g o r i t h m sa n d f u n d a m e n t a lt h e o r yo ft o r n a d oc o d e , l t c o d e ，r a p t o rc o d ea n d f o u n t a i n c o d ei n3 g p pm b m s a n dw ea n a l y z et h em e r i t sa n dd r a w b a c k so ft h e s e c o d e s s e c o n d l y , a st h ed e g r e ed i s t r i b u t i o np l a y sak e y r o l ei nd e t e r m i n i n g t h ee n c o d i n ga n dd e c o d i n gp e r f o r m a n c eo ff o u n t a i nc o d e s ，w eb u i l dt h e r e l a t i o n s h i pb e t w e e nd e g r e ed i s t r i b u t i o na n db i te r r o rr a t e ( b e r ) f r o mt h e p e r s p e c t i v eo ft h eb e l i e fp r o p a g a t i o nd e c o d i n ga l g o r i t h m ，a n dt h e n p r o p o s e dad e s i g n i n gm e t h o do fd e g r e ed i s t r i b u t i o nb yd i f f e r e n t i a l e v o l u t i o n s i m u l a t i o na n dt h e o r e t i c a l r e s u l t ss h o wt h a tf o u n t a i nc o d e s g e n e r a t e db yt h ep r o p o s e dd i s t r i b u t i o nh a v eal o w e ra v e r a g eb e rt h a n t h o s eg e n e r a t e db yt h et r a d i t i o n a ld e g r e ed i s t r i b u t i o n t h i r d l y , w ea n a l y z et h ea f f e c t i o no fr e l a yn o d et ot h ed e g r e e d i s t r i b u t i o n i nc o l l a b o r a t i v e r e l a ys y s t e m s ，a n dp r e s e n t ad e s i g n i n g m e t h o do fd e g r e ed i s t r i b u t i o nb a s e do nt h ee x i s t e dd e g r e ed i s t r i b u t i o n w i t hg o o dp e r f o r m a n c e s i m u l a t i o nr e s u l t ss h o wt h a tt h ed e s i g n e d f o u n t a i nc o d e sh a v eag o o dd e c o d i n gp e r f o r m a n c ei nr e l a ys y s t e m s ， c o m p a r e dt ot h ef o u n t a i nc o d e si n3 g p p i nt h em u l t i c a s ts y s t e m i no r d e r 北京邮电大学硕士学位论文 喷泉码的优化设计 t oi m p r o v et h ed e c o d i n gp e r f o r m a n c ef o ra l lu s e r s ，w ec a nc h o o s et h e o p t i m i z a t i o np a r a m e t e r sa c c o r d i n gt ot h ec i r c u m s t a n c e so fr e l a ys y s t e m f i n a l l y ，a i m i n ga tt h ea p p l i c a t i o no fu n e q u a le r r o rp r o t e c t i o n ( u e p ) c o d e s ，w es t u d yt h eo p t i m i z a t i o nd e s i g nm e t h o do fu e pf o u n t a i nc o d e s 。朊i n v e s t i g a t e t h eu e pf o u n t a i nc o d e sr e a l i z e d b ye n c o d i n gt h e i m p o r t a n td a t am o r ef r e q u e n t l ya n dt h e np r e s e n tad e s i g n i n gm e t h o dt o o p t i m i z et h ep r o p e r t yo fu e pf o u n t a i nc o d eb ya d j u s t i n gt h es e n d i n g p r o b a b i l i t yo fi n p u ts y m b o l sa c c o r d i n gt ot h e i ri m p o r t a n c e s i m u l a t i o n r e s u l t ss h o wt h ep r o p o s e df o u n t a i nc o d e sh a v eab e t t e r d e c o d i n g p e r f o r m a n c et h a nt h eu e p f o u n t a i nc o d e sw i t h o u to p t i m i z e d k e yw o r d s ：f o u n t a i nc o d e s ，d e g r e ed i s t r i b u t i o n , r e l a y , u e p 北京邮电 第一章 1 1 1 2 1 3 1 3 1 分布式数据存储6 1 3 2 多播和广播传输。7 1 3 3 无线协作传输7 1 3 4 深空通信7 1 4 论文的主要贡献和章节安排8 第二章喷泉码技术。1 0 2 1 删除信道模型l o 2 2t o r n a d o 码1l 2 3l t 码：1 2 2 3 1l t 码的编译码算法1 2 2 3 2l t 码的设计规则1 4 2 4r a p t o r 码15 2 53 g p pm b m s 标准。l6 2 5 13 g p pm b m s 的编码算法1 6 2 5 23 g p p b m s 的译码算法l7 2 6 本章小结1 8 第三章喷泉码度分布的优化设计2 0 3 1 引言2 0 3 2 可译集合2 l 3 3 设计方法2 2 3 3 1 可译集合大小与度分布的关系。2 2 3 3 2 优化问题2 4 3 4 仿真结果2 5 3 5 本章小结2 7 第四章协作中继系统中喷泉码的设计2 8 北京邮电大学硕士学位论文 喷泉码的优化设计 4 1 引言2 8 4 2 中继分类。2 8 4 - 3 系统模型2 9 4 3 1 中继系统模型2 9 4 3 2 等效系统模型3 0 4 4 设计方法。3 2 4 4 1 设计方法3 2 4 4 2 举例3 3 4 5 性能仿真。3 4 4 6 本章小结3 5 第五章不等差错保护喷泉码的优化设计3 7 5 1 引言。3 7 5 2u e p 喷泉码。3 8 5 3u e p 喷泉码的优化设计。3 8 5 3 1 与或树分析3 8 5 3 2 设计方法加 5 4 、性能仿真4 l 5 5 、本章小结4 5 第六章结束语4 6 6 1 论文的主要工作4 6 6 2 进一步的研究工作4 7 参考文献4 8 致谢5 2 硕士期间发表的学术论文目录5 3 北京邮电大学硕士学位论文 喷泉码的优化设计 1 1 研究背景 1 1 1 广播和多播的发展 第一章绪论 随着移动通信技术和因特网的迅猛发展，人们在享受信息传递的方便与快捷 的同时也对通信系统的服务能力和范围提出了更高的要求。纵观移动通信的发展 史，向移动用户提供多媒体业务将是未来十年内移动通信发展的主要潮流。从第 一代模拟移动通信系统的仅能提供语音服务，不支持数据传输，到现在的第三代 移动通信系统不仅能够提供速率达到2 m b i t s 数据传输业务并同时提供多种灵活 的多媒体介入能力，通信系统在提升用户容量和传输质量的同时也在不断地提供 更多的业务种类。虽然第三代移动通信系统的传输速率比第二代移动通信快上千 倍，但仍无法满足未来多媒体通信的要求，这些需求推动了人们对第四代移动通 信的期待和研究。由此可见，提供对多媒体信息的高速率数据传输服务是现在及 未来通信的主要任务之一。 p d a 图1 - 1 多媒体广播的网络模型 随着近年来广播技术、无线通信技术、音视频编码技术和大规模集成电路技 术的迅猛发展，以移动电视技术为代表的移动多媒体广播技术也得到了迅速发 北京邮电大学硕士学位论文喷泉码的优化设计 展。图1 - 1 给出了移动多媒体广播的网络模型。移动多媒体广播技术是指面向移 动设备，如手机、车载接收机、p d a 等高速移动或者便携电子设备广播传送实 时音视频内容、多媒体业务以及数据业务等增值业务的广播电视新技术。移动多 媒体广播业务的发展使得人们随时随地接收广播节目和信息服务成为可能，是一 种极具潜力的服务模式，因而成为学术界和产业界研究的热点。 移动多媒体广播系统在进行数据传输过程中，由于信道条件的影响和噪声的 干扰会影响用户的接收性能。解决这个问题的方法往往是采用自动重传请求 ( a u t o m a t i cr e p e a tr e q u e s t ，a r q ) 技术和前向纠错编码( f o r w a r de r r o rc o r r e c t i o n , f e c ) 技术以提高数据传输的可靠性。a r q 技术和前向纠错编码是用于保障数 据可靠性传输的两大差错控制技术，其中，前者是通过对原始信息的重传来保障 数据被正确接收，后者则通过对传输的数据进行纠错编码来降低传输差错。 1 1 2 传统技术存在的问题 当传输的数据增大，接收者大量增加以及网络中的数据包丢失率很大的时 候，采用a r q 技术来实现大量数据的实时可靠传输存在一些问题和不足之处。 首先，所有的a r q 技术都需要使用反馈信道，而在许多通信系统中，并不存在 反向信道或者使用反向信道的代价很高其次，即使拥有充裕的反向信道，a r q 技术的扩展性也比较差，对于广播类应用，其传输效率会随着接收用户数量的增 加迅速恶化，很容易造成网络的反馈拥塞，严重时还会出现网络瘫痪。此外， a r q 技术通常采用应答信号( a c k ) 来进行流量控制，而在信道误码率较高时 会严重抑制传输的带宽。 所以，近年来，使用编码技术来解决数据传输的可靠性问题成为了计算机和 移动通信领域研究的热点。在传统的通信系统中，前向纠错编码技术一般应用于 物理层，用于为上层提供满足要求的信道误码率保证。与a r q 技术相比，前向 纠错编码能够为通信系统中的上层业务提供一个可靠的传输平台，其纠错无需利 用反向信道和重传机制，不会产生重传时延，在广播类应用中具有良好的可扩展 性。但是前向纠错编码也同样存在一些不足之处。在同一通信系统中，往往有多 种类型的业务被同时承载，而不同的业务类型对传输可靠性的要求也有较大的差 异。例如语音通信仅要求误码率低于1 0 - 3 即可，数据传输则需要误码率低于l o 。 由于物理层的信道编码面向的是所有上层应用，仅为了其中少数业务的需求而在 功率，带宽等方面付出过多的代价以追求较低的误码率是得不偿失的。 2 北京邮电大学硕士学位论文喷泉码的优化设计 1 1 3 喷泉码技术的提出及其优势 针对上述问题，m i c h a e ll u b y 及j o h nb y e r s 等人于1 9 9 8 年提出了数字喷泉 ( d i g i t a lf o u n t i a n ) 技术的概念【1 1 【2 】，它是针对大规模数据分发和可靠广播的应 用特点而提出的一种理想的解决方案。喷泉码实际上也是一种前向纠错编码技 术，其基本思想是，发送端可以由原始的数据包生成任意数量的编码包，而接收 端只要接收到足够的编码数据包，即可通过译码以很高的概率成功恢复全部原 始数据包。一般情况下，接收到的编码数据包的个数比原始数据的个数略大。发 送端就如同源源不断产生水滴( 编码分组) 的喷泉，而我们只要用杯子( 接收端) 接收足够数量的水滴，即可达到饮用( 成功译码) 的目的。正因如此，该种编码 被称为喷泉码。在数据的广播和多播传输方面，数字喷泉方案具有以下几点明显 的优势： l 、与a r q 机制相比，反向信道并不是应用喷泉码的必要条件。由于采用喷 泉码作为一种前向纠错编码( f e c ) ，数字喷泉方案不需要接收端进行反馈，收 端只需收够足够的数据就可以恢复出数据，不同接收用户之间的错误的独立分布 并不会对译码性能造成影响。与反馈重传纠错方案相比，它避免了信号往返的延 时，提高了系统的可扩展性，同时也避免了广播应用中的反馈爆炸问题。此外， 由于喷泉码技术的流量控制机制不依赖于应答信号，也不会产生t c p 协议所存 在的传输带宽易被抑制的问题。 2 、与传统的前向纠错编码相比，喷泉码技术更加灵活，它能够适应变化的 信道状况，能充分利用信道容量。在喷泉码发明以前，传统的前向纠错技术通常 基于经典的r s 码和l d p c 码。但无论是r s 码还是l d p c 码，其应用通常须基 于预先假设信道模型的情况，如删除概率( 即丢包率) ，并以此选取码长和码率 ( k ) 等编码参数，之后才能设计具体的编译码方式。但是在实际应用中，由于 信道的时变性，当信道条件优于假设时，前向纠错技术将因增加了过多的校验位 而导致传输效率降低，而当信道条件劣于假设时，前向纠错技术又因为不能提供 更多的校验位而导致传输的可靠性降低。喷泉码的发明很好的解决了上述问题。 由于喷泉码的设计仅仅基于原始数据包数量，而与信道模型无关，其非固定码率 ( r a t e l e s s ) 特性使得发端能够生成无限多的编码包，当收端发现信道条件不好， 丢包较多时，只要接收更多的编码包即可，而不需要发端重新设计编码方案重新 发送，因此它对复杂的信道状况具有很强的适应性。 3 、与传统的r s 等纠删码相比，喷泉码具有更低编译码复杂度。传统的r s 纠删码的编译码复杂度较大，标准算法达到o ( k ( n k ) l o g ，咒) ，因此必须将数据 分成较小的单元进行编码，通常码长n 七) 个编码数据包即可恢复原有的数据包，进而恢 复大型文件，而损坏的编码数据包并不影响对这一文件的恢复。 另外，喷泉码在数据的快速恢复上也有很大的优势。比如，在实际的硬盘存 储中，为了能快速地读取数据，通常的做法是将文件存储在硬盘中连续的空间中。 但是，如果读取过程中某个数据包因为突发性错误丢失了，这时，往往需要将硬 6 北京邮电大学硕士学位论文 盘中的所有数据重新读取才能恢复丢失的数据包，而这有可能需要花费比较长的 时间。如果采用喷泉码的方式存储数据，如果某个数据包丢失了，只需要再多读 取一个或几个数据包，就可以恢复丢失的数据包了，而不需要重新读取所有的数 据，这样可以很大程度上减少数据恢复的时间。 1 3 2 多播和广播传输 在多播和广播通信系统中，有众多的用户接收同样的数据，通信协议的应用 层和传输层传统上采用a r q 技术或基于r s 和l d p c 码的前向纠错编码技术来 保证可靠传输。但是，这些解决方案都存在一些严重的缺陷。例如，但在信道条 件较差的情况下，出错数据可能超出编码纠错能力范围，因此仍无法保证数据的 可靠性。这时往往采用增加反馈信道采用a r q ( 自动重发请求) 和a c k 确认来 保证数据的完整性。但对大量的用户反馈容易引起网络阻塞或发送端自身瘫痪等 问题【1 7 】。喷泉码最初就是为了解决可靠组播和广播问题而提出的，基于喷泉码的 组播和广播的解决方案具有良好的性能。将喷泉码的编码方法应用于广播和多播 传输中具有如下优点：( 1 ) 理想的可扩展性。用户的数量增长对与发送方来说没 有任何影响，发送方可以服务任意数量的用户。( 2 ) 适应时变信道。( 3 ) 适应异 质用户。 1 3 3 无线协作传输 2 0 0 7 年，m o l i s c h 等人【9 】首次将喷泉码技术应用于协作多中继无线网络中， 提出了协作通信系统中互信息累加的概念。通过采用准同步传输协议和异步传输 协议，m o l i s c h 等人有效的降低了传输过程中需要的时间和功率。与传统的编码 技术相比，数字喷泉码的一个最大优点是利用该种编码技术可将源信息包编码为 一无限长编码包流对于协作多中继无线网络，在基于数字喷泉码的异步传输协 议中，每个中继节点一旦对接收到的编码包完成译码，该中继节点便开始向其目 的节点传输通过译码所得的源数据包。由于无线信道的广播特性和数字喷泉码无 限长编码包流特点，这种传输方式不仅可对目标节点提供有用的信息，而且也有 助于未完成译码的中继节点进行其译码。 1 3 4 深空通信 深空通信信道频带资源相对充足，而有限的星上设备总量、尺寸、长传输距 离使得其功率资源严重受限，因此深空通信数据传输信道可视为功率受限而带宽 丰裕信道，是典型的以有效性换取可靠性的传输信道。深空通信中存在以下特点： 7 北京邮电大学硕士学位论文喷泉码的优化设计 ( 1 ) 延时大、航天器存储容量和处理能力有限；( 2 ) 通信中握手过程效率低；( 3 ) 确 认重传效率低；( 4 ) 拥塞控制策略导致吞吐量降低；( 5 ) 发送与接收信息速率的不 对称；( 6 ) 多个接收者时：大量冗余数据浪费通信资源、反馈爆炸。 由于喷泉码的良好的性能和优势，使得它非常适合用于深空通信传输中。首 先，喷泉码是一种无码率前向纠错码，这一特性使得发送端可以根据信道条，发 射功率等条件灵活地选择编码方式，而接收端只要能够获得足够多的编码符号， 就能够成功地还原信息符号。其次，喷泉码的编译码复杂度很低，可以很大程度 的降低深空通信的编译码时间，从而可以很大程度上满足卫星电视，卫星广播对 于时延的要求再次，采用喷泉码技术不需要重传信道，不会引起反馈爆炸和数 据拥塞。最后，数字喷泉方案良好的可扩展性和对异质用户支持有利于深空通信 网的构建和运行。 1 4 论文的主要贡献和章节安排 由于喷泉码在广播和多播场景中的各种优势和广阔的应用前景，近年来对喷 泉码的研究得到了迅速的发展，t o r n a d o 码、l t 码、r a p t o r 码等多种性能良好的 喷泉码相继被提出。但与传统的信道编码领域相比，喷泉码技术在无论在理论研 究还是工程应用方面都仍处于起步阶段，还存在许多问题有待进一步研究。 首先，目前的喷泉码的度分布及大都是根据某种启发式的思想设计出来的， 而且这些度分布及设计方法都是针对长码长的，在实际应用中有一定的局限性。 其次，目前的喷泉码的度分布设计方法都是考虑端对端的通信系统模型，由于中 继节点的增加往往会改变接收端编码数据包的度分布结构，因而目前的度分布设 计方法在某些协作通信系统中并不适用。最后，目前实现不等差错保护喷泉码的 基本思想都是传输尽量多的重要信息，以保证重要信息被优先恢复，但是如何实 现性能更优的不等差错保护喷泉码还需要进一步研究。 针对上述问题，本论文以喷泉码中最关键的度分布设计为研究对象，通过分 析喷泉码的度分布结构对迭代译码过程的影响，提出了一种喷泉码度分布的优化 设计方法，并进一步研究了协作通信系统中喷泉码的度分布设计。最后，在现有 u e p 喷泉码的基础上，提出了一种u e p 喷泉码优化设计方法，为喷泉码的理论 研究和实际应用方面都做出了一定的贡献。论文内容的具体安排如下： 论文第一章从多媒体广播和多播应用需求分析出发介绍了喷泉码技术应用 的主要场景，并比较了喷泉码相对传统信道编码技术的优势，通过对喷泉码的研 究现状和应用前景的综述，指出了喷泉码目前面临的一些问题，引出了本论文的 主要研究内容，最后给出了论文的具体安排。 8 北京邮电大学硕士学位论文喷泉码的优化设计 论文第二章将对喷泉码技术进行详细的介绍和分析。首先分析了喷泉码应用 的主要信道模型删除信道。然后，通过对t o r n a d o 码、l t 码、r a p t o r 码以 及3 g p pm b m s 标准协议的分析，详细介绍了各种喷泉码的编译码算法及其重要 参数，并对这几种喷泉码的优缺点进行了总结。 第三章至第五章是论文的主要研究内容。第三章从喷泉码b p 译码算法角度 出发，提出了可译集合的概念，分析了度分布结构对可译集合大小的影响，建立 了优化设计喷泉码度分布的模型，采用差分进化的方式提出了一种喷泉码度分布 的优化设计方法。 第四章分析了在协作通信系统中，中继节点对喷泉码度分布的影响，推导了 现有中继系统中的度分布与端到端通信系统中度分布的关系，在现有的性能优良 的度分布基础上提出了一种适用于协作通信系统中的喷泉码度分布的设计方法。 第五章从现有的u e p 喷泉码出发，提出了一种优化u e p 喷泉码的设计方法。 该方法分析了现有u e p 喷泉码设计方法的缺点，在此基础上进一步改进了现有 的u e p 喷泉码，基于一定的信道条件情况，全局优化了重要信息和不重要信息 的编码方式和译码性能。 最后，论文的第六章对全文进行总结，并提出了开展下一步研究工作的建议。 9 北京邮电大学硕士学位论文 喷泉码的优化设计 第二章喷泉码技术 作为本论文的研究基础，本章将对喷泉码的信道模型、基本概念和原理进行 介绍。首先对第一种具有数字喷泉思想的t o r n a d o 码进行简要的介绍，说明喷泉 码技术产生的基础和背景。然后介绍第一种真正意义上的喷泉码l t 码以及 在其基础上发展起来的r a p t o r 码，并详细描述这两种喷泉码的编译码算法及思 想最后，介绍了3 g p pm b m s 中采用的喷泉码的编译码协议及实现。 2 1 删除信道模型 喷泉码是定义在删除信道模型上的前向纠错编码技术，因此在介绍喷泉码技 术之前，我们首先回顾一下删除信道模型。1 9 5 5 年e l i a s 首次介绍了二进制删除 信j 遒( b i n a r ye r a s u r ec h a n n e l ，b e c ) t 2 5 1 。删除信道的定义是指传输信号在通过该信 道后，会以删除概率p 被判决为不确定( 即“被删除，以l p 的概率能够被正 确接收。如图2 - 1 所示，即为一个典型的二进制删除信道模型。 o o 9 图2 - 1b e c 信道模型 在实际的通信系统中并不存在物理上的删除信道，但是我们通常可以将数据 包之间通过的信道等效为删除信道。这是因为一般采用信道编码的方式抵抗物理 层中的噪声，若接收端能够正确译码数据包则接收该数据包，否则丢弃( 即删除) 该数据包，进而可以将数据包通过的信道等效成一个二进制删除信道。互联网是 一种比较典型删除信道，互联网中数据包的丢失以及校验信息的不匹配均可认为 信号被删除了。此外，随着通信技术的发展，分组交换通信网络的出现，带检错 的分组交换信道也可以被看作是删除信道。喷泉码是定义在广义的二进制删除信 道上，其信道可以对应用通信系统中的某条链路，也可以将整个连接等效为一个 逻辑信道。因此，喷泉码能够为具体的业务提供端到端的可靠连接。 1 0 北京邮电大学硕士学位论文喷泉码的优化设计 2 2t o r n a d o 码 在喷泉码技术出现以前，通常采用的纠删码是r s 码。r s 码是一种最大距 离分离( m a x i m u md i s t a n c es e p a r a b l e , m d s ) 码，但r s 码编解码复杂度很高， 达到码长的2 次方量级，这大大的限制了r s 码的应用。针对这一问题，l u b y 等人基于不规则稀疏图构造的出了t o r n a d o 码【3 】。t o m a d o 码采用级联的编码方 式，并利用了m d s 码的强纠错能力，同时又避免了m d s 码比较高的编译码复 杂度。由于t o r n a d o 码编译码的效率很高，曾被作为第一种喷泉码加以应用【l 2 1 。 1 ，l 吻 。哆 图2 2t o r n a d o 码的级联生成图 t o r n a d o 码属于系统码，它采用的是一种级联的编码方式，其编码原理可以 用图2 - 2 来说明。在图2 2 中，左边第一层包含y 个节点表示原始输入符号，第 二层励个节点对第一层的输入符号进行校验。第二层每个符号由第一层的若干 个随机的输入符号异或生成。第三层有2 y 个节点，对第二层的节点进行校验。 这一过程一直下去，共生成m + l 级校验节点，最后一级校验采用一个码率为l 一 的传统分组删除码，一般采用典型的m d s 码( 如r s 码) 。这样t o r n a d o 码一 m + l 共包含刀个输入符号和n + p 肿2 n o - p ) = n , o 0 - p ) 个校验符号，码率为 i = 1 1 一。由于t o m a d o 码的最后一级采用m d s 码，可以恢复丢包不超过的码字。 t o r n a d o 码可以恢复总体上丢包不超过( 1 一s ) 的码字，并且其算法时间与符号程 度n 成线性关系。 北京邮电大学硕士学位论文喷泉码的优化设计 对每一级级联的子图，左边的度分布为五= 1 【日( d ) ( f 一1 ) 】，i = 2 ，d + l ，其 中，m ( a ) - - 1 i ，左边节点的平均度值为a t = 日( d ) ( d + 1 ) d 。因此，右边节 点的平均度值为a r - - a t ，右边的度分布采用泊松分布，n = 弋e - 酉a o f _ l - i ，其中口 需要满足等式口e 口( 矿- 1 ) = a r 。 t o r n a d o 码整体译码过程为，先译出右边的子图的输入节点，然后将这些输 入节点作为左边子图的校验节点，译出左边子图的输入节点，这样依次逐级译出 所有原始的输入符号。t o r n a d o 码每一级子图的译码算法，在每一步译码过程中， 先将所有已知的左边节点异的值或到与其相连的右边节点上，然后寻找度值为l 的右边节点，并恢复与其相连的左边节点的值。重复上述过程，直至左侧所有左 边节点的值全部被恢复为止。如果译码过程进行到某一步时，找不到度值为1 的 右边节点，则译码过程停止。 与传统的r s 码相比，t o r n a d o 码将编译码的算法复杂度从平方量级降低到 了线性量级，但是其纠错能力比r s 码稍差一些。虽然t o r n a d o 码具有高效的编 译码算法，但它还不是一种无码率的编码，还不能实现真正意义上的喷泉码。另 外，t o r n a d o 码采用级联的编码方式，将整体编码拆分成若干个子图，并要求其 任何一层子图的丢包率都不超过其纠错能力，这在一定程度上导致了t o r n a d o 码 整体性能的降低。 2 3l t 码 l t 码，又称l u b y 变换码，是l u b y 在2 0 0 2 年提出的一种数字喷泉编码模式。 在该编码中，l u b y 巧妙地解决了编码复杂度问题，并实现了无码率的性能。 2 3 1l t 码的编译码算法 l t 码是第一个真正意义上的喷泉码，它可以生成任意长的编码数据包，l t 码生成每个编码数据包的过程如图2 - 3 所示，具体编码算法如下： 1 ) 根据设计的度分布q ，随机地选取编码符号的度d 。 2 ) 从k 个输入符号中，随机等概率地选取d 个不同的输入符号。 3 ) 将这d 个输入符号模二和，生成一个编码符号。 理论上，生成的编码符号可以无限多次的通过信道传输。l t 码生成的编码 符号之间是相互独立的，因为喷泉码的编码包数目是不固定的，相应的码率也是 1 2 北京邮电大学硕士 不固定的，从 o 输入符号编码符号田异或操作 图2 - 3l t 码的编码示意图 西嘎 s 3 i1 一深。懿 lo 毛 之 ( a ) o 11 ft 1 3 q 011 ( b ) 1o 。力 ( c ) l0 l ooo 码。为了降低 为和积算法。 北京邮电大学硕士学位论文喷泉码的优化设计 为1 的编码符号，恢复与该编码符号相连的输入符号，并将该编码符号从双向图 中移除。对于已经恢复的输入符号，将其模二和到与其相连的所有其他编码符号 中，从而使得这些编码符号的度数减1 ，这样就可能产生新的度为1 的编码符号。 2 ) 重复上述过程，直到成功译出所有的输入符号或者已经没有度为1 的编 码符号，迭代过程停止。 为了说明上述的解码算法，图2 - 4 给出了一个简单的译码实例。 2 3 2l t 码的设计规则 根据l t 码的编码规则，我们知道在进行l t 码编码时，需要先预定一个输 出符号度的概率分布函数，然后根据这个概率分布，随机产生输出符号的度值。 预定的度分布不但影响到l t 码的编码，而且会影响到l t 码的译码算法，所以 该度分布是非常重要的。在译码过程中，为了保证译码能连续进行而不被中断， 需要每次迭代中都有一个输出符号节点的度减少为l ，同时为了保证低的编译码 复杂度，又需要使得输出符号的平均度值尽可能低。根据这一要求，l u b y 给出 了理想情况下的输出符号节点度的分布函数为川： 刺= 跪 d = l d = 2 ，k 在此分布情况下输出符号节点度的平均值近似为i n k 。 事实上，这一概率分布在实际应用中的译码性能是非常差的。这是由于在随 机选取输出符号度的过程中，会出现波动的情况，即选取的输出符号度可能大于 或小于预定结果，而且在实际过程中，接收到的编码符号存在一定的删除，这都 会导致译码在某次迭代后没有度为1 的输出符号的情况出现，从而使得译码失 败。为了提高译码成功率，l u b y 提出了一种修正的度分布( r o b u s ts o l i t o n d i s t r i b u t i o n ，r s d ) 。他首先引入了两个参数c 和万，其中c 为一个常数，万为译 码失败概率的上界，并定义 f ( d ) = 心，去一， d ：生 r d 为其他值 其中，尺= c l n ( k 6 ) , f k ，表示输出符号节点度为1 的平均值。 1 4 一 r一：似 旦出些 。 北京邮电大学硕士学位论文喷泉码的优化设计 于是，r s 。度分布定义为：“( d ) 2 芝揣 2 4r a p t o r 码 为了降低编译码复杂度，l u b y 给出了理想输出符号节点的概率度分布，并 结合应用，提出了修正的概率分布，将l t 码的译码复杂k l n k 。l t 码虽然性能 优良，但仍未达到编译码复杂度的理想目标，即生成每个编码符号需要的运算量 是一个与k 无关的常数，而成功译码需要的运算量是一个关于k 的线性函数。 2 0 0 3 年，s h o k r o l l a h i 提出了另一种数字喷泉码：r a p t o r 码【5 】。他巧妙地应用了 l t 码的特点和l d p c 码的译码算法的特点，将二者有机地结合在一起，设计了 一种级联编码。这样极大的降低了译码的复杂度。r a p t o r 码的编译码复杂度为 o ( kl