（通信与信息系统专业论文）无码率码及其在可靠组播数据传输协议中的应用.pdf

中山大学硕士学位论文中文摘要 无码率码及其在可靠组播数据传输协议中的应用 专业t 通信与信息系统 硕士生：张小清 指导教师：马啸教授 摘要 本文主要介绍了l t 码( l u b yt r a n s f o r mc o d e s ) 。l t 码是新型纠删码也即无码 率码的首次实现。不像传统纠删码，无码率码的编码长度是不固定的，并且信道 的丢失率是未知的。编码符号可以实时产生，其数目随需要而定。无论信道的丢 失率有多大，编码器可以一直产生编码符号并通过删除信道发送出去，直到接收 端恢复出原始信息序列为止。 本文通过r e c e p t i o no v e r h e a d ( 接收的编码符号的个数与传输的输入符号的个 数之比) 这个重要的参数研究了l t 码的性能。通过性能仿真得知，随着数据长度 的增加，l t 码的性能会变得越来越好。由于无码率码可以产生无穷多的编码符 号，我们将其应用于可靠组播数据传输协议中。实际上，当异步分层编码( a l c ) 可靠组播协议中信道编码采用无码率码时，接收端有一个用户，还是有成千上万 个不同类型的用户，服务器的负载都保持常数，a l c 协议也就具有了更强的可 扩展性。 关键词：二进制删除信道，无码率码，l t 码，置信传播译码算法，异步分层编 码可靠组播协议 中山大学硕士学位论文 t i t l e ：r a t e l e s sc o d e sa n dt h e i r a p p l i c a t i o n st o r e l i a b l em u l t i c a s td a t at r a n s m i s s i o np r o t o c o l s m a j o r ：c o m m u n i c a t i o na n di n f o r m a t i o ns y s t e m n a m e ：x i a o q i n gz h a n g s u p e r v i s o r ：p r o f x i a om a a b s t r a c t i nt h i sp a p e r , w ed i s c u s sl tc o d e s ( l u b yt r a n s f o r mc o d e s ) w h i c ha r et h ef i r s t p r a c t i c a lr e a l i z a t i o no fa l le x c i t i n gn e wc l a s so fe r a s u r ec o r r e c t i o nc o d e s ，c a l l e d r a t e l e s sc o d e s u n l i k e 丽血t r a d i t i o n a le r a s u r ec o r r e c t i o nc o d e s ，t h el e n g t ho far a t e l e s s c o d ei sn o tf i x e dap r i o ra n daw i d er a n g eo fc h a n n e ll o s sc o n d i t i o n sc a nb ec o v e r e d f u r t h e r m o r e ，e n c o d i n gs y m b o l sc a nb eg e n e r a t e do n - t h e f l y , a sf e w o ra sm a n ya s n e e d e do nd e m a n d n om a t t e rw h a tt h el o s sp r o b a b i l i t yi s ，t h ee n c o d e rc a l lg e n e r a t e e n c o d i n gs y m b o l sa sr e q u i r e da n ds e n dt h e mo v e rt h e e r a s u r ec h a n n e lu n t i la s u 伍c i e n tn u m b e rh a sa r r i v e da tt h er e c e i v e ri no r d e rt or e c o v e rt h ed a t a i nt h i sp a p e r , w es t u d yt h ep e r f o r m a n c eo fl tc o d e sf o c u s i n go nt h ei m p o r t a n t p a r a m e t e r ：r e c e p t i o no v e r h e a d ( t h er a t eo ft h en u m b e ro fe n c o d i n gs y m b o l sr e c e i v e d a n dt h en u m b e ro fi n p u ts y m b o l st r a n s m i t t e d ) t h r o u g ht h ep e r f o r m a n c ec u r v eo fl t c o d e s ，w ek n o wt h e ya r ev e r ye f f i c i e n ta st h ed a t al e n g t hg r o w s b e c a u s em t e l e s s c o d e sc a ng e n e r a t ea nu n l i m i t e dn u m b e r so fe n c o d i n gs y m b o l s ，w er e c o m m e n dt h e m f o ra p p l i c a t i o n si nr e l i a b l em u l t i c a s td a t at r a n s m i s s i o np r o t o c o l s i nf a c t , w h e n a s y n c h r o n o u sl a y e r e dc o d i n g ( a l e ) r e l i a b l em u l t i c a s tp r o t o c o li s c o m b i n e dw i t h r a t e l e s sc o d e s 。s e r v e rl o a dr e m a i n sc o n s t a n tw h e t h e rt h e r ea r eo n eo rm i l l i o n so f h e t e r o g e n e o u sr e c e i v e r s a l cp r o t o c o lh a sm o r em a s s i v es c a l a b i l i t y k e yw o r d s ：b e c ，r a t e l e s sc o d e s ，l tc o d e s ，b p a ，a l cr e l i a b l em u l t i c a s tp r o t o c o l 1 1 1 中山大学硕士学位论文 缩略词及其说明 l tc o d e s a l c b e c b p a t c p a r q f e c b s c b i a w g n h e c m l a i e e e m b m s r sc o d e s l c t i e t f f l i d 缩略语及其说明 l u b yt r a n s f o r mc o d e s a s y n c h r o n o u sl a y e r e dc o d i n g b i n a r ye r a s u r ec h a n n e l b e l i e f - p r o p a g a t i o na r i t h m e t i c t r a n s f e rc o n t r o lp r o t o c o l a u t o m a t i cr e p e a tr e q u e s t f o r w a r de r r o rc o r r e c t i o n b i n a r ys y m m e t r i cc h a n n e l b i n a r yi n p u ta d d i t i v e 洲t eg a u s s i a nn o i s e h y b 耐e r r o rc o r r e c t i o n m a x i m u ml i k e l i h o o da r i t h m e t i c i n s t i t u t eo fe l e c t r i c a la n de l e c t r o n i c se n g i n e e r s m u l t i m e d i ab r o a d c a s ta n dm u l t i c a s ts e r v i c e r e e d s o l o m o nc o d e s l a y e r e dc o d i n gt r a n s p o r t i n t e m e te n g i n e e r i n gt a s kf o r c e f a i rl a y e r e di n c r e a s e d e c r e a s e 3 9 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立进行研究 工作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的作品成果。对本文的研究作出重要贡献的个人和集 体，均已在文中以明确方式标明。本人完全意识到本声明的法律结果由本人承担。 使用授权声明 学位论文作者签名：冰小吨 日期：潲年步月。8e l 本人完全了解中山大学有关保留、使用学位论文的规定，即：学校有权保留 学位论文并向国家主管部门或其指定机构送交论文的电子版和纸质版，有权将学 位论文用于非赢利目的的少量复制并允许论文进入学校图书馆、院系资料室被查 阅，有权将学位论文的内容编入有关数据库进行检索，可以采用复印、缩印或其 他方法保存学位论文。 学位论文作者签名：张卜、摹 日期：郴年哆月。苦日 导师签名： 日期：风年咯月ge l 中山大学硕士学位论文第一章引言 1 1 研究背景 第一章引言 早在1 9 5 5 年，e l i a s 1 就提出了二进制删除信道( b e c ) ，直到差不多4 0 年后 i n t e m e t 的全球发展，人们才开始真正使用b e c 信道。i n t e m e t 就是一个标准的 b e c 信道实例，在i n t e m e t 上传输的数据很可能丢失。一直以来，如何保证大容 量数据在i n t e m e t 上实时可靠传输是无数学者及研究人员的研究主题。 一般通过使用一些合适的协议来保证数据的可靠传输。在删除信道上传输数 据一般都会使用回传信道，由接收端向发送端发送回传信息，请求发送端将传输 过程中被删除的数据包重新发送。基于确认信息a c k 的t c p 协议就是这样一种 协议，t c p 会在传输窗口之间通知发送端重新发送接收端已经接收到但还没有确 认的数据包，也即反馈重发技术( a r q ) 。这种协议的性能不佳是公认的，尤其在 发送端需要同时发送信息到很多接收端( 即组播传送) ，或者在信道受到严重损害 ( 比如环境恶劣的卫星及无线电) 的情况下。t c p 协议还有一大弊端，就是在发 送端与接收端之间的距离很远时，发送端需要等待很长的时间才能收到接收端发 出的确认信息a c k ，严重拖延数据的传输。 而基于前向纠错( f e c ) 技术的纠删码是可能保证数据实时可靠传输的。对于 组播传送的，如果采用纠删码恢复数据，发送者将数据编码后通过删除信道发送 给多个接收者，在传输过程中由于数据的出错或丢失，不同的接收者收到不同的 数据，但它们可根据所接收数据中一定的冗余位来恢复出原始数据。因而，采用 前向纠错编码技术可以极大减少数据重传，从而加快数据的传输速度。当然，如 果所采用的纠删码的编译码速度很快，则可以实现数据的实时传输。可见，采用 编译码速度快的纠删码技术，对于在可靠组播数据传送中，大量数据的实时可靠 传输的实现是非常关键的。当然，这种纠删码恢复数据的方式不仅可以用于传统 的网络中，对于用在无返回信道的卫星通信、海底电缆、以及无线网络通信中数 据的传输有非常重大的意义。 中山大学硕士学位论文 第一章引言 r s 码是一种纠突发错误的能力比较强的前向纠错码，它的优点是从力个发 送符号中，只要接收到任何k 个数据符号即可以恢复原始的k 个数据符号，但它 的缺点是r s 码只适合在k 、刀及口数值很低的情况下使用，不适合大量数据的 可靠传输。另外，r s 码就如同任何其它分组码一样，需要在传输之前预估信道 删除率及预先选择码率。 我们希望有一种简单的方法可以实时增加编码，生成一个码率较低的码，但 是r s 码并不能实时增加编码。 1 9 9 8 年，m i c h a e ll u b y 提出了一种新的编码方案：无码率码( r a t e l e s sc o d e s ) ， 并于2 0 0 2 年发表“l tc o d e s ”【2 】。无码率码不仅具有简单的编译码算法，而且 能够很好解决由单向删除信道或非对称通信连接所带来的数据分配问题。本文的 目的就是描述这类能够产生无穷多的编码符号的新的编码方案，并仿真出其性能 曲线，分析其性能，给出将这种无码率码应用于可靠组播数据传送协议的方案。 1 2 论文的主要工作及结构 本文主要讨论了目前信道编码领域的热点课题一无码率码的理论。分析了主 要的编译码算法及其性能分析方法，并且提出将无码率码应用于异步分层编码 ( a l c ) 协议的方案。 第二章先介绍了典型通信系统模型，说明主要的信道模型，接着给出差错码 控制系统的分类，最后介绍了纠删码的纠删原理及传统纠删码的编译码方法。 第三章详细阐述了无码率码的编译码方法；给出l t 码的性能仿真曲线并分 析其性能，得知随着数据长度的增加，l t 码的性能会变得越来越好。 第四章介绍了许多可靠组播数据传输协议，通过比较和分析，本文认为异步 分层编码协议( a l c ) 是最适合的可靠组播数据传输协议。由于无码率码能够产生 无穷多的编码符号，本文提出将无码率码应用于a l c 协议的方案。 2 中山大学硕士学位论文第二章通信系统模型及纠删码的介绍 第二章通信系统模型及纠删码的介绍 克服距离上的障碍，迅速而准确地传递信息是通信的任务，传递信息所需要 的一切技术设备的总和称为通信系统。通信系统的基本目的在于将信息由信源高 效、可靠、安全地传送到信宿。有扰通信信道中的噪声及删除信道的丢失率均不 可避免地对传输信息产生不同程度的影响，从而可能降低通信的可靠性。s h a n n o n 在1 9 4 8 年发表信息和编码理论的奠基性论文通信中的数学原理，首次指出实 现有效而可靠地信息传输的途径就是通过编码，参阅 3 】 4 】。 2 1 现代通信系统模型 根据s h a n n o n 的信息理论，以基本的点对点通信为例，通信系统的组成( 通 常也称为一般模型) 如图2 1 所示。 图2 1 通信系统的一般模型 图中，信源( 信息源，也称发终端) 的作用是把待传输的消息转换成原始电信 号，如电话系统中电话机可看成是信源。信源输出的信号称为基带信号，指没有 经过调制( 频谱搬移和变换) 的原始电信号，其特点是信号频谱从零频附近开始， 具有低通性，可分为数字基带信号和模拟基带信号。因此信源也分为数字信源和 模拟信源。 发送设备的基本功能是将信源和信道匹配起来，即将信源产生的原始电信号 ( 基带信号) 变换成适合在信道中传输的信号。变换方式是多种多样的，在需要频 谱搬移的场合，调制是最常见的变换方式。对传输数字信号来说，发送设备又常 常包含信源编码和信道编码等。 中山大学硕士学位论文 第二章通信系统模型及纠删码的介绍 信道是指信号传输的通道，可以是有线的，也可以是无线的，甚至还可以包 含某些设备。 图中的噪声源，是信道中的所有噪声以及分散在通信系统中其它各处噪声的 集合。 在接收端，接收设备的功能与发送设备相反，即进行解调、译码、解码等。 它的任务是从带有干扰的接收信号中恢复出相应的原始电信号来。 信宿( 也称受信者或收终端) 是将复原的原始电信号转换成相应的消息，如电 话机将对方传来的电信号还原成了声音。 图2 1 给出的是通信系统的一般模型，按照信道中所传输信号形式的不同， 可进一步具体化为模拟通信系统和数字通信系统。 2 1 1 模拟通信系统 信道中传输模拟信号的系统称为模拟通信系统。模拟通信系统的组成可由一 般通信系统模型稍加改变而成，如图2 2 所示。这里，一般通信系统模型中的 发送设备和接收设备分别为调制器、解调器所代替。 对于模拟通信系统，它主要包含两种重要变换。一是把连续消息变换成电信 号( 发端信源完成) 和把电信号恢复成最初的连续消息( 收端信宿完成) 。从信源输 出的电信号( 基带信号) 由于它具有频率较低的频谱分量，一般不能直接作为传输 信号而送到信道中去。因此，模拟通信系统里常有第二种变换，即将基带信号转 换成适合在信道中传输的信号，这一变换由调制器完成；在收端由解调器完成相 反的变换。经过调制后的信号通常称为已调信号。已调信号有三个基本特性：一 是携带有消息，二是适合在信道中传输，三是频谱具有带通形式，且中心频率远 离零频，因而已调信号又常称为频带信号。 图2 2 模拟通信系统模型 必须指出，从消息的发送到消息的恢复，事实上并非仅有以上两种变换，通 4 中山大学硕士学位论文第二章通信系统模型及纠删码的介绍 常在一个通信系统里还有滤波、放大、天线辐射与接收、控制等过程。对信号传 输而言，由于上面两种变换对信号形式的变化起着决定性作用，它们是通信过程 中的重要方面；而其它过程对信号变化来说，没有发生质的作用，只不过是对信 号进行了放大和改善信号特性等。因此，这些过程认为都是理想的，而不去讨论 它。 2 1 2 数字通信系统 信道中传输数字信号的系统，称为数字通信系统。数字通信的基本特征是： 它的消息或信号具有“离散 或“数字的特性，从而使数字通信具有许多特殊 的方面。例如前面提到的第二种变换，在模拟通信中强调变换的线性特性，即强 调已调参量与代表消息的基带信号之间的比例特性；而在数字通信中，则强调已 调参量与代表消息的数字信号之间的一一对应关系。 数字通信中还具有以下突出优点，参阅【4 】： 抗干扰能力强，信号可再生； 便于进行各种数字信号处理； 易于实现集成化； 经济效益正在赶上或超过模拟( 载波) 通信； 传输和交换可结合起来，传输电话与传输数据也可结合起来，成为一个 统一体，有利于实现综合业务通信网； 便于多路复用。 数字通信主要的缺点是占用频带宽，需要进行同步，设备复杂等。 点对点的数字通信系统模型一般可用图2 3 所示。 图2 3 数字频带通信系统模型 中山大学硕士学位论文第二章通信系统模型及纠删码的介绍 需要说明的是，图中调制器解调器、加密器解密器、编码器译码器等环节， 在具体通信系统中是否全部采用，这要取决于具体设计条件和要求。但在一个系 统中，如果发端有调n j i 密编码，则收端必须有解调解密译码。 数字通信系统可进一步细分为数字频带传输通信系统、数字基带传输通信系 统、模拟信号数字化传输通信系统。 2 1 2 1 数字基带传输通信系统 在数据通信中，由计算机或终端等数字设备直接发出的信号是二进制数字信 号，是典型的矩形电脉冲信号，其频谱包括直流、低频和高频等多种成份。 在数字信号频谱中，把直流( 零频) 开始到能量集中的一段频率范围称为基本 频带，简称为基带。因此，数字信号被称为数字基带信号，在信道中直接传输这 种基带信号就称为基带传输。在基带传输中，整个信道只传输一种信号，通信信 道利用率低。由于在近距离范围内，基带信号的功率衰减不大，从而信道容量不 会发生变化，因此，在局域网中通常使用基带传输技术。在基带传输中，需要对 数字信号进行编码来表示数据，具体模型如图2 4 所示。 图2 4 数字基带传输系统模型 图中基带信号形成器可能包括编码器、加密器以及波形变换等，接收滤波器 亦可能包括译码器、解密器等。 2 1 2 2 数字频带传输通信系统 频带传输通信系统是将信号调制到一定的频率范围以适应信道，通常把有调 制器解调器的数字通信系统称为数字频带传输通信系统。其传输模型和点对点 的数字通信系统模型基本相同，见图2 3 。 6 中山大学硕士学位论文第二章通信系统模型及纠删码的介绍 2 1 2 3 模拟信号数字化传输通信系统 上面论述的数字通信系统中，信源输出的信号均为数字基带信号。实际上， 在日常生活中大部分信号( 如语音信号) 为连续变化的模拟信号。那么要实现模拟 信号在数字系统中的传输，则必须在发端将模拟信号数字化，即进行a d 转换； 在接收端需进行相反的转换，即d a 转换。实现模拟信号数字化传输的系统如 图2 5 所示。 由抽样、量 数字 化、编码组成通信 的模数转换器 系统 2 1 3 信道模型 图2 5 模拟信号数字化传输系统模型 本文研究的主要部分是数字通信系统中编码，而编码与信道的模型有密切的 关系，实际的信道千差万别，为了研究的方便，将信道进行抽象，常见的有如下 几种模型。 根据信道的输入输出的取值连续与否可以将其分为离散信道、连续信道和离 散输入连续输出信道；根据信道统计特性是否随时间改变可以将其分为平稳信 道和非平稳信道；根据信道的输出之间是否具有相关性可将其分为有记忆信道和 无记忆信道；根据信道的特性对输入端是否具有对称性可以将其分为对称信道和 非对称信道。实际应用中所涉及到的信道大多都是离散输入的平稳无记忆对称信 道，下面列出几个典型信道模型，参阅 3 】： 2 1 3 1 二进制对称信道( b s c ) 输入为二值变量0 、l ，输出也为二值变量0 、l ，且传输过程中发生错误( 输 入为0 输出为l 或输入为1 输出为0 ) 的概率与输入无关。如图2 6 所示，其中 p ( 1 0 ) - - p ( o ld 是转移错误概率。 7 中山大学硕士学位论文 第二章通信系统模型及纠删码的介绍 图2 6 二进制对称信道( b s c ) 2 1 3 2 二进制删除信道( b e c ) 输入为二值变量0 、1 ，输出或为输入的二值变量o 、l ，或为删除e ，且通 常传输过程中不同输入被删除的概率相同。如图2 - - 7 所示，其中q 是被删除的 概率。 图2 7 二进制删除信道( b e c ) 2 1 3 3 二进制输入高斯信道( b i a w g n ) 输入为二值变量o ( 映射为+ 1 ) 、1 ( 映射为- 1 ) ，输出为连续变量，且信道中的 加性噪声为服从n ( o ，仃2 ) 的高斯随机变量，如图2 8 所示，其中仃是独立高斯 分布的方差。 八n p ( y 1 1 ) 一 il y 图2 8 二进制输入高斯信道( b t a w g n ) 8 中山大学硕士学位论文第二章通信系统模型及纠删码的介绍 2 2 差错控制系统 在数字通信系统中，利用纠错码或检错码进行差错控制的方式大概有以下几 类，参阅【3 】： 2 2 1 重传反馈方式( a r q ) 发送端发出能够发现( 检测) 错误的码，接收端收到通过信道传来的码后，在 译码器根据该码的编码规则，判决收到的码序列中有无差错产生，并通过反馈信 道把判决结果用判决信号告诉发端。发端根据这些判决信号，把接收端认为有错 的消息再次传送，直到接收端认为正确接收为止。 图2 9a r q 通信原理图 2 2 2 前向纠错方式( f e c ) 发送端发送能够被纠错的码，接收端收到这些码后，通过纠错译码器不仅能 自动地发现错误，而且能自动地纠正接收码字传输中的错误。 图2 - - 9f e c 通信原理图 9 中山大学硕士学位论文第二章通信系统模型及纠删码的介绍 2 2 3 混合纠错方式( i i e c ) 混合纠错方式综合了上述两种纠错方式，其基本思想是发送端发送具有一定 纠错能力的码字，接收端对所收到的数据进行检测。接收端收到码序列以后，首 先检验错误情况，如果在纠错码的纠错能力以内，则自动进行纠错。如果错误很 多，超过了码的纠错能力，但能检测出来，则接收端通过反馈信道，要求发端重 新传送有错的消息。 2 3 纠删码及其纠删原理 前向纠错编码是一种被广泛应用于通信系统中的纠错技术。在通信系统中前 向纠错主要被用于纠正信号在传输过程中出现的误码，它的错误比特位是未知 的；而在i n t e m e t 中，检测错误是由低层协议来完成的，错误的数据帧被抛弃， 丢失的数据在整个数据流中的位置是知道的。因而，前向纠错技术起的是纠删的 作用，它被用于恢复丢失的数据【5 】。 纠删码的基本原理( 图2 - 1 0 所示) 【6 】：对于要传输k 比特的信息位数据，根据 某种编码方法对其编码，生成甩( 甩 k ) 比特的数据，将k 比特的信息位数据和生 成的，z k 比特的冗余位一起发送，接收方可以利用冗余位恢复传输中丢失的信息 位数据；接收方将接收到的k7 ( 七7 k ) 比特的数据，运用相应译码方法恢复 k 比特的信息位数据。 一个( 刀，七) 线性纠错码是可以表示为y = 箩，其d e x - - ( 而，五，一。) 是源数据，y = ( ，咒，此。) ，g 为k x n 矩阵，称g 为此( ，2 ，七) 线性纠错 码的删除矩阵，若g 的子矩阵可逆，则有如下定理： 定理q 7 1 1 8 1 - 设g 为( 刀，k ) 线性纠错码的删除矩阵，若g 的任意k 列组成的 子矩阵g 。均可逆，则利用接收到的任意k 个数据均可重构原来的k 个源数据。 证明：设y 为y 的任意分量组成的向量，即y 。为接收到的数据，则利用对应 于y 的k 个分量( 即y ) 的k 个方程组可以重构源数据，不妨设q 。l 为表示这个方 程组的系数矩阵，则y = 筘，由此得源数据立= y 。( g 。) 。 1 0 中山大学硕士学位论文第二章通信系统模型及纠删码的介绍 证毕 编码数据接收到的数据 的数据 o o o o o o k 疗k 七 图2 1 0 编译码过程的图形表示 便于理解下面举了一个例子。 例l ：设( 甩，七) = ( 5 ，3 ) ，原始数据符号是兰= ( 五、屯、屯) ，f e c 生成以后 的数据符号是y = ( 乃，y 5 ) ，其中乃、儿、y 3 和五、x 2 、x 3 分别相等，对y = 一x g 两边取转置得到y r = g r x r ： 1oo o1o ool 1 儡彳 il 1 a 2 呸2 五 吃 屯 如果用户端只接收n y , 、y 4 、乃，那么本来的咒、y 4 、y 5 是可以通过下面 的矩阵算出来的，那么只要两边乘以它的逆矩阵就可以算出五、x 2 、墨三个原 始数据符号了。 乃 y 飓4 - j = 一一一一一一一一 m 娩乃以儿 置砭而 。l1j o 彳乏 o q 中山大学硕士学位论文第二章通信系统模型及纠删码的介绍 2 4 纠删码的回顾 当前i n t e m e t 上主流的数据传送采用的都是t c p 协议。然而有些业务天生是 最适合于组播传送的，比如证券信息的发布、软件产品的更新、新闻的发布，这 些业务的特点是由一个发送者( 或者称为源) 发送数据，多个甚至成千上万个接收 者接收数据。如果用t c p 来传送数据，那么必须一个一个地发送，必须发送成 千上万次，这是很不合算、非常浪费资源的。 由于这些原因，其它传输方法被提出了，其中一种是基于编码的。采用编码 技术对原始数据进行编码，发送编码后的数据。在传输过程中可能有一部分数据 丢失了，在接收端应用适当的纠删算法，就可以以很大的概率恢复丢失的数据。 e l i a s 指出删除概率为p 的b e c 信道的容量为1 - p 1 】。他进一步证明了在b e c 信道上，码率任意接近1 p 的随机码能够被以很小的错误概率译出来( 用最大似 然( m l ) 译码算法) 。m l 算法即高斯消去( o a u s s i a ne l i m i n a t i o n ) 法，求解线性方程 组。这种方法非常慢，尤其在码字很长的情况下。 下面介绍一些传统纠删码。 2 4 1r s 纠删码 r s 码是一种有很强纠错能力的多进制b c h 码，也是一类典型的代数几何码。 它首先由里德( r e e d ) 和索洛蒙( s o l o m o n ) 应用m s 多项式于1 9 6 0 年构造出来的【3 】。 由于r s 码具有很强的纠突发错误的能力，而且其编译码速度较快，因而被广泛 地应用于通信工程中。通常用r s 纠删码来实现i n t e m e t 中数据的实时可靠组播传 输，它是最早应用于实时可靠组播传输中的前向纠错技术。同时，因为c a u c h y 矩阵逆运算比任何矩阵的逆运算都要简单得多，所以在组播传输中的r s 纠删码 多采用基于c a u c h y 矩阵的r s s q 删码。下面简单地介绍一下c a u c h y 矩阵以及基于 c a u c h y 矩阵的r s 纠删码的基本性能。 r 、 基于c a u c h y 矩阵的r s 纠删码，其生成矩阵q 。i 是一个l 鲁l 矩阵，厶是( 七七) 1 2 中山大学硕士学位论文 第二章通信系统模型及纠删码的介绍 阶单位矩阵，c 是( 仰一七) 七) 阶c a u c h y 矩阵，( 考) 是一个q | j ) 阶矩阵。 定义1 1 5 1设 五，而， 和 乃，y 2 ，儿) 是有限域f 中两个元 素，若对( 1 ) vf l ，2 ，m ) ，w 1 ，2 ，n 有x t + y j 0 ；( 2 ) 对v f ，j e 1 ， 2 ，m ( f _ ，) 有五x j 和v i ，j e 1 ，2 ，n ) ( f ) 有以* y j ，则如图2 - 1 1 所示的矩阵为域f 上的c a u c h y 矩阵。 1 而+ 耽 1 砭+ 娩 1 + y 2 l 恐+ 虼 l 吃+ l x m + y n 图2 - 1 1c a u c h y 矩阵的结构图 c a u c h y 矩阵具有以下特点： ( 1 ) c a u c h y 矩阵的任意子矩阵都是一个c a u c h y 矩阵； ( 2 ) c a u c h y 矩阵的任意子方阵都是非奇异的； ( 3 ) 在域f 中的任意一个( n xn ) 阶c a u c h y 矩阵的逆运算复杂度为域f 中 o ( n 2 ) 运算操作。 由性质( 3 ) 可知，c a u c h y 矩阵的逆运算比任何其它矩阵的逆运算都要简单得 多，它把乘法和除法运算分别转换成加法和减法运算，从而加快r s 纠删码译码 速度。 i 峪纠删码【5 】是一种最大距离可分码，即信息源为k 字段的数据，经过编码 生成，z 字段发送出去，接收方只需要接收任意k 字段数据即可恢复出原来的数 据，因而称r s 纠删码的接收效率为1 。 将r s 纠删码应用于i n t e m e t 的实时可靠组播传输中，可以解决数据重传的 问题，减少了传输迟延。但是它也存在着缺点【5 】：( 1 ) 由于i 述纠删码要在有限 域上进行矩阵运算等复杂的操作，它的编译码时间复杂度分别为 d l o g 万l o g l o g 刀) 和o ( n l 0 9 2 n l o g l o g n ) ( n 是码字的长度) 9 】，随着数据长度的增 者赤_ i ； 中山大学硕士学位论文第二章通信系统模型及纠删码的介绍 加，编译码时间变得非常长，所以在实际应用中，采用r s 纠删码的数据量大小 受到限制。( 2 ) 这种方法并不能彻底消除数据重传，尤其是当接收者的数目很多 或者数据包的丢失率很高时。( 3 ) r s 码不支持接收者在中断后继续接收数据。( 4 ) 在大容量、多用户同时进行实时可靠组播传输时，采用r s 纠删码会造成较大的 延迟。因而在i n t e m e t 中主要把r s 纠删码应用于数据量较t j 、( k ，由如下公式( 3 1 ) 计算出被传输的编码符号乙。 k t 刀= s f gf刀(3-1) f = l 编码符号在传输的过程中，一部分丢失了，如图3 1 中灰色的符号及与其相 对应的矩阵中的列。接收到的编码符号所对应的矩阵中的列重新组合成生成矩阵 。 1 7 中山大学硕士学位论文 第- - 章无码率码的编译码原理 o r i g i n a lg e n e r a t o rm a t r i x t 1 1 藿 。 1 ： 1 耋， l ， 1 耋 ： 爹 孳善 l j t 爹 t r a n s m i t t e dp a c k e t s 图3 - 1 随机线性码的生成矩阵 1 6 】 如图3 - 1 所示，假设接收到个编码符号，k 和满足怎样的条件才能准确 无误地恢复出输入符号序列呢? 如果n 后呢? 让n = k + e ，e 为额外接收到的信息符号。设随机二进制矩阵 中包含可逆矩阵g k 的概率为1 6 ，6 为当额外接收e 个信息符号接收端不 能成功译码的概率。对任意的k ，译码失败的概率满足公式( 3 3 ) 1 6 】。 艿( e ) 2 - e( 3 3 ) 在b e c 信道上，随机线性码并不是好码( 当接收到k 个符号时可译的概率仅 为0 2 8 9 ) 。多接收e 个符号，成功译码的概率为1 6 ( 6 = 2 ) 。因此，随着k 的 增加，随机线性f o u n t a i n 码会任意接近香农限。然而编译码的代价会随着k 的增 加而增加。随机线性f o u n t a i n 码只适合于k 比较小的情况下( k o ) ，令r = cl n ( k 6 ) 4 k ，定义f 为： ，r d k d = 1 ，k r l z ( d ) = r l n ( r g ) k 拈州r ( 3 - 5 ) 1 0 d = k r + l ，k 七 卢= ( j d ( d ) + r ( d ) ) d = 1 ，2 ，3 ，k ( 3 6 ) d = l p ( d ) = ( p ( d ) + r ( d ) ) f l d = l ，2 ，3 ，k ( 3 7 ) 其中仃为在一定数目的编码符号被接收后译码器译码失败的上界。 图3 3 是当k = 1 0 0 0 0 ，c = 0 2 ，仃= o 0 5 时r o b u s t s o l i t o n 分布。由图知f 和p 在 d = 1 和d = k r 时最大，则j l i 在d = l 和d = k r 时也最大，即度为1 和度为k r 的 编码符号比较多。l u b y 在 1 6 d 0 分析：分段函数r 中，d 取小的值确保译码过程 中山大学硕士学位论文 第三章无码率码的编译码原理 能够开始，而d = k r ( r 取最大值) ，确保每一个输入符号至少有一个编码符号与 其相连。l u b y 的关键结论是：对于一个合适的常数c ，接收到= k + 2 l o g ( r s ) r 个编码符号，能够确保所有的输入符号至少以1 6 的概率被恢复。 l i l i i - ii - ill j jij 图3 3t a l l 柏。图 b p 译码的一个简单的例子如图3 4 所示，其中输入符号数k = 3 ，编码符号数 n = 4 。按照b p 译码算法，得到源信息位是1 0 1 。 3 3 r a p t o r 码和o n l i n e 码简介 r a p t o r 码【1 7 】是l t 码的扩展，在编码之前，首先对数据进行预编码，然后 再用l t 编码算法进行编码。预编码过程是将原始输入符号通过某种传统的纠错 码转换成为中间编码校验符号，然后将中间编码校验符号作为l t 码的输入符号 进行编码。预编码一般要采用高码率的纠错码( 如高码率的l d p c 码、r s 码) ， 由于r a p t o r 码的预编码过程，使得它不像l t 码一样，它适合于传输小量数量或 要求高传输率的环境。 中山大学硕士学位论文第三章无码率码的编译码原理 智是 。eiiei 。辩 。嚣 f1o1 ooo 图3 4 o n l i n e 码【1 8 】也是在l t 码的基础上加了一层预编码，具有线性的编译码时 间，同l t 码一样是无码率码，其性能与r a p t o r 码接近。该算法由纽约大学p m a y m o u n k o v 提出，并以此开发产品，申请了专利。 2 4 中山大学硕士学位论文第三章无码率码的编译码原理 由于r a p t o r 码和o n l i n e 码都要对数据进行预先处理，它们适合于需要传输 小量据量或要求高传输率的环境，在这样的环境下，它们的性能要优于l t 码。 3 4l t 码编译码算法的性能仿真 由于l t 码的度的分布受参数影响，我们将在这一小节设计实验仿真分析不 同的参数对于性能的影响。假定所有的输入符号都存放在物理寄存器中。 l t 码的性能主要通过译码是否有效来衡量，而译码的无效性是由需要接收 多于k ( 假设有k 个输入符号) 个编码符号才能成功译码引起的，还与编码过程中 的随机行为有关，所以需要做多次测试，之后统计分析出变化的规律。由于重量 分布的计算与输入符号的个数k 有关，k 也是影响l t 码性能的主要因素。 如果接收到的编码符号的个数小于输入符号的个数k ，是不可能成功译码 的。那么需要多接收多少个编码符号才能成功译码呢? 设过接收率 r 卢= 孚( 卢 1 ) ，即为了恢复源信息序列，接收端需要接收到卢后个编码符号。3 仅 石 与输入符号的个数有关。 由公式3 - 4 知，c 和6 ( 6 为译码失败的概率) 是影响编码符号度的分布的参 数。图3 5 是k = 1 0 0 0 0 时，c 、艿与p 的关系图。由图3 5 可以看出：( 1 ) 对于任意 接收到的n ( 七) 个编码符号，存在一个常数c 使得译码器能够以至少1 6 的 概率译码。例如对于艿：o 1 ( 即译码器至少能够以9 0 的概率译码) ：接收端接收 到3 k = 1 0 7 0 0 个编码符号时，c 取0 0 3 ；接收到卢七= 11 2 0 0 个编码符号时，c 取0 0 9 ； 接收到1 3 k = 1 2 3 5 0 个编码符号，c 取0 2 。( 2 ) 对于相同的c ，艿越小，卢越大，即 成功译码需要的编码符号越多。例如对于c = 0 0 3 ：6 = 0 1 时，3 = 1 0 7 ，即需多接 收7 0 0 个编码符号，译码器可以以至少1 一艿的概率译码；6 = o 0 5 时，3 = 1 0 7 5 ， 即需多接收7 5 0 个编码符号，译码器可以以至少1 6 的概率译码。 中山大学硕士学位论文 第三章无码率码的编译码原理 o - b e t a + c l e l t a = o 1k = 10 0 0 0 + d e l t a ：o 0 5k = 10 0 0 0 一 矿 。z ，i 。哆 ， ，力 f ， 荔 声。 幸 够 i - i i 0 70 o 磊，o 1o 。 ，5o 2 7d 2 鑫& a 3 s o 图3 5 1 蛩3 - 6 理论上c 与p 的关系图 醛p 窭 雕_ 墨 中山大学硕士学位论文第三章无码率码的编译码原理 怨， 图3 7 实际中c 与卢的关系图 图3 6 是理论上c 与j 6 i 的关系图，其中6 = o 1 ，k 分别取1 0 0 0 0 、5 0 0 0 、1 0 0 0 。 l u b y 在【2 】中分析得出：对于一个合适的常数c ，译码器需要接收 n = k + 2 l o g ( r 3 ) r 个编码符号就可以以1 6 的概率译码。图3 6 显示c 的值越小， 过接收率p 的值就越小，也即成功译码所需的编码符号数就越少。在实际试验仿 真中并非如此，图3 7 为实际中c 与卢的关系图，由图可以看出对于不同的k ，c 都 是在0 0 2 0 0 5 内取值时，卢的值比较小。 由l t 码的度的分布，我们知输入符号的个数k 的大小也是影响译码是否成功 的关键因素。由图3 5 分析可知，对于相同的c ，6 与芦成反比，图3 8 只显示了k 与卢的关系，其中c = 0 0 2 ，艿= o 1 。当k = 1 0 0 时，p = 1 8 0 才能够成功译码，这是 非常大的。然而，随着k 增大，p 减小的很快，当k = 5 0 0 0 0 时，p - - 1 0 3 6 就可以 成功译码了。因此l t 码非常适合大容量数据的可靠传输。 坐奎兰堡圭堂堡垒奎苎三妻二至鎏壁翌型堕塑翌 7 k - b e t a 、 露 黑 图3 8 输入符号数k 与p 的关系图 u n f i n i s l e dr e c e i v e r s 图3 9 照mml寒me口mc协一c|ic3-o o e a 中山大学硕士学位论文第三章无码率码的编译码原理 图3 - 9 是当k = 1 0 0 0 0 ，c = o 0 4 ，艿= 0 1 时，对每一个卢( 做1 0 0 0 次测试) 译码不 成功的概率图( 纵坐标p r o bo f u n f i n i s h e dr e c e i v e r s 为1 0 0 0 次测试中译码不成功