（通信与信息系统专业论文）保证视频通信质量的fec算法研究与实现.pdf

摘要 视频码流是经过高效压缩的数据，其比特流之间的相关性非常强，因此对误 码或数据丢失很敏感。在分组网络通信中，由于因特网只能提供“尽力服务 ， 因此分组丢失不可避免。这样，在网络视频通信中纠错控制的重要性不言而喻。 本论文重点研究应用于视频的纠删码算法，首先阐述了纠删码的研究背景和 进展，详细介绍了r s 码、t o r n a d o 码、l t 码和r a p t o r 码的编解码方法、编解码 复杂度及性能。然后，提出并实现了一种卷积式t o r n a d o 码，把分组t o r n a d o 码 偶图变换成卷积式偶图，并用该偶图对数据分组进行编解码，卷积式t o r n a d o 码 增强了编码数据分组之问的相关性，能够有效地抗网络突发丢包。接下来，提出 了一种基于f e c 的选择重传方法，对于线性f e c 只要接收到的数据分组可以线 性表示全部源数据分组，解码器就可以恢复所有丢失的数据分组，根据线性f e c 的这个特点，对解码失败时偶图对应的矩阵进行列变换，找到需要重传的数据分 组序号。另外，本论文还给出了一种适用于重传的数据封装结构，该结构中含有 两种类型：一种为含有重传分组序号信息的数据结构，另一种为含有视频数据的 数据结构。利用该数据结构的视频传输系统简单易实现。 最后，利用论文中给出的f e c 和重传算法，实现具有抗分组丢失能力的视频 通信系统，同时验证了卷积式t o r n a d o 码和基于f e c 的选择重传方法。实验结果 表明，本论文提出的卷积式t o r n a d o 码和基于f e c 的选择重传方法能有效提高视 频通信的质量，而且算法复杂度低，可用于实际视频通信系统中。 关键词：视频通信纠删码选择性重传卷积式t o r n a d o 码 a b s t r a c t v i d e os t r e a mh i g h l yc o m p r e s s e di sq u i t es e n s i t i v et oc h a n n e le r r o rb e c a u s eo f s t r o n gc o r r e l a t i o nb e t w e e nb i t si nt h es t r e a m m e a n t i m e p a c k e tl o s s e s6 a nn o tb e a v o i d e di ni n t e r n e t s oi ti sa b s o l u t e l yn e c e s s a r yt ou s ee r r o rc o n t r o lm e c h a n i s m si n v i d e oc o m m u n i c a t i o n t h i st h e s i si sb a s e do nn e t w o r kv i d e oc o m m u n i c a t i o n ，m a i n l yf o c u s i n go n f o r w a r de r a s u r ec o r r e c t i o n ( f e c ) f i r s t l y ，t h eb a c k g r o u n da n dd e v e l o p m e n to ff e c a r eg i v e n ，a n dt h e nr sc o d e ，t o r n a d oc o d el tc o d ea n dr a p t o rc o d ea r er e s p e c t i v e l y i n t r o d u c e di nd e t a i l ，i n c l u d i n gt h ee n c o d ea n dd e c o d em e t h o d ，a l g o r i t h mc o m p l e x i t y a n d p e r f o r m a n c e s e c o n d l y t h ec o n v o l u t i o n a lt o r n a d oc o d ea n ds e l e c t i v e r e t r a n s m i s s i o nt e c h n o l o g yb a s e do nf e ca r ep r o p o s e d t h eb i p a r t i t eg r a p ho ft h e p r o p o s e dc o d ei st r a n s f o r m e df r o mt h eg r o u pt o r n a d oc o d e ，w h i c hc a ne n h a n c et h e c o r r e l a t i o no fp a c k e t sa n da v o i dt h ep a c k e tl o s s e sc a u s e db yo u t b u r s te r r o r a st o s e l e c t i v er e t r a n s m i s s i o nb a s e do nl i n e a rf e c ，a l lo ft h el o s tp a c k e t sc a nb er e c o v e r e d w h e nr e c e i v e dp a c k e t sc a np r e s e n ta l ls o u r c ep a c k e t sl i n e a r l y 砀en u m b e ro fp a c k e t r e t r a n s m i s s i o nc a nb ec a l c u l a t e db yt r a n s f o r m i n gm a t r i xc o r r e s p o n d i n gt ob i p a r t i t e g r a p hw h e nd e c o d e rf a i l st or e c o v e ra l ll o s tp a c k e t s t h i r d l y ，p a c k e ts t r u c t u r eu s e di n r e t r a n s m i s s i o ni s p r o p o s e d ，i nw h i c ht h e r e a r e t w ot y p e so fs t r u c t u r e si n v o l v e d ： i n f o r m a t i o na b o u tr e t r a n s m i s s i o np a c k e tn u m b e ra n dv i d e oc o n t e n t s s ot h a tv i d e o c o m m u n i c a t i o ns y s t e mu s i n gp r o p o s e dp a c k e ts t r u c t u r eh a sl o wc o m p l e x i t ya n de a s y i m p l e m e n t a t i o n a tl a s t ，av i d e oc o m m u n i c a t i o ns y s t e mb a s e do nf e ca n dr e t r a n s m i s s i o nt o a v o i dp a c k e tl o s si sd e s i g n e d e x p e r i m e n tr e s u l t ss h o wt h a tt h ec o n v o l u t i o n a lt o r n a d o c o d ea n df e cc o m b i n e dw i t hr e t r a n s m i s s i o nc a l ls i g n i f i c a n t l yr e d u c et h e c o m p u t a t i o n a lc o m p l e x i t ya n dg u a r a n t e et h eg r e a tq u a l i t yo ft h er e c o n s t r u c tv i d e o ，a n d c a nb eu s e di nt h ea c t u a lv i d e oc o m m u n i c a t i o ns y s t e m k e y w o r d s ：v i d e oc o m m u n i c a t i o n f o r w a r de r a s u r ec o r r e c t i o ns e l e c t i v e r e t r a n s m s s i o nc o n v o l u t i o n a lt o r n a d oc o d e 创新性声明 本人声明所呈交的论文是我个人在导师的指导下进行的研究工作及所取得的 研究成果。尽我所知，除了文中特别加以标注和致谢中所罗列的内容以外，论文 中不包含其它人已经发表或撰写过的研究成果：也不包含为获得西安电子科技大 学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志所做的任 何贡献均已在论文中做了明确的说明并表示了谢意。 申请学位论文与资料若有不实之处，本人承担一切相关责任。 本人签名 关于论文使用授权的说明 本人完全了解西安电子科技大学有关保留和使用学位论文的规定，即：研究 生在校攻读学位期间论文工作的知识产权单位属西安电子科技大学。本人保证毕 业离校后，发表论文或使用论文工作成果时署名单位仍然为西安电子科技大学。 学校有权保留送交论文的复印件，允许查阅和借阅论文；学校可以公布论文的全 部或部分内容，可以允许采用影印、缩印、或其它复制手段保存论文。( 保密的 论文在解密后遵守此规定) 导师签名： 后适用本授权- - - i 弓。 日期：7 - i 。，) 第一章绪论 第一章绪论 1 1 研究背景 由于视觉信息给人们直观、生动的形象，目前已有诸多应用，如数字电视( 包 括i p t v ) 、视频点播、可视电话、远程教育以及军事侦察等，它将深入到人们的 物质生活、精神生活以及社会活动等方面。视频通信一般对带宽提出了较高的要 求，而宽带通信技术的发展为视频通信提供了条件，因此视频通信的应用将会越 来越广泛。 图像压缩编码从1 9 4 8 年电视信号数字化提出以来，已有近六十年的历史，不 仅在理论研究上取得了重大进步，而且在实际应用中也获得了很大成果【2 】【1 】【2 1 。近 二十年来，图像编码技术得到了迅速发展和广泛应用，并且同臻成熟，其标志就 是多个关于图像编码的国际标准的制定，即国际标准化组织i s o 和国际电工委员 会i e c 关于静止图像的编码标准j p e g j p e g 2 0 0 0 ，关于活动图像的编码标准 m p e g 1 、m p e g 2 、m p e g - 4 等，以及国际电信联盟i t u t 制定的视频编码标准 h 2 6 x 系列。这些标准采用的图像编码算法融合了各种性能优良的图像编码方法， 代表了目前图像编码的发展水平。 这些标准的制定，极大地推动了视频通信应用的发展。视频及多媒体通信时 代已经到来。但是分组通信中，要保证视频通信的质量，还存在许多问题需要解 决。 在网络通信中，由于因特网是一个“尽力服务”网，因此分组丢失不可避免。 视频码流经过高效压缩的数据，其比特流之间具有非常强的相关性，因此对信道 误码非常敏感，例如某些关键数据的丢失，会使图像的一个区域，甚至一帧图像 不能正确解码。同时信源熵编码符号( 变长码) 非常容易产生误码扩散，通常变长 码的符号错误率比信道误码率高2 3 个数量级。因此在视频通信中，必须应用前 向纠错编码( f e c ) 技术。 克服通信信道的误码率或删除率高的有效方法是利用编码的方法，即把要传 输的k 比特源数据编码为n ( n k ) 比特数据后发送出去，若接收方接收到足够量的 数据，则运用适当的译码方法就可恢复k 比特源数据。由于要在视频通信中应用， 因此构造具有较低编码和译码时间复杂度且性能良好的纠删码非常重要，即这种 纠删码既能以线性时间编码和成功译码，又能以任意接近删除信道容量的速率进 行传输。 自动请求重传技术( a r q ) 可以有效解决分组通信中丢包的问题，经常被使用 2 保证视频通信质鼍的f e c 算法研究与实现 在点对点的单播协议中，当接收端没有收到数据时，接收端就通过反馈信道通知 发送端重发。当重发的数据又丢失时，则接收端会再次要求发送端重发此数据， 以此下去一直到接收端收到数据为止。这种方法虽然可靠，但在一些对实时性要 求比较高，且丢包率较高的地方使用时会产生一些问题。人们又提出了将f e c 和 重传联合应用的差错控制方法，即混合自动请求重传方法( h a r q ) 。该方法充分利 用了f e c 和重传方法的优点，提出不同的方案实现数据的可靠传输。基本原理是 接收端首先利用f e c 恢复丢失包，如果丢包超出f e c 可以恢复的能力，则请求 发送端重传。混合方案可以通过重传有效降低带宽要求，并且在网络条件和时延 限制之间衡量找出平衡点，达到最佳的质量性能。 1 2 论文文内容和结构安排 论文以华为技术有限公司项目针对视频信号传输的选择性重传算法研究 为研究背景，研究保证视频通信质量的f e c 算法，本论文首先介绍了纠删码的基 本原理，并详细介绍了r s 码、t o r n a d o 码、l t 码和r a p t o r 码的编解码方法、编 解码复杂度及其性能，然后在t o r n a d o 码的基础上提出并实现卷积式t o r n a d o 码， 并给出实验结果和性能分析。其次，介绍基于f e c 的选择重传系统和实现方法， 并给出实验结果及其性能分析。接下来，实现一个基于f e c 和重传的视频通信系 统，实验结果表明本论文提出卷积式f e c 和基于f e c 的选择重传方法可以有效 保证视频通信质量。 论文结构安排如下： 第一章主要介绍了与视频相关的f e c 背景和本论文的章节安排。 第二章首先介绍纠删码的基本原理，接着详细介绍了r s 码、t o r n a d o 码、l t 码和r a p t o r 码的编解码方法、编解码复杂度及其性能。 第三章在t o r n a d o 码的基础上提出并实现卷积式t o r n a d o 码，并给出其实验 结果和性能分析。 第四章提出并实现了与基于f e c 的选择重传系统和方法，并给出实验结果及 其性能分析。 第五章实现了一个基于f e c 和重传的视频通信系统，实验结果表明本论文提 出卷积式f e c 和基于f e c 的选择重传方法可以有效保证视频通信质量。 结束语对论文进行了总结，并给出今后的研究方向。 第二章纠删码概述 3 第二章纠删码概述 2 1 纠删码原理 前向纠错码是一种被广泛应用于通信系统中的纠错技术。在通信系统中前向 纠错主要被用于纠正信号在传输过程中出现的误码，它的错误比特的位置是未知 的；而在互联网中，检测错误是由低层协议来完成的，错误的数据帧被抛弃，丢失 的数据在整个数据流中的位置是知道的，因而，在互联网中前向纠错技术起的是 纠删作用，它被用于恢复丢失的数据。纠删码的基本原理( 图2 1 所示) 如下： 对于要传输k 个数据分组，根据某种编码方法对其编码，生成n ( n k ) 数据分 组，将k 个数据分组和生成的n k 个数据分组二一起发送，接收方可以利用冗余数据 分组恢复传输中丢失的信息数据分组； 接收方将接收到的k ( k 助个数据分组后运用相应译码方法恢复k 个数据 分组。 2 2 1r s 码 接收到 数据 k = k 图2 1 纠删码的基本原理 2 2 现有纠删码 r s 码是一种有很强的纠错能力的多进制b c h 码，也是一类典型的代数几何 码f 3 】【4 1 。由于r s 码的纠错能力尤其是纠突发错误的能力强，短分组时编译码速度 较快，因而被广泛地应用于通信系统中。r s 纠删码成为了最早应用于实时可靠传 输中的前向纠错技术。同时，因为c a u c h y 矩阵逆运算比任何矩阵的逆运算都要 徽国营重 4 保证视频通信质量的f e c 算法研究与实现 简单得多，所以在传输中的r s 纠删码多采用基于c a u c h y 矩阵的r s 纠删码。下 面简单地介绍一下c a u c h y 矩阵以及基于c a u c h y 矩阵的r s 纠删码的基本性能 【5 】【6 】【刀。 基于c a u c h y 矩阵的r s 纠删码，其生成矩阵g 是一个矩阵，。是( 后七) 阶 单位矩阵，c 是( ( 疗- 后) 七) 阶c a u c h y 矩阵，( ，。ic ) 是一个伽后) 阶矩阵。 定义1 已知缸。，l ，z 。) 和钞。，l ，y 。) 是域f 中两个元素的集合。如果： ， 1 ，l ，朋) 和 ， l ，l ，栉) ；x f + y f 0 。 ”f 喂 1 ，l ，聊) ，i ；z f 和”f i ，喂 1 ，l ，栉) ，i j ；y f y j 。 那么矩阵： l ! 工l + y l 上 x 2 + y 。( 厶ic ) lm l ! 为域，上的c 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 中的任意一个伽力) 阶c a u c h y 矩阵的逆运算复杂度为域，中 o ( n 2 ) 算术算操作。 根据性质( 3 ) ，由于c a u c h y 矩阵的逆运算比任何矩阵的逆运算都要简单得多， 而且它把乘法和除法运算分别转化为加法和减法运算，从而加快了r s 纠删码译 码速度。 r s 纠删码是一种最大距离可分码。即信息源为k 字段的数据，经过编码生成 n 字段发送出去，接收方只需要接收任意k 字段数据即可恢复出原来的数据，因 而称r s 纠删码的接收效率为1 。 r s 码缺点：由于r s 纠删码要在有限域上进行矩阵运算等复杂的操作，它的 编译码时间复杂度分别是o ( n l o g n l o g l o g n ) 和o ( n l 0 9 2n l o g l o g n ) 【8 l ( 一是码字的长 度) ，随着数据长度的增加，编译码时间变得非常长，所以在实际应用中，采用 r s 纠删码实时处理的数据量大小受到限制。在大量数据实时传输中，采用r s 纠 删码会造成较大的迟延，因而在互联网中主要把r s 纠删码用于数据量较小，迟 延要求不高的实际应用中。 。一m。一m m。一 第二章纠删码概述 5 2 2 2l t 码 r s 码可以在丢包率固定的信道上应用，但不能适应丢包率波动很大的信道。 当以信道最坏情况设计r s 码时，可能会造成冗余浪费。当以信道最好情况设计 r s 码时，可能会遇到数据包不能恢复的情况。：喷泉码可以解决上述问题，2 0 0 2 年，m l u b y 提出了第一种现实可行的喷泉码一l t 列9 1 。 1 ) 喷泉码的概念 所谓喷泉码，是指该种编码可以由k 原始数据分组生成任意数量的编码分组， 而接收方只需收到其中任意m 编码分组，即可通过译码以高概率成功恢复全部原 始数据分组。可以看到，上述编码过程就如同源源不断产生水滴( 编码分组) 的喷 泉( 编码器) ，而我们只要用杯子( 译码器) 接收足够数量的水滴，即可达到饮用( 成 功译码) 的目的。正因如此，该种编码被称为喷泉码。 显然，喷泉码的设计需要考虑两方面的问题。一方面，应该尽量减小译码开 销，使其趋近于0 ；另一方面，应该尽量减小编译码复杂度，理想情况下，应该 使生成每个编码分组需要的运算量是一个与k 无关的常数，而成功译码m 编码分 组获得k 原始数据分组需要的运算量是一个关于k 的线性函数。 2 ) l t 码及其编译码原理 l t 码是第一种实用喷泉码，具有简单的编译码方法以及较小的译码开销和编 译码复杂度，为喷泉码的发展奠定了基础。 l t 码生成每个编码分组的过程如图2 2 所示【1 0 1 ： ( 1 ) 根据设计的度数分布q 进行随机实验，选取编码分组度数d 。 ( 2 ) 从k 原始数据分组中，等概率地随机选取d 个。 ( 3 ) 将这d 原始数据分组模二和( 异或) ，生成个编码分组。 原始数据分组 图2 2 iq i 编码数据分组 l t 码编码 l t 码的译码过程如图2 3 所示： ( 1 ) 接收一定数量的编码分组，根据编码分组与原始数据分组的对应关系建 立双向图。顶层节点代表原始数据分组，底层节点代表编码分组，连接顶层节点 6 保证视频通信质量的f e c 算法研究与实现 和底层节点的边代表该原始数据分组是该编码分组的模二和分量( 图2 3 a ) 。 ( 2 ) 任意选取一个度数为1 的编码分组。如果不存在，则译码停止；如果存 在，则通过简单的复制运算，即可恢复与该编码分组相连的唯一原始数据分组( 图 2 3 b ) 。 ( 3 ) 对于已经恢复的原始数据分组，将其模二和到与其相连的所有其他编码 分组中，生成新的修正的编码分组。相应地，将双向图中对应的边删除，从而使 得这些编码分组的度数减l 。简单实例如图2 3 c 所示。如果在此过程中某个编码 分组的度数减少为1 ，则称该编码分组被“释放 ( 图2 3 e ) 。 ( 4 ) 重复步骤2 和3 ，直至译码停止。如果所有原始数据分组都已经恢复，则 译码成功；否则，译码失败，必须接收更多的编码分组才能继续译码( 图2 3 d 、2 3 e 、 2 3 0 。 ，- - ，n，n， 燃嫩燃 loi ( o 原始数据分组 。 编码数据分组 图2 3l t 码译码 ( 3 ) 度数分配表 度数的分配几率p ( d ) 1 1 1 ( 其中d 是编码节点的度，如p o ) 表示度为1 的编码 节点数目与总编码节点数目的比值) 是l t 码设计最关键的一个环节。有些编码符 号应该有很高的度数，这样才能保证所有的输入符号都会连接上所有的编码符号。 有很多编码符号应该有很低的度数，这样解码过程才能启动，而且才能继续下去。 而且这样编码过程所需要进行的模- - a n 操作才能减到最低。确定一个度数分配 p ( d ) 之后，解码过程的成功几率是可以根据统计学预测的。 为了避免重复操作，接收端图标的理想结构就是每一次循环计算都只有一个 旧 ol 第二章纠删码概述 7 度数为1 的编码符号。这个理想分配就是l u b y 理论中的s o l i t o n 分配 删= 1 他 1 p ( d ) = l d ( d 一1 ) d = 2 ，3 ，k 、7 这个度数分配在实际情况的表现并不理想，因为在解码过程中是很有可能会 遇到没有度数为1 的编码符号，而且还有可能会有一些源符号没有任何边连接。 l t 码的稳健s o l i t o n 分配解决了这些问题。l t 码多使用了两个参数c 和艿，保证 解码过程每次循环计算能找到度数为l 的编码符号不是一个而是 s m - c l n ( k 8 ) 4 k( 2 - 2 ) 参数c 是常数，在l u b y 的理想l t 码c 是l 。实际上它可以是任何数字，并 且在实验中发现低于1 会为编码带来优良效果。l u b y 的研究结果就是，在选择了 适当c 的情况下，只要解码器能接收k = k + 2 1 n ( s 8 ) s 编码符号，就能保障所有 k 输入符号都能以( 1 一万) 的几率成功恢复。 ( 4 ) l t 码的性能 l t 码是第一个无几率纠删码，意味着它可以从有限输入符号生成无限的编码 符号。符号都是可以从单一比特到任意比特大小的二进制矢量。解码可以从任何 七( 1 + s ) 数量的编码符号中以非常高的几率恢复k 输入符号。g 代表编码开销的比 率。 l t 码的开销非常低，通常设计为k 的5 。l t 码的开销的方程式是 k 一k = 4 - k ( t n ( k 万) ) 2 。万是解码器允许为k 符号解码失败的几率。k 越大，l t 码 越简单。在( 1 一艿) 的成功恢复率下进行k 数量符号的传输，编码过程平均需要消 耗k l n ( k 8 ) 符号计算。 l t 码可以实时生成无限的编码符号。无论删除信道的丢包属性如何，l t 编 码器都可以生成足够的编码符号，一直到解码器能接收到足够解码的符号为止。 l t 码的缺点： ( 1 ) 当解码过程中，接收端收到的编码符号数量接近于原始输入符号的数量 时，l tc o d e 不能以固定的时空代价解码。 ( 2 ) 解码过程中需要恢复所有的原始符号，解码才能成功。为了保证所有输 入符号都能被恢复，当编码符号数量接近输入符号数量时，输出符号所在节点的 平均度要大于等于d ( 1 i l ( 七) ) 。运算量与边的数量成正比，因此总运算量随输入符号 增加不成线性增长。 2 2 3r a p t o r 码 为了解决l t 码的缺点引入了r a p t o r 码技术【1 2 】【1 3 】【1 钔，r a p t o r 码的编码过程由 8 保证视频通信质量的f e c 算法研究与实现 预编码过程和l t 码的编码过程组成，预编码过程将原始输入单元通过某种传统 的纠错码转换为中间编码校验单元，然后将中间编码校验单元作为l t 码的输入 单元进行编码。这样在r a p t o r 码的解码过程中，利用l t 码技术解码只需要恢复 固定比例的中间编码校验单元，再利用传统纠错码的解码性质就可以恢复所有的 输入单元。 r a p t o r 码的核心思想是解放了l t 码要恢复所有输入符号的约束，因此r a p t o r 码中l t 码部分的复杂度由o ( k l l l ( 七) ) 降至d ( 七) 。 1 ) r a p t o r 码的结构 如图2 4 所示，r a p t o r 码采用多层校验预编码技术，中间两层节点为中间编 码校验单元，输入单元到第1 层中间编码校验单元的映射采用扩展汉明码，第1 层中间编码校验单元到第2 层中间编码校验单元的映射采用l d p c 码，l d p c 码 g a l l a g e 在1 9 6 3 年提出的【1 4 】，后来m a c k a y 发展了该研究成果，并且提出了基于 b p 算法的和积解码算法【1 6 】。 扩展 汉明码 l d p c 码 l t 码 图2 4r a p t o r 码编码过程 在删除信道上，使用b p 算法的l d p c 码解码过程与采用b p 算法的l t 码解 码过程相似【1 8 】，b p 算法能成功解码当且仅当与删除信息位置相关的二部图中不 包含停止集，所谓停止集是指一部分原始输入单元组成的集合，该集合具有以下 性质：在表示原始输入单元和校验单元邻接关系的二部图中，每个校验单元的邻接 单元集合中都存在停止集中的某些组成元素，并且这些组成元素的数量大于1 。 输入单元到第l 层中间编码校验单元的映射采用的编码是扩展汉明码，该类 编码是在形如( 2 辨一1 ，2 ”一m 1 ) 的汉明码的基础上，再加入一个对于所有码位进行 奇偶校验的码位，即该码位满足以下方程： c o = q i + c ：一2 + q + c ；( 2 - 3 ) 这样( q - ，e 咖，c l ，c o ，c o ) 共同组成一个完整的码字。该类汉明码有效信息 位为k 位，校验位为m + l 位，码长为n + l ，符合( 2 ”一1 ，2 “一m 一1 ) 的形式。 第二章纠删码概述 9 采用扩展汉明码的原因是：在采用b p 算法进行解码的过程中经常由于停止 集过小而引起解码失败，扩展汉明码的最小汉明距离为4 ，在这种情况下停止集 的大小一般为2 或者3 ，因此l d p c 码具有较高的解码成功概率。 2 ) r a p w r 码的性能 因为有了预编码，l t 码对编码符号的度数总和k i n 2 ( 七万) 的要求变宽了，其 中万为错误概率，而只需要恢复一部分中间符号即可，再用传统纠删码来恢复所 有的输入符号，理论及实验结果证明，只要选择了适当的预编码及l t 码选择了 合适度数的分配几率p ( d ) ( d 为编码符号的度数) ，那么r a p t o r 就能达到以下效果： r a p t o r 码能从任何尼( 1 + 占) 个编码符号中以( 1 一万) 的概率恢复k 个输入符号，其编 解码复杂度都为k i n ( 1 占) ，其中占为冗余度。在恶劣的网络环境下，r 印t o r 码能 进行高速大数据量的数据编码发送，可应用于可靠性数据广播及高质量视频流服 务等。 2 3t o r n a d o 码 t o m a d o 码是一种建立在非规则图上的低密度校验码( l o w d e n s i t yp a r i t y c o d e s ) 。s p i e l m 锄于1 9 9 5 年在低密度校验码的基础上，提出了基于规则双向图的 扩展码【1 9 1 ( e x p a n d e rc o d e s ) ，能实现线性时间编译码。人们经研究发现在非规则图 上构造的低密度校验码性能要比在规则图上构造的好得多。因此，b y e r s j w ， l u b y m 等人在扩展码的基础上，于1 9 9 8 年提出了在非规则图上构造的、编译码 算法更为简便的t o r n a d o 码。t o r n a d o 码能以线性时间编译码，编译码速度是原有 纠删码的几十、上百倍，可以被广泛应用于互联网的多媒体传输、无线传输、多 址传输以及信息发布中。 2 3 1t o r n a d o 码的构造 t o m m o 码有两个特点：一是在级连的非规则双向图上构造的码字；二是编 译码只有异或操作，因而编译码速度非常快。 曰。 曰1 而 而 毛 五 m p m 2 m a ：传统t 0 m a d 0 码的编码偶图 l o 保证视频通信质量的f e c 算法研究与实现 五 而 屯 黾 c l = x 10 屯ox 3 c 2 = 西ox 4 c 3 = x 1o 恐o b ：t o r n a d o 的单级编码图 图2 5t o r n a d o 码的编码图 首先介绍一下t o r n a d o 码的编译码方法。设有k 源数据包，通过t o r n a d o 码 编码方法生成n 编码数据包。其中有z 冗余数据包，n = k + l 。则t o r n a d o 码的编码 结构如图2 2 所示。 从图2 5 中a 图可知，t o m a d o 码的构造图是多个非规则双向扩展图级连而成。 对于每一级非规则双向扩展图来说，图的左边是输入的信息位，右边是输出的校 验位。在级连的非规则图中，它把前面一级的输出作为后面一级的输入。在单级 编码的过程中，如图2 2 中b 图所示，t o r n a d o 码的冗余校验位c i 是信息位五，鹚，黾 通过异或操作得到的( c l = 五。屯。屯) ，而冗余位c 2 是信息位而、五的异或 ( g = x io 毛) 。以此类推，每个冗余校验位都是几个信息位值的异或。 解码的过程和编码类似，只不过是用校验结点来恢复数据结点。为了恢复所 需的数据结点先退到最后一级。假如在最后一级，通过解码恢复出了所有丢失的 结点，那么所有由展所产生的校验结点就成为已知了，然后用e 还原出由最一。编 码生成的k 1 级检测结点，以此类推，直到第0 级还原出丢失的数据结点。这儿 所使用的偶图鼠，e ，反应于编码时所使用的鼠，且，鼠相同。对于每一级偶 图，数据是这样恢复的：假如有一个右结点没有丢失，而且与它相邻的所有左结 点中只有一个丢失，其余的结点都没有丢失。那么这个丢失的结点就可以通过这 个右结点与所有未丢失的左结点相异或来恢复，如图2 6 所示。 x l x 2 x 3 x 4o 数据节点 c l c 2 o龟 校验节点 o 丢失的节点 毛= 而ox 2oc i 图2 6t o r n a d o 码的丢失节点的恢复 第二章纠删码概述 2 3 2t o r n a d o 码的性能 t o r n a d o 码要恢复源信息的k 个数据包，则需要接收比k 稍微多一点的数据 包。对于t o r n a d o 码需要接收( 1 + e ) k 个编码数据包才能恢复出k 个源数据包。我 们把1 + s 称译码无效率，占称为译码无效系数。t o r n a d o 码的接收效率为l ( 1 + 占) 。 t o r n a d o 码被称为“旋风码 ，是因为接收方在译码的过程中，如果接收到超过k 个的数据包后，在后面的译码过程有可能出现这种情况：接收方接收到某一个数 据包，就会象旋风刮过一样，将剩下的丢失信息位数据包全部恢复。 t o r n a d o 码的最大优点是能线性时间编译码。由于在编译码过程中，t o m a d o 码只进行异或操作，而r s 纠删码需要在有限域上进行复杂的矩阵运算，所以它 的编译码速度要比r s 纠删码快得多。如果t o r n a d o 码的译码无效率为1 + g ，那 么编译码复杂度是o ( n l o g ( 1 占) ) 【2 0 1 ，其中n 是编码后数据包的数目。 2 4 本章小结 本章首先介绍了纠删码的基本原理，接着详细介绍了r s 码、l t 码、r a p t o r 码和t o m a d o 码的编解码方法、编解码复杂度及其性能。本章介绍的四种纠错码 都是线性码，对于线性码只要接收到的数据分组可以线性表示全部源数据分组， 则解码器可以恢复所有的丢失数据包，下面将会根据线性码的这个特点来研究基 于f e c 的选择重传方法。其中t o r n a d o 码结构简单，便于实现，下一章将会对 t o r n a d o 码进行改进，提出卷积式t o r n a d o 码的具体实现。 第三章卷积式t o r n a d o 码算法研究 1 3 第三章卷积式t o m a d o 码算法研究 传统t o r n a d o 码只能有效防止随机分组丢失，但不能抗突发丢包。分组 t o r n a d o 码中每组编码数据允许丢失的数据包个数是基本是固定的，但m 网络上 出现丢包具有突发性，在某一段时间内，信道中的丢包可能非常少，t o r a n d o 码 的冗余数据包有浪费；但在另一段时间内，信道中的丢包可能非常多，t o r n a d o 码不能完全恢复丢失数据包，因此t o r n a d o 码受信道的突发丢包影响，其丢包成 功恢复率明显下降。另外，传统t o r n a d o 码的编译码算法复杂度较高，对设备资 源占用率高。 本章提出了卷积式t o r n a d o 码，该码具有卷积的特性，克服了传统t o r n a d o 码的上述缺点，具有很强抗突发丢包能力，且进一步降低信道编译码的运算复杂 度，可广泛应用于实时视频通信业务中。 3 1t o r n a d o 码编译码原理 传统t o r n a d o 编码原理【2 4 】如图3 1 所示。 图3 1t o r n a d o 码编码原理 在编码端，第一级节点( 五x 。) 为数据节点，由数据节点按照连线的关系进 行异或运算，生成第二级节点( 校验节点) ，再由第二级节点( 校验节点) 进行简单的 异或运算生成第三级节点( 校验节点) ，依次类推，而最后一级采用传统的编码方 法( 如r s 码) 。在接收端，首先对最后一级传统编码进行解码，恢复出校验节点， 当某一个右节点没有丢失，而与之相连的左节点仅丢失一个节点，就可以通过与 发送端相逆的异或运算，恢复出该节点，依此类推，直至恢复出第一级数据节点。 1 4 保证视频通信质量的f e c 算法研究与实现 3 2 卷积式t o m a d o 码的设计与实现 卷积式t o r n a d o 码以分组t o r n a d o 码的编解码算法为基础上提出的，先选取 一个分组t o r n a d o 码的偶图，然后按一定规则把分组t o r n a d o 码的偶图变换成卷 积式t o r n a d o 码的偶图，卷积式t o r n a d o 码根据卷积式偶图对数据包进行编解码。 卷积式t o r n a d o 码的基本思想是使尽量多的节点互相相关，从而提高抗突发丢包 能力。 3 2 1 生成卷积式t o r n a d o 码的偶图 偶图对解码的恢复概率的高低起着决定性作用，一个有效的偶图当丢失较多 结点时，仍能以很大可能恢复出丢失结点。而在这成千上万种不同连接关系的偶 图中找到一个恢复概率比较高的偶图是一件相当不容易的事，特别是当数据结点 的个数很大时。研究发现卷积式偶图恢复丢包的性能比分组偶图的性能要好，本 节研究卷积式偶图的生成方法。 分组t o r n a d o 码偶图变换成卷积式t o r n a d o 码偶图的步骤分为五步： 1 ) 任意选取一个分组t o r n a d o 码的偶图。假设选取了一个如图3 2 中的a 图 所示的偶图，偶图的校验关系的式为t + 。= z + ，o + o + ，e + 。= + ，o + 。o 矗。 2 ) 从数据节点中为每一个校验节点选取一个位置。校验节点的位置是指它与 本组中哪个数据节点对应。如图3 2 中b 图所示，c + 的位置为z + 。，矗的位置+ 。 选取校验节点的位置的方法是把校验节点位置平均分配到数据节点，假设数据节 点有1 0 个，校验节点有2 个，则数据节点5 和数据节点1 0 就是两个校验节点的 位置。 3 ) 找出所有校验节点的全部后向边。后向边是指校验节点与它的位置后面的 节点相连的边，前向边同理。如图3 2 中b 图t + 。与# + 。和一与之间的边为后向 边。 4 ) 把偶图中所有后向边变换成前向边。把后向边变换成前向边的方法是把偶 图中每一条后向边连接的数据节点改成前一组中同一序号的数据节点，校验节点 不变。如图3 2 中c 图所示，后向边( c + i ，+ 。) 被改成前向边( c + i ，i ) 。校验关 系的式变为之+ ，= z + 。o 。o i ，蠢。= 矗o + 。o 。 5 ) 形成卷积式t o r n a d o 码的偶图。把校验节点看成数据节点放到它的位置中 去，形成卷积式t o r n a d o 码的偶图。如图3 2 中d 图所示，1 ，作为数据节点z + 。， 矗。作为数据节点+ 。校验关系的式变为c + 。= z + ，o 。o e ， 矗l = 矗ioc + lo x 4 n + i 。 第三章卷积式t o r n a d o 码算法研究 1 5 z # 毫+ ， 矗。 宅+ 。 矗。 z z z 霉 t + 。 l t + 。毫+ 。 。 ，东。 x 棚io + 2o 毫+ 2o 以+ ，= 毫卅o 2 + o ， 矗= 矗。o 矗。o 矗， d + 。 e + 。 以+ ，= 一+ 。o ，o e + 。= 矗，o 磊+ 。o 矗。 c 毫+ ：o c 二+ 。 矗， c ：+ 。= t + 。o + 。oc ： 2 + i 。2 + ioc ：+ iox 川4 图3 2 卷积式t o r n a d o 码偶图的生成步骤 按照以上方法生成卷积式偶图，可以用于卷积码中，该偶图具有以下特点的 特点： 1 ) 由3 2 1 节的步骤4 可知：卷积t o r n a d o 码偶图中各节点的度与分组t o r n a d o 码偶图的度一样。因此可以用度数分布来寻找卷积式t o r n a d o 码的偶图。 2 1 生成的偶图具有卷积的特性。由3 2 1 中的步骤4 知：偶图中所有的后向边 都消失了，所有校验节点都由它的位置前面的数据节点运算生成，与它位置后面 的数据节点无关。由3 2 1 中的步骤5 知：校验节点对数据节点和该校验节点位置 前面的校验节点进行校验。这一卷积的特性可以提高t o r n a d o 码抗突发丢包的能 力。 3 2 2 卷积式t o r n a d o 码的编码流程 t o r n a d o 码的性能主要由t o r n a d o 码的偶图决定，偶图的生成方法在上一节 中已经介绍，本节和下一节主要讲述如何利用卷积式偶图对数据分组进行编码和 解码。 憋、憋 z 0 e 艺矗慧蔑 1 6 保证视频通信质量的f e c 算法研究与实现 而恐而黾民j c 7黾 而而。 而l 而2 工1 3 工耳1 5 o o o o o io oqo qo oq o q 一一一一一一一一一一一一一- j i i | o1111i ； j ：i ol l ll；i 一一一一一一一一一一一一一一一一一j： ol1l1i olll1 黾= x 7ox 6o 屯 五o = x 9o 黾。而 而3 = 而2o 五io x i o 52 而4o 工1 30 工1 2 o校验节点 。 数据节点 图3 3 卷积式t o r n a d o 码的编码 卷积式t o m a d o 码编码器，如图3 4 所示，由状态器、校验数据包产生器和 编码缓冲区三部分组成，各部分功能如下： 状态器：用于标记数据包对应的偶图位置，指示是否产生校验分组。 校验数据包产生器：通过偶图，执行异或操作产生校验数据包。 编码缓冲区：用来存储编码的后的数据分组和校验分组。 按照图3 3 中d 图进行编码的过程如图3 3 所示。卷积式t o r n a d o 码和分组 t o r n a d o 码不同，卷积式t o r n a d o 码必须要有一个启动的过程，在启动时必须有 一些数据是发送端和接