一种用于水声通信的喷泉码最大似然译码方法

武岩波　　朱　敏(中国科学院声学研究所声场声信息国家重点实验室　北京　100190)(中国科学院声学研究所海洋声学技术中心　北京　100190)



一种用于水声通信的喷泉码最大似然译码方法

武岩波*朱敏
①(中国科学院声学研究所声场声信息国家重点实验室北京100190)
②(中国科学院声学研究所海洋声学技术中心北京100190)

摘要：针对水声通信特点，研究随机线性喷泉码及最大似然译码，在分块数较小的包传输中纠正删除错误。传统的最大似然译码为整包统一处理，译码延迟大。该文提出一种逐行累增的高斯消去方法，将译码过程划分到各块到达时隙中执行，利用二进制分布求和的概率公式对单块到达所需计算量进行分析。在实际水声通信处理平台上进行了验证，满足实时计算需求，可用于水下图像、传感器数据等的传输。

关键词：水声通信；喷泉码；高斯消去法；随机线性喷泉码

1　引言

水声通信信道时变性强，信道冲击响应、环境背景噪声和干扰是非平稳过程，造成信道容量是时变的，数据块传输错误或丢失的比例较高。目前，实际水声通信系统中多采用选择性重传的反馈机制。水声传播速度小且水声通信为半双工方式，因而反馈信道造成信道利用率低。从信息论来看，反馈信道对信息传输是不必要的。

喷泉码可以显著地降低反馈信道开销。喷泉码(无速率码)是一种应对删除信道的有效方法。理想的无速率特性主要体现在两个方面：(1)对有限数量的信源块进行编码，可产生无限数量的编码块，因而不需要事先知道信道的删除错误概率，(2)解码所需要块的数目尽可能接近信源块的数目，即可以译码冗余接近0。经典的Reed-Solomon码，冗余为0时可以100%正确译码，但编码输出数量是有限的，不满足喷泉码特性，且其译码复杂度高。喷泉码中关注最多的为LT码，及在其基础上构造的Raptor码。2002年，LUBY[1]提出LT码，根据优化的度分布函数进行随机编码，满足无限输出的特征，在大数据包下仅需要少量的冗余，译码为线性复杂度，是最早出现的实用性喷泉码。采用LT码，当信源块数目为10000，冗余为5%时，成功译码概率为90%。2006年，SHOKROLLAHI[2]在LT码的基础上，利用级联编码提出Raptor码，有更高的译码成功概率。LT码和Raptor码在大数据包下，具有低复杂度、低冗余开销的特点，但随着数据包的减小，冗余比特所占比例急剧上升。2015年，HANZO等人[3]指出LT码和Raptor码在传输短块数据时性能急剧恶化原因在于Tanner图次优结构，提出一种改进的Raptor码(IRaptor)，用于特定码率和包长度的传输。

喷泉码已引起水声通信领域的关注，针对点对点传输、组播传输及多跳传输水声网络性能开展了仿真[4，5]。2007年，CHAN等人[6]将LT码用于水声通信文件传输协议，将1 Mbit文件分块后进行LT码编码传输，分块数目为4000时冗余开销最小为15%。2008年，CASARI等人[7]研究了用于水声通信多播消息传输的基于喷泉码的混合自动重传请求策略，文章用喷泉码的统一性能进行仿真，没有涉及到喷泉码的实现。2012年，ZHOU等人[8]提出一种基于喷泉码的自适应多跳可靠数据传输方法。2014年，CUI等人[9]将基于喷泉码的水声通信传输过程建模成一个统计优化问题，利用信道状态估计优化Raptor码的校验比例，系统性能仿真基于Raptor码译码失效概率公式。2015年，CHITRE等人[10]考虑到水下传播延迟对水声通信文件传输的影响，对比不同的自动重传请求(ARQ)模式下的性能，指出喷泉码和Juggling-like ARQ(J-ARQ)相结合的方法在传输可靠性和信道利用率上的优势。

目前，水声通信中喷泉码的研究主要采用仿真的手段，常用LT码或Raptor码，或者不涉及具体的喷泉码，研究侧重于网络整体性能。陆地无线电通信中的喷泉码多用于大数据量的传输，如视频广播，一个数据包包含10000个数据块，传输速率可在1 Mbps以上。水声通信中喷泉码的选择应充分考虑水声通信系统的以下特点：首先，水声通信带宽窄，通信比特速率低。如中程水声通信距离为5 km速率一般在5 kbps以下。低数据率可应用高复杂度的算法，以提升系统性能。其次，一个数据块大小有限。由于水声信道时变性强、带宽窄，中程通信数据块一般不超过2000 bit。无速率编码过程应减少随机编码的块头信息。再次，一次传输所含数据块数有限。水下设备电量有限，且传输每比特能耗高，每比特能耗为1 J量级，更换一次电池传输10 Mbit左右。因而，水声通信数据块数目较少，一般在1000块以下。

本文给出一种实用的水声通信中喷泉码方案。选择随机线性喷泉码及最佳译码，以提升喷泉码在分块数目较小情况下的性能。传统的最佳译码为整包统一处理，译码延迟大。本文提出一种逐行累增的高斯消去译码方法，将译码过程分散到单块到达时隙中，对单块到达的计算量进行分析，其复杂度为线性复杂度。在实际水声通信平台上进行了验证，分析其纠错性能及处理实时性，采用1000块分组，单块计算时间最大60 ms，在采用最佳译码算法降低冗余开销的同时，满足实时计算条件。

2　水声通信中用于小分块数的喷泉码

随机线性喷泉码(Random Linear Fountain code，RLF)[11，12]是一种基本的喷泉码，最佳译码时所需冗余很小，且冗余块数和数据块数无关，在块数小的情况下有很好的优势。在编码过程中，将一个完整的数据包进行分块，每块含M个比特，共K个数据块，第k数据块中第m个比特记为。第n个编码块中第m个元素记为，则

图1给出了RLF码和LT码的译码失效概率。RLF码生成矩阵分布概率取p =0.5，LT码度优选所用参数取及δ =0.5。可以看出在小分块数时，LT码性能较差。为了使包失效概率在0.001以下，对于的LT码，即使采用ML译码方法，仍需要70%的冗余。RLF码仅需要10个冗余块，所需冗余块数目不随K变化。

图1　LT码和RLF码的性能曲线

水声通信中小数据包的情况较为常见，采用RLF码及其最佳译码方法有优势，但其译码计算复杂度有待降低。目前，喷泉码的最佳译码方法主要有高斯消去法(Gaussian Elimination，GE)[12]和RU(Richardson-Urbanke)法[14]。高斯消去法，将生成矩阵通过行变换转换成单位矩阵，同时对接收比特矩阵进行同样变换恢复出信息比特矩阵。高斯消去法的译码复杂度为。对于稀疏编码的喷泉码，可采用RU译码法，将编码矩阵置换处理得到近似三角矩阵，对稀疏矩阵求逆借鉴了低密度奇偶校验码(LDPC)编码方法[15]。RU法译码复杂度约为。现有的喷泉码最佳译码方法是整包统一处理。从满足译码实时性角度考虑，本文提出一种逐行累增的高斯消去译码方法，不限于稀疏编码，将译码过程分散到单块到达时隙中，对每块到达时的译码计算量进行分析，单步处理计算复杂度为。同时在分步处理中及时删除多余的编码块，总计算量略低于传统的高斯消去法。

3　逐行累增的高斯消去法

3.1 算法步骤

RLF码经典的译码方法为高斯消去法。接收端成功收到N个编码块，对应的编码矩阵和生成矩阵为T和G。如果生成矩阵的秩为K，通过高斯消去法将增广矩阵化简得到行最简形(reduced row echelon form)矩阵。这一化简过程记为

其中I为单位矩阵，0为零矩阵，行最简形矩阵包含了信息矩阵，因而完成了译码过程。

在高斯消去法上改进，每收到一个编码块对生成矩阵进行高斯消去法处理，并根据生成矩阵秩的增加进行编码矩阵处理，生成矩阵秩为K做为译码结束条件。因而，本文提出表1所示的逐行累增高斯消去法(Increment Gaussian Elimination，IGE)。

3.2 计算复杂度的预测方法

首先给出多个二进制随机数的模2加和的概率计算方法。相互独立的K个二进制数，概率分别为。它们模2加和为b，则

表 1　IGE的迭代过程

下面分析逐行累增高斯消去法的计算量大小。一般情况下M≫ K，因而只关心对编码矩阵处理的计算量，即表1中第(3)步的计算量。在生成矩阵秩由j变换到时，对编码矩阵行操作的平均次数记为。在一次迭代中，执行两种行操作：用的各行首变量(lead variables)抵消Gn中对应位置，将新增行的首变量抵消所在列的其它元素。两种操作如式(4)，式(5)所示：

3.3 行操作次数的最大值

行操作次数的单步最大值影响着系统的实时处理能力，下面对最大值进行分析。通过仿真计算，可得出经过行累增迭代后自由变量取1的概率接近0.5，即

因而编码矩阵的行操作次数简化为

逐行累增高斯消去法行操作次数的单步最大值为

图3给出了不同生成矩阵稀疏程度p及不同分块数目K下，IGE算法中最大行操作次数的仿真运行结果(仿真1000个数据包，取平均值)及预测值的对比。从图中可知，式(11)很好地给出了最大行操作次数的预测结果。降低p，IGE算法的计算量不能成比例地减少，但性能有所恶化[8]。因而，在水声通信小分块数传输中，选择p =0.5的RLF码及IGE译码方法。采用所提出的IGE算法，在保证最佳译码性能的同时，单次迭代行操作次数为O(K)，相对于单步处理的GE译码，有效地降低了译码延迟。

4 水声通信系统的应用

水下数据包通信主要用于传输水下图像、温盐深链数据、分层流速，采用纠删除错误码进行分块之间的编码有利于大数据包的传输。在“蛟龙号”载人潜水器水声图像传输[16]中，图像数据包用于传输小波压缩后的512×512像素彩色图像，数据包分为60个数据块，每块2000 bit。由于数据包大小固定且显控计算机参与计算，采用基于Reed-Solomon码的纠删除错误方案，所需译码冗余为0。从2013年应用航段开始，应用Reed-Solomon码有效地纠正了船体噪声、吊缆结构件摩擦、定位声呐等突发干扰源造成的块传输错误。

在水声通信系统中，喷泉码比Reed-Solomon码在计算复杂度、信源大小可变、信道删除概率不确定等方面有明显优势。在图像传输应用中，可进一步利用喷泉码根据图像压缩后信源比特的重要性进行不对等保护编码，优化传输效果[17，18]。为了验证喷泉码最佳译码算法在水声通信中的实时性，将本文提出的IGE算法进行平台实现。采用ADI公司的低功耗定点信号处理器ADSP-BF547做为开发平台，系统时钟为480 MHz，将数据包分块，每块2000 bit，采用RLF编码。在VisualDSP++环境下开发，利用c++语言嵌入式标准模板库ESTL中bitset模板进行比特矢量的紧凑存取及处理，图4给出了一个数据包的分块数取K =100及K =1000的计算时间。对于K =1000，单块的最大计算时间为60 ms，远小于数据块传输时间0.5 s，符合实时处理要求。而传统的GE法在接收到足够的数据块之后才进行处理，对于K =1000情况处理时间在33 s以上，不能满足实时处理需要。

图2　IGE的单次迭代中行操作次数(K=100)

图3　IGE最大行操作次数的蒙特卡洛仿真及预测值对比

图 4 本文算法在BlackFin547上的译码时间

图 5 喷泉码译码前后错误率对比(K为每包的数据块数，N为已发送的数据块数)

图5给出了基于逐行累增高斯消去法的随机线性编码在译码前后错误率，可看出对于恶劣的信道增加少量的冗余可以实现可靠的传输，如：将包分成1000个数据块，在块传输错误率为25%的情况下，仅需要40%的冗余，通过喷泉码纠错可实现99.99%的可靠传输。从图中还可看出，在同样的分块错误率下为达到特定的包正确率，分块数目增加，所需冗余比例降低。

5　结论

针对水声通信中数据包的传输，本文提出一种逐行累增的高斯消去法进行随机线性编码的最佳译码，所需要冗余远小于LT码，给出了计算复杂度的预测式，单块到达时的比特计算次数为O(Mk)。在实时处理平台上进行算法实现，验证了所提出算法的实时性满足系统需求。所提译码算法可用于水下图像、视频片段、传感器数据等大数据量的可靠传输。

参考文献

[1]LUBY M.LT codes[C].Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science，Vancouver，2002:271-282.doi:10.1109/SFCS.2002.1181950.

[2]SHOKROLLAHI A.Raptor codes[J].IEEE Transactions on Information Theory，2006，52(6):2551-2567.doi:10.1109/ TIT.2006.874390.

[3]HANZO L，MAUNDER R，CHEN H，et al.Hybrid-ARQ-aided short fountain codes designed for block-fading channels[J].IEEE Transactions on Vehicular Technology，2015.doi:10.1109/TVT.2015.2388632.

[4]赵旦峰，梁明珅，段晋珏.水声网络中喷泉码的应用研究现状与发展前景[J].系统工程与电子技术，2014，36(9):1838-1843.doi:10.3969/ J.ISSN.1001-506X.2014.09.27.ZHAO Danfeng，LIANG Mingshen，and DUAN Jinjue.Survey of fountain codes in underwater acoustic sensor networks[J].Systems Engineering and Electronics，2014，36(9):1838-1843.doi:10.3969/J.ISSN.1001-506X.2014.09.27.

[5]NICOPOLITIDIS P，PAPADIMITRIOU G I，and POMPORTSIS A S.Adaptive data broadcasting in underwater wireless networks[J].IEEE Journal of Oceanic Engineering，2010，35(3):623-634.doi:10.1109/JOE.2010.2049674.

[6]CHAN C Y M and MOTANI M.An integrated energy efficient data retrieval protocol for underwater delay tolerant networks[C].Proceedings of the OCEANS，Aberdeen，2007:1-6.doi:10.1109/OCEANSE.2007.4302341.

[7]CASARI P，ROSSI M，and ZORZI M.Towards optimal broadcasting policies for HARQ based on fountain codes in underwater networks[C].Proceedings of the 2008 Fifth Annual Conference on Wireless on Demand Network Systems and Services，Garmisch-Partenkirchen，2008:11-19.doi:10.1109/WONS.2008.4459350.

[8]ZHOU Z，MO H，ZHU Y，et al.Fountain code based adaptive multi-hop reliable data transfer for underwater acoustic networks[C].Proceedings of the 2012 IEEE International Conference on Communications，Ottawa，2012:6396-6400，doi:10.1109/ICC.2012.6364846.

[9]CUI Y，QING J，GUAN Q，et al.Stochastically optimized fountain based transmissions over underwater acoustic channels[J].IEEE Transactions on Vehicular Technology，2014，64(4):2108-2112.doi:10.1109/TVT.2013.01958.

[10]CHITRE M and SOH W S.Reliable point-to-point underwater acoustic data transfer:to juggle or not to juggle?[J].IEEE Journal of Oceanic Engineering，2015，40(1):93-103.doi:10.1109/JOE.2014.2311692.

[11]SCHOTSCH B，SCHEPKER H，and VARY P.The performance of short random linear fountain codes under maximum likelihood decoding[C].Proceedings of the 2011 IEEE International Conference on Communications，Kyoto，2011:1-5.doi:10.1109/ICC.2011.5962476.

[12]MACKAY D J C.Fountain codes[J].IEE Proceedings-Communications，2005，152(6):1062-1068.doi:10.1049/IP-COM:20050237.

[13]LIVA G，PAOLINI E，and CHIANI M.Performance versus overhead for fountain codes over Fq[J].IEEE Communications Letters，2010，14(2):178-180.doi:10.1109/ LCOMM.2010.02.092080.

[14]MADGE O G H and MACKAY D J C.Efficient fountain codes for medium blocklengths[OL].http://www.inference.phy.cam.ac.uk/oghm2/files/fountain-draft.pdf.2006，1.

[15]RICHARDSON T J and URBANKE R L.Efficient encoding of low-density parity-check codes[J].IEEE Transactions on Information Theory，2001，47(2):638-656.doi:10.1109/ 18.910579.

[16]朱维庆，朱敏，武岩波，等.载人潜水器“蛟龙”号的水声通信信号处理[J].声学学报，2012，37(6):565-573.doi:10.15949/J.CNKI.0371-0025.2012.06.001.ZHU Weiqing，ZHU Min，WU Yanbo，et al.Signal processing in underwater acoustic communication system for manned deep submersible “Jiaolong”[J].Acta Acustica，2012，37(6):565-573.doi:10.15949/ J.CNKI.0371-0025.2012.06.001.

[17]刘国，于文慧，吴家骥，等.基于系统Raptor码不等差错保护的图像压缩传输[J].电子与信息学报，2013，35(11):2554-2559.doi:10.3724/SP.J.1146.2012.01362.LIU Guo，YU Wenhui，WU Jiaji，et al.Compressed image transmission based on systematic Raptor codes with unequal error protection[J].Journal of Electronics ＆ Information Technology，2013，35(11):2554-2559.doi:10.3724/SP.J.1146.2012.01362.

[18]黄太奇，易本顺，姚渭箐，等.基于规则变量节点度和扩展窗喷泉码的不等差错保护算法[J].电子与信息学报，2015，37(8):1931-1936.doi:10.11999/JEIT141530.HUANG Taiqi，YI Benshun，YAO Weiqing，et al.Novel scheme of unequal error protection based on regularized variable-node and expanding window fountain codes[J].Journal of Electronics ＆ Information Technology，2015，37(8):1931-1936.doi:10.11999/JEIT141530.

武岩波：男，1982年生，副研究员，研究方向为水声通信信号处理.

朱敏：男，1971年生，研究员，研究方向为海洋声学技术.

Maximum Likelihood Decoding of Fountain Codes in Underwater Acoustic Communication

WU YanboZHU Min
①(State Key Laboratory of Acoustics，Institute of Acoustics，Chinese Academy of Sciences，Beijing 100190，China)
②(Ocean Acoustic Technology Center，Institute of Acoustics，Chinese Academy of Sciences，Beijing 100190，China)

Abstract:Considering the characteristics of underwater acoustic communication，random linear fountain codes with maximum likelihood decoding are studied to correct erasure errors in the short packet transmission.In existing maximum likelihood decoding methods，processing begins when all the necessary blocks are available，resulting to the unacceptable decoding delay.An increment Gaussian elimination method is proposed to decrease the decoding delay by utilizing the time-slots of every block.The computation complexity is analyzed based on the principle of the probability distribution of the summation of binary random variables.The real-time ability of the proposed method is verified on the low-cost DSP chip for the underwater acoustic modem.The method is applicable to underwater transmissions of images，and sense data.

Key words:Underwater acoustic communication; Fountain code; Gaussian elimination; Random linear fountain code

基金项目：国家自然科学基金(61471351)，中国科学院声学研究所所长择优基金(Y454101231)

*通信作者：武岩波wuyanbo@mail.ioa.ac.cn

收稿日期：2015-05-13；改回日期：2015-10-30；网络出版：2015-12-04

DOI:10.11999/JEIT150572

中图分类号：TN929.3

文献标识码：A

文章编号：1009-5896(2016)02-0288-06

Foundation Items:The National Natural Science Foundation of China(61471351)，Preferred Foundation of Director of Institute of Acoustics，CAS(Y454101231)