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

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

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

噴泉碼；短碼長；度值檢測

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

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

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

1 噴泉碼技術(shù)

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

第一個實(shí)用的噴泉碼——LT碼[6]是在2002年由Luby等人提出的。LT碼以其良好的性能和簡單的編譯碼方法受到學(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噴泉碼碼長要達(dá)到104或者更高的量級[7-8]。這使得該編碼方案在某些應(yīng)用場合下使用具有局限性。

1.2 短碼長LT碼

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

2 信道模型假設(shè)

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

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

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

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

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

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

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

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

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

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

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

表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ī)制（見圖2），只允許度1分組數(shù)量合格的度序列進(jìn)入編碼過程，以提高編碼分組參與譯碼的有效性。

4 仿真分析

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

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

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

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

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

5 結(jié)論

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

[1]周輝，鄭海昕，徐定根.空間通信技術(shù)[M].北京：國防工業(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可靠組播解決方案分組長度研究[J].清華大學(xué)學(xué)報，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]雷維嘉，劉慧峰，謝顯中.開關(guān)度分布：一種改進(jìn)的LT數(shù)字噴泉編碼度分布[J].重慶郵電大學(xué)學(xué)報，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-），男，工程師，碩士。