纠删码

2024年2月15日发(作者：瓷玫瑰)

一 纠删码概念和原理

前向纠错(Forward Error Correcting，FEC)技术近年来广泛应用于信息处理的各个领域。各种纠错码，诸如汉明码、BCH码、Reed-Solomon(RS)码、卷积码、Turbo码、低密度奇偶校验码(Low

Density Parity check codes，LDPC)等，，所讨论的错误检测和纠错多用于低层协议(如链路层)以比特串为单位的纠错。

纠错码纠正的误码位置一般是未知的，误码位置可知的错误被称为删除错误，纠正删除错误的纠错码称为纠删码(Erasure Codes)。纠删码对提高网络通信的质量和可靠性有着重要的意义。

纠删码的原理可简述为：发送方将k个源数据包编码为n(n>k)个编码包，将这n个编码包在网络上传输，接收方只要接收到一定数量的编码包就可以将原始数据恢复。

目前主要有三类纠删码：RS类纠删码、级联低密度纠删码和数字喷泉码。RS类纠删码包括范德蒙码(Vandermonde Code)和柯西码(Cauchy Code)。级联型低密度纠删码(Cascaded Low-Density

Erasure Code)是由级联随机稀疏二部图和一个传统的纠删码构造而成的一种特殊的纠删码，如Tornado码。数字喷泉码(Digital

Fountain Codes)的概念由等人于1998年首次提出，在2002年提出了第一类通用的喷泉码——LT(Luby Transform)码。

为了克服LT码的局限性，随后Shokrollahi提出了Raptor码，它

由一个预编码和LT码构成，是数字喷泉码模型中用于可靠传输的最新码。下面分别介绍这几类纠删码的原理，分析其各自的特点并讨论

纠删码的应用及发展方向。

RS类纠删码

RS码是一类有很强纠错能力的多进制BCH码，首先由Reed和Solomon于1960年提出，它不仅能纠正突发错还可以纠正随机错误。RS类纠删码根据其生成矩阵不同分为两类：范德蒙码和柯西码。一个(m,n)线性纠删码可表示为：y=xG，其中x(x1,x2,,xm)是元数据包向量，y(y1,y2,yn)是编码后得到的数据包，Gmn为线性纠删码的生成矩阵。

范德蒙矩阵

1g02g03Gg0mg01g11g22g23g21gn12gn13gn1

mgn1g12g13g1mg2m即G的任意K列组成的子方阵G'都是非奇异的，因此这样得到的矩阵满足纠删码生成矩阵的特性。

柯西矩阵

x1x2Gx3xm1y11y11y11y11x1y21x2y21x3y21xmy21x1y31x2y31x3y31xmy31x1yn1x2yn

1x3yn1xmyn

其中x1,x2,xm和{y1,y2,,yn}为同一个有限域的两个元素子集，它们必须满足：（1）不同子集中的任意两个元素相加不能为0（2）这两个子集中的每个元素都不相同。

在有限域上，Ikk为单位矩阵，Ck(nk)为柯西矩阵，若取生成矩阵G(I/C)，则称所得到的纠删码为柯西码。

范德蒙码的编码时间复杂度为O(n2)，解码时需要对矩阵求逆，解2码时间复杂度高于O(n2)。而柯西码的编码时间复杂度为O(n)，但是柯西码解码不用求大矩阵的逆，而且把乘法除法运算分别转化为有限域上的加法和减法运算，可用异或实现，因此，柯西码运算复杂度低于范德蒙码。

级联低密度纠删码

为了构造一种具有低运算复杂度，且能以接近信道容量的速率进行传输的纠删码，Spileman用基于扩展图的LDPC码，设计了具有线性编码时间和良好纠错性能的码，Tornado码就是如此，其译码算法能以很高的概率和Onln1/的运行时间恢复删除错误，其编码时间为Onln1/。Tornado码不仅提供接近最优的损失保护，而且能以线性时间编码和解码，大大提高了编解码的速度。

与RS码相比较，Tornado码编码和译码过程只使用简单的二进制异或运算，而RS纠删码需要在有限域上进行复杂的矩阵运算，因此其编译码速度比RS纠删码快很多。但是它与RS码一样都是具有固定码率的纠删码，其编译码算法过慢，这使得Tornado码在许多要求低码率的实际应用中并不适用。

数字喷泉码

数字喷泉码是一类码率不受限的纠删码(RatelessErasure Codes)，也称为无速率编码，其原理类似喷泉的特性，即从k个源符号在线编码产生的编码符号序列是无限的，每个编码符号等于若干随机独立选取的源符号的异或和，接收方只要收到其中任意m个编码符号(m一般略大于k)，就可通过译码以高概率成功恢复全部k个源符号。2002年Luby提出了一类通用的数字喷泉码——LT码，其对于具有不同删除概率的各种删除信道均是最优逼近的。LT码的构造中最为关键的是度分布的设计，因为度分布直接决定了LT码的译码能否成功，也决定着产生编码包所需要的运算量，LT码目前采用较多的是Robust

Soliton度分布，该度分布设计能以很高的概率成功译码。Raptor码在编码之前，首先对数据进行预先处理，然后再用LT编码算法进行编码。由于生成的中间编码包不同，预编码可以分为单层预编码技术和多层预编码技术。

二 纠删码编码与解码的具体细节

假设数据块B长度为L，使用（m,n）线性纠删码生成矩阵Gmn对其进行编码。具体过程如下：

（1）将L分割成长度为m的数据段，共有L/m个段，当L/m不是整数时，就取整数位加1，共有[L/m]+1个段。

（2）对每一个段Mi进行编码计算Mi'MiGmn，所有编码后的段共有n个列向量Pi，每个列向量有[L/m]或者[L/m]+1行。

i1,i2,im[1,n]，（3）如果接收方收到m个列向量Pi1,Pi2,Pim，

m矩阵，此矩阵的行向量为Si，这m个列向量组成(L/m)1iL/m。利用纠删码生成矩阵G中的i1,i2,im列构造mm矩阵G’，因为G’可逆，因此可以得到Si'Si(G')1，这样就恢复了原数据块B。