任 鵬,相 征

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

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

任 鵬,相 征

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

圖3 Truncated-BED度分布

BED和Truncated-BED的平均度值的計(jì)算公式為

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

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

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

ρ′(i)獲取方法為

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

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

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

圖4 Moved-RSD度分布

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

3 性能仿真與分析

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

其次,在碼長(zhǎng)k=1 000的條件下,測(cè)試了BED、Truncated-BED、RSD、Moved-RSD、原始的開(kāi)關(guān)度分布和新的開(kāi)關(guān)度分布6種不同的度分布在LT編碼時(shí),譯碼成功率與正確接收編碼包數(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í)會(huì)因?yàn)槿鄙僮銐虻男《戎禂?shù)據(jù)包出現(xiàn)譯碼中斷的情況.與單一的度分布相比,原始的開(kāi)關(guān)度分布和新的開(kāi)關(guān)度分布的性能較好,起始譯碼成功率分別達(dá)到了41%和56%,譯碼成功率上升速度也較快.且在相同的條件下,新的開(kāi)關(guān)度分布的譯碼成功率高于原始的開(kāi)關(guān)度分布約9%～12%.

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

4 結(jié)束語(yǔ)

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

時(shí)間:2014-12-23

國(guó)家自然科學(xué)基金資助項(xiàng)目(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