任 鵬,相 征

(西安電子科技大學通信工程學院,陜西西安 710071)

LT碼中一種新的開關度分布

任 鵬,相 征

(西安電子科技大學通信工程學院,陜西西安 710071)

針對LT噴泉碼,為進一步增加小度值的可譯碼集出現(xiàn)概率,限制二進制指數(shù)度分布的最大度值,提出了截短二進制指數(shù)度分布;為進一步增加大度值的可譯碼集出現(xiàn)概率,改變魯棒孤子度分布的分布值,提出了滑動的魯棒孤子度分布.結合這兩種度分布,建立了一種新的開關度分布.仿真結果表明,新的開關度分布進行LT編碼時的初始譯碼成功率達到了56%,整體譯碼成功率高于原始的開關度分布約9%～12%.

數(shù)字噴泉碼;二進制指數(shù)度分布;魯棒孤波度分布;開關度分布

目前在實際應用中的主要數(shù)字噴泉碼有LT碼[4]和Raptor碼[5],Raptor碼是對LT碼的改進.關于數(shù)字噴泉碼,它的設計主要包括度分布的設計、編碼方法的設計和譯碼方法設計.其中度分布設計方法與數(shù)字噴泉碼的性能直接相關,決定著譯碼成功率、譯碼代價、編譯碼復雜度等,設計噴泉碼的關鍵在于構造合適的度分布函數(shù).

度分布設計的目標是盡量使少數(shù)編碼符號有較大的度數(shù),以保證編碼符號對所有輸入符號的覆蓋;同時使大多數(shù)的編碼符號有較小的度數(shù),以保證譯碼的正常運行.根據(jù)設計目標,Luby等提出了全一度分布,但由于其覆蓋所有輸入符號所需的編碼符號非常多,因此無法在實際中得到應用.理想孤子度分布要求在每一次譯碼迭代循環(huán)中至少有1個度為1的編碼包,但在實際中此分布的工作效率很低,因此很少被使用.基于理想孤子度分布,Luby等提出了魯棒孤子度分布(Robust Soliton Distribution,RSD)[4],該分布引入了兩個變量,以保證在每次譯碼時度為1的編碼包的數(shù)目不是1個.雖然RSD優(yōu)于理想孤子度分布,但采用RSD進行LT編碼所產生的編碼數(shù)據(jù)包的度值較大,在譯碼時可能會由于缺少足夠的度值較小的編碼數(shù)據(jù)包而導致譯碼中斷.文獻[6]提出的二進制指數(shù)分布(Binary Exponential Distribution,BED),其可以確保生成足夠的度值較小的編碼數(shù)據(jù)包,但由于大部分編碼數(shù)據(jù)包的度值較小,因此,編碼數(shù)據(jù)包可能沒有覆蓋原始數(shù)據(jù)的所有信息,會導致原始數(shù)據(jù)遺漏.此外,還有很多學者在RSD基礎上提出了很多新的度分布[7-10],這些度分布都取得了較好的性能,但由于單一度分布函數(shù)的局限性,這些度分布都很難在編碼包的度值大小方面取得平衡.因此,文獻[11]提出將BED和RSD結合起來,建立一種新的分段式度分布函數(shù),即開關度分布函數(shù).隨后,文獻[12]又提出一種聯(lián)合度分布函數(shù),其將理想孤子度分布、BED和RSD進行組合.與單一的度分布相比,這些方法具有更良好的性能.考慮到文獻[12]的方法具有很高的復雜度,且事先必須規(guī)定多個額外的參量值,因此,文中重點針對開關度分布進行改進和性能提升.強調的是,筆者所提方法同時可以擴展到聯(lián)合度分布的改進中.

為進一步提高噴泉碼的性能,筆者首先對BED和RSD這兩種度分布函數(shù)深入探索,掌握它們各自存在的優(yōu)缺點.其次,利用前一步的分析,建立了一種新的開關度分布函數(shù).最后,對所提的開關度分布函數(shù)進行性能驗證.

1 度分布函數(shù)研究

度分布函數(shù)是影響噴泉碼性能的一個關鍵因素.由于RSD的建立是基于理想孤子度分布,所以這里分別對理想孤子度分布、RSD和BED進行分析.基于此,給出已有的開關度分布.

(1)理想孤子度分布的表達式為

其中,k表示輸入符號個數(shù),即編碼數(shù)據(jù)包數(shù)量.ρ(1),…,ρ(k)分別對應著度數(shù)從1到k的概率.理想孤子度分布在譯碼開始時,產生一個度為1的編碼符號來恢復輸入符號.然后通過迭代后,又產生一個度為1的編碼符號來恢復輸入符號,其整個譯碼過程中可譯碼集大小R都為1,因此,其具有最優(yōu)的平均度數(shù).但由于度選取的隨機性,譯碼過程無法保證可譯集的穩(wěn)定性,可能會導致譯碼失敗.理想孤子度分布具有較低的譯碼性能,在實際系統(tǒng)中并不可用,但它為魯棒孤子度分布提供了理論基礎.

(2)魯棒孤子度分布.在RSD中,引入了兩個參量c和δ,其中,c為常數(shù)且0＜c＜1;δ為譯碼失敗概率的上界,一般取值為0.7,以保證在每一個譯碼迭代時度為1的可譯碼集大小為R=c ln(kδ)k1/2,而不是原來的1個.RSD函數(shù)μ(·)由理想孤子度分布函數(shù)ρ(·)和輔助函數(shù)τ(·)構成,即

李霸崖笑著說：“德公公是說，來歷不明之人，才親近不得。”但心里還是提高了警惕，掂了掂手中釣竿，“這玩意怎么這般重？”說著就盯著釣竿沉甸甸的握把發(fā)愣，顯然是起了疑心。義父說過，小心駛得萬年船，還是小心為妙。

圖1給出了不同參量c下RSD函數(shù)中度i與概率μ之間的關系.可以看出,在不同的c下,度i計算出來的概率μ有明顯差異,但其對應的整體曲線包絡走向都保持一致,呈“雙峰”狀.雖然RSD使得譯碼過程更加趨于穩(wěn)定,然而其產生的度值較小的可譯碼集較小,譯碼過程可能產生中斷.

(3)二進制指數(shù)度分布.針對RSD的不足,提出一種BED的函數(shù)φ(·),即

其中,d表示可譯碼集的度值.BED函數(shù)的概率分布如圖2所示.相比RSD,BED增加了度值較小的可譯碼集出現(xiàn)的概率.但是由于大部分可譯碼集的度值較小,可能沒有覆蓋全部的原始數(shù)據(jù)信息,造成原始數(shù)據(jù)遺漏.

基于BED和RSD,開關度分布ω(·)可表示為

圖1 RSD函數(shù)的概率分布

圖2 BED函數(shù)的概率分布

其中,α為開關點的值.

2 一種新的開關度分布

如前所述,開關度分布由BED和RSD兩種度分布構成,其性能直接與這兩種度分布的性能相關.根據(jù)BED的概率分布圖可以看出,當度值超出某一門限(例如10)時,度值對應的概率雖然很低,但還是會影響小度值可譯碼集出現(xiàn)的概率.為了進一步降低平均度值,提高小度值的可譯碼集出現(xiàn)的概率,文中提出一種新的BED分布,即截斷BED分布(Truncated-BED).根據(jù)RSD的概率分布圖可以看出,第1個“尖峰”位于度值為2處,第2個“尖峰”則隨著參量c的不同而變化.為了進一步提高大度值的可譯碼集出現(xiàn)的概率,文中提出一種新的RSD分布,即滑動RSD分布(Moved-RSD),來抑制第1個“尖峰”的概率,增加大度值對應的概率.最終結合Truncated-BED和Moved-RSD,建立了一種新的開關度分布,來提高數(shù)字噴泉碼的性能.

(1)截斷BED.由式(4)可知,BED的度值區(qū)間為[1,k],則其度值上限為k.引入?yún)⒘縫,0＜p＜1,則定義Truncated-BED的度值區(qū)間為[1,pk],其度值上限即為pk.Truncated-BED的函數(shù)ζ(·)可表示為

其中,D為最大度值.Truncated-BED進一步增加了小度值的可譯碼集出現(xiàn)的概率.圖3給出了當k=1 000時,不同p值下所對應的Truncated-BED度分布函數(shù)的概率曲線.

圖3 Truncated-BED度分布

BED和Truncated-BED的平均度值的計算公式為

當k-1＞pk+2,即p＜1-3/k時,有X-Y＞0,即X＞Y.所以,Truncated-BED的平均度值小于BED的平均度值.

(2)滑動RSD.在RSD中,第1個“尖峰”點是由理想孤波分布ρ(i)決定的,根據(jù)式(1)可知,其處于度值

為2的位置.為了削減該“尖峰”,提升大度值可譯碼集出現(xiàn)的概率,則Moved-RSD的函數(shù)η(·)可表示為

ρ′(i)獲取方法為

其中,n為第1峰值點,b為第1峰值系數(shù),且0＜b≤1.

與RSD相比,Moved-RSD的第1個“尖峰”點可根據(jù)需要后移到任意度值點.圖4給出了n=6,b=0.7時,Moved-RSD函數(shù)的概率曲線.

(3)新的開關度分布.Truncated-BED增大了小度值的可譯碼集出現(xiàn)概率,Moved-RSD增大了大度值的可譯碼集出現(xiàn)概率.結合這兩個改進的度分布函數(shù),建立一種新的開關度分布函數(shù)θ(·),即

圖4 Moved-RSD度分布

其中,參量α直接決定著編碼器發(fā)送編碼數(shù)據(jù)包的數(shù)目.在進行噴泉編碼時,前αk個噴泉數(shù)據(jù)包服從Truncated-BED,保證小度值的可譯碼集數(shù)目足夠大;后面的噴泉編碼數(shù)據(jù)包服從Moved-RSD,保證大度值的可譯碼集數(shù)目足夠大,以此進一步降低冗余信息的傳輸.

3 性能仿真與分析

首先,測試了在譯碼器成功譯碼時,α的取值與編碼器發(fā)送的編碼數(shù)據(jù)包數(shù)量之間的關系,如圖5所示.從圖5可以看出,當編碼器原始數(shù)據(jù)包數(shù)量k分別取500、1 000和2000時,原始開關度分布與新的開關度分布都在α=0.1時達到編碼數(shù)據(jù)包數(shù)的最小值.此外,在譯碼端成功譯碼時,新的開關度分布所需要的編碼數(shù)據(jù)包數(shù)量少于原始的開關度分布,即譯碼代價更低.

其次,在碼長k=1 000的條件下,測試了BED、Truncated-BED、RSD、Moved-RSD、原始的開關度分布和新的開關度分布6種不同的度分布在LT編碼時,譯碼成功率與正確接收編碼包數(shù)量之間的關系.其中,令Truncated-BED中p=0.01,RSD和Moved-RSD中c=0.2,δ=0.7,n=6,b=0.7.圖6給出了仿真結果.

從圖6可以看出,由于Truncated-BED的平均度值小于BED的,因此,Truncated-BED的起始譯碼成功率較高,但譯碼成功率上升最慢.由于Moved-RSD的度值1概率高于RSD的,并且提高了大度值的概率,因此,Moved-RSD的起始譯碼成功率高于RSD的,但有時會因為缺少足夠的小度值數(shù)據(jù)包出現(xiàn)譯碼中斷的情況.與單一的度分布相比,原始的開關度分布和新的開關度分布的性能較好,起始譯碼成功率分別達到了41%和56%,譯碼成功率上升速度也較快.且在相同的條件下,新的開關度分布的譯碼成功率高于原始的開關度分布約9%～12%.

圖5 不同k值下譯碼成功接收編碼數(shù)據(jù)包數(shù)量與α的關系圖

4 結束語

噴泉碼在多個前沿領域的應用使得它成為業(yè)界關注的重點,而度分布是噴泉碼的核心研究內容之一.筆者對BED和RSD分別進行了改進,提出了Truncated-BED和Moved-RSD.同時將這兩類度分布結合起來,建立了一種新的開關度分布.通過仿真對比,新的開關度分布具有高的起始譯碼成功率,且隨著譯碼的進行,譯碼成功率上升很快.在同等條件下,譯碼成功率高于原始的開關度分布約9%～12%.

圖6 不同度分布下各自的譯碼性能

[1]Byers J W,Luby M,Mitzenmacher M,et al.A Digital Fountain Approach to Reliable Distribution of Bulk Data[C]// Computer Communication Review:28.New York:ACM,1998:56-67.

[2]Byers J W,Luby M,Mitzenmacher M,et al.A Digital Fountain Approach to Asynchronous Reliable Multicast[J]. IEEE Journal on Selected Areas in Communications,2002,20(8):1528-1540.

[3]Zare S,Rahbar A G.Congestion Control in IPTV over PON Using Digital Fountain forward Error Correction[J]. Journal of Network and Computer Applications,2014,37(1):240-252.

[4]Luby M.LT Codes[C]//Proceedings of 43rd Annual IEEE Symposium on Foundations of Computer Science.Los Alamitos:IEEE Computer Society,2002:271-280.

[5]Shokrollahi A.Raptor Codes[J].IEEE Transactions on Information Theory,2006,52(6):2551-2567.

[6]Al Agha K,Kadi N,Stojmenovic I.Fountain Code with XOR of Encoded Packets for Broadcasting and Source Independent Backbone in Multi-hop Networks Using Network Coding[C]//IEEE Vehicular Technology Conference. Piscataway:IEEE,2009:5073564.

[7]Li L,Zhao J X.LT Codes with a New Degree Distribution[C]//Porceedings of the 2nd International Conference on Multimedia Information Networking and Security.Piscataway:IEEE Computer Society,2010:531-535.

[8]Hussain I,Xiao M,Rasmussen L K.Design of LT Codes with Equal and Unequal Erasure Protection over Binary Erasure Channels[J].IEEE Communications Letters,2013,17(2):261-264.

[9]Zhu Z L,Liu S,Zhang J W,et al.Performance Analysis of LT Codes with Different Degree Distribution[C]// Proceedings of the Fifth International Workshop on Chaos-fractals Theories and Applications.Washington:IEEE Computer Society,2012:142-146.

[10]Yen K K,Liao Y C,Chen C L,et al.Modified Robust Soliton Distribution(MRSD)with Improved Ripple Size for LT Codes[J].IEEE Communications Letters,2013,17(5):976-979.

[11]雷維嘉,劉慧鋒,謝顯中.開關度分布:一種改進的LT數(shù)字噴泉編碼度分布[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(Natural Science Edition),2012, 24(1):34-38.

[12]Zhang M,Lei W J,Xie X Z.Combined Degree Distribution:a Simple Method to Design the Degree Distribution of Fountain Codes[C]//Proceedings of IEEE Third International Conference on Information Science and Technology. Piscataway:IEEE,2013:1089-1092.

(編輯:齊淑娟)

New switch degree distribution for the LT code

REN Peng,XIANG Zheng
(School of Telecommunication Engineering,Xidian Univ.,Xi’an 710071,China)

Truncated-binary exponential distribution is proposed for improving the occurrence of the decoding set,and Moved-robust soliton distribution is simultaneously put forward for increasing the occurrence of the decoding set.Combining the above two distributions,a new switch distribution is constructed in this paper. Simulation results show that the proposed method can reach 56%of initial decoding success,and that the total decoding success rate is higher than that by the original method by 9%～12%.

digital fountain code;binary exponential distribution;robust soliton distribution;switch distribution

TN919.3

A

1001-2400(2015)05-0043-05

2014-05-05< class="emphasis_bold">網絡出版時間:

時間:2014-12-23

國家自然科學基金資助項目(61072102)

任 鵬(1984-),男,西安電子科技大學博士研究生,E-mail:pren@stu.xidian.edu.cn.

http://www.cnki.net/kcms/detail/61.1076.TN.20141223.0946.008.html

10.3969/j.issn.1001-2400.2015.05.008