数字喷泉码课件

1、数字喷泉码，吴彬彬，2011.10.23，大纲，喷泉码的随机线性喷泉码的生成LT码：LT码的解码度分布函数的设计Raptor码，喷泉码的生成，信息以数据包的形式在互联网上传输。通常，每个数据分组或者被接收端无差错地接收，或者根本不被接收。在TCP协议中，网络丢包采用错误检测和重传机制。这种简单的检错重传协议的优点是可以保证接收方接收到的数据没有错误，但是反馈会严重浪费信道资源，而且当接收方和发送方之间的距离较远时，会有很大的时延。1998年，卢比首次提出喷泉码的概念。2002年，卢比给出了一个现实可行的喷泉码LT码。2004年，在LT码的基础上，肖克罗拉希和卢比提出了复杂度低于LT码的数字喷泉

2、码猛禽码。喷泉码是指编码可以从k个原始源信息中产生任意数量的编码包，然后通过解码可以高概率地恢复原始包。编码过程就像一个不断产生水滴的喷泉，只要我们接收到足够多的水滴，我们就可以达到喝水的目的，所以这叫做喷泉编码。同时，由于喷泉码中没有码长，码率的定义也被称为无码码。由于数字喷泉码的非码率特性，发送方可以不断生成编码符号信息，每个编码符号都是由信源信息的独立随机异或生成的。由于每个码字的独立随机性，每个码字都包含源信息。因此，删除编码信息的任何部分都不会影响其他符号信息参与解码。随机线性喷泉码，假设编码器需要编码的文件是，它们只能被正确传输或删除。在每个时钟周期内，编码器生成一个k阶随机二进制

3、矩阵，编码器的输出由异或运算形成，即不同的异或运算，对于每k个随机性，可以在半无限二进制矩阵中定义一个新的列，如下图所示。然后，通过信道传输编码的数据包，并且删除数据包，并且接收端总是接收数据包，直到接收到n个数据包。假设接收方知道随机矩阵，并且随机矩阵与和相关，因此上图中矩阵的可用部分可以被称为G，并且源文件可以被G恢复。随着源文件大小(k)的增加，随机线性喷泉码可以接近香农理论的极限，但是编码和解码随机线性喷泉码的成本是k的二次幂。当k大时，编码和解码的复杂度非常高。因此，人们希望找到一种复杂度较低的喷泉码，于是出现了吕比变换码。LT码是第一个真正意义上的实用喷泉码，其编码算法如下：将原始

4、源数据平均分成k个数据包，根据1k内编码的度分布随机选择一个整数d，其中d称为编码包的度；从数据包中统一随机选择d个不同的数据包；一个编码包可以通过否定或d个数据包获得。注：编码度分布表明随机选择整数d的概率为，其中d是可获得的最大度。编码度的分布也可以表示为：LT的解码方法是高斯消去法，高斯消去算法是喷泉码的一种通用解码方法。假设接收机接收到N个符号，每个接收到的符号代表一个具有K个未知输入的线性方程，整个解码过程可以看作是一个由N个方程联合求解K个未知输入的方程组。该方法包括：假设h为删除信道后的生成矩阵，将h矩阵扩展为包含接收信息向量n的扩展矩阵；通过矩阵初等变换对增广矩阵进行变换，使得

5、如果单位矩阵I满秩，则解码成功，解码输出x为：如果单位矩阵低于秩，则意味着接收的信息不足，解码失败。接收端继续接收信息并进入下一轮解码。注意：高斯消去算法的缺点是解码复杂度高，不适合长码运算。LT解码算法、BP算法、BP算法适用于仅丢失一组接收的编码符号集而不引入删除信道后的误差的情况。我们将接收到的编码数据包称为校验码。解码过程如下：解码器在校验节点中寻找d=1的节点，即校验节点只与唯一的符号节点相连。如果存在，则将与该节点连接的节点的值恢复为检查节点的值；搜索与上一步恢复的符号节点连接的校验节点集，并与异或运算，然后删除它们的连接；循环重复这个过程，直到所有符号都被正确翻译。如果在循环迭代

6、开始时没有d=1的节点，则无法开始解码，d=1的节点在循环迭代中耗尽，循环将终止，解码器无法解码，接收器继续接收信息，并进入下一轮解码。喷泉码的度分布函数和度分布信息的设计是喷泉码编码和性能的关键。因为喷泉码解码取决于接收信息中d=1个节点的分布，解码的持久性取决于迭代过程中d=1个节点的持久性。良好的度分布应满足以下条件：大多数节点的度值应较小，以减少编解码的异或运算次数，保证解码过程的连续性；参与编码的少量节点应该具有较大的度值，以避免丢失编码信息点。理想孤子分布：理想孤子分布是最理想的解码状态，也就是说，在每个解码周期中，至少有一个校验码的阶数为1。同时，在一个校验码被处理之后，一个新的

7、1级校验码出现，因此解码时间可以被优化。为了简单起见，取K=100，这表明1度的概率是1/100；2度的概率是1/2；3度的概率是1/6；100度的概率是1/9900。为了简单和准确，概率区间0，1将被扩展10，000倍到(0，10，000)，然后(0，10，000)将根据每个度的概率被分成100个区间。通过调用RAND函数，随机数将在0到10，000之间生成，随机程度将通过观察这个随机数落在哪个区间来确定。度只决定代码由几个异或组成，但它不决定哪个异或。事实上，在一定程度上，它对应的代码可以通过源文件中的任何异或操作获得。就像确定随机性的方法一样，它也可以随机选择。但是选择每一个的概率是一样

8、的，是1/k。同样，为了精确，概率区间0，1被扩展10，000倍到0，10，000，然后0，10，000被等分成区间。在一定程度上，再次调用MATLAB中的RAND函数来随机生成0到10，000之间的数字，并根据这个随机数落在哪个选定的区间来确定编码中涉及哪些数字。但是在实际应用中，编码度分布的采样不能准确符合理想分布，并且存在一定的波动误差，导致迭代介质为1的节点故障，导致解码失败，实际性能不理想。鲁棒孤子分布：改进的鲁棒孤子分布有效地结合了理想分布的优点，并增加了另外两个调节参数c和；它们的引入将确保在每个解码周期中校验码的数量等于1，而不是1。参数是给定数据包无法解码的概率极限。在实际应

9、用中，c可以用作小于1的可调常数，以优化性能。鲁棒孤子分布分为两部分，一部分如下：另一部分是上述的理想孤子分布：可以归一化得到鲁棒分布：在成功解码的概率至少为零的情况下，需要接收的编码数据包的数量。解码直方图(Raptor码)所需的接收数据包数，对于LT码，为了确保所有输入符号都以高概率恢复，其解码图需要多条边。此外，为了确保所有数据包都参与编码，必须有一些编码度较大的数据包。一旦这些编码包丢失，就可能导致解码失败。Raptor代码的基本思想是，只有一些输入符号可以通过放宽所需的边数来恢复具体地，Raptor代码首先对原始数据分组进行预编码，使得即使只有一部分编码数据分组可以被恢复，也可以通过使用恢复的编码分组来恢复所有原始数据分组。在预编码过程中，通过传统的纠删码将原始的K个输入符号转换成k1个中间符号，然后将这些中间符号作为LT码的输入符号进行二次编码，得到Raptor码的编码符号。由于预编码具有一定的纠删能力，放宽了对LT码的要求，降低了整体编解码复杂度。在实际应用中，Raptor码采用多层校验编码技术，从源数据到第一层编码校验单元的映射采用扩展汉明码，从第一层编码校验单元到第二层的映射采用LDPC码，如下图所示：Raptor码编码过程中采用的LT码是一种低平均维数的LT码。这是因为平均维数较低的LT码能够以较高的概率恢