一種用于水聲通信的噴泉碼最大似然譯碼方法

武巖波　　朱　敏(中國科學院聲學研究所聲場聲信息國家重點實驗室　北京　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)