（信号与信息处理专业论文）喷泉码的性能分析与设计.pdf

i i i i r ll lr rll l l l r j l l l rj iri f j l l f l l l jp i i i j f j l y 17 5 8 7 1 8 独创性 或创新性 声明 本人声明所呈交的论文是本人在导师指导下进行的研究工作及取得的研究 成果 尽我所知 除了文中特别加以标注和致谢中所罗列的内容以外 论文中不 包含其他人已经发表或撰写过的研究成果 也不包含为获得北京邮电大学或其他 教育机构的学位或证书而使用过的材料 与我一同工作的同志对本研究所做的任 何贡献均已在论文中作了明确的说明并表示了谢意 申请学位论文与资料若有不实之处 本人承担一切相关责任 本人签名 盔 l 象 日期 坌丝 墨 2 2 关于论文使用授权的说明 学位论文作者完全了解北京邮电大学有关保留和使用学位论文的规定 即 研究生在校攻读学位期间论文工作的知识产权单位属北京邮电大学 学校有权保 留并向国家有关部门或机构送交论文的复印件和磁盘 允许学位论文被查阅和借 阅 学校可以公布学位论文的全部或部分内容 可以允许采用影印 缩印或其它 复制手段保存 汇编学位论文 保密的学位论文在解密后遵守此规定 保密论文注释 本学位论文属于保密在一年解密后适用本授权书 非保密论 文注释 本学位论文不属于保密范围 适用本授权书 本人签名 导师签名 日期 垒缝 主 丝 r 期 垄 翌 呈 兰 喷泉码的性能分析与设计 摘要 数字喷泉码是针对大规模数据分发和可靠广播的应用特点而提 出的一种新的信道编码方案 近年来受到了学术界和产业界的广泛关 注 为了提高喷泉码的纠错性能 论文在分析其编码结构和编译码性 能的基础上提出了喷泉码预编码的一种设计方法 并对喷泉码不等错 误保护的策略进行了研究 作为论文的研究基础 首先对数字喷泉码的基本概念和编译码原 理进行了概述 介绍了数字喷泉码的信道模型 定义和特点等相关内 容 然后对三种典型的喷泉码 而m a d o 码 l t 码和r a p t o r 码进行了 重点介绍 详细描述了它们的编译码算法 并对它们的编译码性能做 了一定的分析和讨论 r a p t o r 码由预编码和l t 码级联而成 设计一种好的预编码对 r a p t o r 码有着重要意义 为了进一步提高r a p t o r 码的性能 论文选 取了一种可以逼近信道容量的高码率l d p c 码来构造r a p t o r 码的预 编码 给出了两种不同条件下l d p c 码度分布的设计 并对采用该预 编码的r a p t o r 码的性能进行了仿真 仿真结果表明 所设计的r a p t o r 码在中间符号译码开销y 1 1 5 时 误码率小于l o 具备良好的性能 对实际设计与应用具有一定的指导意义 论文的最后从某些多媒体应用中对数据不等错误保护的需求出 发 以l t 码为例 对喷泉码不等错误保护的实现方案做了一定的分 析与研究 并提出了相应的改进方法 仿真表明 当接收端收到较少 的编码符号时 改进的u e p 方法比原有的方案表现出了更好的性能 关键词 喷泉码l d p c 码删除信道b p 译码算法不等错误保 护 p e r f o r m a n c ea n a iy s i sa n dd e s i g n o ff o u n l l ai nc o d e s a b s t r a c t d i g i t a lf o u n t a i nc o d ei sp r o p o s e da san e w c h a n n e lc o d i n gs c h e m e f o rt h ea p p l i c a t i o nc h a r a c t e r i s t i c so fl a r g es c a l ed a t ad i s t r i b u t i o na n d r e l i a b l eb r o a d c a s t i n g w h i c hi sc o n c e m e db ya c a d e m i c sa n di n d u s t r yi n r e c e n ty e a r s i no r d e rt oi m p r o v et h ee r r o r c o r r e c t i n ga b i l i t yo ff o u n t a i n c o d e s i nt h i sp a p e rw ep r o p o s ea ni m p r o v e dp r e c o d i n gd e s i g n w h i c hi s b a s e do nt h ea n a l y s i so ff o u n t a i nc o d es t r u c t u r ea n dp e r f o r m a n c eo f e n c o d i n ga n dd e c o d i n g w ea l s os h o wt h er e s e a r c ho nu n e q u a le r r o r p r o t e c t i o ns t r a t e g yo ff o u n t a i nc o d ef o rs o m em u l t i m e d i aa p p l i c a t i o n s a sab a s i cr e s e a r c ho ft h i sp a p e r f i r s tw ei n t r o d u c et h eb a s i c c o n c e p t sa n dp r i n c i p l e so fd i g i t a l f o u n t a i nc o d e i n c l u d i n gc h a n n e l m o d e l s d e f i n i t i o n s a n dc h a r a c t e r i s t i c s t h e nt h r e ek i n d so ft y p i c a l f o u n t a i nc o d e t o m a d oc o d e l tc o d ea n dr a p t o rc o d ew e r e h i g h l i g h t e d 肫g i v eac o m p r e h e n s i v ed e s c r i p t i o no ft h e i re n c o d i n ga n d d e c o d i n ga l g o r i t h m s a n da l s os o m ea n a l y s i sf o rt h e i rp e r f o r m a n c e r a p t o rc o d ec o n s i s t so fp r e c o d ea n dl tc o d e t h e r e f o r eag o o d p r e c o d i n gd e s i g n i so fg r e a t s i g n i f i c a n c e w es e l e c t ak i n do f c a p a c i t y a p p r o a c h i n gl d p c c o d ee n s e m b l e st oc o n s t r u c tt h ep r e c o d eo f r a p t o rc o d e w h i c h i s g i v e nb yt w o d i f f e r e n td e s i g n so fd e g r e e d i s t r i b u t i o n a n dw ef u r t h e rv e r i f yo u rw o r kw i t hs i m u l a t i o n s t h e s i m u l a t i o nr e s u l t si n d i c a t et h a tw h e no v e r h e a d7 1 15 t h eb i te r r o rr a t e o f r a p t o rc o d ei sl e s st h a n 1o 5 w h i c hp r o v i d e sag o o dp e r f o r m a n c ea n d ac e r t a i ns i g n i f i c a n c et ot h ea c t u a ld e s i g na n da p p l i c a t i o n f i n a l l y f r o mn e e do fu n e q u a le r r o rp r o t e c t i o ni ns o m em u l t i m e d i a a p p l i c a t i o n s u s i n gl tc o d ea sa ne x a m p l e t h i sp a p e rp r o v i d e sa n a l y s i s a n dr e s e a r c hf o ri m p l e m e n t a t i o no fu 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 nc o d e p r o p o s e sa ni m p r o v e dm e t h o d t h es i m u l a t i o nr e s u l t ss h o wt h a tt h e i m p r o v e dm e t h o do fu e pa c h i e v e sb e t t e rp e r f o r m a n c et h a nt h eo r i g i n a l m e t h o dw h e nt h er e c e i v e rg e t sf e w e rc o d i n gs y m b o l s k e yw o r d s f o u n t a i nc o d e l d p cc o d e b e c b pd e c o d i n g a l g o r i t h m u e p 目录 第一章绪论 1 1 1研究背景及研究意义 1 1 2数字喷泉码的提出及其优势 3 1 3 喷泉码的应用 一5 1 3 1多播传输 5 1 3 2多源下载 5 1 3 3无线协作传输 6 1 3 4深空通信 6 1 4喷泉码存在的问题 7 1 5论文主要研究内容及章节安排 7 第二章数字喷泉码概述 一9 2 1 引言 9 2 2数字喷泉码的基本概念 9 2 2 1 二进制删除信道模型 9 2 2 2数字喷泉码的相关定义 l o 2 3几种典型喷泉码的介绍 1 1 2 3 1 t o r n a d o 码 1 l 2 3 1 1t o r n a d o 码的编码 1l 2 3 1 2t o r n a d o 码的译码 1 2 2 3 1 3t o r n a d o 码分析 12 2 3 2 i t 码 12 2 3 2 1l t 码的编码 l3 2 3 2 2l t 码的译码 1 4 2 3 2 3l t 码分析 15 2 3 3 r a p t o r 码 l6 2 3 3 1 r a p t o r 码的编码 1 6 2 3 3 2 r a p t o r 码的译码 1 7 2 3 3 3 r a p t o r 码分析 1 7 2 4本章小结 1 8 第三章r a p t o r 码的编码分析与设计 l9 3 1引 言 l9 3 2l d p c 码概述 1 9 3 2 1l d p c 码的定义和表示 1 9 3 2 2p e g 法构造校验矩阵 2 l 3 2 3l d p c 码的编码 2 3 3 2 4l d p c 码的译码 2 4 3 2 4 1a w g n 信道下的译码算法 2 4 3 2 4 2b e c 信道下的译码算法 2 6 3 3b e c 信道下逼近信道容量的l d p c 码度分布的设计 2 7 3 4 r a p t o r 码编码的联合设计与实现 2 9 3 4 1基于与或树理论分析方式的设计 3 0 3 4 2基于l t 码实际仿真方式的设计 3 2 3 5仿真结果与分析 3 4 3 6本章小结 3 6 第四章喷泉码不等错误保护的策略研究 3 8 4 1 引 言 3 8 4 2喷泉码u e p 的实现分析 3 8 4 2 1大概率选取法 3 8 4 2 2分配小度值法 4 0 4 3一种改进的喷泉码u e p 实现方案 4 0 4 4仿真结果与分析 4 1 4 5本章小结 4 4 第五章结束语 4 5 5 1论文工作总结 4 5 5 2工作展望与建议 4 5 参考文献 4 7 致谢 4 9 攻读学位期间发表的学术论文目录 5 0 北京邮电大学硕 学位论文喷泉码的性能分析与设计 1 1 研究背景及研究意义 第一章绪论 在过去的几十年里 移动通信技术和因特网得到了迅猛的发展和广泛的应 用 移动通信技术已经从只能提供语音服务的第一代移动通信系统发展到今天的 以大容量 高速率 高质量以及具有灵活的多媒体接入能力为特点的第三代移动 通信系统 3 g 目前 对下一代移动通信系统l t e 的研究也已经逐步拉开了序 幕 纵观移动通信的发展历史可以看出 提供高速率高质量的多媒体数据业务将 成为未来移动通信系统的基本特征之一 通信系统的基本目的在于将信息由信源高效 可靠 有时还需安全地传送到 信宿 有扰通信信道中的噪声会不可避免地对传输信息产生不同程度的干扰 从 而可能降低通信可靠性 所以通信系统设计的核心问题就是在存在随机噪声的信 道中如何克服干扰 减小信息传输的差错 同时又不降低信息传输的效率 即如 何解决系统的有效性与可靠性之间的矛盾 一般地 通信系统的可靠性用误比特 率 b e r 来衡量 其有效性则用信息传输速率r 比特 信道符号来衡量 在相关领域的研究中 如何提高数据传输的可靠性一直是通信领域研究的重 要课题之一 也是改善通信系统性能的关键所在 在有线通信中 物理信道通常 能为上层应用提供较低的误码率保证 但链路层和网络层的数据包碰撞和拥塞问 题会造成数据的丢失 在无线通信中 无线信道受到地形 建筑物 移动和传播 介质等多种复杂因素的影响 传输条件较差 使得信道具有比较高的误码率 解 决这类问题的方法之一就是采用信道编码技术 它可以有效地改善通信系统的传 输质量 早期人们普遍认为 通信系统的可靠性与有效性之间是一对不可调和的矛 盾 一方的改善总是以牺牲另一方为代价 并指出当功率受限时 在有扰通信信 道上实现任意小错误概率的信息传输的唯一途径就是把信息传输速率降低至零 1 9 4 8 年贝尔实验室的香农 s h a n n o n 在其开创性的著名论文 1 1 中奠定了信息论 的基础 改变了这一观点 他首次指出 对于一离散无记忆平稳信道容量c 则 只要信息传输率r c 时 对任何编码方式 译码差错率大 于o 这就是著名的有噪信道编码定理 香农第二定理 它奠定了信道编码理 北京邮电大学顾一b 学位论文 喷泉码的性能分析与设计 论研究的基础 香农第二定理已经向我们证明 既要效率高 即可以用任意接近信道容量c 的传输效率r 来传送 又要抗干扰性强 即传输差错率可以任意小的编码方法是 存在的 但他只是利用随机编码和最大似然译码从数学上严格证明了确实存在一 个适当的编译码方法能够达到这一理论极限 并未给出实际的编码方法 因此 如何构造出一种工程可实现且能够有效逼近香农限的编码方案并为之提供一种 有效的译码算法成为了众多专家学者努力的方向 自动请求重传 a r q a u t o m a t i cr e p e a tr e q u e s t 和前向纠错 f e c f o r w a r d e r r o rc o r r e c t i o n 是上个世纪四五十年代以来兴起的用于保障数据传输可靠性的 两大差错控制技术 2 自动请求重传技术可以有效地提高数据传输的可靠性和避 免网络拥塞的出现 但可能导致较大的时延 这个缺点在大容量数据的实时传输 中是不可接受的 克服这一缺点的方法是采用前向纠错编码技术 前向纠错也称 为自动纠错 即发端发送具有一定纠错能力的码 收端译码时 若传输中产生差 错的数目在码的纠错能力之内译码器可以对差错进行定位并自动加以纠正 反 之 若差错数目大于纠错能力则无能为力 前向纠错方式的主要优点是不需要反 馈信道并能自动纠j 下差错 所以它比较适合于实时传输系统 基于f e c 的信道 编码方案有很多种 最典型的两类是分组码 以线性分组码为代表 和非分组的 卷积码 分组码从早期的汉明码到后来的循环码 b c h 码 r s 码等 在实际通信系 统中都得到了广泛的应用 可以说分组码在理论分析和数学描述方面已经非常成 熟 但分组码固有的缺陷限制了它的进一步发展 首先 由于分组码是面向数据 块的 因此 在译码过程中必须等待整个码字全部接收到之后才能开始进行译码 在数据块长度较大时 引入的系统延时是非常大的 分组码的第二个缺陷是它要 求精确的帧同步 即需要对接收码字或帧的起始符号时间和相位精确同步 2 另 外 大多数基于代数的分组码的译码算法都是硬判决算法 而不是对解调器输出 未量化信息的软译码 从而造成了一定程度的增益损失 可以说 在低信噪比下 分组码的性能由码字本身的特性和硬判决译码的性能共同决定 虽然也可以实现 分组码的软判决译码 但译码的复杂性通常都是比较大的 基本上是随着码字长 度的增加而呈指数形式的增长 分组码所存在的固有缺点可以通过采用其他的编码方法来改善 这种编码方 法就是卷积码 卷积码与分组码的不同在于分组码在编码之前先将信息序列按照 一定的数据块长度分组 然后对每一组信息进行独立编码 即对于 刀 后 分组 码来说 码字中的刀 后个检验元仅与本码字的k 个信息元有关 而与其他码字的 信息元无关 在卷积码的译码过程中 不仅要从本码中提取译码信息 还要充分 2 北京邮电大学硕士学位论文喷泉码的性能分析与设计 利用以前和以后收到的码组 从这些码组中提取译码相关信息 而且译码是可以 连续进行的 这样可以保证卷积码的译码延时相对比较小 通常 在系统条件相 同的情况下 在达到相同译码性能时 卷积码的信息块长度和码字长度都要比分 组码的信息块长度和码字长度小 相应译码复杂度也小一些 虽然软判决译码 级联码和编码调制技术都对信道码的设计和发展产生了重 大影响 但是其增益与香农理论极限始终都存在2 3 d b 的差距 因此 信道截 止速率r 一直被认为是差错控制码性能的实际极限 香农极限仅仅是理论上的 极限 是不可能达到的 t u r b o 码和l d p c 码的推出打破了这一观点 1 9 9 3 年法国人b e r r o u 等在i c c 国际会议上提出了一种采用重复迭代 t u r b o 译码方式的并行级联码 并采用软输入 输出译码器 可以获得接近香农限的性 能 仿真结果表明 在采用长度为6 5 5 3 6 的随机交织器并译码迭代1 8 次情况下 在信噪比e 从 0 7 d b 并采用二元相移键控 b p s k 调制时 码率为1 2 的t u r b o 码在加性高斯白噪声 a w g n 信道上的误比特率 b e r 1 0 叫3 1 t u r b o 码是 一种信道编码理论界梦寐以求的可实用非常好码 它的出现标志着信道编码理论 研究进入了一个崭新的阶段 t u r b o 码成功的根本原因在于其实现方案中长码构 造的伪随机性是核心 它通过随机交织器对信息序列的伪随机置换实现了随机编 码的思想 从而为香农随机编码理论的应用研究奠定了基础 低密度校验码 l d p c 4 1 也是一种逼近香农限的 易实现和复杂度低的优 秀线性分组码 它是由g a l l a g e r 于1 9 6 0 年在其论文中首先提出的 由于当时技 术条件的限制 l d p c 码没有引起研究人员的重视 随着二十世纪九十年代t u r b o 码研究的重大成功 m a c k a y 等人重新研究了l d p c 码 发现其具有很多优良的 特点 逼近香农限 易于描述和实现 易于理论分析和研究 译码简单且可并行 译码 适于硬件实现等 由于l d p c 码具有在中长码长时超过t u r b o 码的性能 并且具有译码复杂度更低 能够并行译码及译码错误可检测等特点 成为目前信 道编码理论一个新的研究热点 n 曲o 码的提出和l d p c 码的重新发现 大大推动了香农编码理论的发展 它们也得到了业界的广泛认可和应用 1 2 数字喷泉码的提出及其优势 数字喷泉 d i g i t a lf o u n t a i n f 5 的概念最早由m l u b y 等人于1 9 9 8 年首次提 出 是针对大规模数据分发和可靠广播的应用特点而提出的一种新的信道编码方 案 但当时并没有给出现实可行的喷泉码设计方案 2 0 0 2 年 m l u b y 提出了 第一种现实可行的喷泉码一l t 码 目前 凭借着强大的技术吸引力和应用潜 3 北京邮电大学硕 e 学位论文喷泉码的性能分析 j 设计 力 喷泉码已经受到了产业界的广泛关注 获得了越来越多的实际应用 所谓喷泉码 是指该种编码在发送端可以由一定数量的原始数据包生成任意 数量的编码数据包 而接收端只要正确收到任意足够数量的编码数据包 即可通 过译码以较高概率成功恢复全部原始数据包 不必考虑接收到的是哪些数据包以 及这些数据包的接收顺序 喷泉码的编码过程就如同源源不断产生水滴 编码分 组 的喷泉 编码器 而我们只要用杯子 译码器 接收足够数量的水滴 即 可达到饮用 成功译码 的目的 因此该种编码被称为喷泉码 喷泉码可工作在 链路层 传输层或应用层 它将带有检错机制的分组交换信道等价为删除信道 把传统纠错编码的处理对象从符号扩展到了数据分组 通过各数据分组间的校验 关系来恢复因误码或拥塞等原因引起的传输错误 喷泉码的特点与优点主要包括 1 信息被分散在各个编码信息单元内 不 需要重传 可通过后续信息单元的接收恢复原始信息 2 付出的代价是需要的 编码信息单元数比原始信息单元数量略有增加 可通过某种设计使得开销和性能 得到较好的折衷 与传统的物理层信道编码技术相比 数字喷泉码更加灵活 物理层的信道编 码仅能纠正点到点链路上因误码带来的错误 对链路层或由于碰撞拥塞导致的丢 包则无能为力 因此无法为具体业务提供全面的端到端的可靠保障 数字喷泉码 恰好可以有效解决上述问题 在传输层或应用层采用时 因碰撞或网络拥塞而导 致的丢包可以被喷泉码所恢复 它与t c p 协议一样 可以针对有较高可靠度需 求的具体业务单独采用 喷泉码兼有传统信道编码和自动请求重传机制的优点 可以有针对性地为数据业务提供一种具有良好扩展性的端到端的可靠解决方案 f 2 o 随着通信技术的迅猛发展 大量多媒体业务涌现 其中一些应用业务 需要 多个用户能同时接收相同数据 如视频点播 电视广播 视频会议 网上教育 互动游戏等 这些多媒体业务和一般数据相比 具有数据量大 持续时间长 时 延敏感等特点 这些传输必须是完全可靠的 同时允许众多的用户可以随时从网 络中接收数据 并且能正确恢复 当传输的数据增大 接收者大量增加以及网络 中的数据包丢失率很大的时候 如果采用原有的自动反馈重传技术来实现大容量 数据实时可靠传输 很容易造成网络的反馈拥塞 严重时还会出现网络瘫痪 这 种情况下 使用点对点的无线承载效率较低 因此 非常需要能够提供点到多点 传送多媒体的发送机制的多媒体广播多播业务 m b m s m u l t i m e d i ab r o a d c a s ta n d m u l t i e a s ts e r v i c e 6 而数字喷泉码具备的低编译码复杂度 不固定码率 无需 反馈重传 适应时变信道和异质用户等优点 使其在这种大数据量的广播多播应 用中有着巨大的技术优势 非常适合上述场景的应用 因此 由d i 西t a lf o u n t a i n 4 北京邮电大学硕 匕学位论文 喷泉码的性能分析与设计 公司设计的系统r a p t o r 码已经被d v b h 标准和3 g p p 组织的m b m s 标准采用 成为这些标准的组成部分之一 1 3 喷泉码的应用 凭借着强大的技术优势 目前数字喷泉码在可靠多播传输 多源下载 无线 协作传输和深空通信等方面已得到了广泛的应用 而且正在被推广到越来越多的 其它应用领域 1 3 1 多播传输 数字喷泉码可用于诸如新软件产品发布等可靠多播环境中 假设有众多用户 要求在不同的时间下载同样的文件 组成文件的数据包通常分布在面向接收者的 一个或多个多播树中 而接收者仅仅需要从与其处在同一分支的多播树结点中下 载相关的数据包 这就避免了需要向网络中每个用户发送所有数据包而产生的开 销 将数字喷泉码的编码方法应用于多址传输中具有如下优点 7 1 1 由于每个 用户的数据损失率可能不同 如果众多用户同时要求从相同的数据源下载相同的 软件 就会导致网络阻塞 而利用数字喷泉码的编码方法就能避免重传和反馈 2 数字喷泉码的使用便于处理众多用户进行数据传输中遇到的问题 例如网 络传输中两个接收者除了最后一跳外具有相同的路径 但具有不同的下载速率 可将数据包在路径中以较高的速率发送 这样可保证较快的接收者有高的下载速 率 这时较慢的接收者会因为低的下载速率而丢弃一些数据包 由于接收到的每 个数据包都可用于数字喷泉码的译码 所以丢掉的数据包并不会影响较慢接收者 的接收 1 3 2 多源下载 利用数字喷泉码技术可以简化一个接收者的多源并行下载 每个数据源可利 用数字喷泉码独立产生无限长的编码包数据流 接收者从多个数据源下载时就不 会接收到相同的数据包 当接收者接收到足够的数据包后就可以关闭所有的连 接 而不需要关心这些数据包来自何方与每个数据源具有的数据损失率和发送速 率 以并行下载应用为例 假设用户从多台服务器同时下载同一文件 则为了避 免重复接收并减少下载时间用户必须在多台服务器之问适当协调以便从不同服 5 北京邮电大学硕 i 学位论文 喷泉码的性能分析与设计 务器以不同速度下载文件的不同部分 如果考虑到服务器可能加入或退出则问题 将更为复杂 而与此相对如果将喷泉码应用于并行下载应用中 则问题将大大简 化 各个服务器利用喷泉码生成编码分组 而用户从各个服务器以各自最快速度 下载这些编码分组 由于喷泉码的编码分组是彼此独立的随机生成的任何两个编 码分组发生重复的概率极低 因此有效避免了重复接收 显然在基于喷泉码的并 行下载解决方案中服务器之间不需要任何协调 服务器可以直接加入或退出而用 户需要的下载时间近乎最短 1 3 3无线协作传输 2 0 0 7 年 m o l i s c h 首次提出了数字喷泉码在协作多中继无线网络中的应用方 案 同时指出基于数字喷泉码的协作传输方法可以看作一种逼近多中继信道信息 论容量限的实用方案 8 与传统的编码技术相比 数字喷泉码的一个最大优点是 利用该种编码技术可将源信息包编码为一无限长编码包流 对于协作多中继无线 网络 在基于数字喷泉码的异步传输协议中 每个中继节点一旦对接收到的编码 包完成译码 该中继节点便开始向其目的节点传输通过译码所得的源数据包 由 于无线信道的广播特性和数字喷泉码无限长编码包流特点 这种传输方式不仅可 对目标节点提供有用的信息 而且也有助于未完成译码的中继节点进行其译码 1 3 4深空通信 深空通信 9 l 一般指地球与位于月球和月球以外的宇宙空间中的探测器之问 的通信 其最大特点是距离遥远 延时长 遥远的通信距离导致接收的信噪比 s n r 极低 这导致对编码增益 功率有效性 的要求非常高 而巨大的通信 时延 例如如火星到地球的平均单程传输时延就为7 6 0 s 使得反馈重传方式效 率很低 这导致通信可靠性主要依靠前向纠错编码来完成 因此研究高增益的信 道编码历来是深空通信的一个重要研究课题 喷泉码的诸多特点使得它在深空通信应用中具有明显的优势 首先 喷泉码 非固定码率的特性使得发送端可以根据通断时间 信道状况 能量状况等条件精 确而灵活地控制码率 其次 喷泉码低复杂度的编译码算法有利于深空探测器的 节能和简化设计 再次 喷泉码的纠删性能只与码长 数据包数量 和编码结构 有关 而与包长度无关 有利于更好地抵抗复杂深空电磁环境可能引发的长突发 错误 最后 数字喷泉方案良好的可扩展性和对异质用户支持有利于未来深空通 信网的构建和运行 因此 喷泉码能够满足深空通信对于信息传输可靠性和通信 质量的要求 在深空通信领域具有很大的应用潜力 6 北京邮电大学硕上学位论文喷泉码的性能分析与设计 1 4 喷泉码存在的问题 喷泉码采用的是随机编码算法 收端根据接收到的编码包重建的生成矩阵就 是一个随机矩阵 这样的矩阵不能保证一定满秩 因此喷泉码在译码时存在一定 的译码失败概率 通常采用两种措施来减少这种失败概率 一方面是采用较长的 码长 依靠大数定律来保证较稳定的译码表现 另一方面就是增加接收包的数量 译码开销 通过增加生成矩阵的满秩概率来提升译码成功率 另外 喷泉码 采用的译码算法是一种次优译码算法 9 l 它降低了复杂度 但也损失了一定的译 码成功率 由于喷泉码必须接收到足够的数据才能译码 因此码长太长意味着更 长的译码时延和更多的存储空间 不利于对时延要求严格的多媒体应用 而当接 收的数据包数量不足时 喷泉码译出的数据比例相当低 不利于它在高差错 低 冗余的恶劣信道环境中的应用 回顾l t 码和r a p t o r 码等经典喷泉码的设计过程可以发现 它们都是根据某 种启发式思想设计出来的 因此现有的喷泉码设计还不是最优的结果 存在改进 的余地 事实上 喷泉码的性能主要由编码结构和编译码算法所决定 对此人们 在喷泉码编码度分布设计 编译码算法的改进上付出了很大努力并取得了一定的 成果 但与传统信道编码领域相比 喷泉码技术无论在理论研究还是工程应用方 面都仍处于起步阶段 还存在诸多问题有待进一步研究 1 5 论文主要研究内容及章节安排 综上所述 数字喷泉码作为近年来新提出的一种信道编码方案 在通信网络 传输的各个领域都有着广阔的应用前景 但同时也存在着一些问题 喷泉码的设 计上仍有较大的改进余地 本论文以数字喷泉码作为主要研究对象 在分析其编 码结构和编译码性能的基础上提出了喷泉码预编码的一种设计方法 并对喷泉码 不等错误保护的策略进行了研究 为喷泉码从理论走向实际应用做出了一定的贡 献 论文共分五章 章节内容安排如下 论文第一章首先回顾了信道编码的发展历史 在此背景下数字喷泉码的提出 及其优势 然后介绍了喷泉码在各个领域的应用现状和其存在的问题 最后给出 了论文的主要研究内容和章节安排 第二章对本文的主要研究对象数字喷泉码的基本概念和编译码原理进行了 概述 首先对数字喷泉码的信道模型 定义和特点等相关内容做了简单介绍 然 后对三种典型的喷泉码 t 0 m a d o 码 l t 码和r a p t o r 码进行了重点介绍 详细 描述了它们的编译码算法 并对它们做出了一定的分析和讨论 以引出后面的章 7 北京邮电人学硕士学位论文 喷泉码的性能分析与设汁 节 第三章在前面介绍r a p t o r 码的基础上 重点对r a p t o r 码的编码构造进行分 析与设计 首先对设计所选用的预编码一l d p c 码进行了概述 介绍了其定义 表示 p e g 法构造校验矩阵及编译码算法等相关内容 然后给出了整个r a p t o r 码的联合设计与实现 并对设计方案进行了仿真 仿真结果表明 所设计的r a p t o r 码在中间符号译码开销y 1 1 5 时 误码率小于l o 一 具备了良好的性能 对实 际设计与应用具有一定的指导意义 第四章从某些多媒体应用中对数据不等错误保护的需求出发 以喷泉码中比 较具有代表性的l t 码为例 对喷泉码不等错误保护的实现方案做了一定的分析 与研究 并提出了相应的改进方法 仿真表明 当接收端收到较少的编码符号时 改进的u e p 方法比原有的方案表现出了更好的性能 能够更好地满足现有多媒 体传输等应用对不等错误保护的要求 第五章对论文的主要工作进行了总结 并提出了对今后工作的展望 8 北京邮电人学硕士学位论文 喷泉码的性能分析与设计 2 1 引言 第二章数字喷泉码概述 作为这篇论文的研究基础 本章主要对数字喷泉码的基本概念和编译码原理 进行了概述 首先对数字喷泉码的信道模型 定义和特点等相关内容做了简单介 绍 然后对三种典型的喷泉码 t o m a d o 码 l t 码和r a p t o r 码进行了重点介绍 详细描述了它们的编译码算法 并对它们做出了一定的分析和讨论 以引出后面 的章节 2 2 数字喷泉码的基本概念 2 2 1二进制删除信道模型 喷泉码是定义在删除信道模型f l o 上的前向纠错编码技术 删除信道的定义是 指待传输信号在通过该信道后 或者能确知为原信号 或以删除概率p 被判决为 不确定 即 被删除 图2 1 为二进制删除信道 b i n a r ye r a s u r ec h a n n e l b e c 模型 其输入为二进制变量0 l 输出为输入的0 1 或者为某个删除值x 且通常传输过程中不同输入被删除的概率相同 oo x 图2 1 二进制删除信道 b e c 模型 在实际的通信系统中并不存在物理上的删除信道 删除信道模型更多还是在 通信理论研究中被作为一种理想的信道模型使用 随着通信技术的发展 分组交 9 北京邮电大学硕上学位论文 喷泉码的性能分析与设计 换通信网络的出现 带检错机制的分组交换信道可以被看作是天然的删除信道 通过计算每个分组 或数据包 的检错校验和 接收端很容易判决出所收到数据 分组的正确与否 若忽略校验和的漏检概率 则可以把分组交换信道等效成一个 二进制删除信道 此时 在二进制删除信道中所传输的不再是单个的比特 而是 完整的数据分组 而信道的删除概率p 等于分组交换信道的总误包率 包含丢包 率 2 2 2数字喷泉码的相关定义 喷泉码定义在一个更加广义的逻辑二进制删除信道上 其既可以对应通信系 统中某一具体物理通信链路 也可以将整个通信网络中整条端到端连接都等效为 一个逻辑信道 所谓喷泉码 是指该种编码可以由尼个原始数据符号生成任意数 量的编码符号 而接收方只要收到其中任意m 个编码符号 即可通过译码以高概 率成功恢复全部原始数据符号 一般情况下 肌略大k 从而引入一定的译码冗 余占 定义为s m k 一1 也即m k 1 f 可以看到 上述编码过程就如同源 源不断产生水滴 编码符号 的喷泉 编码器 而我们只要用杯子 译码器 接收足够数量的水滴 即可达到饮用 成功译码 的目的 正因如此 该种编 码被称为喷泉码 显然 喷泉码的设计需要考虑两方面的问题 一方面 应该尽量减小译码冗 余g 使其趋近于o 另一方面 应该尽量减小编译码复杂度 理想情况下 应 该使生成每个编码符号需要的运算量是一个与露无关的常数 而由m 个编码符号 成功恢复出k 个原始数据符号需要的运算量是一个关于k 的线性函数 无码率码 l l j r a t e l e s sc o d e 是一种为了解决数据在网络中重传导致信道容 量浪费以及不能使数据实时可靠传输的基础上发展起来的 它能很好地适应信道 的多变性 无码率码对于产生编码符号的个数是没有限制的 并且接收端可以从 接收到的任意比源符号多一些的编码符号中恢复出源符号 不管信道模型如何 发送端总能产生足够的编码符号通过信道 便接收端接收到足够的编码符号成功 恢复出源符号 以l t 码为代表的无码率喷泉码很好地实现了数字喷泉技术的原 始构想 l t 码通过精心设计的随机编码方式 能够持续产生任意数量的编码符 号 而收到的编码符号只要达到一定比例 原始发送数据能被正确恢复的概率就 充分大 i o 北京邮电人学硕士学位论文喷泉码的性能分析与设计 2 3 几种典型喷泉码的介绍 本节以几种典型的喷泉码为代表 介绍了它们的编译码算法实现过程 并对 它们进行了简要分析 以引出后面的章节 2 3 1t o r n a d o 码 1 9 9 5 年s p i e l m a n 在低密度校验码的基础上提出的基于规则双向图的扩展 码 能实现线性时间编译码 人们经研究发现在非规则图上构造的低密度校验码 性能要比在规则图上构造的好得多 于是j w b y e r s m l u b y 等人在扩展码的基 础上 于1 9 9 8 年提出了在非规则图上构造的 编译码算法更为简便的t o r n a d o 码 1 2 1 t o m a d o 码是喷泉码的前身 其最大的优点是具有线性编译码时间 由于其 编译码的高效性 曾最先被推荐为数字喷泉的一种编码方案 9 2 3 1 1t o r n a d o 码的编码 i 传统分组删除码 i 卜 l i l l o 输入符号 校验符号 图2 2t o r n a d o 码编码示意图 t o m a d o 码是一种层叠式的编码 其编码原理如图2 2 所示 图中除最后一 级外每一列的节点数从左至右呈等比数列递减 比例为 从左起第一列的n 个 节点表示原始输入符号 从第二列起每个节点为校验符号 其值为前一列随机选 出的若干节点的异或和 依次从左至右级联编码 该过程一直持续到当所在列的 北京邮i 乜人学硕上学位论文 喷泉码的性能分析与设计 节点数降低至第一列节点数量的方根量级时 使用一个码率为l 一 的传统分组 删除码进行最后一级编码 t o r n a d o 码属于系统码 编码符号中包含h 个输入符号 由图2 2 我们可以 得出 编码符号中的校验符号数为 耖川m 堋一 s 等笋 等 删柏协t 因此t o r n a d o 码的总体码率为 r 一 1 一口 2 2 z z 1 一 2 3 1 2t o r n a d o 码的译码 t o r n a d o 码的译码算法是这样的 在译码的每一步 寻找所有左连接点中有 且仅有一个节点丢失的右节点 并将该右节点的值与所有其他左节点的值进行异 或后赋给丢失的节点 迭代上述过程直至左侧节点的值全部被恢复 如果进行到 某一步时找不到这样的右节点 而左节点值尚未被全部恢复 则译码过程宣告失 败 此译码过程的复杂度是线性的 9 2 3 1 3t o r n a d o 码分析 t o r n a d o 码通过采用级联稀疏图码和传统线性删除码的编码方式 有效利用 了传统线性删除码的纠错能力并同时降低了编译码的复杂度 从上面对编译码过 程的描述可以看出t o r n a d o 码的设计难点在于对每一级二分图的分析与设计 因 为这决定了译码过程能否成功 从而直接关系到其纠删性能 对此 文献 1 2 中给 出了保证译码成功的具体构造算法及严密的数学证明 与传统的r s 码相比 t o r n a d o 码将编译码算法复杂度与数据包数j j 的关系 从平方量级降到了线性量级 这种进步所付出的代价是其纠错能力比r s 码稍差 一些 并且 虽然t o r n a d o 码具有高效的编译码算法 它仍然是一种固定码率的 编码 因此并不能真正实现发端的 喷泉 特性 由于不能实时无限制地改变码 率 使得固定码率喷泉码存在纠错的门限 一旦信道删除概率低于门限即无法成 功恢复原始数据 接收用户也无法实现在任意时刻加入接收队列 接收到足够的 数据包从而成功译码 2 3 2l t 码 1 2 北京邮电大学硕士学位论文喷泉码的性能分析与设计 l t l u b yt r a n s f o r m 码 1 3 是第一种真j 下意义上的可变码率喷泉码 它可以 生成任意长的一个编码数据流 从而更好地适应信道状况的变化以及接收用户的 切换 其编译码方法简单 且译码开销和编译码复杂度都相对较小 2 3 2 il t 码的编码 l t 码的设计核心在于找到一个好的维度分布 它对编译码的性能有很大的 影响 所谓维度分布是指任一编码输出符号具有维度d 即有d 个邻居节点 的 概率分布 文献 1 3 1 中提出了一种称为r o b u s t s o l i t o nd i s t r i b u t i o n r s d 的维度分 布 其表达式如下 删2 赫 公式 2 3 中 p 0 f d 1 k l d p 1 2 3 d l 2 4 d 2 k 瓦r d 1 生r l出 r l n r 6 d 一k kr 0 d 后 尺 1 k 2 5 其中 k 为输入符号数 万为可接受的解码失败概率 r c 1 n k 万 尼 c 为合适的常数 求得维度分布后 按如下方法生成编码符号 如图2 3 所示 1 根据维度分布随机地选取编码符号的度数d 2 从k 个输入符号中均匀地随机选取d 个不同的输入符号做为编码符号的 邻居节点 3 对这d 个输入符号做异或运算 得到一个编码符号的值 北京邮电大学硕上学位论文喷泉码的性能分析0 设计 卜 7 7 扛3 型 r 输入符号 编码符号 图2 3l t 码编码示意图 理论上 生成的编码符号可以无限多次的通过信道传输 l t 码生成的编码 符号之间是相互独立的 这使得它的编码符号数目是不固定的 相应码率也不是 固定的 l t 码通过其随机编码方式 成功实现了码率的实时任意调节 2 3 2 2l t 码的译码 l t 码采用了置信传播 b e l i e fp r o p a g a t i o n b p 的迭代译码算法替代了类 似矩阵求逆的最大似然译码算法 在译码的每一步 b p 算法都利用部分已经译 码的数据包在剩余的编码包中解出一部分新的数据 如此反复 直至所有信息都 被恢复 采用这种译码方式的好处是可以大大降低算法的复杂度 译码的具体算 法如下 1 接收一定数量的编码符号 根据编码符号与输入符号的对应关系建立双 向图 2 任意选取一个度为1 的编码符号 如果不存在这样的编码符号 则译码 停止 如果存在 即可恢复与该编码符号相连的唯一输入符号 3 对于已经恢复的输入符号 将与其相连的所有其他编码符号分别进行异 或 将计算结果取代原编码符号的值 然后在双向图中删除它们之间的 连接关系 从而使得这些编码符号的度数减1 4 重复步骤2 和3 直至译码停止 如果所有输入符号都已经恢复 则译 码成功 否则 译码失败 则必须接收更多的编码符号才能继续译码 图2 4 给出了一个译码示例 为了简单说明问题 这里的输入符号和编码符 号都只有一个比特 如图2 4 所示 这里有三个输入符号 顶层节点 和四个编 码符号 底层节点 其中编码符号的初始值为 f 2 f 3 t 4 1 0 1