（通信与信息系统专业论文）基于喷泉码的导航电文发播研究.pdf

摘要 掣iii1 2 il10111111111iiiiiiiiilliiillll67351y 2 0 全球卫星导航系统在各领域得到越来越广泛的应用。为了提高卫星导航系统 的定位成功率，尤其是在特殊深衰落环境中的定位成功率，需要研究新的导航电 文的发播结构和编码技术。本文主要研究深衰落环境中，卫星导航电文的发播策 略与编码方案。主要工作如下： 1 、讨论了卫星阴影遮挡导致的深衰落环境中的信道建模，在物理层将其建 模为a w g n 信道，在链路层将其建模为删除信道；对l t 码在删除信道和a w g n 信道下进行了仿真。 2 、研究了在a w g n 信道下的r a p t o r 短码的码字构造和译码方案，通过对预 编码的不同码率和码字构造方法的选取，并基于性能仿真结果给出了可适用于导 航深衰落环境下的喷泉码字及其编译码方案。 3 、对深衰落环境中导航系统的定位难题进行了研究，提出了基于喷泉码的电 文发播解决方案并进行了性能分析。结果表明，该方案与传统发播方案相比，在 不同信道删除概率下有更高的定位成功率，提高了系统的鲁棒性。 4 、针对所提出的电文喷泉编码方案，给出了喷泉编码矩阵传递问题的解决方 案。分析表明，相比传统方法该方案所增加的冗余更少，实用性更强。 关键字：卫星导航系统喷泉码 r a p t o r 码电文发播 a b s t r a c t g n s s ( g l o b a ln a v i g a t i o ns a t e l l i t es y s t e m ) h a sf o u n dw i d ea p p l i c a t i o n s i n v a r i o u sa r e a s i no r d e rt oe n h a n c et h er o b u s t n e s so fn a v i g a t i o ns y s t e m ，e s p e c i a l l yo n d e 印f a d i n gc h a n n e l s ，i ti sn e c e s s a r yt od e s i g na p p l i c a b l en a v i g a t i o nm e s s a g es t r u c t u r e a n dt oc h o o s ea p p r o p r i a t ec h a n n e lc o d i n gm e t h o d t i l i st h e s i sf o c u s e so nt h em e s s a g e b r o a d c a s t i n gb a s e do nf o u n t a i nc o d e s 1 1 l em a i nc o n t r i b u t i o n sa l ea sf o l l o w s ： 1 ad i s c u s s i o ni sm a d eo nt h ec h a n n e lm o d e l i n gi nd e e pf a d i n ge n v i r o n m e n t c a u s e db yt h es h a d o w i n g n ec h a n n e li sm o d e l e da sa w g nc h a n n e lo nt h ep h y s i c a l l a y e ra n d e r a s u r ec h a n n e lo nt h ed a t al i n kl a y e rr e s p e c t i v e l y t h e nt h es i m u l a t i o n so fl t c o d e so nb o t hc h a n n e lm o d e l sa r ec o n d u c t e d 2 r e s e a r c h e so nt h ec o d e - w o r dc o n s t r u c t i o na n dd e c o d i n gs c h e m eo fs h o r t r a p t o rc o d ea r em a d e b yt h ec o m p a r i s o no fd i f f e r e n tc o d er a t ea n dc o d e w o r d c o n s t r u c t i o no ft h ep r e - c o d e s ，t h ed e l i b e r a t e l yc h o s e nf o u n t a i n - c o d e ss o l u t i o ni s p r e s e n t e do nt h eb a s i so fs i m u l a t i o nr e s u l t si nd e e pf a d i n gs i t u a t i o n s 3 a i m i n ga tt h ep o s i t i o n i n gp r o b l e mi nn a v i g a t i o nd e e pf a d i n ge n v i r o n m e n t ，a n e wm e s s a g eb r o a d c a s t i n gs o l u t i o nb a s e do nf o u n t a i nc o d ei sp r o p o s e da n dt h e p e r f o r m a n c ea n a l y s i si sm a d e 硒e r e s u l t sd e m o n s t r a t et h a tt h i ss o l u t i o np r o v i d eh i g h e r p o s i t i o n i n gr a t et h a nt r a d i t i o n a lm e t h o di nd i f f e r e n te r a s u r ep r o b a b i l i t i e s 4 w i t ht h ef o u n t a i n - c o d i n g - b a s e dm e s s a g eb r o a d c a s t i n gs c h e m em e n t i o n e d a b o v e ，as o l u t i o nf o rt h et r a n s f e r r i n gp r o b l e mo ff o u n t a i n - c o d e sm a t r i xi sp r o p o s e d a n a l y s i sr e s u l t sd e m o n s t r a t et h a tt h ep r o p o s e dm e t h o dn e e d sf e w e rr e d u n d a n c i e sa n d h a sb e t t e ru s a b i l i t yt h a nt r a d i t i o n a lo n e s k e y w o r d s ：g n s s f o u n t a i nc o d e s r a p t o rc o d e sm e s s a g eb r o a d c a s t i n g 第一章绪论 第一章绪论 1 1 课题研究背景和意义 全球卫星导航系统( g n s s ) 是当今世界国家综合国力及科学技术发展水平的重 要标志，它已经进入人们的日常生活中并在各个领域发挥着重要的作用，与社会 发展和经济建设更是息息相关。导航技术是一种为个人或运载体航行时提供连续、 安全和可靠服务的技术，其基本作用是引导飞机、船舶、车辆等运载体和个人， 精确地沿着所选定的路线，安全准时地到达目的地。卫星导航系统最早出现于2 0 世纪9 0 年代，而美国的全球定位系统( g p s ) 是世界上第一个实现全球覆盖的卫星 定位系统，它在全球范围内为数量不限的海陆空用户提供全天候的、连续精确的 位置、速度和时间信息，为美国带来了巨大的军事和经济利益。世界上第二个卫 星导航系统是俄罗斯的g l o n a s s 系统，但其影响远逊于g p s 。之后，欧洲联盟 吸取了g p s 系统的建设经验，并利用最新技术发展成果，尤其是g p s 现代化中的 科技成果，发展了自己的卫星导航系统- - - - g a l i l e o 系统，其技术起点高，定位精 度高，并兼容现有的g p s 卫星导航系统。 到目前为止，我国绝大多数的定位应用还采用着美国的g p s 导航定位系统， 如果一旦发生任何紧急情况，我国的用户就很难得到可靠的定位保证。而且g p s 高精度定位的部分还在保密范围之内，用户并不能广泛自由地使用，因此在卫星 导航系统市场快速发展和要求日益提高，各种卫星导航系统之间潜在竞争越来越 激烈的今天，我国发展和完善独立自主的全球卫星导航系统迫在眉睫。 事实上，自1 9 9 4 年起我国已经投入大量的资金和人力，积极进行北斗卫星导 航系统的研究，目标是建成独立自主、开放兼容、技术先进、稳定可靠并覆盖全 球的北斗卫星导航系统，以促进卫星导航产业链形成，建成完善的卫星导航的应 用产业支撑、推广和保障体系，从而推动卫星导航在国民经济以及社会各行业的 广泛应用。 2 0 0 3 年6 月1 日，我国自主研发的北斗一代系统正式投入使用。它采用双星 定位原理，由地面中心控制系统负责解算，为用户提供三维定位服务。其原理决 定了这种工作方式存在设备体积大、测距精度低、隐蔽性弱的缺点。为此，我国 正加紧发展独立自主的第二代卫星导航系统“北斗二代”( c o m p a s s ) 卫星导航系统， c o m p a s s 将和g p s ，g a l i l e o 及g l o n a s s 一道成为世界主流的卫星导航系统，并 能够独立或与其它卫星导航系统共同向陆地、海洋和天空用户提供连续、稳定和 高精度定位、导航和授时( n 汀) 服务。 2基于喷泉码的导航电文发播研究 但是，目前主流的全球卫星导航系统普遍难以满足在一些特殊环境中的特殊 要求，如卫星存在阴影遮蔽而导致深衰落的信道环境里的定位要求。全球导航定 位系统的技术实现依赖于卫星向接收机发射定位数据信息的完整性和准确性，这 些信息以电文为载体向所有接收机以广播的方式发送。上述深衰落恶劣的信道环 境将导致接收端无法收集到足够多定位数据以解算位置信息。因此，导航电文的 检错与纠错能力是未来卫星导航信号设计的关键之一。 针对这个问题，各国的卫星导航系统在进行电文信号设计时，均考虑了信道 纠错编码。采用纠错码对导航数据进行信道编码，不仅可对发送数据进行保护， 同时可以提高系统干扰容限，改善接收机性能。但是目前g p s 和g a l i l e o 系统中的 纠检错机制有很大局限性。一般仅以保护物理层信息比特为出发点去进行信息码 字到编码码字的映射，从而为数据在信道中的传输提供可靠性保证【8 】，而没有考虑 在实际通信中以分组( 帧、数据包) 为单位的发播结构。 导航电文发送时具有固定的电文发播结构，需对不同时效性数据定义不同的 发播周期，且需要慎重安排不同时效性的数据在帧结构中的位置分布。由于这种 以帧为单位的发播，接收端需要在本地生成同步码对接收数据进行滑动相关以搜 索分组的起始位置，因此这种发播结构必然会导致分组丢失。在一般应用和接收 机低速运动情况下，由于卫星导航系统中卫星电文的发播频率高，系统可以容忍 这种丢失，一般只会引起可接受的解算时间的延迟。但是，在深衰落情况下，这 种影响就不能忽略了。比如卫星受到阴影遮挡影响，导航通信链路误码率高、易 中断，造成接收端丢帧率很高，有些对时效性要求很高的分组无法满足即时接收 的要求。因此结合发播结构的信道编码的研究具有重要意义。 另一方面，在很多广播通信网络中，都会采用某些特殊手段来保证分组的可 靠接收，例如自动请求重传( 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 l a s u r ec o r r e c t i o n ，f e c ) 编码方法，喷 泉编码被认为是极其适合于广播信道的一种前向纠删编码方式，它可以在无需反 馈信道的情况下，提供一种高效可靠的删除恢复机制，避免频繁的重传，缩短文 件成功接收传输时间，提高了传输效率，理论上非常适合于卫星广播通信的特殊 环境。在本论文涉及到的深衰落的环境中，将导航电文的发播与喷泉码结合起来， 能够巧妙避开a r q 机制在卫星广播通信应用中的瓶颈。因此研究喷泉码在卫星导 航信道中的应用有着重要的意义。 第一章绪论 1 2 喷泉码的国内外研究和发展现状 数字喷泉码是一种与码率无关的随机编码方式，它可以有效地解决“反馈风 暴 问题，并且可以保证每次发送的信息对接收节点来说均是有用信息。j o h nb y e r s 及m i c h a e ll u b y 等人于1 9 9 8 年首次提出了数字喷泉( d i g i t a lf o u n t i a n ) 的概念， 它是针对大规模数据分发和可靠广播的应用特点而提出的一种理想的解决方案。 2 0 0 2 年，m i c h a e ll u b y 最先为这种概念上的喷泉码找到了一种具有线性编译码复 杂度的实现方式，称为l t 码( l u b yt r a n s f o 肌c 0 d e s ) 【1 3 】。m a c k a y 和s h o k r o l l a h i 在2 0 0 3 2 0 0 5 年间逐步将其成熟完善【1 4 1 1 1 5 】，并迅速被应用到实际工程中，尤其之 后s h o k r o l l a h i 又对其进行进一步的增加预编码的改进，使编译码复杂度进一步减 小，并起名r a p t o r 码，它是目前实际应用最为广泛的喷泉码的具体实现，之后 s h o k r o l l a h i 专门成立了d f ( d i g i t a lf o u n t a i n ) 公司，专门提供喷泉码尤其是r a p t o r 码的服务支持。 在理论日渐完善的同时，数字喷泉码日益受到产业界的关注，得到了越来越， 广泛的应用，主要的应用发展可以概括如下l l7 l ： ( 1 ) 在长时延的国际互联网、广域网、卫星网上进行大型文件的高速传输。以 r s 码为代表的前向纠错编码，是以保护小块数据的原则和要求设计的，主要对受量， 到破坏的多个比特或单个比特进行检测和校正。而喷泉码意在保护大型文件，而 且其编译码速度非常快。由于摒弃了反向链路，大大减小了影响吞吐量的时延， 采用喷泉编码方式的大文件数据能够在国际互联网和卫星网上以接近网络带宽的， 速度传输。 ( 2 ) 在无线网、移动网提供优质的流媒体点播或广播服务。利用喷泉码技术来 处理无线移动网络中最棘手的流媒体音频、视频、游戏、m p 3 文件等，可以提供 质量完善的流媒体点播或广播服务。 ( 3 ) 在3 g 移动网、电信组播网、数字电视广播网及卫星广播系统中提供无需 反馈信道的可靠数据广播。由于无需反馈，用户数量的增长对发送方来没有任何 影响，发送方可以服务于任意数量的用户，大大增加了用户容量。 2 0 0 5 年，d f 公司先后与美国卫星广播公司s i r i u s 公司以及手机厂商诺基亚公 司签署协议，向它们的后续产品提供数字喷泉编码技术的支持。另外，d f 公司设 计的系统r a p t o r 码已经被d v b h 标准和3 g p p 组织的多媒体广播与多播业务 ( m b m s ) 标准采纳【1 6 1 ，该公司的d i 西m lf o u n t a i nr a p t o rf e c 技术已成为3 g p p 流式 文件下载服务的m b m s 标准的一部分。 r a p t o r 码是喷泉编码的典型代表，由于它能即时生成无限的数据包，在没有 反馈信道的情况下也能保证可靠通信，减小了通信的传输延时，因此被认为是卫 4基于喷泉码的导航电文发播研究 星广播组播服务和电视信号传输环境中理想的信道编码技术，也是未来卫星宽带 互联网【9 】上进行大型文件传输和卫星移动网络中数据业务传输的最理想差错控制 手段。因此对卫星导航通信信道中的喷泉码编译码技术进行深入的研究和分析， 构造符合此信道特点的、具有较低复杂度的信道编码，为新型的卫星导航定位系 统体制提供技术支撑具有重要的意义。 1 3 论文的主要工作和内容安排 本文主要针对卫星阴影遮挡而导致深度衰落影响严重的场合，结合喷泉码的 研究，设计新型的导航定位系统电文发播策略。本文主要章节内容安排如下： 第一章，介绍当前主要的全球卫星导航系统和喷泉编码的发展现状。阐述本 文的研究背景和意义。最后给出本文章节内容安排。 第二章，研究导航电文发播过程中涉及到的系统架构，并对数字喷泉码的基 本原理进行简单介绍。 第三章，研究数字喷泉纠错编码方式，提出其在卫星导航广播信道中的应用 方案。重点讨论r a p t o r 码在a w g n 信道建模时的译码算法，然后针对卫星广播信 道的特性，分析了r a p t o r 码的预编码构造方式和码率的选取原则，最后给出相应 的方案，并对其进行性能仿真和分析。 第四章，针对深衰落信道特性造成的传统导航系统无法成功定位的问题，给 出一种基于喷泉编码的鲁棒性电文发播解决方案。在该电文发播的喷泉编码结构 确定后，又据此提出了喷泉编码收发双方编码矩阵传递方案。最后结合b o c 调制 的思想，完成了整个卫星发送端的电文发播过程。 第二章北斗卫星导航系统相关技术和喷泉码原理 5 第二章卫星导航系统相关技术和喷泉码原理 本文重点研究喷泉编码在卫星导航系统中的应用。喷泉码是一种新型的针对 “反馈风暴 和“反馈破裂 问题而提出的信道编码技术。本章首先讨论卫 星导航系统的系统架构，定位算法，特殊的频谱处理等技术，然后阐述了喷泉码 的基本原理。 2 1 1 系统架构 2 1 卫星导航系统架构及相关技术 我们假定以北斗( c o m p a s s ) - 1 星导航系统为平台研究发播策略和编码技术。系 统由空间端、地面端和用户端三部分组成，空间端由5 颗静止轨道卫星和3 0 颗非 静止轨道卫星组成其中包括2 7 颗平均分布在倾角为5 5 度的三个平面上、轨 道高度为2 1 5 0 0 公里的中轨道( m e o ) 卫星和3 颗倾斜同步( i g s o ) 卫星。地面端包括 主控站、注入站和监测站等若干个地面站；用户端由北斗用户终端以及与其它卫甓i 星导航系统兼容的终端组成。 总体系统建设规划在2 0 2 0 年左右建成覆盖全球的北斗卫星导航系统( 5 颗 g e o + 3 颗i g s o + 2 7 颗m e o 组成) 。信号设计使用b o c ( b i n a r yo f f s i t ec a r d e r ) 调制 方式，导航电文将发播在三个频段，分别为b 1 ：1 5 5 9 0 5 2 1 5 9 1 7 8 8 m h z ，b 2 ： 1 1 6 6 2 2 - 1 2 1 7 - 3 7 m h z ，b 3 ：1 2 5 0 6 l8 - 1 2 8 6 4 2 3 m h z 。 2 1 2 定位原理 假定导航系统定位的原理与g p s 相同，利用空间几何三点定位原理。为了消 除时间精度引入的误差，北斗二代系统在技术上采取四星定位。定位大致过程可 描述如下峨 首先，卫星导航系统向所有接收终端发送导航信息，接收机跟踪、选择卫星， 接收选定卫星的信号。 其次，根据卫星广播的星历信息解读、解算出第f 颗卫星的准确位置 s i = ( 而，y t ，乃) ； 然后，根据测量卫星信号的延迟来确定伪距( p r ) ，解算出用户与第f 颗卫星之 间的相对距离； 6基于喷泉码的导航电文发播研究 最后，根据以上步骤得到的卫星位置和伪距计算用户的三维位置 u = ( 毛，儿，乙) 。 由上述描述可知，定位问题可以归结为两个关键步骤：1 ) 确定卫星的位置； 2 ) 解算用户位置。 1 ) 卫星位置坐标计算( 利用星历信息) ： 星历信息可以由6 个轨道的参数描述。在某特定时刻瞬间( 称为历元时刻或 星历时刻) 卫星真实位置和速度矢量可由6 个参考轨道参数精确描述。当时间从 参考时刻推移，卫星的真实位置将偏离由这6 个积分常数或参数描述的位置和速 度。因此要描述任意时刻的卫星位置和速度矢量不仅需要基本的6 个轨道参数， 还需要历元时刻等时钟校改参数。 2 ) 用户位置的解算： 要解算用户位置首先要测量卫星到用户的距离。用户与卫星的距离r 可以通过 测量由卫星产生的测距码从卫星传送到用户接收机天线所需的传播时间来计算。 即： ，= c a t = c ( 瓦一瓦) ( 2 - 1 ) 但是卫星与接收机的距离，的测定与时间量有关，而用户便携接收机一般不可 能有十分准确的时钟，因而测出的距离也不准确，这种距离称为伪距( p r ) ，用p 表 示。它包含了：l ，卫星到接收机的几何距离，；2 ，系统时钟与用户时钟之间的差 异造成的偏移。利用伪距获得的信息可以通过进一步校正来接近真实距离，。距离 ，与伪距p 的关系如下： p = d ( 正+ 厶) 一正】 = c ( 瓦一正) + c 乙 ( 2 - 2 ) = r + c f _ 其中，乙表示接收机时钟互与系统时钟瓦之间的偏移。 得到卫星与用户的距离关系后，用户位置坐标的解算可建模如下，假设已知 卫星的大地坐标s = ( 黾，弘，乙) ( 由卫星的星历数据计算) ，用户到卫星的距离，求 用户的位置坐标u = ( 毛，儿，乙) 。显然，卫星到接收机的几何距离可表示为： ，爿l s u l i 又结合式( 2 2 ) 可得：p 爿l s - u0 + 吮。 再由四颗卫星定位的原理，可得到非线性方程组： n = ( 而一毛) 2 + ( 朔一儿) 。+ ( z l 一乙) 2 + c 乙 p 2 - 、f ! 兰二兰! ：二! 兰二兰! ：! 三! 二兰! ：+ 矾 ( 2 3 ) 庙= ( 而一毛) 2 + ( 弘一儿) 2 + ( 勿一乙) 2 + 矾 矶= ( 知一毛) 2 + ( 弘一儿) 2 + ( z 4 一毛) 2 + 吒 第二章北斗卫星导航系统相关技术和喷泉码原理 7 利用基于线性化的迭代技术求解上述非线性方程组，可解算出得毛，儿，乞，乙， 从而得到用户的位置坐标u = ( 毛，儿，乙) 。 2 1 3b o c 调制技术 为了在频谱资源有限、已发播信号频谱极其拥挤的导航频段发播北斗导航信 号，在将信号上变频发射之前采用了b o c ( b i n a r yo f f s e tc a r d e r ) 调制技术。b o c 调制也, q - 进制偏置载波调制f 3 l ，是一种新的载波调制方式。它的基本原理是在原 有的b p s k 调制基础上，增加一个二进制副载波( 由正弦或余弦型符号函数 s g n ( s i n ( t ) ) 或s g n ( c o s ( t ) ) 构成) ，使得其功率谱的主瓣分裂成对称的两部分，随着副 载波频率与扩频码速率比例的变化，两个分裂主瓣之间的距离也发生变化。这种 关系可以表示为b o c ( m ， ) 的形式，其中m 表示副载波频率，刀表示扩频码速率， 具体数值分别为1 0 2 3 m h z 的m 倍和刀倍。 标准b o c 调制过程是将基带扩频信号乘以一个实数形式的方波副载波信号， 即： s o ) = x ( t ) s g n ( s i n ( 2 7 r f , t ) ) ( 2 - 4 ) 其中x 9 ) 为数据信号，s g n ( s i n ( 2 z r f g ) ) 为正弦方波副载波，其频谱由无限个n 次谐波组成，因为其中1 次谐波幅值最大。副载波的频谱可近似于正弦信号频谱， 由左右两部分冲击函数6 ( 正) 组成。时域相乘的b o c 调制过程在频域上表现为 卷积运算，相当于将x ( ，) 的频谱x ( 门搬移到频域z 处，从而实现频谱分裂。如 下式描述： 1 s ( 力亡x ( 门陋( f - z ) 一艿( 厂+ z ) 】 ( 2 - 5 ) z 兀 其中6 ( 厂) 为单位冲击函数，符号“幸”表示卷积运算。 由于国际电联给导航频段分配的频谱有限，抢先发播的g p s 和g a l i l e o 信号已 经使得卫星导航频段十分拥挤，而b o c 调制的频谱分离特性使得新型卫星系统在 播发自己的卫星导航信号时，能有效避开g p s 和g a l i l e o 信号，减少相互间干扰。 另外相比一般m p s k 而言，b o c 调制具有更高的码跟踪精度和抗多径的能力。g p s 和g a l i l e o 导航系统在b o c 调制基础上，又衍生了很多演进型b o c 调制技术，并 将其用于自己导航信号的发播中，最具代表性的是m b o c 调制和a i t b o c 调制。 下面对其进行简单介绍。 舢t b o c ( a l t e r n a t i v eb o c ) 是g a l i l e o 系统进行信号体制设计时发展的一种新 的调制方式【6 1 。调制过程为： s ( ，) = x ( ，) ( s 印( c o s ( 2 万正t ) ) + js g n ( s i n ( 2 t r f g ) ) ) ( 2 6 ) 8 基于喷泉码的导航电文发播研究 其中副载波是复指数形式： 易= c r + a = s 驴( c o s ( 2 7 r f , t ) ) + js g n ( s i n ( 2 7 r f g ) ) ( 2 - 7 ) 观察副载波形式可得出结论：s g n ( c o s ( 2 z r f g ) ) + j s g n ( s i n ( 2 7 r f ) ) 可近似于 c o s ( 2 n f ) + js i n ( 2 z r f , t ) = e 2 ，所以a l t b o c 调制后信号的频谱不再分裂为两部 分而是整体单侧偏移，即频域表示为： l s ( 力二l x ( s o 6 ( 一正) ( 2 - 8 ) z 石 与b o c 调制相比，a i t b o c 调制还有很多优点：首先，砧t b o c 调制后信号频 谱的单侧偏移特性，使得调制信号的上下边带可以分别承载不同的信息，从而可 更有效地利用频带资源。其次，接收灵活。比如g a l i l e o 信号在接收端，既可以将 e 5 a 、e 5 b 频段信号作为整体，按照a l t b o c 接收技术进行处理，也可以对各子频 段信号单独进行接收，等效于传统的q p s k 信号接收： m b o c ( m u l t i p l e x e db i n a r yo f f s e tc a r r i e r ) 调制信号功率谱由两个或多个b o c 调制信号功率谱的加权组成，它实质是频域上的定义 4 1 。m b o c 调制是为了满足 g a l i l e o 系统和g p s 系统兼容与互操作性而产生的，具体的时域实现有t m b o c ( t i m e m u l t i p l e x e db o c ) 和c b o c ( c o m p o s i t eb o c ) 两种方式。g a l i l e o 系统和g p s 系统的兼容与互操作工作组经过讨论，决定以b o c ( ，1 ) 调制作为基础，同时开发 新型的调制方式，在2 0 0 7 年6 月二者达成一致，将m b o c ( 6 ，l ，l 1 1 ) 作为g p s 和 g a l i l e o 系统的互操作导航信号调制方式。因此在发播我国北斗信号时必须也要考 虑与g p s 系统和g a l i l e o 系统的兼容与互操作性问题，将m b o c 调制作为互操作 信号的备选调制方式之一。 2 2 喷泉码基本原理 喷泉码是一种在广播删除信道下提出的性能优越的稀疏矩阵码。数据在链路 层或网络层等高层传输时，以帧或者包为单位，每个数据包或者被接收端无差错 的接收，或者收不到，因此这个过程需要采用反馈信道告知哪些数据包丢失而需 要重新传送。在广播通信中也是这样，发送端需要对许多接收端发送数据，一旦 有一个接收方有一个数据包丢失而没有成功接收到，就要求发送端向所有接收端 重新发送此数据包，而大部分接收端可能已经接收到了该数据包，因此十分浪费 资源。另外这种方式也会造成信道拥塞，比如当用户发送的反馈信息占据了绝大 多数网络资源时，正常的通信就很难顺利进行，这被称作“反馈风暴”。在这种 情况下，重传方式完全不起作用。深衰落的卫星导航信道也是一种典型的广播信 道，并且由于卫星通信信道链路长，不存在反馈链路，所以接收端无法将接收状 况告知发送端，这被称作“反馈破裂”。 第二章北斗卫星导航系统相关技术和喷泉码原理 9 因此找到一种编码方式用于无需反馈信道或更少占用反馈信道的通信场景， 来解决反馈的问题很有必要。数字喷泉码就是这样一种码，它是与码率无关、支 持异步接入且具有线性编译码复杂度的随机编码方式，在基于包通信的系统中有 接近理想的纠删性能，可以有效地解决网络拥塞及卫星广播通信中的“反馈破裂” 问题，具有很大的应用前景。 2 2 1 数字喷泉码原理 喷泉码是这样的概念：它可以由k 个原始数据分组生成任意数量的编码分组， 而接收方只要收到其中任意m 个编码分组，即可通过译码以高概率成功地恢复全 部原始数据分组。一般情况下，m 略大于k ，从而引入一定的译码开销，定义为 s = m k l 。可以看到，上述编码过程的基本思想可描述为：单个源节点编码器如 同喷泉一样源源不断产生水滴( 编码分组) ，每次发送的水滴都从待传输原始分组 包中随机选择，并通过某种方式重新组合起来生成新的编码包，而接收端接收编 码分组的过程就像是用杯子( 译码器) 接收水滴，而不必关心是哪一滴水流入了 杯中，只要杯中水满了以后即可饮用( 成功译码) 。正因为如此，该种编码被称为 喷泉码。 因为喷泉码与码率无关，所以由源文件经过编码产生的码元数目不受限制， 可以产生无限多的码元。不管信道中删除的编码分组数目为多少，都能发送足够 多的经过编码的分组。接收端只要接收到足够供解码器恢复源文件的编码分组即 可。显然，喷泉码的设计需要考虑两方面的问题：一方面，应该尽量减小译码开 销，使其趋近于0 ；另一方面，应该尽量减小编译码复杂度。 2 2 2 几种典型的喷泉码 本小节对几种典型的喷泉码进行简单的介绍。 1 l t 码简介 l tc o d e 是一类通用喷泉码的实现，假设待传输数据分组为k 个，则在编码过 程中，每个编码分组都可以通过平均进行o ( t n ( k 艿) ) 次异或运算产生，且各个编码 分组的产生相互独立。接收端收到m 个编码分组后能以l 一6 的概率通过平均进行 o ( k t n ( k 6 ) ) 次异或运算恢复原数据分组，参与上述过程的编码信息单元数量为 k + o ( k v 2l n ( k 8 ) ) 。 1 0基于喷泉码的导航电文发播研究 口 原始数据分组 0 编码分组 图2 1u 编码过程不恿图 具体编码过程如图2 1 所示，按以下步骤进行1 1 2 j ： 将待编码的源数据分成等长的七个数据分组，记为 s l , s 2 s k ，由此k 个源数 据分组通过l t 编码产生拧个编码包 r l ，f 2 厶) 。第f 个编码分组通过以下规则产生： ( 1 ) 根据度概率分布函数q o ) ，产生第f 个编码分组的度，记为面。 ( 2 ) 从源数据符号列表中，随机的选取西个数据分组。 ( 3 ) 将选择出的4 个数据分组进行异或运算，得到一个编码包。 ( 4 ) 重复以上各步骤即可源源不断地产生编码分组，直至达到预先设定的编码 包数量。 ?o? 0 7 o0ol0 ( a ) 01ool ( b ) ( c ) ?0l l0l 口口口 0o ll ( d )( e ) ( f ) 图2 2l t 码译码过程示意图 图2 2 阐述的是l t 码的具体译码过程( b p 硬判决译码) ，可描述为： ( 1 ) 接收一定数量的编码分组根据编码分组与原始数据分组的对应关系建立 双向图。顶层节点代表原始数据分组，底层节点代表编码分组，如图2 2 ( a ) 。 第二章北斗卫星导航系统相关技术和喷泉码原理 i i ( 2 ) 寻找一个度为1 的编码分组。若不存在，则译码停止；若存在恢复与该 编码分组相连的唯一原始数据分组，如图2 2 ( b ) 。 ( 3 ) 对已恢复的原始数据分组，将其与其相连的所有其它编码分组异或，生成 修正的编码分组，删除双向图中对应的边，从而使得这些编码分组的度数减1 。称 该编码分组被“释放 ，如图2 2 ( c ) 。 ( 4 ) 重复步骤( 2 ) 和( 3 ) ，直至译码停止，如图2 2 ( d ) ( e ) ( f ) 。如果所有原始数据分 组都已经恢复，则译码成功；否则，译码失败。必须接收更多的编码分组才能继 续译码。 由上述过程可以看出l t 码解码效率很高，但是l t 码也具有以下缺点： ( 1 ) 当译码过程中，接收端收到的编码分组数量接近于原始数据分组的数量 时，l t 码不能保证以固定的时空代价解码。 ( 2 ) 译码过程需要恢复所有的原始数据分组，才算译码成功。 2 r a p t o r 码 为了解决l t 码的缺点，在l t 码基础上发展出来了改进版的r a p t o r 码技术， 它是基于这样一个认识：l t 码生成的编码包中有少量连接度很高的包，这些包的 作用主要是保证对所有数据包的良好覆盖，从而保证译码的完整性，然而这些高 连接度包的存在消耗了很多编译码异或操作，同时也降低了低连接度包的比例， 从而减小了译码过程中输入输出波纹( 输出波纹指译码过程中度数减小为1 的编 码分组的集合，输入波纹指与输出波纹连接的数据分组集合) 的大小，降低了译 码成功概率。 基于这个思想，r a p t o r 码提出采用两步编码的方式，如图2 3 所示。 原始数据分组 预编码 l t 编码 图2 3r a p t o r 编码过程 首先对原始信息用一个分组码进行预编码，然后采用一个弱化的l t 码对数据 进行编码并发送。接收端译码也分两步，首先进行l t 译码，然后对预编码进行译 码。所谓弱化的l t 码是指它生成的编码包中没有高连接度包，无法完整译出全部 的原始数据，但是能以很高的概率恢复出绝大多数的数据包，因此剩下未译出的 数据包所占的比例就被控制在一个很小的范围以内，这些未译出的数据包不再通 过高连接度的编码包来保证覆盖和恢复，而是利用预编码的纠错能力进行恢复。 1 2基于喷泉码的导航电文发播研究 预编码一般可以采用性能良好的线性分组码，比如t o r n a d o 码，l d p c 码。 通过联合优化弱化的l t 码和预编码的码率等参数，r a p t o r 码可以获得更低的 编译码复杂度，从而在相同译码开销下实现更高的译码成功率，达到以下效果： 对任何实数g 0 ，r a p t o r 码可以从七( 1 + s ) 个编码符号恢复k 个输入符号。其中每 一个编码符号需要进行i n ( 1 + ) 次操作获得，而恢复所有k 个符号仅需进行 o ( k i n ( 1 s ) ) 次符号操作。可见，r a p t o r 码的编译码复杂度与码长成线性关系，优 于l t 码的对数关系o ( k 眦七6 ) ) 。 r a p t o r 码的无码率性质来源于对l t 码的继承，而它的额外的低复杂度性能和 低误码平台特性依赖于外码和度分布的精心设计，同时它的编译码的低复杂度依 赖于短的外码与稀疏的内码的设计，第三章我们将会对外码和内码的设计做专门 讨论。 2 2 3 喷泉码的度分布 习惯上将喷泉码度数分布用一个度分布生成多项式的函数表示： f 2 ( x ) = ：l q ，而 ( 2 - 9 ) 第f 项表示度数f 被采用的概率。上一节已经介绍过，喷泉码编码要保证每个 原始数据节点都被覆盖以参与编码；喷泉码译码的开始依赖于接收编码分组输出 波纹的大小，译码的顺利开展，则有赖于在迭代过程中波纹的持续产生。因此合 理的度分布是l t 码性能的关键。从l t 码编码过程考虑，一方面应使平均度数较 小，才可以减小生成每个编码分组需要的运算量；另一方面又应给予较大度数一 定的选取概率，以保证任何一个原始数据节点都参与编码。从l t 译码过程考虑， 一方面应该使编码分组保持一定的释放速度，这样才可以保证译码过程不会终止； 另一方面编码分组释放速度又不能过快，否则大量已释放的编码分组将增加重复 覆盖的可能性，从而引入不必要的冗余。 基于以上考虑，l u b y 首先给出了i d e a ls o l i t o n ( 理想孤波) 分布，i d e a ls o l i t o n 分布基于这样一个理想的译码状态，即在每次迭代译码过程中输出波纹大小一直 为l 。它实现了译码运算次数的最优化。分布的表达式如下： 陆 捌 p ( d ) = ， ( 2 - 1 0 ) l上d=2，3，kla r d - 0 。 其中k 表示原始数据符号数，d 表示度数。 但是在实际应用中，这种度概率分布函数在实际运用中很少采用。原因是编 第二章北斗卫星导航系统相关技术和喷泉码原理 1 3 码时度分布的抽样无法精确符合i d e a l 分布，在译码过程中围绕理想状态的波动很 容易造成在某些时刻没有度数为l 的编码分组出现，从而致使迭代中输出波纹断 层出现空集，导致译码失败。更严重的是，一些原始数据分组可能根本就没参与 编码。 之后l u b y 通过修正理想孤波分布，给出了更加实用的r o b u s ts o l i t o n ( 鲁棒孤 波) 分布。改进型r o b u s ts o l i t o n 分布结合i d e a l 分布的优点加入另外两个调节参 数c 和6 ，这样的设计保证在译码过程中输出波纹大小的期望值近似于 s 量c l n ( k 6 ) 七，而不是1 。其中6 是一个概率约束，表示接收到m 个确知的数据 包厶后无法解码的概率的极限；c 是一个用于优化的小于1 且可调整的常数。理论 分析证明，在鲁棒孤波分布下，当收到k + d ( 七) 个编码分组后，译码器就能以很高 概率成功译码。 r o b u s ts o l i t o n 分布由两部分组成，一部分是i d e a ls o l i t o n 分布，另一部分是 f ( d ) 。如式( 2 1 1 ) 所示： f ( d ) = s1 七d 扣如8 ) d = 1 ，2 ，3 ，( 七s ) - i d = k | s q d k s 对两者取归一化即得到r o b u s t 分布： p ( d ) ：地婆盟 ( 2 1 2 ) z 其中， z = d p ( d ) + f ( d ) ( 2 - 1 3 ) 喷泉码的核心l t 码在两种不同的分布下，性能有较大的差别。i d e a ls o l i t o n 分布具有理论最优值，但实际应用中经常译码中断严重；相比r o b u s ts o l i t o n 分布 存在可调参数，有较大的应用价值。本节仅基于l t 码对度分布做简单介绍。第三 章涉及采用r a p t o r 编码方式时，将会对涉及到的弱化度分布、最优度分布与次优 度分布的设计问题做具体分析。 2 3 本章小结 本章首先给出了论文的导航模型架构及相关技术，然后基于卫星导航电文发 播的需要，研究了数字喷泉码技术的基本思想原理，几种喷泉码的实际实现码型 和度分布概念，为下一章节喷泉编码的实现奠定基础。 第三章卫星导航信道中的喷泉码研究 第三章卫星导航信道中的喷泉码研究 卫星导航系统主要依靠卫星向各个用户接收机广播包含系统时间、卫星星历、 时钟改正参数、电离层改正参数等数据的导航电文，然后在用户终端进行解算定 位。而电文是在信道中传播的，所以本章对卫星导航信道中数据的编码传输进行 研究，下一章研究基于喷泉码的导航电文发播策略。 卫星导航信道主要指的是从卫星到用户接收机的链路。由于该链路距离较长， 信号在传播过程中将受到严重的衰减，同时由于受到卫星体积和载重等因素限制， 发送功率受到限制，因此强纠错能力的差错控制方法将有利于提高信号的误码性 能。另一方面，由于卫星导航信道是天然的广播信道，所以采用喷泉编码有着独 特的优势。在卫星通信系统中应用喷泉编码，将提高系统的可靠性和传输的稳定 性，特别是广播删除信道下的性能。 卫星导航信道的建模可以从两个角度来考虑：一方面，卫星导航信道是比较 典型的功率和带宽受限信道，只存在少量的非线性多径衰落，引入的噪声基本上 是高斯白噪声。所以整个卫星导航信道从物理层仿真的角度可以建模为加性高斯 白噪声( a w g n ) 信道。另一方面，从更高层链路层角度考虑，阴影遮挡导致深衰落 的信道环境中普遍存在导航电文帧的丢失，这又可以理解为删除信道，而且喷泉 码的理论提出背景是在删除信道中，因此需要对删除信道下的喷泉码【2 4 】进行研究。 本章首先研究喷泉码在删除信道和加性高斯白噪声信道的性能，进而对适合卫星 广播的短码长的喷泉码预编码方案进行仿真分析，最后给出卫星导航信道中以 a w g n 信道建模、结合精心选取的预编码的喷泉码编译码方案。 3 1l t 码的删除信道建模和度分布仿真 本节首先进行了l t 码在删除信道下的仿真。基于两个原因：第一，在卫星上 导航电文以帧为发播单位，接收端通过同步码和奇偶校验位检验是否接收到某一 帧，因此卫星导航信道从数据链路层来看可以建模为删除信道。第二，通过研究 基础度分布对l t 码的性能影响，能为进一步的喷泉码的度分布研究