喷泉码编译码原理研究和分析

廖林冰（国防科技大学，长沙　410000）

喷泉码编译码原理研究和分析

廖林冰
（国防科技大学，长沙410000）

摘要:喷泉码是一种新型的纠删码技术，其创新性源于它能成图，因此在工程领域应用前景较好。本文首先综合性地分析了喷泉码的原理以及实现方式，然后研究了喷泉码编译中两种译码形式，并分析其优缺点。

关键词:喷泉码;高斯消元算法；算法

1　前言

喷泉码具有传播速度快、无需信道反馈的优势，所以被广泛应用在3G网络中，不但如此喷泉码已经延伸到分布式储存和太空通信领域，可见喷泉码会随着时代的发展，产生巨大的经济效应。因此研究喷泉码的编译原理是当下时代的需要。

2　喷泉码编译的原理和实现方式

无码率是喷泉码的一个特征，该特征能够完成无终结性的编码符号译码，并且编码符号都是随机、独立生成。这类编码无休止的生成，就如同是水滴向外喷，喷向如同杯子形状的接收端。喷泉码具有独立且随机性的特征，各个字码块中都包括源信息并不被杯状的接收端重视，而是在到达删除信道后，可以任意的删减喷泉码中的任意码，同时并不影响其余的译码参与到信息传输中去。

2.1LT译码原理

LT编码方式能够直接将向量信号向(x1,x2....xk)输入后，就会将任意的独立向量计算出来。以下是对任意一个编码符号进行计算的环节：

2.2输入信息度分布

之所以度分布信息作为喷泉码中设计编码特性的关键所在，是因为喷泉码进行译码时以接收信息中d等于1节点的分列形式为依托。这样才能够确保译码的实现，并且在更迭过程中将节点1永无休止的生成。大多数节点都有较小的度值，这样就会降低译码的复杂运算度，保证译码顺利完成；度值如果较大，就表明编码的节点和参与量均少，为了杜绝遗漏编码就会有调用较大的度值。为了确保正确的译码实现，一个节点信息相连接编码时，至少是一条边。

3　介绍喷泉码中典型的编译方式以及其仿真结果

3.1高斯消元译码算法

作为一类在喷泉码技术中较为常见的高斯消元译码算法，能够适合各类喷泉码的译码。通过研究删除信道得知，运用最大似然译码算法应用在线性译码中与线性公式求解相等，所以高斯消元法是可以实现喷泉码的译码。以下是高斯消元算法的流程：

将n定义为接收端接收的符号，N则是表示输入的n×1接受向量，H表示为矩阵。第一步，在N的作用下，将H扩展为H'即增广矩阵，即H/N＝H’。第二步，将H’转换成为1的矩阵单位，必须依托于矩阵的初等变化原理，此时1/N’＝H’。第三步，当矩阵的单位有最大的矩阵值时，那么说明能实现译码，这时译码输出的待求解信息向量X与增广向量N’相等；当没有尽可能大的矩阵出现，就说明译码无法成功，这时信息会继续输入到接收端，再进行下一个流程的译码。

通过对高斯消元译码整个流程得知，k这一信息块长度的增加会导致运算量的迅速增长，所以计算的难度也有所增加，因此只适合用于短喷泉码的译码工作。

3.2置信传播编译算法

置信传播算法即BP算法，通常被人叫做消息传播（MP）算法。在度适当分布的情况下，利用该种算法能够在一定程度上提升计算机性能，然而在进行中长码字进行译码时，无法提升计算机的运算速度。截至目前为止，BP算法是被人广泛应用却计算喷泉码时较为有效的算法。

根据喷泉码是带图纠删码技术的原理，所以用Tanner图来表示较为恰当。将信息符号n个输送到接收端之后，一个信息符号所表达出来的都会用k维的列向量，这时H作为校验矩阵，n×k等于H.接收的图像中用坐标（V,E）来表示，每组节点的组合都是用V=Vs∪Vc来表示，而每组符号的节点是用VS={S0,S1...SK-1}来表示，校验节点则是用VC={C1,C2,...CK}来表示；每组边集合用E来表示，当hi,j≠0,hi,jH,且i小于k大于0和j小于n大于0时，则会得出存在边的与集合的关系(Si,Cj)E，因此Vs1表示的集合是由全部符号节点与其作用的校验节点所组成。

当有k个接收符号在接收端时，会激活译码器，进行译码作业。当将k个符号全部译完后，就会停止这一段落的译码。在译码工作停止后，进行下一个流程的符号接收工作，一直到满足k个时，译码器再进行译码时才会停止接收符号。BP算法是一个循环往复的计算过程。因此在置信传播译码算法中我们通常将其分为两类，即硬判决算法和软判决算法。

在删除信道丢失后的一组编码符号，没有任何误差的情况下，可以利用硬判决进行译码。特别是在某一个符号左右的信息节点是相对固定时，译码器就会默认为相邻信息符号一致。软判决算法则是能在信道信号弱或者受到噪声影响的情况下执行译码作业，这时采用软判决译码方法会在很大程度上确保译码的正确性。

3.3结果分析

通过以上我们对GE算法与BP算法的性能表述和线性随机编码情况下对两种算法相比较得知，BP在节点起始点小于1的状况下，无法成功译码。GE译码却不受以上状况的影响，能够在线性随机译码的任何状况下，确保译码的准确性。而在信息分布度中来比较GE 和BP两种算法，在译码信息的长短和性能上，BP算法都优于GE算法。

4　结论

通过本文对GE和BP两种计算喷泉码的方法可以得知，GE算法能够普遍应用在各种编码中，不过如若是运算的程度较为复杂，就会由于信息过多，计算的会变得迟缓。而BP算法则是只需要起始节点保证为1，即使对再复杂的喷泉码译码都会在保证效率的情况下，进行准确的译码。因此BP算法运用在工程上能够很大程度上满足各种需要。

参考文献：

[1]杜超.深空通信中喷泉码编译码性能研究[D].哈尔滨工业大学,2013（05）：120-127.

[2]李璐颖,吴湛击,王文博.喷泉码编译码原理研究和分析[J].中国新通信,2012（07）:41-46.

[3]詹奇聪.喷泉码与极化码的改进及应用[D].华南理工大学,2014 （03）：31-20.