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

武巖波　　朱　敏(中國(guó)科學(xué)院聲學(xué)研究所聲場(chǎng)聲信息國(guó)家重點(diǎn)實(shí)驗(yàn)室　北京　100190)(中國(guó)科學(xué)院聲學(xué)研究所海洋聲學(xué)技術(shù)中心　北京　100190)

?

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

武巖波*朱敏
①(中國(guó)科學(xué)院聲學(xué)研究所聲場(chǎng)聲信息國(guó)家重點(diǎn)實(shí)驗(yàn)室北京100190)
②(中國(guó)科學(xué)院聲學(xué)研究所海洋聲學(xué)技術(shù)中心北京100190)

摘要：針對(duì)水聲通信特點(diǎn)，研究隨機(jī)線性噴泉碼及最大似然譯碼，在分塊數(shù)較小的包傳輸中糾正刪除錯(cuò)誤。傳統(tǒng)的最大似然譯碼為整包統(tǒng)一處理，譯碼延遲大。該文提出一種逐行累增的高斯消去方法，將譯碼過(guò)程劃分到各塊到達(dá)時(shí)隙中執(zhí)行，利用二進(jìn)制分布求和的概率公式對(duì)單塊到達(dá)所需計(jì)算量進(jìn)行分析。在實(shí)際水聲通信處理平臺(tái)上進(jìn)行了驗(yàn)證，滿足實(shí)時(shí)計(jì)算需求，可用于水下圖像、傳感器數(shù)據(jù)等的傳輸。

關(guān)鍵詞：水聲通信；噴泉碼；高斯消去法；隨機(jī)線性噴泉碼

1　引言

水聲通信信道時(shí)變性強(qiáng)，信道沖擊響應(yīng)、環(huán)境背景噪聲和干擾是非平穩(wěn)過(guò)程，造成信道容量是時(shí)變的，數(shù)據(jù)塊傳輸錯(cuò)誤或丟失的比例較高。目前，實(shí)際水聲通信系統(tǒng)中多采用選擇性重傳的反饋機(jī)制。水聲傳播速度小且水聲通信為半雙工方式，因而反饋信道造成信道利用率低。從信息論來(lái)看，反饋信道對(duì)信息傳輸是不必要的。

噴泉碼可以顯著地降低反饋信道開(kāi)銷(xiāo)。噴泉碼(無(wú)速率碼)是一種應(yīng)對(duì)刪除信道的有效方法。理想的無(wú)速率特性主要體現(xiàn)在兩個(gè)方面：(1)對(duì)有限數(shù)量的信源塊進(jìn)行編碼，可產(chǎn)生無(wú)限數(shù)量的編碼塊，因而不需要事先知道信道的刪除錯(cuò)誤概率，(2)解碼所需要塊的數(shù)目盡可能接近信源塊的數(shù)目，即可以譯碼冗余接近0。經(jīng)典的Reed-Solomon碼，冗余為0時(shí)可以100%正確譯碼，但編碼輸出數(shù)量是有限的，不滿足噴泉碼特性，且其譯碼復(fù)雜度高。噴泉碼中關(guān)注最多的為L(zhǎng)T碼，及在其基礎(chǔ)上構(gòu)造的Raptor碼。2002年，LUBY[1]提出LT碼，根據(jù)優(yōu)化的度分布函數(shù)進(jìn)行隨機(jī)編碼，滿足無(wú)限輸出的特征，在大數(shù)據(jù)包下僅需要少量的冗余，譯碼為線性復(fù)雜度，是最早出現(xiàn)的實(shí)用性噴泉碼。采用LT碼，當(dāng)信源塊數(shù)目為10000，冗余為5%時(shí)，成功譯碼概率為90%。2006年，SHOKROLLAHI[2]在LT碼的基礎(chǔ)上，利用級(jí)聯(lián)編碼提出Raptor碼，有更高的譯碼成功概率。LT碼和Raptor碼在大數(shù)據(jù)包下，具有低復(fù)雜度、低冗余開(kāi)銷(xiāo)的特點(diǎn)，但隨著數(shù)據(jù)包的減小，冗余比特所占比例急劇上升。2015年，HANZO等人[3]指出LT碼和Raptor碼在傳輸短塊數(shù)據(jù)時(shí)性能急劇惡化原因在于Tanner圖次優(yōu)結(jié)構(gòu)，提出一種改進(jìn)的Raptor碼(IRaptor)，用于特定碼率和包長(zhǎng)度的傳輸。

噴泉碼已引起水聲通信領(lǐng)域的關(guān)注，針對(duì)點(diǎn)對(duì)點(diǎn)傳輸、組播傳輸及多跳傳輸水聲網(wǎng)絡(luò)性能開(kāi)展了仿真[4，5]。2007年，CHAN等人[6]將LT碼用于水聲通信文件傳輸協(xié)議，將1 Mbit文件分塊后進(jìn)行LT碼編碼傳輸，分塊數(shù)目為4000時(shí)冗余開(kāi)銷(xiāo)最小為15%。2008年，CASARI等人[7]研究了用于水聲通信多播消息傳輸?shù)幕趪娙a的混合自動(dòng)重傳請(qǐng)求策略，文章用噴泉碼的統(tǒng)一性能進(jìn)行仿真，沒(méi)有涉及到噴泉碼的實(shí)現(xiàn)。2012年，ZHOU等人[8]提出一種基于噴泉碼的自適應(yīng)多跳可靠數(shù)據(jù)傳輸方法。2014年，CUI等人[9]將基于噴泉碼的水聲通信傳輸過(guò)程建模成一個(gè)統(tǒng)計(jì)優(yōu)化問(wèn)題，利用信道狀態(tài)估計(jì)優(yōu)化Raptor碼的校驗(yàn)比例，系統(tǒng)性能仿真基于Raptor碼譯碼失效概率公式。2015年，CHITRE等人[10]考慮到水下傳播延遲對(duì)水聲通信文件傳輸?shù)挠绊?，?duì)比不同的自動(dòng)重傳請(qǐng)求(ARQ)模式下的性能，指出噴泉碼和Juggling-like ARQ(J-ARQ)相結(jié)合的方法在傳輸可靠性和信道利用率上的優(yōu)勢(shì)。

目前，水聲通信中噴泉碼的研究主要采用仿真的手段，常用LT碼或Raptor碼，或者不涉及具體的噴泉碼，研究側(cè)重于網(wǎng)絡(luò)整體性能。陸地?zé)o線電通信中的噴泉碼多用于大數(shù)據(jù)量的傳輸，如視頻廣播，一個(gè)數(shù)據(jù)包包含10000個(gè)數(shù)據(jù)塊，傳輸速率可在1 Mbps以上。水聲通信中噴泉碼的選擇應(yīng)充分考慮水聲通信系統(tǒng)的以下特點(diǎn)：首先，水聲通信帶寬窄，通信比特速率低。如中程水聲通信距離為5 km速率一般在5 kbps以下。低數(shù)據(jù)率可應(yīng)用高復(fù)雜度的算法，以提升系統(tǒng)性能。其次，一個(gè)數(shù)據(jù)塊大小有限。由于水聲信道時(shí)變性強(qiáng)、帶寬窄，中程通信數(shù)據(jù)塊一般不超過(guò)2000 bit。無(wú)速率編碼過(guò)程應(yīng)減少隨機(jī)編碼的塊頭信息。再次，一次傳輸所含數(shù)據(jù)塊數(shù)有限。水下設(shè)備電量有限，且傳輸每比特能耗高，每比特能耗為1 J量級(jí)，更換一次電池傳輸10 Mbit左右。因而，水聲通信數(shù)據(jù)塊數(shù)目較少，一般在1000塊以下。

本文給出一種實(shí)用的水聲通信中噴泉碼方案。選擇隨機(jī)線性噴泉碼及最佳譯碼，以提升噴泉碼在分塊數(shù)目較小情況下的性能。傳統(tǒng)的最佳譯碼為整包統(tǒng)一處理，譯碼延遲大。本文提出一種逐行累增的高斯消去譯碼方法，將譯碼過(guò)程分散到單塊到達(dá)時(shí)隙中，對(duì)單塊到達(dá)的計(jì)算量進(jìn)行分析，其復(fù)雜度為線性復(fù)雜度。在實(shí)際水聲通信平臺(tái)上進(jìn)行了驗(yàn)證，分析其糾錯(cuò)性能及處理實(shí)時(shí)性，采用1000塊分組，單塊計(jì)算時(shí)間最大60 ms，在采用最佳譯碼算法降低冗余開(kāi)銷(xiāo)的同時(shí)，滿足實(shí)時(shí)計(jì)算條件。

2　水聲通信中用于小分塊數(shù)的噴泉碼

隨機(jī)線性噴泉碼(Random Linear Fountain code，RLF)[11，12]是一種基本的噴泉碼，最佳譯碼時(shí)所需冗余很小，且冗余塊數(shù)和數(shù)據(jù)塊數(shù)無(wú)關(guān)，在塊數(shù)小的情況下有很好的優(yōu)勢(shì)。在編碼過(guò)程中，將一個(gè)完整的數(shù)據(jù)包進(jìn)行分塊，每塊含M個(gè)比特，共K個(gè)數(shù)據(jù)塊，第k數(shù)據(jù)塊中第m個(gè)比特記為。第n個(gè)編碼塊中第m個(gè)元素記為，則

圖1給出了RLF碼和LT碼的譯碼失效概率。RLF碼生成矩陣分布概率取p =0.5，LT碼度優(yōu)選所用參數(shù)取及δ =0.5。可以看出在小分塊數(shù)時(shí)，LT碼性能較差。為了使包失效概率在0.001以下，對(duì)于的LT碼，即使采用ML譯碼方法，仍需要70%的冗余。RLF碼僅需要10個(gè)冗余塊，所需冗余塊數(shù)目不隨K變化。

圖1　LT碼和RLF碼的性能曲線

水聲通信中小數(shù)據(jù)包的情況較為常見(jiàn)，采用RLF碼及其最佳譯碼方法有優(yōu)勢(shì)，但其譯碼計(jì)算復(fù)雜度有待降低。目前，噴泉碼的最佳譯碼方法主要有高斯消去法(Gaussian Elimination，GE)[12]和RU(Richardson-Urbanke)法[14]。高斯消去法，將生成矩陣通過(guò)行變換轉(zhuǎn)換成單位矩陣，同時(shí)對(duì)接收比特矩陣進(jìn)行同樣變換恢復(fù)出信息比特矩陣。高斯消去法的譯碼復(fù)雜度為。對(duì)于稀疏編碼的噴泉碼，可采用RU譯碼法，將編碼矩陣置換處理得到近似三角矩陣，對(duì)稀疏矩陣求逆借鑒了低密度奇偶校驗(yàn)碼(LDPC)編碼方法[15]。RU法譯碼復(fù)雜度約為?，F(xiàn)有的噴泉碼最佳譯碼方法是整包統(tǒng)一處理。從滿足譯碼實(shí)時(shí)性角度考慮，本文提出一種逐行累增的高斯消去譯碼方法，不限于稀疏編碼，將譯碼過(guò)程分散到單塊到達(dá)時(shí)隙中，對(duì)每塊到達(dá)時(shí)的譯碼計(jì)算量進(jìn)行分析，單步處理計(jì)算復(fù)雜度為。同時(shí)在分步處理中及時(shí)刪除多余的編碼塊，總計(jì)算量略低于傳統(tǒng)的高斯消去法。

3　逐行累增的高斯消去法

3.1 算法步驟

RLF碼經(jīng)典的譯碼方法為高斯消去法。接收端成功收到N個(gè)編碼塊，對(duì)應(yīng)的編碼矩陣和生成矩陣為T(mén)和G。如果生成矩陣的秩為K，通過(guò)高斯消去法將增廣矩陣化簡(jiǎn)得到行最簡(jiǎn)形(reduced row echelon form)矩陣。這一化簡(jiǎn)過(guò)程記為

其中I為單位矩陣，0為零矩陣，行最簡(jiǎn)形矩陣包含了信息矩陣，因而完成了譯碼過(guò)程。

在高斯消去法上改進(jìn)，每收到一個(gè)編碼塊對(duì)生成矩陣進(jìn)行高斯消去法處理，并根據(jù)生成矩陣秩的增加進(jìn)行編碼矩陣處理，生成矩陣秩為K做為譯碼結(jié)束條件。因而，本文提出表1所示的逐行累增高斯消去法(Increment Gaussian Elimination，IGE)。

3.2 計(jì)算復(fù)雜度的預(yù)測(cè)方法

首先給出多個(gè)二進(jìn)制隨機(jī)數(shù)的模2加和的概率計(jì)算方法。相互獨(dú)立的K個(gè)二進(jìn)制數(shù)，概率分別為。它們模2加和為b，則

表 1　IGE的迭代過(guò)程

下面分析逐行累增高斯消去法的計(jì)算量大小。一般情況下M? K，因而只關(guān)心對(duì)編碼矩陣處理的計(jì)算量，即表1中第(3)步的計(jì)算量。在生成矩陣秩由j變換到時(shí)，對(duì)編碼矩陣行操作的平均次數(shù)記為。在一次迭代中，執(zhí)行兩種行操作：用的各行首變量(lead variables)抵消Gn中對(duì)應(yīng)位置，將新增行的首變量抵消所在列的其它元素。兩種操作如式(4)，式(5)所示：

3.3 行操作次數(shù)的最大值

行操作次數(shù)的單步最大值影響著系統(tǒng)的實(shí)時(shí)處理能力，下面對(duì)最大值進(jìn)行分析。通過(guò)仿真計(jì)算，可得出經(jīng)過(guò)行累增迭代后自由變量取1的概率接近0.5，即

因而編碼矩陣的行操作次數(shù)簡(jiǎn)化為

逐行累增高斯消去法行操作次數(shù)的單步最大值為

圖3給出了不同生成矩陣稀疏程度p及不同分塊數(shù)目K下，IGE算法中最大行操作次數(shù)的仿真運(yùn)行結(jié)果(仿真1000個(gè)數(shù)據(jù)包，取平均值)及預(yù)測(cè)值的對(duì)比。從圖中可知，式(11)很好地給出了最大行操作次數(shù)的預(yù)測(cè)結(jié)果。降低p，IGE算法的計(jì)算量不能成比例地減少，但性能有所惡化[8]。因而，在水聲通信小分塊數(shù)傳輸中，選擇p =0.5的RLF碼及IGE譯碼方法。采用所提出的IGE算法，在保證最佳譯碼性能的同時(shí)，單次迭代行操作次數(shù)為O(K)，相對(duì)于單步處理的GE譯碼，有效地降低了譯碼延遲。

4 水聲通信系統(tǒng)的應(yīng)用

水下數(shù)據(jù)包通信主要用于傳輸水下圖像、溫鹽深鏈數(shù)據(jù)、分層流速，采用糾刪除錯(cuò)誤碼進(jìn)行分塊之間的編碼有利于大數(shù)據(jù)包的傳輸。在“蛟龍?zhí)枴陛d人潛水器水聲圖像傳輸[16]中，圖像數(shù)據(jù)包用于傳輸小波壓縮后的512×512像素彩色圖像，數(shù)據(jù)包分為60個(gè)數(shù)據(jù)塊，每塊2000 bit。由于數(shù)據(jù)包大小固定且顯控計(jì)算機(jī)參與計(jì)算，采用基于Reed-Solomon碼的糾刪除錯(cuò)誤方案，所需譯碼冗余為0。從2013年應(yīng)用航段開(kāi)始，應(yīng)用Reed-Solomon碼有效地糾正了船體噪聲、吊纜結(jié)構(gòu)件摩擦、定位聲吶等突發(fā)干擾源造成的塊傳輸錯(cuò)誤。

在水聲通信系統(tǒng)中，噴泉碼比Reed-Solomon碼在計(jì)算復(fù)雜度、信源大小可變、信道刪除概率不確定等方面有明顯優(yōu)勢(shì)。在圖像傳輸應(yīng)用中，可進(jìn)一步利用噴泉碼根據(jù)圖像壓縮后信源比特的重要性進(jìn)行不對(duì)等保護(hù)編碼，優(yōu)化傳輸效果[17，18]。為了驗(yàn)證噴泉碼最佳譯碼算法在水聲通信中的實(shí)時(shí)性，將本文提出的IGE算法進(jìn)行平臺(tái)實(shí)現(xiàn)。采用ADI公司的低功耗定點(diǎn)信號(hào)處理器ADSP-BF547做為開(kāi)發(fā)平臺(tái)，系統(tǒng)時(shí)鐘為480 MHz，將數(shù)據(jù)包分塊，每塊2000 bit，采用RLF編碼。在VisualDSP++環(huán)境下開(kāi)發(fā)，利用c++語(yǔ)言嵌入式標(biāo)準(zhǔn)模板庫(kù)ESTL中bitset模板進(jìn)行比特矢量的緊湊存取及處理，圖4給出了一個(gè)數(shù)據(jù)包的分塊數(shù)取K =100及K =1000的計(jì)算時(shí)間。對(duì)于K =1000，單塊的最大計(jì)算時(shí)間為60 ms，遠(yuǎn)小于數(shù)據(jù)塊傳輸時(shí)間0.5 s，符合實(shí)時(shí)處理要求。而傳統(tǒng)的GE法在接收到足夠的數(shù)據(jù)塊之后才進(jìn)行處理，對(duì)于K =1000情況處理時(shí)間在33 s以上，不能滿足實(shí)時(shí)處理需要。

圖2　IGE的單次迭代中行操作次數(shù)(K=100)

圖3　IGE最大行操作次數(shù)的蒙特卡洛仿真及預(yù)測(cè)值對(duì)比

圖 4 本文算法在BlackFin547上的譯碼時(shí)間

圖 5 噴泉碼譯碼前后錯(cuò)誤率對(duì)比(K為每包的數(shù)據(jù)塊數(shù)，N為已發(fā)送的數(shù)據(jù)塊數(shù))

圖5給出了基于逐行累增高斯消去法的隨機(jī)線性編碼在譯碼前后錯(cuò)誤率，可看出對(duì)于惡劣的信道增加少量的冗余可以實(shí)現(xiàn)可靠的傳輸，如：將包分成1000個(gè)數(shù)據(jù)塊，在塊傳輸錯(cuò)誤率為25%的情況下，僅需要40%的冗余，通過(guò)噴泉碼糾錯(cuò)可實(shí)現(xiàn)99.99%的可靠傳輸。從圖中還可看出，在同樣的分塊錯(cuò)誤率下為達(dá)到特定的包正確率，分塊數(shù)目增加，所需冗余比例降低。

5　結(jié)論

針對(duì)水聲通信中數(shù)據(jù)包的傳輸，本文提出一種逐行累增的高斯消去法進(jìn)行隨機(jī)線性編碼的最佳譯碼，所需要冗余遠(yuǎn)小于LT碼，給出了計(jì)算復(fù)雜度的預(yù)測(cè)式，單塊到達(dá)時(shí)的比特計(jì)算次數(shù)為O(Mk)。在實(shí)時(shí)處理平臺(tái)上進(jìn)行算法實(shí)現(xiàn)，驗(yàn)證了所提出算法的實(shí)時(shí)性滿足系統(tǒng)需求。所提譯碼算法可用于水下圖像、視頻片段、傳感器數(shù)據(jù)等大數(shù)據(jù)量的可靠傳輸。

參考文獻(xiàn)

[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]趙旦峰，梁明珅，段晉玨.水聲網(wǎng)絡(luò)中噴泉碼的應(yīng)用研究現(xiàn)狀與發(fā)展前景[J].系統(tǒng)工程與電子技術(shù)，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]朱維慶，朱敏，武巖波，等.載人潛水器“蛟龍”號(hào)的水聲通信信號(hào)處理[J].聲學(xué)學(xué)報(bào)，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]劉國(guó)，于文慧，吳家驥，等.基于系統(tǒng)Raptor碼不等差錯(cuò)保護(hù)的圖像壓縮傳輸[J].電子與信息學(xué)報(bào)，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]黃太奇，易本順，姚渭箐，等.基于規(guī)則變量節(jié)點(diǎn)度和擴(kuò)展窗噴泉碼的不等差錯(cuò)保護(hù)算法[J].電子與信息學(xué)報(bào)，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年生，副研究員，研究方向?yàn)樗曂ㄐ判盘?hào)處理.

朱敏：男，1971年生，研究員，研究方向?yàn)楹Ｑ舐晫W(xué)技術(shù).

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

基金項(xiàng)目：國(guó)家自然科學(xué)基金(61471351)，中國(guó)科學(xué)院聲學(xué)研究所所長(zhǎng)擇優(yōu)基金(Y454101231)

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

收稿日期：2015-05-13；改回日期：2015-10-30；網(wǎng)絡(luò)出版：2015-12-04

DOI:10.11999/JEIT150572

中圖分類(lèi)號(hào)：TN929.3

文獻(xiàn)標(biāo)識(shí)碼：A

文章編號(hào)：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)