分組級短碼長LT噴泉碼的工程應用

分組級短碼長LT噴泉碼的工程應用

張 濤1，王澤林2
（1.91655部隊，北京100036；2.96219部隊，廣東清遠511533）

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

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

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

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

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

1 噴泉碼技術

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

第一個實用的噴泉碼——LT碼[6]是在2002年由Luby等人提出的。LT碼以其良好的性能和簡單的編譯碼方法受到學術界和工業界的廣泛關注。

1.1 Robust經典算法

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

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

τ(d）為補充函數，表達式為

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

1.2 短碼長LT碼

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

2 信道模型假設

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

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

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

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

3 基于數據分塊的分組級短碼長LT碼解決方案

本文放寬了對度分布函數的優化要求，采用基于數據分塊的分組級短碼長LT碼設計，方案如下。

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

圖2 子塊數據短碼長度序列產生流程圖Fig.2 Flow chart of short code degree sequence generation with sub block

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

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

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

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

鑒于度1分組的重要性，本文在不改變度分布函數的基礎上，加入度1檢驗機制（見圖2），只允許度1分組數量合格的度序列進入編碼過程，以提高編碼分組參與譯碼的有效性。

4 仿真分析

為便于本文方案和原始LT碼方案的對比，引入參數：①開銷ε[13]；②計算代價（Dmean-1）×D×N，區別于文獻[13]，計算代價表達了信息分組字節長度D、開銷ε和節點平均度Dmean之間的一個權衡，是異或運算進行的操作數；③傳輸效率η[14]；④完成編譯碼所耗時間t。

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

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

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

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

5 結論

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

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

[2]李暉，姚文頂，張乃通.深空通信中的噴泉編譯碼技術[J].電訊技術，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]臧求實.噴泉碼技術的研究[D].南京：南京郵電大學，2011. ZANG QIUSHI.Research on fountain codes technology [D].Nanjing University of Post and Telecommunication，2011.（in Chinese）

[4]姜博，曹志剛，晏堅.PLFEC可靠組播解決方案分組長度研究[J].清華大學學報，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]朱宏杰.噴泉碼編譯碼技術與應用研究[D].北京：清華大學，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]雷維嘉，劉慧峰，謝顯中.開關度分布：一種改進的LT數字噴泉編碼度分布[J].重慶郵電大學學報，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.現代通信系統[M].2版.北京：電子工業出版社，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-），男，工程師，碩士。