数字喷泉编码的研究

张晓晨，苑 林，李晓光

河北大学，河北 保定 071002

0 引言

通信系统的基本目的在于将信息由信源高效且可靠地传送到信宿。早期人们普遍认为：通信系统的可靠性和有效性是一对不可调和的矛盾。随着香农在他的论文《通信中的数学理论》[1]中，提出了著名的有扰信道编码定理，这篇文章奠定了信息理论的基础，构造接近香农容量限的纠错码一直是信道编码理论的理想，一般使用的都是差错控制编码技术[2]。进行差错控制的方式主要是重发反馈或者是前向纠错，或者是两者混合的方式。但在不管在何种方式下，进行编码时，都给予一定的信道假设，必须预先设定好信道的删除性，才能设计具体的编译码方法。由于信道的时变性，当信道优于假设时，传输效率就会降低；当信道劣于假设时，传输的可靠性就会降低[3]。近年来受到普遍关注的数字喷泉码（Digital Fountain Codes）成为构造这种可靠传输方案的最佳技术，喷泉码的发明解决了以上问题。

文件在网络中传输时，是基于包通信的。传统传输协议是简单的把文件分成若干个数据包，进行重复传输直到每一个反馈信道都告知准确接收到。相反，喷泉码编码是对文件的随机编码，可以产生半无限长的编码序列，而不考虑信道删除概率就能恢复源文件。喷泉码是一种在删除信道下性能优越的稀疏矩阵码，也是一种纠删码。它是一种与码率无关的且具有线性译码复杂度的随机编码方式，由源文件经过编码产生的码元不受限制，可以产生无限多的码元，不论信道中被删除的码元有多少，都能通过发送足够多的编码码元供解码器恢复源文件。由于其编译码的特性以及成功译码的高概率，不需要对每个数据帧进行逐帧反复确认，因此不会产生“反馈风暴”。 喷泉编码由k个原始分组生成任意数量的编码分组,而接收方只要收到其中任意m个编码分组,即可通过译码以高概率成功恢复全部原始数据分组。一般情况下,这里的m略大于k,从而引入一定的译码开销ε,定义为ε=m/k-1,也即m=k（1+ε）。该种编码生成的数据包有如水珠，接收端有如水杯，每个编码包不分先后顺序，对于接收端，只需要接收足够数量的编码包，传输就能顺利完成。可以形象地说，喷泉码编码器就如同源源不断产生水滴的喷泉，我们只要用杯子接足够数量的水珠，就可达到饮用的目的[4]。

1 喷泉码介绍

1.1 LT码的编译码原理

1998年，Luby等首次提出了用于分布数据的数字喷泉技术。一个理想的数字喷泉应该具有如下特征：

1）能够利用原数据产生无限编码包序列；

2）对于被分割为k个数据包的一消息，一旦接收到编码包流中任意m个编码包，接收者就能重构这一消息。这种重构算法应该非常快。

2002年，Luby提出了一个非常适用于网络数据分布的编码方案——LT码[5]，这是第一类码率不受限码的实用实现。LT码的度分布定义为一个输出符号节点的度为d的概率。它的编码算法：

根据给定的度分布函数随机选取度d；

随机选取d个不同的输入符号；

3）编码后的输出符号为这d个不同输入符号的异或和。

如图1，编码过程：

1）取一个度分布函数，根据度分布函数进行随机试验，选取编码分组的度数d；

2）从预编码之后的数据分组中，随机的选取d个；

3）将这d个数据分组进行模二相加，生成编码分组。

图1 编码过程

解码过程：

1）在接收端收到的编码信息单元中，如果存在邻接度为1（即只有一个邻接单元）的节点，则其邻接单元（对应于某一码层次的输入数据单元）可以被恢复，因为根据编码过程该单元是接收到的编码信息单元的拷贝；

2）如果已经被恢复的输入数据单元是某个邻接度不为1的编码信息单元的邻接单元，则该编码信息单元的邻接度减1，并且在相应的邻接图中删除二者邻接的边；

3）如果已经被恢复的输入数据单元是某个邻接度为1的编码信息单元的邻接单元，则删除两者邻接的边以及上述与之相连的编码信息单元；

4）如果在代表邻接关系的二部图中找不到与上面刚被恢复的输入数据单元邻接的其他编码信息单元，则删除该原始输入数据单元和步骤1）中发起本次叠代过程的编码信息单元，最后在相应的邻接图中删除代表二者之间邻接关系的边，重复从步骤1）开始新一轮的叠代过程；

5）如果在某次叠代过程中，邻接图右侧不再具有邻接度为1的编码信息单元节点则解码过程结束，若邻接图中左侧的原始输入数据单元的节点都得到成功恢复，则解码过程成功，否则解码过程失败[6]。

理论上，生成的编码符号可以无限多次的通过信道传输，编码符号之间是相互独立的，这使得喷泉码是无码率的，因为喷泉码的编码包数目是不固定的，相应的，码率也是不固定的。实际上，LT码的编码算法定义了一个连续输出符号到输入符号的二部图，而度分布直接决定了LT码的译码是否成功，同时也决定产生编码包所需要的异或运算次数。

度分布函数设计的好坏在很大程度上决定了译码的成功率。一个好的度分布函数既要保证编码器输出中含有一小部分d 与k差不多大的数据包， 这样才能保证所有的源数据参与到最终的编码。同时，又要包含许多d 较小的数据包， 这样才能保证译码的过程不会因为预译码集的消失而使译码被终止。最初，理想孤波分布被认为是理论上最适合的度分布函数∶

理想孤波分布函数定义：

在理想的情况下，LT码的编码分组在每一步中解码的概率是1/k，每一个释放的原始分组就会增加到预处理集中，经过k步解码，k组原始数据就会恢复。但是这个过程是在均值分析的基础上进行的，在实际应用中，上述过程经常会出现波动，在将k组原始数据都被恢复出来之前，预处理集可能已经为空。因此，由于理想孤波分布的输入波纹期望值为1，一些小的变化也会导致译码的完全失败。Luby在此基础上使用了鲁棒孤波分布：

鲁棒孤波分布如下式：

其中s=cln（k/δ） k1/2[7]，c 取一适当的常数c＞0。δ是接收到K 个确认的数据包后无法解码的概率的极限， 其中K=k+O（k1/2ln2（k/δ））。将理想孤波分布ρ（d）加上τ（d）就生成了鲁棒孤波分布μ（d）。

在使用鲁棒孤波分布的情况下，能够使用接近最小的包来恢复所有的原始数据，LT 码译码成功率至少为1-δ。但是效果也并非十分理想，为了将LT码的译码复杂度降低为线性时间复杂度，可以对其增加预编码，这种码就叫做Raptor码[8]。

1.2 Raptor码的编译码原理

Raptor码是由Shokrollahi提出的迄今为止最有效的一类数字喷泉码[9]，如图2，Raptor码采用多层预编码，首先对原始数据进行预编码，最后使用LT码进行编码。中间两层节点为中间编码校验单元，输入单元到第一层中间编码校验单元的映射采用扩展汉明码，第一层到第二层中间编码校验单元的映射采用的是是Gallager在1963年提出的[10]LDPC码。

图2 Raptor码预编码过程

输入单元到第1层中间编码校验单元的映射采用的编码是扩展汉明码，扩展汉明码是在（2m-1,2m-m-1）的汉明码的基础上，再加入一个对于所有码位进行奇偶校验的码位，因此扩展汉明码码位满足以下方程：

这样（Cn-1，Cn-2，……，C1，C0，C0′）共同组成一个完整的码字。扩展汉明码有效信息位为k位，校验位为m+1位，码长为n+1，符合（2m,2m-m-1）的形式。在进行解码的过程中经常由于停止集过小而引起解码失败，扩展汉明码的最小汉明距离为4，在这种情况下停止集的大小一般为2或者3，因此LDPC码具有较高的解码概率。

由于Raptor码的编码过程包括预编码过程和LT编码过程，使得即使编码后的数据包仅有一部分可恢复，也可以利用这部分被恢复的编码包来恢复原来的所有数据包。这样将一个经过预编的码与一个适当选取的LT码级联即得一个具有线性时间译码复杂度的Raptor码。

2 结论

LT Code有着较小编译码复杂度，Raptor Code由于采用了预编码技术对LT Code进行了扩展，因此具有更高的解码效率。目前，喷泉码仍在不断发展，应用领域不断扩大，具有光明的发展前景。尝试其它编码技术（如RS码和交织码）与Raptor Code相结合将是今后进一步的研究方向。

[1]C.E.SHANNON.A Mathematical Theory of Communication,Bell Syst.the.J，1948：27.

[2]王新梅.纠错码-原理与方法[M].西安：西安电子科技大学出版社，2003：259-268.

[3]王新梅，肖国镇.纠错码——原理与方法[M].西安：西安电子科技大学出版社，1991.

[4]J W Byers,M Luby,M Mitzenmacher.A digital fountain ap-proach to reliable distribution of bulk data[A].Proceedings of the ACM SIGCOMM’98conference on Applications,technolo-gies,architectures,and protocols for computer communication[C].Canada:Vancouv er1998,28(4):56-67.

[5]Luby M.LT-codes[C]//Proceedings of the 43rd Annual IEEE Symposium on the Foundations of Computer Science，2002：271-280.

[6]孟庆春，王晓京.Raptor Code预编码技术研究.计算机工程，2007，33(1)：1-3.

[7]L uby M. LT codes.In:Proceeding of the 43rd Annual IEEE.Symposium on the Foundations of Computer Science(STOC),Vancouver, Canada, 2002，11.

[8]Amin Shokrollahi.Raptor codes.IEEE Transactions on Information Theory，2003，52(6):2551-2567.

[9]A Shokrollahi.Raptor codes[J].IEEE Transactions on Infor-mation theory, 2006, 52(6):2551-2567.

[10]Gallager R G.Low Density Parity Check Codes[D].Cambridge:Cambridge University，1963.