（通信与信息系统专业论文）衰落信道上无码率码技术研究.pdf

摘要 传统的信道编码具有固定的码牢，而喷泉码打破了这一约束，通过在发送端 源源不断地产生任意多的编码符号，来实现种无码率的编码方式。喷泉码的无 码率特性使其能够在发送端未知信道状态信息的条件下，根据信道状态自适应地 调整码率，从而提高信息传输的有效性。 喷泉码在删除信道上的成功应用，使得人们考虑将其推广到更加一般的信道 上去。本文主要研究了一类针对a w g n 信道设计的无码率纠错码k i t e 码，并在 该码的基础上进行了改进，提出了一类新的无码率码s e m i r a n d o mk i t e ( s r - k i t e ) 码。通过在原始纯随机生成的校验矩阵中添加一些简单的约束，s r k i t e 码可以在 一定程度上有效地降低错误平层。 本文研究了s r 。k i t e 码在a w g n 及独立r a y l e i g h 衰落信道上的性能，并介绍 了一种基于仿真的贪心优化算法来优化码设计。同时还推导了s r k i t e 码的重量枚 举函数，并利用联合限分析了该码的最大似然译码性能。除此之外，本文还考察 了s r k i t e 码在独立r a y l e i g h 衰落信道上与高阶调制相结合的性能。不同于传统的 编码调制方案，s r k i t e 码的无码率特性，使其与高阶调制相结合时可以实现谱效 率在一定范围内的连续变化。 关键词：喷泉码l d p c 码r a 码联合限r a y l e i g h 衰落信道 a b s t r a c t f o u n t a i nc o d e sa r ean e wc l a s so fc o d e sd e s i g n e df o rr e l i a b l et r a n s m i s s i o no v e r a n e r a s u r ec h a n n e l d i f f e r e n tf r o mt r a d i t i o n a lc h a n n e lc o d e s ，f o u n t a i nc o d e sa r er a t e l e s s t h e yc a np r o d u c eap o t e n t i a l l yl i m i t l e s ss t r e a mo fo u t p u ts y m b o l sf o rag i v e ns e to f i n p u ts y m b o l s t h u sf o u n t a i nc o d e sc a na d a p to p p o r t u n i s t i c a l l yc o d e r a t e st ot h e c h a n n e lr e a l i z a t i o nb yt h e i rd y n a m i c d e c o d i n gn a t u r ew i t h o u tc h a n n e li n f o r m a t i o na tt h e t r a n s m i t t e r t h es u c c e s so ff o u n t a i nc o d e sf o re r a s u r ec h a n n e l ss u g g e s t st h a ts i m i l a rr e s u l t sm a y a l s ob ep o s s i b l ef o ro t h e rc h a n n e l s ，s u c ha sa w g na n df a d i n gc h a n n e l s t h i st h e s i sf i r s t d i s c u s s e san e wc l a s so fr a t e l e s sf o r w a r de r r o rc o r r e c t i o nc o d e sf o ra w g nc h a n n e l s ， w h i c ha r ec a l l e dk i t ec o d e s a n dt h e nw ei n t r o d u c ean e wc o d e s e m i r a n d o mk i t e ( s r k i t e ) c o d e s ，a ne x t e n s i o no fk i t ec o d e s t h ep r o p o s e dc o d e si m p o s es o m es i m p l e c o n s t r a i n t so nt h eo r i g i n a lp u r e l yr a n d o mp a r i t y c h e c km a t r i xt ol o w e rd o w ne r r o r f l o o r s w ee x p l o r et h ep e r f o r m a n c eo fs r k i t ec o d e so nb o t ha w g na n di n d e p e n d e n t r a y l e i g hf a d i n gc h a n n e l s ，a n du s eas i m u l a t i o n - b a s e dg r e e d yo p t i m i z a t i o na l g o r i t h m t o d e s i g nt h ec o d e m o r e o v e r t h ea v e r a g ew e i g h te n u m e r a t o ro ft h ee n s e m b l eo fs r - k i t e c o d e si sc a l c u l a t e d w h i c hi st h e nu s e dt oe v a l u a t ei t s p e r f o r m a n c eo fm a x i m u m l i k e l i h o o d ( m l ) d e c o d i n gv i au n i o nb o u n d f i n a l l y , w ec o m b i n es r k i t ec o d e sw i t h h i g h - o r d e rm o d u l a t i o ns c h e m e st oo b t a i nac o n t i n u o u s l yv a r i a b l es p e c t r a le f f i c i e n c yi na l a r g er a n g eo fs n r s k e y w o r d s ：f o u n t a i nc o d e s l d p cc o d e sr ac o d e su n i o nb o u n d r a y l e i g hf a d i n gc h a n n e l s 第一章绪论 第一章绪论 本章首先回顾了传统数据传输系统中所使用的差错控制方案：自动请求重传 ( a r q ) 方法和前向差错控制( f e c ) 方法；然后介绍了数字喷泉码技术的提出和发 展概况；最后给出了本文的主要工作和全文内容安排。 1 1 研究背景 随着因特网的普及和人们对网上共享资源需求的增加，如何在互联网上高效、 可靠地进行大规模数据的广播和多播成了通信领域亟待解决的问题。在互联网上， 信息是以数据包的形式进行传输的，这些数据包通过网络中的路由器进行转发最 终到达信宿。由于各种原因，包括中问路由器的缓存溢出，或是传输出错使得数 据包中的c r c 校验不被满足等，都会导致发送数据包的丢失。为了解决这一问题， 最直观的做法就是重新发送丢失的数据包，而现行的t c p 协议正是通过基于a r q 的反馈重传机制来保证通信的可靠性。显然，当链路质量较差或网络中需要服务 的用户数过多时，大量的反馈信息可能会淹没服务器，并且导致网络链路拥塞， 降低网络的吞吐量。 解决这一问题的另一方案是采用前向差错控制技术( f e c ) ，l i p i d 用纠错码在接 收端自动地纠正检出的错误。由于在互联网上传输的数据包要么正确接收，要么 发生丢失，因此互联网是二进制删除信道( a e c ) 的一个典型实现。e l i a s 【lj 证明了删 除概率为p 的b e c 的信道容量为j 节，并进一步证明当采用最大似然译码( m l d e c o d i n g ) 时，码率无限逼近j p 的随机码可以在该信道上实现错误概率任意小的 信息传输。b e c 上线性码的最大似然译码实际上等价于解一组线性方程组，因此 可以采用高斯消元法求解，但是该方法需要花费多项式时间( p o l y n o m i a lt i m e ) ，尤 其在码长较长时译码速度较慢。 r e e d s o l o m o n ( r s ) 码是一类极大最小距离可分码( m d s 码) ，该码的最小距离 比其奇偶校验符号数多l ，达到了线性码的最大可能最小距离，因此具有很强的纠 删能力。在b e c 上，一个( mk ) r s 码只要接收到个发送符号中的任意k 个就 能够恢复出原始的k 个信息符号，但其编、译码开销为0 ( k ( n - k ) l o g ：) 。当 mk 较大时，过长的编、译码时间很难被许多应用所接受，因此在实际应用中r s 码仅用于k ，较小的情况。针对r s 码编译码时间过长的缺点，在文献 2 】中作者 构造了一种新的具有线性编译码时间的纠删码t o m a d o 码，然而该码的编译码时 衰落信道二无码率码技术研究 问与其分组长度成正比，在码率较低的情况下，其编译码速率仍然较慢。 在点对点的单播传输环境中，精心设计的a r q 协议或是传统纠删码均能有效 实现可靠通信。然而，对于点对多点的广播、多播应用，不同的用户与发送端之 间的链路质量各不相同，因此不能简单的用同一个信道模型来刻画。此外，传统 纠删码的码率是固定的，如果要想使用同一个码来保证所有用户的可靠通信，那 么码率的设计必须按照最坏的情况考虑，这势必会降低信道质量好的用户的传输 效率。并月在某些应用环境中，例如无线传输，信道的质量随时间动态变化，使 用固定码率的纠删码就无法保证可靠通信。还有一些实际应用，除了需要保证向 大规模的用户提供可靠通信外，还要满足不同用户能够以不同的速率随时接收数 据。 为了更好的满足广播、多播传输中的种种要求，b y e r s 等人在文献 3 e e 首次提 出了数字喷泉( d i g i t a lf o u n t a i n ) 的思想。数字喷泉的核心特征是发送端能够产生任意 多的编码符号，而接收端利用与原始信息符号个数相同的任何一个接收符号子集 都能准确地译出原始信息。就如同源源不断产生水滴的喷泉，我们只要用杯子接 收足够量的水滴，即可达到止渴的目的，而无需关心接收到的是哪些水滴。 1 2 数字喷泉码技术 理想的数字喷泉可以通过喷泉码( f o u n t a i nc o d e s ) 来实现，但文献 3 】中并未给出 具体的构造方法。喷泉码最主要的特征是具有无码率特性，即编码器可以由价原 始数据符号生成任意数量的编码符号，因此喷泉码也被称为无码率码。2 0 0 2 年l u b y 构造出了喷泉码的第一个实现l t 码【4 】。l t 码可以看作一类稀疏随机线性喷泉码， 它继承了随机线性喷泉码的良好性能，同时编译码复杂度相对于r s 码明显降低。 但l t 码的不足之处是不具有线性编译码时间，假设信息长度为k ，其编译码代价为 k l o g 。k ，考虑只需阶输出符号即可译码的理想情况，此时每个输出符号平均要与 l o g 。k 个输入符号相连( 然而很多应用希望喷泉码输出符号的平均重量为一个常 数) 。为了实现线性时间的编译码效率，2 0 0 6 年s h o k r o l l a h i 提出t r a p t o r 石- q t 副。r a p t o r 码是对l 1 码的扩展，它在l t 码的基础上级联了一个预编码，这种级联结构使得l t 码只需纠正一部分删除错误，而剩余的错误可由预编码来纠正，因此放宽了对l t 码纠删能力的要求，使得我们使用一个弱l t 码即可得到良好的性能。l t 和r a p t o r 码的一个不足之处是均为非系统码，这意味着不能由输出符号不经过译码而直接 恢复出部分信息符号。文献 5 1 1 6 】中提出了系统r a p t o r 码的编译码算法，这种系统 r a p t o r 码已被用于3 g p p 中的多媒体广播多播业务( m b m s ) 标准及d v b h 标准。 自从l t 码、r a p t o r 码出现之后，关于其性能分析及度分布设计的研究逐步成 第一章绪论 为人们关注的焦点【7 h 1 。文献 7 】分析了有限长l t 码的性能，提出了一种在给定度 分布及接收符号数目的条件下计算译码错误概率的方法。文献 8 】提出了一种估计 有限长r a p t o r 码迭代译码性能的简单模型，这一模趔为我们在给定参数的条件下设 计最优的度分布提供了指导。 喷泉码在删除信道上的成功应用，使得人们考虑将其推广到更加一般的二进 制输入对称信道上【1 2 】圳i5 1 。e t e s a m i 等在文献 1 2 q b 给出了l t 码在a w g n 信道上的性 能曲线，并简要分析了可达到信道容量的r a p t o r 码的渐进度分布。与此同时，p a l a n k i 等在文献 1 3 1 中也得到了类似的结论。文献 1 4 贝l j 进行了更加详细地分析，给出了 r a p t o r 码在二进制输入无记忆对称信道( b i m s c ) 上的置信度传播( b p ) 译码算法，推 导出了可达到信道容量的r a p t o r 码的输出符号中度值为l 、2 的比例，并且提出了 一种改进的高斯近似( g a u s s i a na p p r o x i m a t i o n ) 方法来优化二进制输入a w g n ( b i a w g n ) 信道上r a p t o r 码的度分布。 除了二进制输入对称信道外，喷泉码固有的自适应特性使其适用于时变衰落 信道【1 6 】【2 2 】。c a s t u r a 等在文献【1 6 】中仿真t r a p t o r 码在分块衰落信道上的性能，并指 出和传统的固定码率的编码方案相比，喷泉码可同时满足有效性、可靠性和健壮 性等要求。f a n 等在文献 2 2 】中从分集复用权衡( d i v e r s i t y m u l t i p l e x i n gt r a d e o f f ) 的角 度分析了喷泉码在多输入多输出( m i m o ) 衰落信道上的性能限，并提出了m i m o 衰 落信道上喷泉码的设计准则。 此外，喷泉码在中继信道上的应用也成了近年来人们关注的热点，相关的研 究成果可参阅文献 1 7 】， 2 3 【3 3 】。由于l t 码编码过程的随机性，使其在噪声信道 上使用时会有较高的错误平台，因此我们常常将其与其它前向纠错码级联使用， 例如，i t e r a t i v e l yd e t e c t e db i t - i n t e r l e a v e dc o d e dm o d u l a t i o n 州，g e n e r a l i z e dl d p c 恻， c o n v o l u t i o n a la n dt u r b oc o d e s l 3 6 】。1 3 引。 除了将经典的喷泉码( 包括l t 码、r a p t o r 码) 推广到更加一般的信道上外，喷 泉码构造也是人们的研究方向之一1 3 9 1 【4 5 】。文献【4 0 】提出了一类系统无码率码，该 码具有线性编译码复杂度，并且可在任意b e c 上达到信道容量。文献【4 4 】中构造了 另一类系统的基于半随机l d p c 码( s r l d p c ) 的无码率纠删码，该码不仅可以达到 信道容量，而且当信道删除概率较低时，相对于非系统码，该系统码可以不经过 译码直接恢复出部分信息比特。 由于在噪声信道上，喷泉码不具有通用的度分布，因此仅使用一个固定的度 分布显然难以满足不同信噪比的要求。为了解决这一问题，文献【4 5 】中构造了一类 新的无码率纠错码r e c o n f i g u r a b l er a t e l e s sc o d e s ，该码可以看作一类r a t e l e s sr a c o d e s 。除了具有传统喷泉码的无码率特性外，该码还能够在发送端未知信道状态 信息的情况下自适应地调整度分布。类似地，文献 4 6 】提出了另一类无码率纠错码， 该码是由一个r s 码和一个被称为k i t e 码的内码串行级联构成的，其中k i t e 码是 4 衰落信道上无码率码技术研究 一类特殊的r a t e l e s sl d p c 码，它可以产生任意多个随机校验比特，并且也具有时 变的度分布。 除了已有的应用外，我们还可以考虑将喷泉码用到深宅通信【5 6 】中。长时延是 深空通信的特点之一，而这使得a r q 方案不适合在深空通信中使用。因此，除了 在物理层使用传统的纠错码之外，可以考虑在高层使用喷泉码来作为一种应用层 的编码。当发送码字无法j 下确译码使得对应数据包丢失时，我们可以利用喷泉码 的纠删特性恢复出原始信息，从而代替传统的a r q 方案。 1 3 本文的主要研究工作和内容安排 本文结合新一代宽带无线移动通信网国家科技重大专项中的“i m t - a d v a n c e d 开放性关键技术研究课题，对喷泉码在衰落信道上的应用进行了研究。首先阐 述了数字喷泉码的基本原理，并详细介绍了经典的l t 码和r a p t o r 码。接着介绍了 一类新的无码率纠错码k i t e 码，并在此基础上进行改进，提出了s e m i r a n d o m k i t e ( s r - k i t e ) 码，研究了s r k i t e 码的最大似然译码性能及其与高阶调制相结合的 应用。全文共分为五章，其它章节具体安排如下： 第二章介绍了数字喷泉的基本思想，以及l t 码和r a p t o r 码的编译码算法和度 分布设计。 第三章介绍了类新的无码率纠错码k i t e 码，给出了相应的编译码算法， 推导了k i t e 码的重量枚举函数，并给出了一种码优化的方法。 第四章在前一章的基础上，对k i t e 码进行了改进，提出了一类新的无码率纠 错码s e m i r a n d o mk i t e ( s r k i t e ) 码，推导了s r k i t e 码的部分重量枚举函数，并 使用联合限分析了s r k i t e 码的最大似然译码性能。最后，讨论了独立r a y l e i g h 衰落信道上s r k i t e 码与高阶调制相结合的性能。 第五章对全文的工作进行了总结，并提出了进一步的研究方向。 第二- ：章数：j ，喷泉码 第二章数字喷泉码 本章主要是围绕删除信道上的喷泉码展开的。首先简要叙述了数字喷泉的基 本思想；接着详细介绍了两类经典的喷泉码一l t 码和r a p t o r 码，讨论了其编译 码算法和度分布设计 2 i 数字喷泉 数字喷泉的思想i 妇b y e r s 等人于1 9 9 8 年首次提出【3j ，主要是为了解决网络中大 规模数据的广播、多播传输问题。与传统的信道编码不同，数字喷泉码采用了一 种无码率的编码方式，即发送端能够产生任意多个编码符号，而接收端利用与原 始信息符号个数相同的任何一个接收符号子集都能准确地译出原始信息。就如同 源源不断产生水滴的喷泉，我们只要用杯子接收足够量的水滴，即可达到止渴的 目的，而无需关心接收到的是哪些水滴。 2 1 1 理想广播、多播传输协议的要求 随着互联网的不断发展和人们对网络资源需求的增加，可靠性已经不再是人 们对信息传输的唯一要求。为了更好地实现网络资源的共享，一个理想的传输协 议需要满足以下几个特性【5 5 j 。 1 可扩展性( s c a l a b l e ) 。无论网络中用户数量的多少，服务器的负荷始终保 持恒定。 2 可靠性( r e l i a b l e ) 。每一个用户都能够准确地恢复出原始文件。 3 接收有效i 生( r e c e p t i o n e f f i c i e n t ) 。每个用户能够以最少数量的接收数据包来 恢复出原始文件。理想情况下只需接收与原始文件长度相等的数据包个数即 可。 4 时间有效性( t i m e e f f i c i e n t ) 。发送端产生数据包以及接收端重构原文件所需 的时间均最少。 5 时问独立性( t i m e i n d e p e n d e n t ) 。用户可以选择在任意时刻进行下载，并且 可以中途暂停，在随后的某一时刻继续下载。 6 服务器独立性( s e r v e r - i n d e p e n d e n t ) 。用户可以接收不同服务器发送的关于同 一文件的数据包，而这些服务器之间无需相互协作。 7 容忍性( t o l e r a n t ) 。当网络中用户的端到端丢包率和数据速率不同时，仍需 6 衰落信道卜无码率码技术研究 满足这些用户的不同需求。 2 1 2 数字喷泉解决方案 无论是a r q 协议还是传统的前向纠错编码，都无法很好地实现上述理想传输 协议的要求。而为了实现这一目标，人们提出了数字喷泉的解决方案。 数字喷泉最主要的特征是接收端可由任意一个与发送数据长度相等的接收符 号子集来准确地译出原始信息。这正满足了理想传输协议中可靠性和接收有效性 的要求。虽然r s 码也具有理想的纠删特性，但是用户间信道条件的差异性使得不 同用户接收到的数据包的个数是不同的，这就导致一个r s 码无法满足众多用户的 需求。而数字喷泉通过无码率的编码方式来“屏蔽”用户信道的差异，使得各个用户 可以根据自身的情况进行接收。 数字喷泉的思想是由喷泉码( f o u n t a i nc o d e s ) 来实现的。这种编码的发送端可以 由k 个原始的数据符号生成任意数量的编码符号，接收端只要收到其中任意 七( 1 + 占) 个编码符号即可以很高的概率成功译码。显然，喷泉码的设计需要考虑两 方面的问题：一方面，应该尽量减小译码开销占，使其趋于0 ；另一方面，应该尽 量减小编译码复杂度。理想情况下，应使生成每个编码符号所需要的运算量是一 个与k 无关的常数，而成功译出k 个原始信息符号所需要的运算量是关于k 的线性 函数。 理想传输协议的要求为数字喷泉方案的设计提供了指导与目标，然而如何具 体地实现这一理想的解决方案却是另一回事。在后面的几节中我们将具体介绍两 种数字喷泉的实现方式。 2 2l t 码 l ，t 码是喷泉码的第一个实现，也被称为通用删除码( u n i v e r s a le r a s u r ec o d e s ) 。 其“通用”性体现在，无论信道的删除概率多大，该码总能达到近似最优的性能。并 且随着信息长度的增加，l t 码的译码开销趋于0 。简单的编译码算法和较小的译 码开销，使得l t 码为喷泉码的进一步发展奠定了坚实的基础。 2 2 il t 码的编码原理 考虑k 个发送符号& ，s 2 ，其编码过程如下： 1 根据给定的度分布p ( d ) 为编码符号随机选择一个度值d 。 2 从k 个发送符号中等概率的随机选取d 个不同的符号，作为该编码符号的 第二章数字喷泉码 令i s 居节点。 3 将选取的d 个发送符号进行异或运算即可得到所需的编码符号。 上述编码过程也可以使用一个二部图( b i p a r t i t eg r a p h ) 来简单地表示，如图2 1 所 示。该图的一边为k 个输入符号，另一边为生成的编码符号。显然，所得到的l t 码是一个非系统码。当编码符号的平均度值远小于k 时，得到一个稀疏二部图。 此时，我们也可以把该码看作是一个非规则l d g m ( i o w d e n s i t yg e n e r a t o r - m a t r i x ) 码。 输入符号 编码符号 图2 1l t 码的二部图 编码之后的符号通过删除信道进行传输，在接收端要么被正确接收，要么发 生删除错误。接收端译码时需要知道每个正确接收符号的度值及其与输入符号之 间的连接关系，而l t 码的随机性使得收端无法提前预知这些信息。在实际应用中， 这一问题有多种解决方案。例如，我们可以将这些信息放在待发送数据包的头部， 或者通过在发端和收端同步使用同一伪随机数产生器来得到相同的生成矩阵。 2 2 2l t 码的译码原理 当l t 码用于删除信道时，接收端需要根据正确收到的符号序列t 进行译码， 即由t = s g 恢复出原始信息s ，其中g 是与t 对应的生成矩阵。显然，删除信道上 l t 码的译码实际等价于解二组线性方程组，我们可以采用高斯消去法进行求解。 然而，该方法需要大量的时间和空间来求矩阵的逆，因此只适用于传输数据量较 小的场合。本节我们将介绍另一种较为简单的译码算法b p ( b e l i e f - p r o p a g a t i o n ) 算法。该算法描述如下： 1 接收一定数量的编码符号，并根据它们与输入符号之间的连接关系构建二部图。 2 任意选择一个度为l 的编码符号。如果不存在，则译码停止；如果存在，则可 恢复出与之相连的唯一输入符号。 3 将已恢复的输入符号和其它与之相连的编码符号模2 和，更新编码符号的取值。 相应地，将二部图中对应的边删除，使得这些编码符号的度值减1 。 4 重复步骤2 ，3 ，直至译码停止。如果所有的输入符号都已恢复，则译码成功： 否则，译码失败，需要接收更多的编码符号才能继续译码。 我们也可以使用图示来更形象地描述上述译码过程，如图2 2 所示。其中包含 衰落信道卜无码率码技术研究 三个输入符号( 用方块表示) ，及四个编码符号( 用圆圈表示) ，且编码符号序列的取 值为1 0 1 0 。最终译h 朱的输入符号序列为l l o 。 2 2 3l t 码度分布设计 从上述编译码过程可以清楚地看到，度分布对l t 码的性能有着至关重要的影 响。一个好的度分布既要使得成功译码所需的接收符号数尽可能得少，又要保证 每个编码符号的度值尽可能得小；也就是说，编译码的复杂度要尽可能得低。 l u b y 在文献【4 】中首先给出了理想孤子分布( i d e a ls o l i t o nd i s t r i b u t i o n ) ， 即) 屯兰一，七 ( 2 - ) 从平均意义上考虑，该分布可以保证成功译码所需的符号数恰好等于输入符 号的个数，并且在译码过程中每次只释放一个编码符号。但是在实际应用中，由 于度值产生的随机性，很可能出现译码过程中没有度为l 的编码符号的情况，更 有甚者，一些信源符号可能并未参与编码，而这都将导致译码失败。 l 1 口 1 1 口 1 o1 ol ( a ) olo ( b ) 1 ll1 ( c ) 1 00 ( e ) 【 ll ( d ) 1lo 口口口 o oo 10o1 ( 置) 图2 2l t 码的译码实例 第二章数字喷泉码 9 虽然理想孤子分布在实际应用中的性能较差，但它却为我们设计一个好的度 分布提供了启示。在此基础卜，l u b y 又提出了鲁棒孤子分布( r o b u s ts o l l t o n d i s t r i b u t i o n ) 。该分布引入了两个额外的参数c 和万，其中c 足常数，在实际应用中 通常选择比l 小的值，万表示接收到一定数量的编码符号后所允许的译码失败概 率。令足= c l n ( q & ) , j k ，定义 f 剐腩， f = l ，k e - l f ( f ) = r i n ( r s ) k ，江k r ( 2 2 ) 1 0 ， i = r + l ，k 将理想孤子分布p ( f ) 与f ( ，) 相加并归一化，得到鲁棒孤子分布 。 ( f ) = ( p ( f ) + f ( f ) ) 胪，i = 1 2 ，k ( 2 3 ) 其中，= ：。 p ( 少f ( f ) 。 理想孤子分布性能的不稳定性是由于在译码过程中度为l 的编码符号的平均 个数为l ，因此稍有波动，很容易导致没有度为l 的编码符号出现。而鲁棒孤子分 布通过引入f ( f ) ，使得在译码过程中度为l 的编码符号集合的平均大小为 c l l l f 露万) 后，从而以很高的概率保证译码顺利进行。同时，对于一个合适的常数 c ，正确接收到后+ 2 l n ( r g ) r 个编码符号，即能保证所有输入符号至少以l 一万的概 率被恢复。 2 3r a p t o r 码 虽然l t 码的性能优良，但其编译码复杂度仍为k i n k ( 其中七为输入符号的个 数1 ，即每个编码符号平均要与i n k 个输入符号相连。然而在很多实际应用中，我 们需要构造具有线性编译码复杂度的码，即编码符号的平均重量为一个常数。为 了解决这一问题，s h o k r o l l a h i 在2 0 0 6 年提出t r a p t o r 码1 5 1 。r a p t o r 码在l t 码的基础 上，通过级联一层预编码，来实现线性编译码复杂度。 2 3 1r a p t o r 码构造 r a p t o r 码是由外码和内码级联而成的，其中内码是一个弱化的l t 码，外码为 传统的纠错码，一般采用低密度奇偶校s t y x ( 1 0 w - d e n s i t yp a r i t y - c h e c k ，l d p c ) t i 马。通常 我们也将其外码的生成过程称为r a p t o r 码的预编码。由于使用了级联结构，l t 码 译码只需恢复固定比例的中间编码符号，再利用外码的译码特性来最终恢复出所 i o 衰落信道上无码率码技术研究 有输入符号。这就降低了对l t 码度分布的要求，使得我们使用个弱化的度分布 即可达到优良的性能。 令c 表示一个维数为k ，长度为, 的线性分组码，q ( x ) 为度分布，则相应的 r a p t o r 码记为( 七，c ，q ( x ) ) 。其编码过程可以简单描述如下，对于给定的k 个输入 符号，将其编码成c 中的一个码字，然后使用度分布q ( x ) 对该码字进行l t 编码 得到最终的输出符号。我们也可以使用二部图来简单地表示这一过程，如图2 3 所示。 p r e c o d i n g l t - c o d i n g 2 3 2 系统r a p t o r 码 图2 3r a p t o r 码的二部图 在许多实际应用中，人们常希望接收端可以不经译码而直接收到部分信息比 特，这样那些无法进行译码的用户也就能加入会话进程。而要实现这一目标，系 统码的使用就成了最佳选择。由于随机的构造方法，l t 和r a p t o r 码本身都不是系 统的，因此，构造系统r a p t o r 码成了实际应用所必需考虑的问题【5 1 【6 1 。 图2 4 系统r a p t o r 码编码框图 由编码理论可知，码的性能是由其包含的所有码字决定的，而不是码字和信 第二章数字喷泉码 息序列问的映射关系。因此，只需要合理地设计码：# 和信息序列的映射关系就可 以将非系统r a p t o r 码转换为系统r a p t o r 码，图2 4 给i i 了一种系统r a p t o r 码的编 码框图。k 个信源符号c 首先通过预处理转换为k 个输入符号d ，接着使用一个 高码率的系统分组码对d 进行编码得到l 个中问符号f ，对f 进行l t 编码得到 最终的输出符号e 。对于上述系统码，有 巨= e ，i = l ，k ( 2 - 4 ) 其中，e 为第i 个输出符号，c ，为第f 个信源符号。假设前阶输出符号所对应的非 系统r a p t o r 码的生成矩阵为g 。，则有e = g t d 。为了满足式( 2 - 4 ) ，显然有 d ：g c 。正如图2 4 所示，系r a p t o r _ i i qn - - i 看作是g ，预编码g p 和l t 码 g ，的串行级联，因此我们可以直接构造g ：_ n ，并使用非系统r a p t o r 编码来实现 该系统码。但实际上，并不需要这么复杂的操作，而是可以直接由信源符号c 得到 中间符号f 【4 7 1 。 定义一个码约束矩阵a 0 ，2 ，k ) ，且满足 a 0 ，2 ，七) f 兰 0 7c7 r ( 2 - 5 ) 不难推导出， 榔，= 慨厶 仁6 ， 其中，g p 为预编码的生成矩阵，i s 为s j 的单位阵，g l r ( 1 ，七) 为l t 码前七个 编码符号的生成矩阵。我们也可以用图示来更清晰地描述式( 2 5 ) 中的约束关系， 如图2 5 所示。 ks g p g 丁( 1 ，2 ，k ) 图2 5 系统r a p t o r 码中的约束关系 在实际应用中，例如，m b m s ( m u l t i m e d i ab r o a d c a s t m u l t i c a s ts e r v i c e ) ，系统 r a p t o r 码的译码既不使用b p 算法，也不使用高斯消去法，而是直接通过图2 4 中 1 2 衰落信道f ：无码率码技术研究 编码的逆过程来实现。r a p t o r 码在实际应用中的编译码框图如图2 6 所示。显然， 其编译码器都是由两个基本模块构成的，1 ) 码约束处理器；2 ) l t 编码器。 在发送端，码约束处理器通过解方程a 0 ，2 ，k ) f = 【0 7c7 】7 求得中间符号 f 。然后进行l t 编码输出编码符号e = g 。，( 1 ，z ) f 。 在接收端，经过删除信道后，译码器正确接收到，个编码符号k 以及相应 的生成矩阵g 。，( ，) ，根据码约束处理器计算中间符号f ，即求解以下方程： a ( f l ，g r ) 。f = 0 。e 口 ( 2 - 7 ) 最后，由于是系统码，所以可通过l t 编码得到信源符号c ，即 c = e = g r ( 1 ，霓) f ( 2 - 8 ) 图2 6 系统r a p t o r 码在实际应用中的实现框图 2 4 本章小结 在本章中，我们首先给出了理想广播、多播传输协议的要求，并由此引出数 字喷泉解决方案。接着详细描述了l t 码和r a p t o r 码的编译码原理和度分布的设计。 第二：章数字喷泉码 最后针对前述两种码均为非系统码的缺陷，介绍了一种系统r a p t o r 码的编泽码过 程以及在实际应用中的实现。 第i 章k i t e 码 第三章k i t e 码 本章我们将介绍一类新的无码率前向纠错码k i t e 码。首先介绍了k i t e 码的 编码原理及其与现有喷泉码的区别；其次详细介绍了k i t e 码的译码原理；接着推 导了k i t e 码的重量枚举函数；最后给出了一种基于仿真的贪心算法来进行码优化。 3 1k i t e 码的编码原理 本节我们将介绍一类新的无码率前向纠错码k i t e 码【4 6 1 ，该码可以看作是一 种特殊的无码率低密度奇偶校验码( r a t e l e s sl o w d e n s i t yp a r i t y c h e c kc o d e s ) 。与传统 的喷泉码不同，该码主要是针对高斯信道设计的，具有简单的编译码算法。此外， 当r e e d s o l o m o n ( r s ) 码作为外码与其串行级联时，能够进一步降低错误平层，实 现接近香农限的性能。 在正式介绍k i t e 码之前，我们先给出前缀无码率l d p c ( p r e f i xr a t e l e s sl d p c ) 码的概念。令e 表示含有口个元素的有限域，譬为取自中的元素构成的无限长 序列的集合。显然，在通常的序列加法和标量乘法运算下，f 可构成一个线性空 间。类似传统线性分组码的定义，一个无码率线性码c o o ，k 】同样定义为覃的一个 k 维子空间。令c n ，k 1 表示c o o ，k 】中码字所对应的长度为疗的前缀码，即 c 【玎，k 】垒 丛咒】叁( c o ，q ，c n 一) i d 玎】是c ，七】中无限长序列的前缀 ( 3 - 1 ) 显然，c ，z ，k 】也是一个线性码。如果c k ，k 】的维数为k ( 由此可得c n ，七】，刀 k 的 维数均为k ) ，则称c 陋，k 】为一个前缀无码率线性码( p r e 行xr a t e l e s sl i n e a rc o d e ) 。更 进一步，如果所有c n ，k 1 码都具有低密度奇偶校验矩阵，我们则称c o o ，k 】为前缀 无码率l d p c 码。 接下来，我们将介绍一类特殊的