（通信与信息系统专业论文）无线通信系统中无速率码的编译码技术与应用研究.pdf

浙江大学博士学位论文中文摘要 摘要 随着无线通信技术的飞速发展，高效而又可靠地数据传输技术受到了越来越多的重 视和关注。面对当前越来越复杂的通信环境，很多情况下发射机难以预先获知准确的信 道状态信息。如何在不知道准确的信道状态信患的情况下，自适应的选择合适的码率对 数据传输进行保护? 无速率码为我们提供了一种解决问题的新思路。无速率码具有码率 自适应信道状态传输的特点，且在传输过程中发送端不需要接收端的反馈，是一种高 效、可靠的差错控制技术，为研究与设计具有自适应特性的、高效、可靠的多用户无线 通信网络提供了一种新的方向。本文主要从无速率码的编译码技术及其在无线通信中的 应用等方面展开深入研究，概括如下： 研究了适用于噪声信道的无速率码的编码结构及译码算法在对编码结构的研究 中，首先分析了类似l t 码的无速率编码结构应用在噪声信道下所产生的问题，指出产生 差错平台问题的关键在于存在着度数为1 的编码节点直接与噪声信道相连。然后区别于 现有的类似r a p t o r 码的级联编码结构，设计了一种利用累加器消除度数l 的编码节点的无 速率编码结构，命名为a r ( a c c u m u l a t er a t e l e s s ) 码。具有线性编译码复杂度的a r 码不 仅结构简单，还有效解决了差错平台问题，且性能可以逼近采用级联结构i 均r a p t o r 码 在对译码方法的研究中，以当前应用最为广泛t 均r a p t o r 码的译码为例，首先总结了无速 率码的译码特点分析了现有译码方法的不足，并结合无速率码的译码特点，提出了串行 存储置信度传播算法然后利用高斯近似密度进化理论进行分析，证明了其所需迭代次 数更少，且通过对比串行译码算法和并行译码算法在每一轮迭代中的计算复杂度，证明 了其在不降低误比特率性能的基础上，具有更低的译码复杂度。 研究了利用无速率编码与多接入技术相结合的问题，提出了一种新的分布式多接入 技术：无速率编码多接入技术在无速率编码多接入系统中，各接入用户发射机的行动 模式是相同的，且在传输过程中无需相互协调，具有与a l o h a 技术相似的简便性首 先，我们研究了在删除信道下无速率编码多接入的最大吞吐率问题为达到系统吞吐率 性能最佳，每个接入用户的接入概率由各自的控制器进行控制分析表明，每个用户的 最优接入概率与接入系统的总用户数有关仿真结果显示，做为一种分布式随机接入技 术，无速率编码多接入可以取得极佳的系统吞吐率性能接下来，我们研究了在噪声信 道下无速率编码多接入的传输与译码恢复问题各用户无速率编码构造的随机性，为用 户消息的区分提供了天然保证公共接收机采用迭代译码与干扰抵消技术，可以有效克 i 浙江大学博士学位论文 中文摘要 服各用户之间的干扰。在仿真中，我们与i d m a 技术进行了对比，验证了无速率编码多 接入技术的良好性能。无速率编码多接入技术，以其协议的简便性与良好的吞吐率性 能，在发射机无法预知信道状态的分布式系统中拥有很强的竞争力。 进一步研究了无速率多用户接入问题，提出了一种新的分布式随机多接入技术：非 编码无速率多接入技术。我们将多接入问题中的每个独立的用户数据看作一个整体，将 接收端的用户分离问题看作是一个分布式联合译码的问题。我们将用户信号的空间叠加 看作是一种无限域信号编码，提出了相应的译码方法，并提出利用其中存在的分集增益 可以对译码带来便利。考虑到迭代译码中软信息之间的独立无关性要求与信号合并增益 之间的折衷，提出了适用于非编码无速率多接入系统的用户信号迭代恢复算法接着， 利用外信息传递技术对迭代过程进行了研究，并分析了迭代算法中用户信号合并产生的 影响。通过仿真，我们验证了非编码无速率多接入系统在两种工作模式下的系统吞吐 率。n c r m a 系统可以方便的进行分布式设计，通过对接入概率的控制，实现系统性能 的最佳。 关键词：无速率编码，喷泉码，多用户接入，密度进化理论，外信息传递 浙江大学博士学位论文 英文摘要 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 t e c h n o l o g y ，m o r ea n dm o r ea t t e n t i o nh a sb e e np a i dt ot h ee f f i c i e n ta n dr e l i a b l ed a t at r a n s m i s s i o nt e c h n o l o g y i nf a c eo ft h e i n c r e a s i n g l yc o m p l e xc o m m u n i c a t i o n se n v i r o n m e n t ，t h et r a n s m i t t e ri sd i f f i c u l tt op r e k n o wt h e e x a c tc h a n n e ls t a t ei n f o r m a t i o ni nm a n yc a s e s t h e n ，h o wt oa d a p t i v e l yc h o o s et h ea p p r o p r i a t e c o d er a t et op r o t e c tt h ed a t a ? r a t e l e s sc o d ep r o v i d e su san e w w a yt os o l v et h ep r o b l e m r a t e - l e s sc o d e ，a sak i n do fe f f i c i e n ta n dr e l i a b l ee r r o rc o r r e c t i o nt e c h n o l o g y ，a t t r i b u t et h ec h a r a c t e ro f c o d er a t ea d a p t i o nt ot h ec h a n n e ls t a t e ，d o e sn o tr e q u i r et h ef e e d b a c ks i g n a ld u r i n gt h et r a n s m i s s i o n ，a n dp r o v i d ean e ww a yo fr e s e a r c ha n dd e s i g nt h ea d a p t i v e ，e f f i c i e n ta n dr e l i a b l em u l t i u s e r w i r e l e s sc o m m u n i c a t i o nn e t w o r k s i nt h i sd i s s e r t a t i o n ，t h ec o d e c t e c h n o l o g ya n dt h ea p p l i c a t i o n s o fr a t e l e s sc o d ei nw i r e l e s sc o m m u n i c a t i o na r ei n t e n s i v e l yi n v e s t i g a t e d ，a n dt h ec o n t e n t so ft h i s w o r ka r el i s t e da sf o l l o w s ： f o rt h ec o d e ct e c h n o l o g y , w ei n v e s t i g a t et h ec o d i n gs t r u c t u r ea n dt h ed e c o d i n ga l g o r i t h m o fr a t e l e s sc o d ef o rn o i s yc h a n n e l s f r o mt h ep e r s p e c t i v eo fc o d i n gs t r u c t u r e ，b ya n a l y z i n gt h e p r o b l e mo fa p p l y i n gt h es t r u c t u r es i m i l a rt ol tc o d eo v e rn o i s yc h a n n e l s ，w ep o i n to u tt h a tt h e e x i s t e n c eo fd e g r e e1p a r i t yn o d e sc o n n e c t i n gt on o i s yc h a n n e ll e a d st h ep r o b l e mo fe r r o rf l o o r t h e n ，w ed e s i g nar a t e l e s se n c o d i n gs t r u c t u r en a m e da r ( a c c u m u l a t er a t e l e s s ) c o d e ，w h i c h u t i l i z et h ea c c u m u l a t o rt oe l i m i n a t et h ed e g r e eip a r i t yn o d e sa n di sd i f f e r e n tw i t ht h es e r i a lc o n - c a t e n a t e ds t r u c t u r es u c ha sr a p t o rc o d e w i t hl i n e a re n c o d i n ga n dd e c o d i n gc o m p l e x i t y , a rc o d e e f f e c t i v e l ys o l v e st h ep r o b l e mo fe r r o rf l o o r , a n dc a na p p r o x i m a t et h ep e r f o r m a n c eo ft h er a p t o r c o d e f r o mt h ep e r s p e c t i v eo fd e c o d i n ga l g o r i t h m ，w et a k er a p t o rc o d e ，t h em o s tp o p u l a rr a t e - l e s sc o d ea tc u r r e n t ，a sa ne x a m p l e ，a n ds u m m a r i z et h ec h a r a c t e r i s t i c sa n dt h ed e f i c i e n c i e so ft h e e x i s t i n gd e c o d i n ga l g o r i t h m s f o r t h ec h a r a c t e r i s t i c so f d e c o d i n gr a t e l e s sc o d e ，w ep r o p o s e dt h e s e r i a ls t o r a g eb e l i e fp r o p a g a t i o na l g o r i t h m t h e n ，u t i l i z i n gt h eg a u s s i a na p p r o x i m a t i o nd e n s i t y e v o l u t i o n ，w ep r o v et h a ti tr e q u i r e sf e w e rd e c o d i n gi t e r a t i o n s b yc o m p a r i n gt h ec o m p l e x i t yo f t h es e r i a la n dp a r a l l e ld e c o d i n ga l g o r i t h mi ne a c hd e c o d i n gi t e r a t i o n ，w e p r o v et h a to u ra l g o r i t h m h a sl o w e rd e c o d i n gc o m p l e x i t yw i t h o u tt h el o s so fb i te r r o rr a t ep e r f o r m a n c e f o rt h ea p p l i c a t i o n so fr a t e l e s sc o d e ，w ei n v e s t i g a t et h ec o m b i n a t i o no fr a t e l e s sc o d ea n d t h em u l t i p l ea c c e s st e c h n o l o g y w c p r o p o s ea n e wm u l t i p l ea c c e s st e c h n o l o g y ：c o d e d r a t e l e s s 浙江大学博士学位论文英文摘要 m u l t i p l ea c c e s s ( c - r m a ) i n t h ec r m a s y s t e m ，t h et r a n s m i t t e ro f e a c hu s e rw o r k si nt h es a m e m o d ew i t h o u tt h en e e do fc o o r d i n a t i o nd u r i n gt h et r a n s m i s s i o n ，j u s tf i t ss i m p l ea st h ea l o h a s y s t e m f r o mt h ep e r s p e c t i v eo ft h ei n v e s t i g a t i o no v e re r a s u r ec h a n n e l ，e a c hu s e ru t i l i z ei t s o w na c c e s sc o n t r o l l e rt oa d j u s tt h ea c c e s sp r o b a b i l i t yi no r d e rt oa c h i e v i n gt h em a x i m u ms y s t e m t h r o u g h p u t o u rr e s e a r c hs h o w st h a tt h eb e s ta c c e s sp r o b a b i l i t yf o re a c hu s e ri sr e l a t e dt ot h e t o t a ln u m b e ro fu s e r ss e r v i n gi nt h es y s t e m s i m u l a t i o nr e s u l t ss h o wt h a t 硒ak i n do fd i s t r i b u t e d r a n d o ma c c e s st e c h n o l o g y , c r m aa c h i e v e sg o o dp e r f o r m a n c eo ft h es y s t e mt h r o u g h p u t n e x t , f r o mt h ep e r s p e c t i v eo ft h ei n v e s t i g a t i o no v e rn o i s yc h a n n e l ，w ei n v e s t i g a t et h ep r o b l e mo fr a t e - l e s st r a n s m i s s i o na n dt h e r e c o v e r ya l g o r i t h mo f e a c hu s e lt h er a n d o m n e s se n c o d i n gs t r u c t u r eo f e a c hu s e rp r o v i d ean a t u r a lf e a t u r et od i s t i n g u i s ht h em e s s a g e so fe a c hu s e r b yi t e r a t i v ed e c o d i n ga n di n t e r f e r e n c ec a n c e l a t i o n ，t h ec o m m o nr e c e i v e rc a l le f f e c t i v e l yo v e r c o m et h ei n t e r f e r e n c e b e t w e e nd i f f e r e n tu s e r s i nt h es i m u l a t i o n ，w ev a l i d a t et h eg o o dp e r f o r m a n c eo fc - r m at e c h n o l - o g yc o m p a r i n gw i t hi d m at e c h n o l o g y w i t ht h es i m p l i c i t ya n dg o o dt h r o u g h p u tp e r f o r m a n c e ， c r m at e c h n o l o g yh a sas t r o n gc o m p e t i t i v e n e s si nt h ed i s t r i b u t e dc o m m u n i c a t i o ns y s t e mi n w h i c ht h et r a n s m i t t e r sa r ed i f f i c u l tt op r e - k n o wt h ee x a c tc h a n n e ls t a t ei n f o r m a t i o n f i n a l l y ，t h ep r o b l e mo fr a t e l e s sm u l t i p l ea c c e s si sf u r t h e rs t u d i e d w ep r o v i d ean e wd i s t f i b u t e dr a n d o mm u l t i p l ea c c e s st e c h n o l o g yn a m e dn o n - c o d i n gr a t e l e s sm u l t i p l ea c c e s s ( n c r m a ) w er e g a r da l lt h ed a t ao ft h eu s e r si nt h em u l t i p l ea c c e s ss y s t e ma saw h o l e ，a n dr e g a r d t h ep r o b l e mo f s e p a r a t i n gt h eu s e rd a t a 觞ak i n do fd i s t r i b u t e dj o i n td e c o d i n gp r o b l e m w er e - g a r dt h es u p e r p o s i f i o no ft h eu s e r s s i g n a l s 硒ak i n do fp h y s i c a ll a y e rc o d i n gi ni n f i n i t ed o m a i n 。 p r o p o s et h ec o r r e s p o n d i n gd e c o d i n ga l g o r i t h m ，a n dp r o p o s et ou t i l i z et h eu s e rd i v e r s i t yg a i nt o p r o v i d ec o n v e n i e n c et ot h ed e c o d i n g h o w e v e r , d u r i n gt h ei t e r a t i v ed e c o d i n g ，t h ed e p e n d e n c e w i l ld e t e r i o r a t et h ep e r f o r m a n c eo fi t e r a t i v ed e c o d i n g t a k i n gi n t oa c c o u n tt h ei n d e p e n d e n tr e q u i r e m e n to ft h em e s s a g e si nt h ei t e r a t i v ed e c o d i n gp r o c e s sa n dt h eg a i nb r o u g h tb yt h es i g n a l c o m b i n i n g ，w ep r o p o s et h ei t e r a t i v er e c o v e r ya l g o r i t h mf o rn c r m as y s t e m t h e n ，b ye x t r i n s i c i n f o r m a t i o nt r a n s f e rt e c h n o l o g y ，w ea n a l y z et h ei m p a c to ft h es i g n a lc o m b i n i n gi nt h ei t e r a t i v e r e c o v e r ya l g o r i t h m s i m u l a t i o n sv e r i f yt h eg o o dp e r f o r m a n c eo fn c r m as y s t e mi nb o t l lt w o w o r k i n gm o d e s n c - r m as y s t e mc a n b ee a s i l yd i s t r i b u t e dd e s i g n e d , a n da c h i e v et h em a x i m u m t h r o u g h p u tb yc o n t r o l l i n gt h ea c c e s sp r o b a b i l i t yo fe a c hu s e r k e y w o r d s ：r a t e l e s sc o d e ，f o u n t a i nc o d e ，m u l t i p l ea c c e s s ，d e n s i t ye v o l u t i o nt h e o r y , e x t r i n s i c i n f o r m a t i o nt r a n s f e r ，e x i t 插图 图1 1l t 码的译码过程示意图【2 1 】 6 图1 2r a p t o r 码的编码结构示意图 7 图2 1l t 码的t a n n e r 图1 6 图2 2a r 码的编码结构图1 8 图2 3a r 码的t a n n e r 图 1 9 图2 4 采用l t 码+ 累加器结构的误比特率性能仿真图2 0 图2 5a r 码、l t 码以及r a p t o r 码的误比特率性能仿真曲线对比图2 1 图2 6 噪声信道下利用无速率码进行传输的模型2 4 图2 7r a p t o r 码的t a n n e r 图2 5 图2 8 串行存储b p 译码算法各分组中信息的更新次序2 9 图2 9 并行译码与串行译码算法中，译码迭代次数与译码错误概率之间的关系图 3 2 图2 1 0a w g n 信道环境中，不同译码算法在不同的最大迭代次数限制下的误比 特率性能3 6 图2 1 1 串行存储b p 译码算法与并行存储b p 译码算法，误比特率降到1 0 _ 7 以下 时，所需的平均迭代次数。横坐标表示码率为2 3 - 1 时，记录的软信息的 迭代次数；纵坐标表示需要的平均迭代次数。 3 6 图2 1 2 瑞利衰落信道环境中，不同译码算法在不同的最大迭代次数限制下的误 比特率性能3 7 图2 1 3 莱斯衰落信道环境中，不同译码算法在不同的最大迭代次数限制下的误 比特率性能3 7 图3 1 两用户无速率编码多接入系统中的数据包发送示意图4 0 图3 2 删除信道下无速率编码多接入系统模型图4 1 图3 3 在m 用户无速率编码多接入系统中，某经历了z 次突发事件的用户的包的 能级分布的示意图4 6 图3 4 不同的用户下，无速率编码多接入系统的吞吐率性能以及与a l o h a 系统 吞吐率的比较4 9 v i i 浙江大学博士学位论文 插图 图3 5 噪声信道下无速率编码多接入系统模型图5 l 图3 6 噪声信道下无速率编码多用户接入的误比特率性能 5 9 图3 7c r m a 与i d m a 的性能比较5 9 图4 1 非编码无速率多接入系统模型 6 l 图4 2 非编码无速率多接入系统的t a n n e r 示意图6 3 图4 3n c r m a 中，进行用户信号合并时，输出软信息与输入软信息的关系示 意图6 6 图4 4 接收节点与变量节点的外信息传递示意图7 1 图4 5n c r m a 系统的外信息传递图示例7 4 图4 6n c r m a 系统中，用户信号合并对接收节点的外信息传递曲线的影响。 系统用户数为8 ，a w g n 信道，s n r = 5 d b ，p - - 0 1 7 ，假设有4 个用户通过用 户信号合并被直接恢复。 7 6 图4 7 非编码无速率多用户接入系统的工作模式一示意图 7 8 图4 8 非编码无速率多用户接入系统的工作模式二示意图 7 8 图4 9 工作模式一中，8 用户非编码无速率多用户接入系统的吞吐率性能与用户 发送概率的关系图7 9 图4 1 0 工作模式一中，1 6 用户非编码无速率多用户接入系统的吞吐率性能与用 户发送概率的关系图7 9 图4 1 1n c r m a 系统- 与a l o h a 系统的单次传输能量消耗下的传输效率比较图8 1 图4 1 2 工作模式二中，8 用户非编码无速率多用户接入系统的吞吐率性能与用 户发送概率的关系图8 2 图4 1 3 工作模式二中，1 6 用户非编码无速率多用户接入系统的吞吐率性能与用 户发送概率的关系图8 2 图4 1 4 工作模式一中，不同滑动窗长度限制下，非编码无速率多用户接入系统 的吞吐率性能图8 3 图4 1 5 工作模式二中，不同滑动窗长度限制下，非编码无速率多用户接入系统 的吞吐率性能图8 3 表格 表3 1 删除信道下，m 用户无速率编码多接入系统吞吐率性能仿真结果5 0 i x 1 1 研究背景 第1 章绪论 从1 8 9 7 年马可尼首次实现长距离无线通信，到现在第三代( 3 g ) 移动通信系统的普 遍应用以及下一代通信系统( b 3 g 4 g ) 商用实验网络的建立的百余年间，无线通信技术 的飞速发展深刻地影响着人类的生活如今，信息已经成为人类社会发展的一个基本要 素。传统的固定电话通信方式已经无法满足人们的需求，人们需要移动的、可靠的、高 速的无线通信方式来满足多样化、普及化、网络化和全球化的信息交流，并希望可以最 终实现：“任何人( w h o e v e r ) 在任何时候( w h e n e v e r ) 可以与任何地方( w h e r e v e r ) 的任何人 ( w h o m e v e r ) 进行任何方式( w h a t e v e r ) 的通信” 1 1 1 信道编码技术与差错控制 相比有线信道而言，在无线信道中传递的数据由于无线信道的开放性更容易被干 扰，使得传输的数据信号出现差错如何进行差错控制是无线传输中需要面对的重要问 题。为了可以在实际通信中有效地对抗噪声干扰，实现准确、可靠地数据传输，往往在 要发送的信息序列中再增加一些冗余位，以便接收机检测和纠正信息在传输中由于干扰 而产生的误码这便是信道编码技术【1 】采用信道编码可以减小传输误码率，提高数据 传输效率，增加通信的可靠性但是，由于信道编码增加了冗余位，使得有效信息的传 输速率降低了。因此，信息的传输速率与可靠性之间存在着某种折衷关系，如何增加冗 余，提高检错和纠错能力，是信道编码的主要研究内容。1 9 4 8 年，香农首先分析了在特 定的信道下，采用最佳信道编码时可以达到的传输速率极限，即信道容量【2 】他指出， 在传输速率小于或等于信道容量的前提下，存在着某种信道编码方案，可以使得传输的 错误概率趋近于0 然而，香农只是在理论上证明了利用码长无限长的编码可以达到信 道容量，并没有给出具体的编码方案，而且，码长很长时在具体实现中会给编译码带来 困难 在很长的一段时间内，出于对复杂度的考虑，人们将构造信道编码的研究重点放在 寻找短码上最早的编码是基于有限域的线性分组码【3 】把输入数据分为长度固定的 组，对每一组分别编码，通过设计，使得编出的码字具有较大的最小码问距离，从而取 l 浙江大学博士学位论文第1 章绪论 得较强的纠错能力。译码时，根据最大似然准则，将接收序列与所有码字进行比较，找 出汉明距离最短的码字作为译码结果，其译码复杂度与码长成指数关系，因此实际应用 中的码长都比较短。比较著名的分组码有汉明( h a m m i n g ) 码、b c h 码、r s 码等等【4 【5 】【6 】然而，由于线性分组码的每个码字只与一组较少的比特信息有关，忽略了各信 息分组之间的联系，导致信息量的丢失，且信息序列切割的越碎( 码字越短) ，丧失的 信息越多。因此，其性能相比信道容量相差比较远。于是，人们想到将有限个分组的相 关信息添加到码字里构成有限记忆系统，来等效地增加码长，这就导致了卷积码的产生 【7 】 卷积码是一个有限记忆系统，它将信息序列切割成一个个分组当某一分组进行编 码时，不仅根据本时刻的分组，而且根据本时刻以前的l 个分组( l 表示卷积码的回溯深 度) 共同来决定输出码字因此，可以说卷积码是一种加长的分组码。卷积码的解码基 于最大似然准则，根据输入解码器的码序列寻找一条最可能是原始信息的比特序列，复 杂度同样与码长成指数关系。不过，著名的维特比( v i t c r b i ) 算法【8 】提出利用了卷积码 的结构和状态转移信息来进行路径回溯，使得译码复杂与码长成线性关系，也使得卷积 码成为了一种十分具有吸引力的编码。 卷积码在低信噪比时编码增益比较高，而在高信噪比时则表现不佳。于是，人们提 出将两种编码方法串联结合起来，构成级联码【9 首先利用以r s 码为代表的分组码作 为“外码”进行编码，再利用卷积码作为“内码”进行编码这样，接收机首先对卷积 码进行译码得到一个低误码率的序列，再利用分组码进一步纠错，降低误码率，其纠错 能力为两种编码的乘积然而，由于本质上其构造的码字都是基于短码而人为设计的， 级联码并没有达到人们的预期，反而在信道质量较差时，存在某种“门限效应”，即新 增加的一层编码反而使得误码越纠越多，使得差错进一步扩展，一旦码率接近信道容 量，其译码性能会很差 由此，人们思考不再单纯局限于最小码间距离人为构造码字，而是借鉴香农在证 明信道容量时的思想，设计基于概率的随机编码，因为足够长的随机序列基本都是典 型列1 9 9 3 年，b e r r o u 等人提出t l l 加码【l o 】，利用随机交织器与并行级联的结构，将两 个短码构造成具有一定随机特性的长码，并且利用迭代的方法进行译码，取得了很好 的效果t u r b o 码中，码字的最小码间距离有可能会很近，但这些码字的比例非常小， 2 浙江大学博士学位论文第1 章绪论 因此整体的误码率可以很低。低密度奇偶校验( l d p c ) 码是另一种基于概率的随机 编码，在码字很长时具有逼近香农限的良好性能。l d p c 码早在二十世纪六十年代就 i 妇g a l l a g e r 提出【1 1 】【1 2 】，但由于当时i c 水平的限制使得其在实现上有困难，直到1 9 9 6 年 被m a c k k a y 等人重新发掘【1 3 】，才引起了人们的广泛重视并应用到实际系统中。 然而，尽管上述基于概率的随机编码具有良好的编码增益，基本达到了香农限，但 其编码码率是预先设定的，且需要发送端编码器预先知道信道状态信息，并选择相应合 适的码率进行编码然而，随着无线应用的不断发展，通信环境越来越复杂，实际中很 多情况下发送端无法事先准确预知信道状态信息，或者在广播时同时面对多个接收端的 多种信道状态，传统的固定码率的前向纠错( f o r w a r de r r o rc o r r e c t i o n ，f e c ) 编码无法 满足数据的可靠传输要求【1 4 】在无线通信网络化的今天，需要更加可靠高效的差错控 制技术。 自动重传请求( a u t o m a t i cr e p e a tr e q u e s t ，a r q ) 技术【1 5 】是除信道编码技术之 外另一种对抗通信中信道干扰的差错控制技术它通过接收端给发送端发送重传请 求，重传出错的数据从而恢复错误数据传统t 均a r q 技术分成为三种：停止等待( s t o p a n d w a i t ) a r q 、回退n 帧( g o - b a c k - n ) a r q 以及选择性重传( s e l e c t i v er e p e a t ) a r q 然而其带宽效率低，信道利用率不高在此基础上，发展出结合f e c 与a r q 的混 合a r q ( h a r q ) 技术【1 6 。在混合a r q d f f ，接收端接收到的数据即使在传输中出错 也不会被丢弃，而是通过各种合并( c o m b i n i n g ) 以及递增冗余( i n c r e m e n t a lr e d u n d a n c y ，i r ) 技术，将再次传送中收到的数据与先前的接收数据综合处理，以纠正差错 【1 7 】【1 8 1 。然而，现代无线网络必须有能力支持更多的用户在传输用户数目较多的条 件下，大量用户的反馈信号容易引起网络阻塞，导致通信无法正常进行而且，当发送 端与接收端距离较远时，反馈信号需要经历较长的时间才可被发送端接收到，从而增加 了传输延迟因此，现代无线通信网络传输，需要一种既具备良好编码增益，又可以自 适应信道状态且尽可能减少反馈信号的高效传输机制 1 1 2 无速率编码技术 无速率编码技术正是一种既具备良好编码增益，又具有良好的自适应信道状态传输 特性的高效的差错控制技术，且接收端在正确恢复所有消息后，只需要发送一个最简单 的结束信号告知发送端停止发送印可无速率编码与传统信道编码的最大差另0 在于，其 3 浙江大学博士学位论文第1 章绪论 发送端不预先设定固定码率，而是按照某种编码生成方式源源不断的产生编码包并发送 出去，其接收端则根据接收到的编码包尝试译码。如果译码失败，接收端可以再多接收 一些编码包继续尝试译码，直到译码成功。一旦成功译码，接收端只需要发送一个非常 简单的结束信号告知发送端译码成功，然后发送端停止发送即可，而在传输过程中无需 任何反馈信号无速率编码的实际传输码率取决于实际发送的编码包数量，发送的编码 包数量则与信道质量的好坏有关，具有自适应传输的特点。从某种意义上可以认为，无 速率编码技术是一种具有最简单反馈形式h a r q 。 最初，无速率编码是针对以因特网为代表的数据通信网中，广播通信与时延敏 感业务而设计的。由于网络链路质量具有时变性，且广播中不同用户接收端与发送 端之间的信道质量也不同，发送端很难仅仅依靠固定码率的f e c 实现高效而可靠的传 输，因为信道质量较差的链路需要低码率的编码来保证传输的可靠性，而信道质量 较高的链路可以采用更高码率的编码来提高传输效率，低码率意味着传输的浪费 为此，b y e r s 、l u b y 等人于1 9 9 8 年针对二元删除信道( b i n a r ye r a s u r ec h a n n e l ，b e c ) 提 出了无速率删除码( r a t e l e s se r a s u r ec o d e ) 的概念( 因特网的链路控制层即可看做一 个b e c 实例) 【1 9 】，指出编码器可以类似一个喷泉一样，源源不断的产生编码因 此，无速率删除码又被形象的称为喷泉码( f o u n t a i nc o d e ) 文献【1 9 】中提出可以借 鉴t o r n a d o 码【2 0 的不规则稀疏生成矩阵的方式，构造喷泉码。然而，若是仅仅采用随 机选择的方式进行编码，虽然可以逼近香农限，但其编译码复杂度为多项式复杂度 【2 1 ，难以应用与实际系统。2 0 0 2 年，l u b y 正式提出了u 码【2 2 ，通过设计编码包的度 数分布，使得编码矩阵形成了具有较低代价的稀疏矩阵，与线性随机无速率编码相比 大大降低了复杂度然而，l t 码编码包的平均度数和以及译码开销( o v e r h e a d ) 与输入 编码器的数据长度有关为了进一步降低编译码复杂度和减小译码开销，s h o k r o l l a h i 提 出了r a p t o r 码【2 3 r a p t o r 码采用了串行级联的结构，通过预编码降低对u 码译码性能 的要求，从而使得l t 码编码包的平均度数可以降低为常数r a p t o r 码的运算复杂度降 为线性复杂度，且其译码开销也为常数，与输入数据长度无关- 9 r a p t o r 码类似的还 有m a y m o u n k o v 提出的在线编码( o n l i n ec o d e ) ，其也是采用了级联编码的形式，但更接 近于t o r n a d o 码的级联稀疏生成矩阵的方式进行编码，设计理念上r a p t o r 码大致相同 在线编码的编译码复杂度也是线性复杂度 4 浙江大学博士学位论文第1 章绪论 无速率编码的速率自适应匹配的特性，使得它可以实现高效而可靠的传输，可以广 泛应用于广播、中继、认知无线电等无线通信系统中，也可适合于存储、压缩编码和网 络编码。下一节中，将更加详细的介绍无速率编码的研究现状及其应用。 1 2 研究现状与研究动机 对于无速率编码技术的研究可以分为两个方面，一方面是对其编码结构及译码方法 的研究，另一方面是将其在各种通信场景与系统中进行应用的研究。 1 2 1 无速率码的编译码技术研究 1 2 1 1 两个经典的无速率编码一一l t 码与r a p t o r 码 l t 码是第一种可以应用于实际的无速率编码设输入l t 码编码器的数据包数量 为k ，分别记为岛，岛，以生成第n 个编码包t n 为例，编码器首先按照一定概 率随机产生一个度数d t ，然后从k 个数据包中，随机选取d 个数据包，按照对应的比特进 行模2 加合运算，从而生成编码包t 住从编码过程中可见，l t 码可以被看成是一个无速 率低密度生成矩阵( l o wd e n s i t yg