分組級(jí)短碼長(zhǎng)LT噴泉碼的工程應(yīng)用

分組級(jí)短碼長(zhǎng)LT噴泉碼的工程應(yīng)用

張 濤1，王澤林2
（1.91655部隊(duì)，北京100036；2.96219部隊(duì)，廣東清遠(yuǎn)511533）

針對(duì)LT噴泉碼在準(zhǔn)單向鏈路、高差錯(cuò)、鏈路惡劣易中斷的信道環(huán)境應(yīng)用時(shí)出現(xiàn)的運(yùn)算量大、譯碼時(shí)延長(zhǎng)、編碼效率較低等問(wèn)題，文章提出使用基于數(shù)據(jù)分塊的分組級(jí)短碼長(zhǎng)噴泉碼方案。其思想是將短碼長(zhǎng)LT碼方案和分組級(jí)LT碼方案結(jié)合起來(lái)，并且在數(shù)據(jù)子塊的度序列生成過(guò)程中加入度值檢測(cè)機(jī)制。實(shí)驗(yàn)仿真結(jié)果表明：與已提出的LT碼方案相比，該方案能夠有效地降低譯碼開(kāi)銷(xiāo)、計(jì)算代價(jià)和譯碼時(shí)延，提高系統(tǒng)的最大傳輸效率。

噴泉碼；短碼長(zhǎng)；度值檢測(cè)

近年來(lái)，隨著我國(guó)航天和海洋技術(shù)的發(fā)展，深空通信、水聲通信受到廣泛關(guān)注。這2種通信場(chǎng)景面臨相似的挑戰(zhàn)[1]：傳輸時(shí)延大；前向與反向鏈路速率不對(duì)稱；誤碼率和丟包率大。為克服這些問(wèn)題，實(shí)現(xiàn)可靠傳輸，須要采用相應(yīng)的傳輸編碼技術(shù)。

文獻(xiàn)[2]提出了利用噴泉碼方案來(lái)解決深空通信面臨的上述問(wèn)題，文獻(xiàn)[3]提到了采用糾錯(cuò)碼的無(wú)記憶高斯信道可以等效為刪除信道。文獻(xiàn)[4]在忽略分組額外開(kāi)銷(xiāo)和鏈路誤比特率為10-6的實(shí)驗(yàn)條件下采用噴泉碼方案時(shí)，選取較短的分組來(lái)傳輸數(shù)據(jù)文件，以獲得較高的成功概率。

本文針對(duì)上述惡劣通信環(huán)境下LT噴泉碼碼的工程應(yīng)用問(wèn)題展開(kāi)研究，提出了使用基于數(shù)據(jù)分塊的分組級(jí)短碼長(zhǎng)LT碼方案。與傳統(tǒng)LT碼方案相比，在額外冗余信息（包頭、包號(hào)、校驗(yàn)碼等）不能忽略的情況下，系統(tǒng)的傳輸性能得到了較大的提高。

1 噴泉碼技術(shù)

數(shù)字噴泉概念由M.Luby等人在1998年提出[5]。噴泉碼的編譯碼過(guò)程可概括為：由k個(gè)信息分組生成無(wú)限多的編碼分組，而用戶只要接收到其中任意k(1+ε)個(gè)編碼分組，即可通過(guò)譯碼以高概率成功恢復(fù)全部原始數(shù)據(jù)分組，其中ε是開(kāi)銷(xiāo)。

第一個(gè)實(shí)用的噴泉碼——LT碼[6]是在2002年由Luby等人提出的。LT碼以其良好的性能和簡(jiǎn)單的編譯碼方法受到學(xué)術(shù)界和工業(yè)界的廣泛關(guān)注。

1.1 Robust經(jīng)典算法

LT碼噴泉碼的編譯碼性能直接由度分布函數(shù)決定，LT碼Robust度分布函數(shù)[6]μ(d)定義為：

式（1）中：ρ(d)為理想孤子分布，是度數(shù)值為d的概率，且

τ(d）為補(bǔ)充函數(shù)，表達(dá)式為

為獲得良好的性能，經(jīng)典LT噴泉碼碼長(zhǎng)要達(dá)到104或者更高的量級(jí)[7-8]。這使得該編碼方案在某些應(yīng)用場(chǎng)合下使用具有局限性。

1.2 短碼長(zhǎng)LT碼

為進(jìn)一步提高LT碼的實(shí)用性，文獻(xiàn)[7，9-11]對(duì)短碼長(zhǎng)LT碼進(jìn)行了研究。對(duì)短碼長(zhǎng)的分析，文獻(xiàn)[9-10]算法目前只有理論上的意義；文獻(xiàn)[11]提供了最優(yōu)化方法來(lái)計(jì)算短碼長(zhǎng)度分布，但局限于碼長(zhǎng)極端（10以內(nèi)）的情況[7]。文獻(xiàn)[7]提出的一種編碼度分布函數(shù)的改進(jìn)設(shè)計(jì)方法，得到了103量級(jí)的短碼長(zhǎng)噴泉碼，擴(kuò)展了噴泉碼的應(yīng)用。如果將103量級(jí)的短碼長(zhǎng)應(yīng)用在鏈路誤比特率為10-3環(huán)境中使用，基于信息分組數(shù)量K的度序列隨機(jī)生成方案，亦會(huì)產(chǎn)生相對(duì)較大的度值以保證良好的覆蓋率，這樣含有冗余信息的編碼分組的丟包概率較大，因而文獻(xiàn)[7]設(shè)計(jì)的10-3量級(jí)的短碼長(zhǎng)在通信質(zhì)量惡劣的環(huán)境中使用效果欠佳。

2 信道模型假設(shè)

為使問(wèn)題分析起來(lái)簡(jiǎn)單，假設(shè)隨機(jī)錯(cuò)誤是導(dǎo)致分組“刪除”的唯一原因，不考慮其他因素[4]。設(shè)鏈路誤比特率為e，則每個(gè)編碼分組的丟失率q可以表示為：

N為待傳輸文件長(zhǎng)度，d為信息包長(zhǎng)，L為編碼分組的包長(zhǎng)（包括信息分組，也包括包頭、包號(hào)、校驗(yàn)碼等冗余信息），K=ceil(N/D)為原始信息分組數(shù)量。圖1為不同信道質(zhì)量（誤碼率）下對(duì)應(yīng)的丟包率。

圖1 不同信道質(zhì)量下的丟包率Fig.1 Package loss rate of different channel quality

利用噴泉碼的無(wú)碼率特性，使發(fā)送端以適應(yīng)優(yōu)質(zhì)信道的參數(shù)條件來(lái)進(jìn)行噴泉碼的發(fā)送。在信道質(zhì)量良好下，此方案可收到較好的傳輸效果。然而實(shí)際信道卻多是時(shí)變的，甚至有時(shí)信道的質(zhì)量相當(dāng)惡劣，如圖1所示，在誤比特率為10-3時(shí)，以優(yōu)質(zhì)信道方案（一般數(shù)據(jù)包較長(zhǎng)）進(jìn)行傳送數(shù)據(jù)，惡劣的信道質(zhì)量會(huì)導(dǎo)致編碼分組的丟包率較高，那么系統(tǒng)為完成譯碼而不得不接收更多的編碼分組來(lái)彌補(bǔ)丟包率帶來(lái)的“包丟失”，這樣系統(tǒng)的傳輸效率就會(huì)非常低下。另外，如果采用較短信息分組來(lái)切割原始數(shù)據(jù)文件，那么會(huì)得到較大的信息分組數(shù)量K，而按照原有LT碼方案進(jìn)行編碼，那么會(huì)得到冗余信息較多的編碼分組。同樣，較長(zhǎng)的編碼分組在惡劣信道下的丟包率也會(huì)很高。

3 基于數(shù)據(jù)分塊的分組級(jí)短碼長(zhǎng)LT碼解決方案

本文放寬了對(duì)度分布函數(shù)的優(yōu)化要求，采用基于數(shù)據(jù)分塊的分組級(jí)短碼長(zhǎng)LT碼設(shè)計(jì)，方案如下。

首先，根據(jù)實(shí)際信道傳輸統(tǒng)計(jì)數(shù)據(jù)將信息分組長(zhǎng)度劃為24 Byte，將原始數(shù)據(jù)切割成子數(shù)據(jù)塊長(zhǎng)度在1 024～2 048 Byte之間（亦可根據(jù)信道狀態(tài)進(jìn)行相應(yīng)長(zhǎng)度劃分）；然后，對(duì)每個(gè)子塊進(jìn)行短碼長(zhǎng)LT碼編碼生成編碼分組；接著，這些編碼分組通過(guò)無(wú)線信道傳輸后，被接收端接收并參與譯碼；最后，將譯碼成功的子數(shù)據(jù)塊進(jìn)行拼接，完成編譯碼過(guò)程。對(duì)數(shù)據(jù)子塊進(jìn)行短碼長(zhǎng)度序列產(chǎn)生的流程圖見(jiàn)圖2。

圖2 子塊數(shù)據(jù)短碼長(zhǎng)度序列產(chǎn)生流程圖Fig.2 Flow chart of short code degree sequence generation with sub block

Robust度分布函數(shù)是一種通用的設(shè)計(jì)，可以改變其中的參數(shù)來(lái)適應(yīng)不同的通信需求，本文采用的Robust度分布函數(shù)的參數(shù)為c=0.093 1，δ=0.601和式（2）中K=24。目的是為了取消大度值對(duì)信息分組的覆蓋，以降低迭代次數(shù)，減小運(yùn)算量。圖3是Robust度分布函數(shù)在參數(shù)c=0.093 1，δ=0.601和K=24時(shí)產(chǎn)生子塊數(shù)據(jù)短碼長(zhǎng)序列的度概率分布圖。

圖3 分組級(jí)短碼長(zhǎng)LT碼方案采用的度概率分布Fig.3 Probability distribution of pack level short LT block codes

研究短碼長(zhǎng)度序列時(shí)發(fā)現(xiàn)：度函數(shù)序列的產(chǎn)生是遵循度分布函數(shù)規(guī)律的一個(gè)隨機(jī)過(guò)程，度序列中度1的比重及其在譯碼迭代過(guò)程中是否能夠持續(xù)產(chǎn)生，這直接決定著LT譯碼能夠成功。無(wú)論是實(shí)用的Robust度分布或者其他改進(jìn)的度分布函數(shù)，如開(kāi)關(guān)度分布[12]產(chǎn)生的度序列，隨機(jī)不確定因素使得在理論上性能優(yōu)良的度分布函數(shù)也無(wú)法確保每次生成的度序列中度1所占的比重能達(dá)到相應(yīng)的概率要求。表1為Robust和二進(jìn)制指數(shù)度分布函數(shù)在采用不同的隨機(jī)種子分別重復(fù)104次的度序列產(chǎn)生實(shí)驗(yàn)中度1概率不合格的概率。按這些度序列生成的編碼分組通過(guò)刪除信道后，被送到接收端來(lái)參與譯碼的失敗率較高。Robust度分布函數(shù)特別是在短碼長(zhǎng)的應(yīng)用中，度1的產(chǎn)生概率很低（低于10%，很多情況下，甚至無(wú)度1產(chǎn)生），而且還要通過(guò)信道的刪除作用。因此，基于Robust度分布函數(shù)的短碼長(zhǎng)在惡劣信道中的有效性欠佳。

表1 不同的度函數(shù)產(chǎn)生序列中不合格度1的比重信息Tab.1 Speeific gravity information of sequence unqualified degree 1 with different degree function

鑒于度1分組的重要性，本文在不改變度分布函數(shù)的基礎(chǔ)上，加入度1檢驗(yàn)機(jī)制（見(jiàn)圖2），只允許度1分組數(shù)量合格的度序列進(jìn)入編碼過(guò)程，以提高編碼分組參與譯碼的有效性。

4 仿真分析

為便于本文方案和原始LT碼方案的對(duì)比，引入?yún)?shù)：①開(kāi)銷(xiāo)ε[13]；②計(jì)算代價(jià)（Dmean-1）×D×N，區(qū)別于文獻(xiàn)[13]，計(jì)算代價(jià)表達(dá)了信息分組字節(jié)長(zhǎng)度D、開(kāi)銷(xiāo)ε和節(jié)點(diǎn)平均度Dmean之間的一個(gè)權(quán)衡，是異或運(yùn)算進(jìn)行的操作數(shù)；③傳輸效率η[14]；④完成編譯碼所耗時(shí)間t。

圖4是采用帶檢測(cè)機(jī)制的本文方案和已提出的LT碼方案在開(kāi)銷(xiāo)、傳輸效率、計(jì)算代價(jià)和編譯碼時(shí)間的比較。原始數(shù)據(jù)長(zhǎng)度為1 024～9 216 Byte，鏈路誤比特率為10-3。經(jīng)典LT碼的Robust參數(shù)為c=0.03，δ=0.5，這個(gè)參數(shù)設(shè)置和文獻(xiàn)[2-3]相對(duì)應(yīng)。仿真平臺(tái)是WindowsXP操作系統(tǒng)，CPU為3.0 GHz，內(nèi)存2 GB，仿真工具M(jìn)atlab7.8.0，以不同的噴泉碼方案發(fā)送不同長(zhǎng)度的源數(shù)據(jù)，分別重復(fù)1 000次取均值。

圖4 本文提出的分組級(jí)短碼長(zhǎng)方案和經(jīng)典LT碼的性能對(duì)比Fig.4 Performance comparison of proposed short LT code and classical LT code

從圖4中可以看出，隨著原始數(shù)據(jù)長(zhǎng)度的增長(zhǎng)，已提出的LT碼方案的計(jì)算代價(jià)和編譯碼時(shí)間的增長(zhǎng)非常大，而帶檢測(cè)機(jī)制本文方案的計(jì)算代價(jià)和編譯碼時(shí)間增加相對(duì)較慢；無(wú)論是開(kāi)銷(xiāo)和傳輸效率帶檢測(cè)的本文方案均優(yōu)于已提出的LT碼方案，而不帶檢測(cè)機(jī)制方案的性能介于兩者之間。值得注意的是，在源數(shù)據(jù)長(zhǎng)度較小，或信息分組數(shù)量不大時(shí)，隨機(jī)度序列具有較高的不合格率，接收端不得不接收更多的分組來(lái)保證譯碼成功，因而導(dǎo)致系統(tǒng)的譯碼開(kāi)銷(xiāo)和傳輸效率的波動(dòng)較大。這說(shuō)明，檢測(cè)機(jī)制的引入能夠提高短碼長(zhǎng)LT碼編碼分組的有效性。

仿真結(jié)果說(shuō)明帶檢測(cè)機(jī)制的基于數(shù)據(jù)分塊的分組級(jí)短碼長(zhǎng)LT碼是可行而且實(shí)用的。借助Robust度分布函數(shù)的通用性，可為工程應(yīng)用提供較為方便但不是最優(yōu)的度分布函數(shù)[13]。原因是實(shí)際工程中原始數(shù)據(jù)不可能被分為無(wú)限個(gè)信息分組；LT碼進(jìn)行一次的編譯碼行為也不能與精準(zhǔn)的數(shù)學(xué)理論分析相匹配；即使具有優(yōu)化結(jié)構(gòu)的度分布產(chǎn)生的編碼分組經(jīng)過(guò)信道而丟失部分分組后，會(huì)導(dǎo)致優(yōu)化的編碼分組構(gòu)成被破壞。

5 結(jié)論

本文針對(duì)LT噴泉碼實(shí)際工程應(yīng)用，對(duì)基于數(shù)據(jù)分塊的分組級(jí)短碼長(zhǎng)LT噴泉碼進(jìn)行了研究，仿真表明，在打破了信息分組數(shù)量K的束縛后，能夠在誤比特率10-3的信道條件下，使得開(kāi)銷(xiāo)、最大傳輸效率、計(jì)算代價(jià)和編譯碼時(shí)間4個(gè)方面的性能均優(yōu)于現(xiàn)有LT碼方案。本文的數(shù)據(jù)分塊和信息分組的長(zhǎng)度是大量實(shí)驗(yàn)所得的經(jīng)驗(yàn)數(shù)據(jù)。下一步的研究將著眼于如何改進(jìn)數(shù)據(jù)分塊和信息分組的長(zhǎng)度切割，以使得基于數(shù)據(jù)分塊的分組級(jí)短碼長(zhǎng)噴泉碼的性能趨向最優(yōu)化。

[1]周輝，鄭海昕，徐定根.空間通信技術(shù)[M].北京：國(guó)防工業(yè)出版社，2010：12-13. ZHOU HUI，ZHENG HAIXIN，XU DINGGEN.Space communication technology[M].Beijing：Defense Industry Press，2010：12-13.（in Chinese）

[2]李暉，姚文頂，張乃通.深空通信中的噴泉編譯碼技術(shù)[J].電訊技術(shù)，2008，48（4）：8-12. LI HUI，YAO WENDING，ZHANG NAITONG.Fountain codes in deep space communication[J].Telecommunication Engineering，2008，48（4）：8-12.（in Chinese）

[3]臧求實(shí).噴泉碼技術(shù)的研究[D].南京：南京郵電大學(xué)，2011. ZANG QIUSHI.Research on fountain codes technology [D].Nanjing University of Post and Telecommunication，2011.（in Chinese）

[4]姜博，曹志剛，晏堅(jiān).PLFEC可靠組播解決方案分組長(zhǎng)度研究[J].清華大學(xué)學(xué)報(bào)，2008，48（4）：567-570. JIANG BO，CAO ZHIGANG，YAN JIAN.Packet lengths of PLFEC-based reliable multicast solutions[J].Journal of Tsinghua University，2008，48（4）：567-570.（in Chinese）

[5]BYERS J W，LUBY M，MITZENMACHER M，et al.A Digital fountain approach to reliable distribution of bulk data[C]//Proceedings ofACM Sigcomm’98.1998：56-67.

[6]LUBY M.LT codes[C]//IEEE Symposium on Foundations of Computer Science.2002，16（19）：271-282.

[7]朱宏杰.噴泉碼編譯碼技術(shù)與應(yīng)用研究[D].北京：清華大學(xué)，2008. ZHU HONGJIE.Research on codec technology and applications of fountain codes[D].Tsinghua University，2008.（in Chinese）

[8]MACKAY D J C.Fountain code[J].IEEE Proceedings on Communications，2005，152（6）：1062-1068.

[9]KARP R，LUBY M，SHOKROLLAHI A.Finite length analysis of LT codes[C]//IEEE International Symposium on Information Theory.2004：37-39.

[10]MANEVA E，SHOKROLLAHI A.New model for rigorous analysis of LT-codes[C]//IEEE International Symposium on Information Theory.2006：2677-2679.

[11]HYYTIA E，TIRRONEN T V J.Optimal degree distribution for LT codes with small message length[C]//International Conference on Computer Communications.2007：2576-2580.

[12]雷維嘉，劉慧峰，謝顯中.開(kāi)關(guān)度分布：一種改進(jìn)的LT數(shù)字噴泉編碼度分布[J].重慶郵電大學(xué)學(xué)報(bào)，2012，24（1）：34-38. LEI WEIJIA，LIU HUIFENG，XIE XIANZHONG. Switch degree distribution：an improved degree distribution for LT digital fountain code[J].Journal of Chongqing University of Posts and Telecommunications，2012，24（1）：34-38.（in Chinese）

[13]CHEN CHIHMING，CHEN YINGPING，SHEN TZU CHING.Optimizing degree distributions in LT codes by using the multiobjective evolutionary algorithm based on decomposition[C]//Proceedings of Evolutionary Computation.2010：1-8.

[14]ROY BLAKE.現(xiàn)代通信系統(tǒng)[M].2版.北京：電子工業(yè)出版社，2003：321-322. ROY BLAKE.Electronic communication systems[M]. Beijing：Publishing House of Electronics Industry，2003：321-322.（in Chinese）

Practical Research on Short Block Length Packet-Level LT Codes

ZHANG Tao1,WANG Zelin2
（1.The 91655thUnit of PLA,Beijing 100036,China;2.The 96219thUnit of PLA,Qingyuan Guangdong 511533,China）

In quasi unidirectional links,poor channel environment and high error rate situations,LT fountain codes often cause a large amount of computing,extended decoding time,low coding efficiency and other problems.In this paper,the small code length packet-level coding scheme was proposed,which combined the short block length coding and packetlevel LT codes,and applying degree detection mechanism in the process of sequence data generated in the sub-blocks. The simulation results showed that compared with the conventional LT codes,the proposed scheme could effectively re?duce the cost of decoding,computing costs and decoding delay and increase the maximum transmission efficiency of the system.

LT codes;short blocke length;degree detection

TN919.8

A

1673-1522（2015）05-0433-04

10.7682/j.issn.1673-1522.2015.05.007

2015-07-05；

2015-08-15

張 濤（1977-），男，工程師，碩士。