LT碼中一種新的開關(guān)度分布

任 鵬,相 征

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

LT碼中一種新的開關(guān)度分布

任 鵬,相 征

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

其中,α為開關(guān)點的值.

2 一種新的開關(guān)度分布

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

圖3 Truncated-BED度分布

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

當(dāng)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)新的開關(guān)度分布.Truncated-BED增大了小度值的可譯碼集出現(xiàn)概率,Moved-RSD增大了大度值的可譯碼集出現(xiàn)概率.結(jié)合這兩個改進的度分布函數(shù),建立一種新的開關(guān)度分布函數(shù)θ(·),即

圖4 Moved-RSD度分布

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

3 性能仿真與分析

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

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

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

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

4 結(jié)束語

噴泉碼在多個前沿領(lǐng)域的應(yīng)用使得它成為業(yè)界關(guān)注的重點,而度分布是噴泉碼的核心研究內(nèi)容之一.筆者對BED和RSD分別進行了改進,提出了Truncated-BED和Moved-RSD.同時將這兩類度分布結(jié)合起來,建立了一種新的開關(guān)度分布.通過仿真對比,新的開關(guān)度分布具有高的起始譯碼成功率,且隨著譯碼的進行,譯碼成功率上升很快.在同等條件下,譯碼成功率高于原始的開關(guān)度分布約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]雷維嘉,劉慧鋒,謝顯中.開關(guān)度分布:一種改進的LT數(shù)字噴泉編碼度分布[J].重慶郵電大學(xué)學(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(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">網(wǎng)絡(luò)出版時間:

時間:2014-12-23

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

任 鵬(1984-),男,西安電子科技大學(xué)博士研究生,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