喷泉编码(喷泉编码发明人)

喷泉编码

本文内容来自于互联网，分享喷泉编码(喷泉编码发明人)

喷泉编码

[编辑本段]简介

　　喷泉编码是一种删除编码，与物理层信道编码不同，它以符号(比特组)为编码单位。在用二分图描述编码时，符号可用图中的节点表示，因此在后面的叙述中我们将节点、符号和包这几个概念视作同义。我们称待编码的原始符号为输入符号或输入节点，编码后得到的符号为编码符号或编码节点。

[编辑本段]主要分类

　　LT码

　　M. Luby提出的LT（Luby Transform）码是第一个可以实用的喷泉编码，它是基于不规则稀疏二分图构造出来的一种非系统码。其编码算法如下：

　　1．假设输入符号个数为 ，编码器首先在1～ 范围任选一个服从某一分布的整数 作为该编码符号的度

　　2．在所有输入符号中随机均匀地选取 个符号作为该编码符号的邻节点符号

　　3．将这 个输入符号求异或，得到一个编码符号

　　所有的编码符号都是采用这一流程独立生成的。

　　LT码的解码采用迭代的方法进行。在解码的每一步，解码器都在编码符号集合中寻找度为1的符号，从而直接恢复出它们所连接的输入符号，然后将这些输入符号与跟它们有连接的编码符号进行异或并将结果取代该编码符号原来的值，完成之后删去它们之间的连接关系，并相应地修改编码符号的度。重复上述过程直至不存在度为1的符号为止。如果所有输入符号都被恢复则解码成功，否则解码失败。

　　LT码的单位符号的编码和解码平均算术复杂度（符号异或操作）均为 ，比经典的RS码大为降低（RS码为 ）。收端平均只需接收略大于 个编码符号( + )即可以 的概率成功解码。

　　成功解码必须的编码符号个数与原始输入符号之比的小数部分称为解码开销（overhead）。LT码实际上是通过略为增加了一些解码开销（RS码的解码开销为0）来降低编解码复杂度。

　　Raptor码

　　Raptor码是LT码的改进版。它首先对原始信息进行预编码，然后采用一个弱化的LT码对数据进行编码并发送。弱化LT码能以很高的概率恢复出大多数符号，而剩余的符号依靠预编码恢复。通过联合优化这两部分编码的码率和参数，Raptor可以在相同解码开销下实现更高解码成功率。

　　Raptor码的单位符号的编码和解码平均算术复杂度为 ，其中 是解码开销。因此Raptor码的单位编解码复杂度是与码长成线性关系，比LT码的对数关系又有所进步。

　　RU码

　　如果保持LT码的编码算法不变，仅仅改变其解码算法，用一种所谓的RU解码器代替LT码采用的BP解码器，就生成了一种新型的喷泉编码，称为RU码。它需要根据RU解码器的特点重新优化编码度分布。由于RU解码器采用的是类似高斯消去的算法，因此可以获得比BP解码高得多的解码成功率。而作为代价，它的复杂度有所增加。但是可以通过生成矩阵三角化和度分布优化设计，在复杂度和解码成功率之间取得一种良好的折中。