（信号与信息处理专业论文）raptor码在视频通信中的应用研究.pdf

南京邮电大学硕士研究生学位论文 摘要 i 摘摘 要要 近年来，诸如视频点播、iptv 等基于 ip 网络的多媒体应用变得越来越广泛。由于 ip 网 络不可避免的丢包问题，因此，采用一种差错控制策略以提高多媒体应用的 qos 一直是人们 研究的一个重要课题。 常用的差错控制策略有自动重传请求(arq)和前向纠错(fec)， arq 是 以时延和吞吐量为代价换取传输的可靠性，不利于 ip 网络中的多媒体数据的实时传输。作为 一种灵活的、可扩展的纠删码，喷泉码受到了学术界和产业界的广泛关注。本文以喷泉码的 第二种有效实现形式raptor 码作为研究对象，具体的工作如下： 首先，说明了本文的研究背景及研究现状，之后简要介绍了删除信道和纠删码的概念， 然后系统地介绍了几种常见的纠删码， 包括rs码、 ldpc码和ldgm码， 并重点介绍了ldgm 码。 其次，在研究 lt 码编译码算法的基础上，提出了一种 ldgm-lt 级联的 raptor 码实现 方案，探讨了度分布准则、预编码方案及伪随机数生成器对 raptor 码的影响，最后用 c 语言 实现了 raptor 方案的编译码算法，并对 raptor 的性能进行了实验仿真。 再次，提出了一种基于 raptor 码的不等差错保护策略，通过对具有较高优先级的数据实 施较强的保护程度，而适当减弱对具有较低优先级数据的保护程度，以达到对不同优先级的 数据实施不等差错保护的目的。仿真结果表明，本文提出的基于 raptor 码的不等差错保护策 略能恢复出更多的较高优先级的数据。 最后，针对ip网络中视频传输面临的丢包问题，本文将raptor码作为应用层前向纠删码， 为视频传输系统提供了一种有效的差错控制策略，给出了详细的系统设计和实现过程。实现 结果表明，整个视频传输系统运行良好，能有效客服视频丢包，显著改善视频播放质量。 关键词关键词：喷泉码，lt 码，raptor 码，不等差错保护，视频传输 南京邮电大学硕士研究生学位论文 abstract ii abstract in recent years, the multimedia applications over ip networks, such as video on demand, iptv, are becoming increasingly widespread. the phenomena of packet loss is unavoidable for ip network, so an error control strategy, which is used to improve qos of multimedia applications, has been one of an important issue. common error control strategy that used to overcome packet loss include automatic repeat request (arq) and forward error correction (fec). arq is based on the cost of delay and throughput for transmission reliability ,and is not conducive to real-time multimedia data transmission in ip networks. as a flexible, scalable erasure codes, fountain codes has drawn increasing attention in academia and industry. in this paper, we focus on the second practical realizations of fountain codes-raptor codes. specific tasks as follows: firstly, after illustrating the background and status, this paper gives a brief introduction to the concept of erasure channel and erasure codes, and next systematically introduces several common erasure codes, including rs codes, ldpc codes and ldgm codes, among which we lay emphasis on ldgm codes. secondly, on the base of researching the codec algorithm of lt codes, we propose an implementations of raptor codes with a concatenation of ldgm codes and lt codes. then we discuss the factors that influencing the performance of raptor codes, including the degree distribution, the pre-coding scheme and pseudo-random number generator. last, the realization of the codec algorithm of raptor codes is given in the form of c language, and a simulation experiment is held to measure the performance of raptor codes. thirdly, we propose an unequal error protection strategy based on raptor codes, which privides higher priority data with strong degree of protection and privides lower priority data with strong degree of protection, in order to achieve the purposes of prividing unequal error protection for different priority data. the simulation result shows that the proposed unequal error protection strategy based on raptor codes can restore larger number of the higher priority data. finally, against packet loss of video transmission in ip network, we take raptor code as the application layer erasure codes, provide an error control strategy for video transmission system, and then give a detailed description of system design and system implementation. the implementation result shows that the video transmission system with raptor codes is running well, which can overcome the packet loss effectively and improve the playback quality significantly. key words: fountain codes, lt codes, raptor codes, unequal error protection, video transmission 南京邮电大学学位论文原创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得 的研究成果。尽我所知，除了文中特别加以标注和致谢的地方外，论文中不包 含其他人已经发表或撰写过的研究成果，也不包含为获得南京邮电大学或其它 教育机构的学位或证书而使用过的材料。与我一同工作的同志对本研究所做的 任何贡献均已在论文中作了明确的说明并表示了谢意。 南京邮电大学学位论文使用授权声明 南京邮电大学、中国科学技术信息研究所、国家图书馆有权保留本人所送 交学位论文的复印件和电子文档，可以采用影印、缩印或其它复制手段保存论 文。本文电子文档的内容和纸质论文的内容相一致。除在保密期内的保密论文 外，允许论文被查阅和借阅，可以公布（包括刊登）论文的全部或部分内容。 论文的公布（包括刊登）授权南京邮电大学研究生部办理。 研究生签名：_ 日期：_ 研究生签名：_ 导师签名：_ 日期：_ 南京邮电大学硕士研究生学位论文 第一章 绪论 1 第一章第一章 绪论绪论 1.1 研究背景和意义研究背景和意义 1.1.1 喷泉码的提出 随着全球互联网(internet)的迅猛发展，以因特网技术为主导的数据通信在通信业务总量 中的比例迅速上升，多媒体通信已成为因特网业务中发展最为迅速、竞争最为激烈的领域。 随着多媒体通信和ip网络的高速发展，传统的视频编码和传输方法在不断进步的网络面 前正面临着越来越大的挑战。因此，如何实现视频数据在不可靠信道上的可靠传输一直都是 网络多媒体研究的一个重要问题，也是一个具有实际意义的研究课题1。 ip网络是一个包交换网络，传输错误主要以丢包形式出现。在ip网络中，绝大多数的流 量都是采用tcp协议进行传输的，tcp协议中采用了拥塞控制机制，可以避免和缓解网络拥 塞，但是实时的多媒体应用由于其对延时和抖动的较严格要求，通常都是采用没有拥塞控制 机制的udp协议进行传输，所以网络上的多媒体流量往往会在很大程度上恶化网络的拥塞情 况，从而产生大量的丢包问题，严重影响多媒体应用的qos。因此如何在不改变ip网络服务 模型的前提下，采用一种差错控制机制来提高多媒体应用的qos一直是人们研究的一个重要 课题2。 针对这一问题，人们一直在研究可扩展的可靠数据广播方案。michael luby等人于1998 年提出了数字喷泉(digital fountian)的概念，它是针对大规模数据分发和可靠广播的应用特点 而提出的一种理想的解决方案3。 1.1.2 喷泉码的技术特性 一个数字喷泉具有类似于水喷泉的特性：当你在水喷泉下用水杯接水喝时，只需要接到 足够量的水来解渴，而不必关心是哪一滴水流入你的杯中。相应的，采用喷泉编码技术，一 个接收端从一个或多个发送端接收编码包，一旦收到足够的编码包，那么该接收端就可以重 构源文件，而与具体接收到编码包序列中的哪些编码包却并没有关系。如图1-1所示 南京邮电大学硕士研究生学位论文 第一章 绪论 2 图 1-1 数字喷泉码技术特性 一个理想喷泉码应该具有如下特性3,4： (1) 一个源能够利用原始数据产生无限编码包序列，且生成每个编码包的时间是线性的。 (2) 接收端一旦接收到编码包序列中的任意 k 个编码包， 就能够重构这个消息， 且重构算 法应该非常快。 在实际实现中，通过放宽一些条件来近似实现数字喷泉码，比如： (1) 编码包个数可以为有限； (2) 编译码算法可以慢一些； (3) 需要接收到的编码包个数可略大于源包个数 k 。 针对不同的应用，对上述条件的要求程度也不近相同。 喷泉码是一类码率不受限的纠删码，即由源符号编码产生的编码符号序列是无限的，而 且可以在线产生这些编码符号序列。发送端的 k 个源符号称为输入符号(input symbols)，经过 喷泉编码后的编码符号称为输出符号(output symbols)。 对于给定的 k 个输入符号s1，s2。sk， 喷泉码可产生无限的输出符号流c1，c2。cn。，每个输出符号都等于若干随机独立选取的 输入符号的异或和。为描述方便，在本论文中，符号与数据包是同一概念(symbol)的两种不同 中文表述，都是指编译码过程中的一个基本单元。 michael luby 等人于 1998 年提出的喷泉码仅仅是一个理想的概念， 却一直没有现实可行 的实现方案。 luby 等人在 tornado 码5的基础上， 于 2002 年提出第一类有效的喷泉码lt 码6，shokrollahi 于 2006 年在 lt 码的基础上增加预编码，提出了 raptor 码7。 content enc 南京邮电大学硕士研究生学位论文 第一章 绪论 3 1.1.3 喷泉码的应用 喷泉码在网络通信传输中具有广泛的应用，目前数字喷泉码在可靠多播传输3、多源并 行下载8、分布式存储9等方面的研究受到了普遍关注。 (1) 多播传输 数字喷泉码的提出本身就是为了解决诸如软件更新等可靠多播问题，将数字喷泉码应用 于多播，可以容忍不同层次的客户端，使得不同丢包率的客户端只要接收到足够多的编码包 即可，只是速率低、丢包率大的客户端接收时间长点，速率高、丢包率小的客户端接收时间 短点，且当编码包足够多时，能保证每个客户端能可靠地恢复原文件，避免反馈和重传。 (2) 多源下载 由于数字喷泉码的每一个编码符号都是独立、随机地产生，而接收端只要收到足够的编 码符号就可以恢复出原始的k个输入符号，不管这些编码符号是编码符号集合中的哪一个， 因此我们可以采用多个发送端负责编码发送编码符号，接收端同时连接多个发送端，从不同 的发送端同时接收编码符号，不管这些符号来自哪一个源端以及每个源端的发送速率和数据 丢失率，只要收到足够的编码符号，即可断开所有的连接，恢复出原始文件，大大缩短下载 过程。 (3) 分布式存储 在 p2p 和大型分布式文件系统中常常利用备份的方法来提高文件访问的性能和容错性， 诸如一个广域网中由分布式存储结点组成的文件系统，若多个客户端要求访问同一个文件， 传统方法是文件系统将这个文件分成大小相同的多个数据包，再将这些数据包的备份分布式 存储在文件系统中， 假设文件系统有m个服务器， 那么必须复制1m次才能完成完整的备份， 且客户端必须寻找该文件的最近备份，而一个特定数据包的损坏或者对特定数据包的较慢访 问会导致整个文件系统的访问性能较低，显然传统方法的代价较高。 另外，喷泉码还可以应用到无线传感网络10、深空通信11,12、无线协作通信13,14、数据 压缩15、视频点播16,17等网络通信系统中。 1.2 研究研究现状现状 1.2.1 喷泉码存在的问题 尽管喷泉码的研究已取得一些可喜成果，但是目前所进行的研究大部分停留在理论研究 和工程应用仿真方面，喷泉码的理论研究和实际实现有待人们进一步的深入研究。喷泉码的 南京邮电大学硕士研究生学位论文 第一章 绪论 4 研究及实现过程中主要存在以下问题： (1) 喷泉码是针对大规模数据分发和可靠广播的应用而提出的，在码长较长时，能取得 优异的性能，而在码长较短时的性能却不够好；但码长太长意味着更长的译码时延和更多的 存储空间，从而不利于在对延迟有严格要求的环境中的应用。 (2) 由于喷泉码的随机编码结构，因此存在着一定的译码失败概率，降低了通信的可靠 性。此译码失败概率与码长、度分布准则密切相关。 (3) 由于喷泉码在译码时的“雪崩”效应18，必须收到足够的数据才能译码，当接收数 据不足时，译出的数据比例相当低，这不利于它在高丢包、低冗余的恶劣信道环境中的应用。 由此可见，喷泉码独特的设计在带来巨大的技术优势的同时也导致了一些缺点的存在， 使得它在某些应用上还存在不足，需要加以改进。 在学术理论日渐完善的同时，喷泉码也日益受到产业界的关注，获得了越来越多的实际 应用。m.luby、a.shokrollahi等人联合创立了digital fountain公司4，以推广喷泉码的实际应 用。目前，一种由digital fountain公司设计的系统raptor码也已经被dvb-h标准19和3gpp组 织的多媒体广播和多播业务(multimedia broadcast multicast service，mbms)标准20采用，并 且正在参与其他多项国际标准的制定。 1.2.2 喷泉码的研究概况 喷泉码的概念提出后，很多学者尝试用传统的纠删码来实现喷泉码，诸如用rs码21和 tornado5码来实现，但是鉴于传统纠删码的固定编码效率，效果不很理想。luby在tornado 码的基础上，于2002年提出了一种稀疏的随机线性喷泉码lt码6，至此喷泉码才有了真 正的具体实现。2006年，shokrollahi在lt码的基础上增加了预编码过程，提出了raptor码7， raptor码是迄今为止最有效的一种喷泉码。 许多学者对喷泉码进行了大量的研究，获得了许多可喜的研究成果，下面对此做一些简 要的介绍。 合理的度分布函数是lt码设计中的关键问题，zhu提出了一种次优度分布准则，通过实 验仿真取得了很好的译码性能22。 harrelson等证明了随机性受限的lt码和完全随机lt码的性 能几乎一样，这就提供了一种通过分析有限随机lt码来研究lt码的一理论依据23。 saejoon等人针对接收到编码符号的个数少于源符号的个数的情况，分析了喷泉码的译码 性能，并对度分布和编码方式做了一定的改变，提升了喷泉码的性能24,25。zhou在喷泉码的 编译码过程中引入了混沌思想，用混沌序列来代替线性同余序列作为伪随机数生成器，降低 南京邮电大学硕士研究生学位论文 第一章 绪论 5 了传输的开销，并减小了译码时的符号异或次数26,27。 有关喷泉码在各种信道条件下的性能分析， 也有不少研究成果。 文献28-31研究了raptor 码在二进制无记忆对称信道、加性高斯白噪声信道(awgn信道)以及各种衰落信道下的性能， 并对喷泉码的性能好坏与编译码复杂度的关系，以及如何降低译码算法复杂度等问题进行了 探索。由于本论文研究删除信道下的喷泉码性能，这部分内容本文不再展开。 1.3 本论文的主要工作和内容安排本论文的主要工作和内容安排 本文主要工作分为三部分： (1) 在 lt 码的基础上增加预编码过程，提出了一种 ldgm-lt 级联的 raptor 方案； (2) 针对恶劣信道环境下的多媒体应用， 提出了一种基于 raptor 码的不等差错保护策略； (3) 针对 ip 网络中视频传输面临的丢包问题，本文将 raptor 码作为应用层前向纠删码， 为视频传输系统提供了一种有效的差错控制策略，有效地克服了视频传输中的丢包现象，达 到提高视频传输质量的目的。 论文共分为 6 章： 第一章为绪论，主要介绍本论文的研究背景、意义以及研究现状； 第二章首先简要介绍了 rs 类纠删码，然后着重介绍了 ldpc 码的编译码原理，最后介 绍了 ldpc 码的一种特殊实现形式-ldgm 码，分析了其性能及存在的问题； 第三章在 lt 码的基础上增加预编码过程，提出了一种 ldgm-lt 级联的 raptor 码实现 方案，探讨了度分布准则、预编码方案及伪随机数生成器对 raptor 码的影响； 第四章针对恶劣信道环境下的多媒体应用，提出了一种具有不等差错保护特性的 raptor 码uep-raptor，给出了具体的设计过程和详细的分析； 第五章针对 ip 网络中视频传输面临的难题及解决方案， 将 raptor 码作为应用层前向纠删 码，为视频传输系统提供了一种有效的差错控制策略，给出了详细的系统设计和实现过程； 第六章对论文工作进行了总结，并对下一步的研究方向进行了展望。 南京邮电大学硕士研究生学位论文 第二章 基于删除信道的信道编码 6 第二章第二章 基于删除信道的信道编码基于删除信道的信道编码 2.1 删除信道删除信道和纠删码和纠删码 1、删除信道 目前，大部分现有网络中的数据是以数据包的形式进行传输的，一般认为在传输的接收 端每个数据包要么正确地接收到，要么完全丢失，这种模型较准确地反映了基于ip的网络特 性。在一般的通信系统中，前向纠错码纠正的错误所在的位置事先通常是不知道的，而当系 统中的信道为删除信道时，错误的数据被遗弃，丢失的数据在数据流中的位置是知道的2。 删除信道一个典型的例子就是二进制删除信道32。下面介绍二进制删除信道(binary erasure channel，bec)，输入集为1，0、输出集为1,，e，0且参数为p的二元删除信道如 图2-1所示，输出符号e称为删除(错误)，p称为删除概率，这类信道的信道容量为1-p。我们在 不本论文讨论的各类纠删码均指这类信道下的纠删码。 图2-1 二进制删除信道 删除信道在实际通信系统中是很常见的，如在互联网的多播/广播(multicast/broadcast)传 输系统、p2p系统、大容量存储系统等。此类信道中每个编码包丢失的概率均为p,且在传输中 编码包的丢失是相互独立的，这样纠删码比纠错码处理起来容易些。 2、纠删码 将前向纠错技术用于删除信道，就得到了纠删码，以此克服丢包现象，提高数据传输的 可靠性。纠删码(erasure codes)的基本原理（图2-2所示）是把要传输的k个源数据包编码为 n( n k)个数据包后发送出去，若接收方接收到足够量的数据包，则运用适当的译码方法就可 重构k个源数据包32。 0 0 1 1 p p e 1-p 1-p 南京邮电大学硕士研究生学位论文 第二章 基于删除信道的信道编码 7 源符号 n 编码 k 解码 k k 编码 符号 接收到的 符号 恢复的 符号 图2-2 纠删码原理示意图 一个(n,k)线性纠删码可以表示为 y=xg，其中 011 , k xx xx 是源数据， 011 , n yyyy 是编码数据，g为kn矩阵，是此(n,k)线性纠删码的生成矩阵。理想情况下， g的任意k列组成的子矩阵g均可逆，即接收端收到编码符号中的任意k个都能恢复出k个源符 号。 3、系统码 在纠删码编码过程中，输入 k 个源符号，输出 n 个编码符号，如果输出的 n 个编码符号 是由原来的 k 个源符号和由这 k 个源符号产生的 n-k 个冗余符号组成，即编码不改变源符号， 源符号是编码符号的组成部分，那么称此纠删码为系统码33。 在丢包率不太大的网络中，系统码尤为重要，因为此时丢包较少，如果纠删码是系统码， 那么有很大一部分源包已经收到，我们只需通过译码去恢复少部分丢包即可，此时译码时间 只与丢包个数有关，可加快译码，更好地满足某些应用的实时性要求。 目前主要有两种纠删码：rs码类纠删码和低密度纠删码。rs码类根据生成矩阵的不同， 主要有两种形式：范德蒙码和柯西码。低密度纠删码的生成矩阵为稀疏矩阵，这种码是基于 随机稀疏二分图构造的，包括基于删除信道的ldpc码、ldgm码、喷泉码等。下面简要介绍 下几种典型的纠删码；rs码类、ldpc码和ldgm码。 2.2 rs 码类纠删码码类纠删码 rs(reed solomon)码是一类有很强纠错能力的多进制bch码，也是一类典型的代数几何 码，它于1960年首先由里德(reed)和所罗门(solomon)提出33。 南京邮电大学硕士研究生学位论文 第二章 基于删除信道的信道编码 8 rs 码是2mgf域上的多进制线性分组码。, n krs 码中，一组输入信息包含k个符号， 每个符号由m比特组成。 一个能纠正t个符号错误的, n krs 码具有这样的参数： 信息符号个 数为k，监督符号个数为2t，总码字符号个数为2nkt，最小码距为21dt。 要进行 rs 编码，首先要得到 rs 码的生成多项式。设为2mgf域上的本原元，一个 能纠正t个符号错误的, n krs 码的生成多项式为： 232 2212 21210 t tt t g xxxxx xgxg xg xg (2.1) g x的系数取自2 m gf域，以， 2 ， 3 ， 2t 作为它的全部根。 得到 rs 码的生成多项式后，即可求得其生成矩阵 1 2 k k xgx xgx g x xg x g x (2.2) 设由k个信息符号组成的符号数组为 1210 , kk mmm m ，则编码后的码字为： 1210 1 2 1210 12 1210 12 1210 , , kk k k kk kk kk kk kk c xmmm m g x xg x xg x mmm m xg x g x mxg xmxg xm xg xm g x mxmxm xmg x m x g x (2.3) 由此可见，码多项式 c x都可以被生成多项式 g x整除，任一次数不大于1k 的多项 式乘以生成多项式 g x都是码多项式。rs 码的编码步骤包括以下几点。 (1) 用 n k x 乘以 m x，得到 n k xm x 。显然， n k xm x 次数小于n。这一步相当于在信 息码后附加nk个 0； (2) 用 g x除 n k xm x ，得到商 q x和余式 r x； 南京邮电大学硕士研究生学位论文 第二章 基于删除信道的信道编码 9 (3) 得到编码码字 n k c xxm xr x 。 2.3 ldpc 码码 ldpc( low density parity check)码是1962年由gallager首先提出的， 由于当时的计算机能 力太低，无法仿真出较好的性能，被沉寂了几十年。直到上世纪90年代中期，以mackay和 neal为代表的几位学者对具有稀疏校验矩阵的线性码进行了深入的研究， 并说明了ldpc码能 够像turbo码一样接近香农容量限33。 ldpc码是一种线性分组码，它的名字来源于其校验矩阵的稀疏性，即校验矩阵中只有数 量很少的元素为1，大部分元素都是0。gallager最早给出了正则ldpc码的定义36，具体来 讲正则ldpc码的校验矩阵h满足下面三个条件： (1) h矩阵的每行有个1； (2) h矩阵的每列有个1，3； (3) 与码长k和h矩阵的行数相比，和都很小。 2.3.1 概述 ldpc码可以用一个二分图37来表征，二分图又称为tanner图，这是由tanner在1982年首 次用它来表示低密度码的，一个tanner图和一个校验矩阵完全对应；ldpc码的tanner图由两 类节点组成：变量节点(variable node)和校验节点(check node)，分别对应于校验矩阵h中的n 列和n-k行。同一个集合内部的节点没有连线，只有属于不同集合的两点之间可能有连线， 每一条连线对应于校验矩阵中的1 。 在tanner图中，变量节点集合(v1, v2 , vn)和校验节点集合(c1, c2 , cn-k)内部不存在相连的 边，但两类节点之间存在着连线。变量节点和校验节点之间存在连线意味着该变量比特参加 了此校验方程式，也就是校验矩阵某一行中1的位置。 一个码长n=6，码率r=1/3，列重=2，行重=3，的校验矩阵h如下（如图2-3所示）： 图 2-3 ldpc 码的校验矩阵 h 根据校验矩阵我们可以画出它的tanner图（如图2-4所示）：图中有4个校验节点、6个变 110100 001110 100011 011001 h 南京邮电大学硕士研究生学位论文 第二章 基于删除信道的信道编码 10 量节点。每个校验节点有3根连线（因为行重为3），因此对应的校验节点的度为3；而每个变 量节点有2根连线（因为列重为2），则对应的变量节点的度为2。tanner图中的边代表变量节 点和校验节点间的联系，只有当变量包含于某一校验方程式中时，对应的变量节点和校验节 点之间才存在边。显而易见，在ldpc码的tanner图表示中，边的条数与稀疏校验矩阵中的非 零元素个数(即1的个数)相等。 图 2-4 ldpc 码的 tanner 图 2.3.2 编译码原理 与普通线性分组码一样，ldpc码在编码的时候，可以先将校验矩阵h做高斯消去，转化 成| p i形式，然后获得生成矩阵 | t gi p，最后用信息向量与生成矩阵相乘来得到码字。 ldpc码通用的一类译码算法，即所谓的消息传递 (message passing, mp) 算法。消息传 递算法是一种迭代译码算法(iterative algorithms)，在算法的每一轮迭代过程中，关于各个节 点的置信消息需要在变量节点和校验节点之间传递。删除信道下的迭代译码算法是一种简化 的mp算法，即置信传播算法(belief propagation, bp)32。 bp迭代译码过程实际上是在tanner图上逐渐去边的一个过程，下面是对bp迭代译码算法 的描述40： (1) 初始化：所有变量节点根据接收值赋为0，1或删除e，所有校验节点赋值为0； (2) 直接恢复：对所有的变量节点，若该变量节点未被删除，则将该变量节点的值加到 所有与其相连的校验节点上，并从原先的tanner图中去除所有与该变量节点相连的边； (3) 迭代恢复：若剩下的tanner图中存在度为1的校验节点，则该校验节点的值就等于与 其相连的变量节点的值，这样就能恢复出这个变量节点的值；然后再从tanner图中去掉恢复 出的变量节点及其相连的边； 1 v 2 v 3 v 4 v 5 v 6 v 1 c 2 c 3 c 4 c 变量节点 校验节点 南京邮电大学硕士研究生学位论文 第二章 基于删除信道的信道编码 11 (4) 重复迭代：重复步骤(3)，直到所有变量节点被恢复出来（译码成功）或者不存在度 为1的校验节点（译码终止）。 图2-5 给出了一个bp迭代译码过程实例，其中每个节点仅包含1个比特。 1 c 2 c 3 c 4 c 1 v 2 v 3 v 4 v 5 v 6 v 7 v 8 v 校验 节点 变量 节点 1 c 2 c 3 c 4 c 1 v 2 v 4 v 5 v 7 v 8 v 校验 节点 变量 节点 1 c 2 c 3 c 4 c 1 v 2 v 4 v 5 v 7 v 8 v 校验 节点 变量 节点 1 c 1 v 2 v 4 v 5 v 7 v 8 v 校验 节点 变量 节点 6 v 3 v 2 c 3 c 4 c (a)初始化 (b)直接恢复 (c)迭代恢复(d)重复迭代 10e0 1 e10 ? 3 v 6 v 10e0 1 e10 0110 10e0101010101010 01100110 3 v 6 v 图2-5 ldpc码的bp迭代译码过程 2.4 ldgm 码码 ldgm( low density generator matrix)码是一种(n,k)线性分组码，k 个信息节点：si， i0,.,k-1和 n-k 个冗余节点： i p，ik,.,.n-1之间存在一组线性方程式。基于线性方程组 可以得出每个冗余节点即是由某些信息节点所组成的集合中各个信息节点的异或41,42。 ldgm 码把变量节点 c 分解为两个部分 c=d p，这里的 d 和 p 分别表示信息节点和冗余 节点 （如图 2-6 (a)所示） ， 相应的把校验矩阵 h 也分解为两个子矩阵 h=hd hp （如图 2-6(b) 所示），其中 hp子矩阵为(n-k)(n-k)单位矩阵，hd子矩阵为(n-k)k 的随机稀疏矩阵。因此 hc=hd hpd p=hd d +hp p=0。 南京邮电大学硕士研究生学位论文 第二章 基于删除信道的信道编码 12 (a) tanner 图 (b) 校验矩阵 图 2-6 ldgm 码的 tanner 图及校验矩阵 由于hd子矩阵为随机稀疏矩阵，hp子矩阵为单位矩阵，因此校验矩阵h也是稀疏矩阵， ldgm码可以被视为一类特殊形式的ldpc码，这也是ldgm码中“ld”的意义所在；但由 于受矩阵大小的限制，图2-6 (b)所示校验矩阵的稀疏性并不太明显。 2.4.1 编译码原理 ldgm 码的校验矩阵 h 可直接用于编码，而不需要像标准 ldpc 码那样将 h 矩阵转化 成生成矩阵 g 才能进行编码，这也是 ldgm 码中“gm”的意义所在。由 tanner 图可以看出 ldgm 码的编码过程就是求解冗余节点的过程，其中各冗余节点的值等于同一校验节点中所 有与其相连的信息节点的模 2 和，例如，在图 2-6 (a)中 p7=s2s4s5s6，p8=s1s2s3s6， p9=s1s3s3s5。将冗余节点 p 和信息节点 d 合并，便得到 ldgm 码的编码节点。 ldgm码属于ldpc码的一种特殊形式，所以ldgm码的译码过程同样采用bp迭代算法， 2.3.2节已详细阐述了删除信道下ldpc码的bp迭代算法，本节不再对其进行描述。 s1 s6 p7p9 0 1 0 1 1 1 1 0 0 c1 hdhp = 1 1 1 0 0 1 0 1 0 c2 1 0 1 1 1 0 0 0 1 c3 (n) message nodes (n-k) check nodes k source nodes c1：s_2+ s_4+ s_5+ s_6+ p_7=0 c2：s_1+ s_2+ s_3+ s_6+ p_8=0 c3：s_1+ s_3+ s_4+ s_5+ p_9=0 n-k parity nodes p_7 p_8 p_9 s_1 s_2 s_3 s_4 s_5 s_6 南京邮电大学硕士研究生学位论文 第二章 基于删除信道的信道编码 13 2.4.2 两种实用形式 由于ldgm码的变量节点分为信息结点和冗余结点两部分，其中冗余结点的度都为1，在 译码迭代过程中，这些冗余节点传给与它相连的唯一校验节点的信息始终都是相同的，故 ldgm码存在较高的错误平层效应41,42，在实际应用中并不可行。为了消除错误平层效应， 通过对ldgm码hp子矩阵进行一定的修改便可得其两种实用形式： staircase型(梯型)和triangle 型(三角型)，两者的编译码算法与ldgm码保持相同。 1、ldgm staircase码 ldgm staircase 码主要是在 h 矩阵中使用 staircase 型矩阵替代了 hp单位矩阵。修改后 的 h 矩阵如图 2-7(a)所示。 具体方法就是在第 i 行第 k+i-1 列中填入1， 使其成为双对角线型 矩阵。 这种变化对编码基本上没有构成影响，编码过程依然是非常简单且高效的。唯一的约束 就是编码过程必须按冗余节点的顺序有序进行。举例来说，编码从节点 p7开始，然后是 p8 （可以计算因为 y1已知） ，等等。 在 ldgm 码中，如果 p7在传输过程中丢失，那么 p7将无法被恢复，除非与 p7相关联的 所有信息节点被恢复， 但在这种情况下再来恢复 p7已经没有意义； 而在 ldgm staircase 码中， 如果 p8没有丢失，那么 p7仍可以通过 p8来恢复，因为它们与同一个校验节点相连。通过这 种方法增加了冗余节点之间的相关性。 (a) ldgm staircase 校验矩阵 hd l l l ll l l ll l l ll l . l ll l l ll l l l l n-k n-k k 0 0 南京邮电大学硕士研究生学位论文 第二章 基于删除信道的信道编码 14 (b) ldgm triangle 校验矩阵 图 2-7 ldgm 码校验矩阵的两种变形 2、ldgm triangle码 ldgm triangle 码是在 ldgm staircase 码的基础上进行稍微修改而得的。将 h 矩阵中的 staircase 型子矩阵中对角线左下方那块空白部分，随机填入1，构成 triangle 型矩阵（如图 2-7(b)所示） 。 通过这种构造规则，使得 staircase 矩阵中低序号冗余节点的度数大于高序号冗余节点的 度数，比起 ldgm staircase 码来，这种改变提升了 ldgm triangle 码在高码率下的性能。因 为这种改变让所有的信息节点之间的关系更为密切， 一个校验节点与更多的冗余节点相关联。 同样ldgm triangle码的编码也须依冗余节点的序号有序进行，由于triangle型子矩阵中 每列中1的个数有所增加，使得编码速度稍慢于ldgm staircase码，但ldgm triangle码依然 是高效的。 在后续章节中，我们对ldgm staircase 码和ldgm triangle码的性能进行了实验仿真， 仿真结果证明，在高码率情况下，ldgm triangle码的纠删性能要优于ldgm staircase码。 本章介绍的 rs 码、ldpc 码和 ldgm 码都属于传统的纠删码，往往是先确定编码参数， 然后产生生成矩阵，再编码得到编码符号，每次编码过程产生的冗余符号的个数是固定的， 即码率/rk n是固定的。在实际应用时，往往是先估计信道状况，确定丢包率，再确定编 码参数，然后再编码。由于实际传输信道的丢包率经常会发生变化，预测的信道状况难免与 实际信道情况会有所偏差。当真实丢包率比预测丢包率小时，冗余包数量就会多余，造成带 宽等资源浪费；当真实丢包率比预测丢包率大时，冗余包又不够，这时接收端将无法恢复丢 失的数据包。 下一章我们将要介绍的两种码率不受限的喷泉码：lt码和raptor码，此类纠删码不需要 提前预测信道的状况，由原始信息就可以产生无限长的编码符号流。 n-k k hd l l l ll l 0 l l0 l l l l 0 0 l ll l . l l 0 l l ll l 0 l l l 0 l l 0 0 l l 0 0 0 l ll l l 0 l l 0 l 0 0 l 0 l ll 0 l l l 0 l 0 l l 0 1 n-k 0 南京邮电大学硕士研究生学位论文 第二章 基于删除信道的信道编码 15 2.5 本章小结本章小结 本章首先简要介绍了rs类纠删码， 着重介绍了ldpc码的编译码原理， 然后介绍了ldpc 码的一种特殊实现形式-ldgm 码，最后分析了传统纠删码存在的问题。 南京邮电大学硕士研究生学位论文 第三章 raptor 码性能研究 16 第三章第三章 raptor 码性能研究码性能研究 喷泉码4的最初提出仅仅是一个理想的概念，直到 lt 码6和 raptor 码7的出现，才有了 具体的实现。本章在研究 lt 码编译码算法的基础上，提出了一种 ldgm-lt 级联的 raptor 码方案，并给出了详细的实现过程。 3.1 lt 码编译码原理码编译码原理 3.1.1 编码原理 lt码是喷泉码的第一类有效