一种多进制喷泉码短码的编译码方法

陈莉华

（北京理工大学出版社有限责任公司，北京 100081）



一种多进制喷泉码短码的编译码方法

陈莉华

（北京理工大学出版社有限责任公司，北京 100081）

摘 要：喷泉码在码长较长时，采用复杂度与码长呈近线性关系的置信传播译码，可靠性接近香农限，编码效率接近1。由于喷泉码在编码效率和译码复杂度方面具有优势，因而在多媒体广播多播、分布式存储、容迟容断网络等领域得到广泛应用。但基于二进制的传统喷泉编码，为了获得较好的译码性能和编码效率，码长比较长，一般都需要达到几千甚至几万个符号；应用于短文件的存储、传输，编码效率大为下降，带来存储和效率的急剧下降。文章介绍了一种多进制喷泉编译码，其效率与二进制编码相比，在效率和性能方面得到显著提升，但译码复杂度仅略有上升。

关键词：喷泉码短码；LT码；Raptor码

1　概述

数字喷泉码是一种应用于删除信道的纠错编码技术，其典型应用多媒体广播多播、分布式存储、容迟容断网络等［1］。该编码的基本思想如下：在发送端，将需要发送的K个数据包进行线性组合，按需生成N个编码包；在接收端，接收到K个编码包，求解线性方程组就可以求出信源数据包。每一个传输的编码包可嵌入包编号、CRC校验等。接收端检查CRC即可获知某编码包是否被正确传输，因而信道可等效为删除信道。采用伪随机的方法选取编码系数，接收端根据包编号即可生成编码系数，恢复编码方程，因而无须传输编码系数。基于此，不管接收到哪些编码包，无论喷泉包的顺序如何，接收端都可以求解线性方程组恢复原始数据。这好比人们使用杯子接水来喝，饮水者只关心杯子是否装满；至于哪些水滴接入杯中，则不必关心。

基于喷泉码的基本思想，M.Luby和A.Shokrollahi分别提出了两种实用的喷泉码，即LT码和Raptor码。目前，LT码已经在无线组播、分布式存储等多个领域得到应用［2-5］。但目前实用的喷泉码在码长很长时，其译码复杂度、译码性能和编码效率表现优异。但对于短喷泉码，这些性能表现不佳。例如，采用LT码，如果希望编码开销小于5%，则信源长度需要10000以上。如果编码长度小于1000，则编码开销高于30%。实际的有线通信、无线通信及文件存储系统，长度很短的信息、短文件比较多；这些短信息、短文件不太适合码长很长的喷泉码编码。基于此，本文介绍一种高效率的多进制喷泉码。这种编码基于有限域，其效率与二进制编码相比，在效率和性能方面得到显著提升，但译码复杂度仅略有上升。

2　多进制喷泉码的编码

考虑二进制编码的线性方程组的系数矩阵只能选取0和1，因此希望矩阵的秩为K，比较有效的方法是增加方程组的数量N。这样，当码长较短时，增加N会造成编码效率的下降。如果采用多进制编码，由于系数矩阵中每个元素的维度增加，容易达到满秩。基于此，采用多进制编码可有效提高短码的编码效率。

对喷泉码进行编码的方法如下：

选取非负整数di。一般地，该非负整数可基于鲁棒孤子分布µ（d）随机选取。称di为编码符号Vi的编码度。然后，随机均匀地从K个信源符号中选di个符号，并基于有限域GF（q）随机均匀地生成di个非零编码系数。将选出的信源符号和这些非零系数对应相乘，然后作和，就得到编码符号Vi的值。

3　多进制喷泉码的译码算法

由上小节可知，多进制喷泉编码可表示成线性方程组w=A·m。只要矩阵A的秩为K，收到w=［w1，w2，…，wN］T后，译码器通过基于有限域GF（q）的高斯消元就能够求解出信源矢量m=［m1，m2，…，wK］T，实现最大似然序列译码。但直接进行高斯消元时，由于存在大量的行列置换及消元所需的乘法和加法运算，复杂度为O（K2）到O（K3），难以实际应用。事实上，注意到的w=A·m矩阵为稀疏矩阵。利用该特性，可大大降低译码复杂度。基于此，给出低复杂度译码过程如下：

（1）对矩阵A进行主元选择。

主元选择的步骤和常规的高斯消元法一致，包括K步前向迭代过程。在第K步，将第K行用（K，K）位置的元素归一化，然后将该行的适当倍数并叠加到下面各行，使下面各行第K列的元素全化成零。重复该过程K次，矩阵变成上三角形式。为了最小化局部填充元和局部操作量，选取最大填入和操作数最小的元素作为主元。

（2）主元原位高斯消元。

在常规的高斯消元法中，存在大量的行交换。由于行交换需要反复复制数据，造成译码计算和存储量的上升。对于稀疏编码矩阵，矩阵中存在大量的零元，这些零元参加运算和存储器的存取会造成存储和计算资源的浪费。实际上，不需要进行实际的行列交换，用2K个存储单元记录迭代过程中主元行号和列号就可以了。

具体地，在迭代过程的每一步，基于稀疏存储，每次消元，根据所存取的行，读取非零元素，然后进行消元操作，更新非零元素的存储记录。在此基础上，根据步骤1选取主元，记录其行号和列号。重复该过程，直到完成整个方程组的消元，将系数矩阵化为下三角矩阵。

最后，采用后向迭代，求解线性方程组w=A·m中的未知量m的元素，得到译码输出序列m。这样就完成了多进制喷泉码的编码和译码过程。

4　仿真结果

采用鲁棒孤子（Robust-Soliton）分布作为编码度分布函数µ（d）。令信源长度为K，设c和δ是满足c＞0和c＜δ＜1的两个参数，令其1n（x）表示自然对数。设d=1时，时，设当时；当d=K时，；对于其他的

为了说明使用鲁棒孤子分布选取编码度时多进制喷泉码的性能，选取喷泉短码长度K=100，C=0.05，改变参数δ，编码度采用鲁棒孤子分布，使用多进制喷泉码编译码方法。选取q=2和q=16两种情况。经验证，在译码失败概率为10-2时，码长为100的16进制短码，其编码开销只需要5%。对于二进制编码，若实现这样低的编码开销，如第1节所述，其编码长度需要10000以上。

使用鲁棒孤子分布，选取N=1250，K=1000，C=0.05，δ =0.05构造二进制和十六进制的LT码，基于稀疏矩阵的高斯消元法实现了最大似然序列译码。经仿真验证，多进制喷泉码的最大似然译码远远快于常规的高斯消元法，计算复杂度仅为BP算法的4倍。作为比较，通过仿真验证常规的高斯消元法对该编码译码的复杂度，发现采用常规高斯消元法时，计算复杂度为BP算法的170倍，不具实用价值。这说明，多进制喷泉码比二进制编码在复杂度方面只略有提高，但短码性能获得显著提升。

5　结语

二进制喷泉码在码长很长时具有很高的效率和优异的译码性能。但码长较短时，编码效率急剧下降。基于此，本文介绍了一种多进制喷泉码，给出了喷泉短码的编码，并利用编码矩阵的稀疏特性，讨论了主元原位消元和稀疏存储和计算的低复杂度译码方法。经仿真验证，与二进制编码相比，多进制编码在效率和性能方面得到显著提升，但译码复杂度仅略有上升。

［参考文献］

［1］LUBY M.CODES LT.In Proceeding of the 43rd Annual IEEE Symposium［J］.Foundations of Computer Science ，2002（10）：271-282.

［2］Mitzenmacher M.Digital Fountains:A Survey and Look Forward［J］.Information Theory Workshop，2004（10）：271-276.

［3］LUBY M.CODES LT.［J］.In Proceeding of the 43rd Annual Symposium［J］. Foundations of Computer Science，2002（6）：271-282.

［4］PALANKI R，Yedidia J S.Rateless codes on Noisy Channels［J］.International Symposium on Information Theory，2004（6）：1008-1010.

［5］CASTURA J，MAO Y.Rateless Coding over Fading Channels［J］.Communications Letters，2006（1）：46-48.

A Kind of Multi-band Fountain Code Short Code Decoding Method

Chen Lihua
（Beijing Institute of Technology Press，Beijing 100081，China）

Abstract:The fountain code when the code length is longer，the complexity and code length is nearly linear relationship of belief propagation decoding，reliability is close to shannon limit，coding efficiency is close to 1. Because of fountain codes have an advantage in terms of coding efficiency and decoding complexity，therefore in the multimedia broadcast multicast，distributed storage，let ChiRong broken network in areas such as widely used. But traditional fountain based on binary coding，in order to obtain better performance of decoding and encoding efficiency，code length is longer，usually need to reach thousands or even tens of thousands of symbols；Used in short file storage，transmission，coding efficiency decrease，bring the efficiency of storage and fell sharply. This paper introduces a fountain of multi-band compiled code，its efficiency compared with binary encoding，received a significant boost in terms of efficiency and performance，but only slightly higher decoding complexity.

Key words:fountain code short code；LT codes；raptor code

作者简介：陈莉华（1976-），女，北京，硕士；研究方向：通信技术。