基于規則變量節點度LT碼的協作傳輸

祝開艷, 王洪玉, 孫文珠, 宋維波

(1. 大連理工大學電子信息與電氣工程學部, 遼寧 大連 116024;

2. 大連海洋大學信息工程學院, 遼寧 大連 116023;

3. 山東理工大學計算機科學與技術學院, 山東 淄博255049)

?

基于規則變量節點度LT碼的協作傳輸

祝開艷1,2, 王洪玉1, 孫文珠3, 宋維波2

(1. 大連理工大學電子信息與電氣工程學部, 遼寧 大連 116024;

2. 大連海洋大學信息工程學院, 遼寧 大連 116023;

3. 山東理工大學計算機科學與技術學院, 山東 淄博255049)

摘要：規則變量節點度Luby變換(Luby transform, LT)碼能夠改善傳統LT碼編碼過程中隨機選取鄰居節點方式導致的差錯平臺現象。提出一種新的實現規則變量節點度LT的編碼方法,利用數組的賦值和清空操作來實現信息符號度值規則化,降低了現有方法的編碼復雜度,并利用對度分布的修正來改善解碼瀑布區;將該編碼方法應用到協作通信系統中,并分析了誤符號率性能。實驗結果表明,此方法能節省系統編解碼時間,有效降低誤符號率差錯平臺,減少成功解碼所需的平均傳輸開銷。

關鍵詞：協作通信; 噴泉碼; 規則變量節點度Luby變換碼; 差錯平臺; 度分布

0引言

噴泉碼又稱為無碼率碼,信源根據信息符號(又稱輸入符號或變量節點),可以源源不斷地編碼出無窮多個編碼符號(又稱輸出符號或校驗節點),解碼端只要接收到足夠多的編碼符號就能成功還原信息符號[1]。與固定碼率編碼方法相比,噴泉碼的無碼率特性使得噴泉碼更能適應時變信道。因此,噴泉碼非常適合應用到具有多條傳輸鏈路的協作通信系統中。近幾年不斷有學者將數字噴泉碼應用到無線協作通信網絡中[2-4]。

2002年Luby提出了第1種可以實用的噴泉碼——Luby變換(Luby transform, LT)碼,并給出了理想孤波分布(ideal soliton distribution, ISD)和魯棒孤波分布(robust soliton distribution, RSD)2種度分布[5]。隨著研究的深入,對數字噴泉碼的研究主要集中在編譯碼算法、度數分布函數、碼長設計、網絡容量等方面[6-8],而且隨著工程類實際應用的推廣,近年來更加集中于數字噴泉碼的應用研究[9-11]。

在大多數數字噴泉碼的編碼過程中,對信息符號的選取均為隨機選取。文獻[12-14]首次提出了規則變量節點度分布LT碼(regular variable-node degree LT codes,RLT)的概念和編碼方法[12-14],基本思想是在編碼端使得信息符號參與編碼的次數相同,即度值規則化。RLT碼被分別應用于刪除信道和噪聲信道中,顯著降低了傳統LT碼的差錯平臺,但該RLT碼編碼方法需要維護一個信息符號度值查找表,編碼過程中需要對該表進行排序和查找操作,這在一定程度上增加了編碼的復雜度,且復雜度隨著信息符號數增大而快速增加;此外,該RLT編碼方法會導致解碼瀑布區域(雪崩區域)延后,相比于傳統LT碼增加了成功解碼所需的傳輸開銷。

針對上述問題,本文提出一種新的RLT碼編碼方法,省去了對信息符號度值查找表的排序、查找和更新過程,降低了編碼復雜度,并將其應用于協作通信系統。與現有方法相比,本文方法能節省系統編解碼時間,有效降低誤符號率差錯平臺的同時不會增加信源平均傳輸次數。

1LT碼

LT碼可由2個參數(k,q(x))簡單表示,k為信息符號的數目,q(x)為集合Nk={1,2,…,k}上的離散概率分布,稱為編碼符號度分布(degree distribution,DD)。LT碼編碼過程首先根據度分布q(x)隨機產生一個度值d(d稱為編碼符號的度),然后從k個信息符號中選取d個信息符號進行異或來產生編碼符號,參與編碼的信息符號稱為編碼符號的鄰居節點(neighbor node,NN)。

LT碼中度分布分為節點度分布和邊度分布,前文中度分布q(x)指編碼符號節點度分布。編碼符號節點度分布q(x)和信息符號節點度分布v(x)為

(1)

編碼符號邊度分布ω(x)與信息符號邊度分布λ(x)定義為

(2)

式中，qi,vi,ωi,λi分別表示各節點度值和邊度值為i的概率。

邊度分布與節點度分布之間的關系為

(3)

定義α和β分別為信息符號節點平均度和編碼符號節點平均度,其值為

(4)

設信息符號數目為k,接收端成功譯碼需要接收到的編碼符號數為Nd,定義譯碼開銷為ε=Nd/k,則α和β有如下關系:

(5)

(6)

2RLT碼

2.1編碼方法描述

在傳統LT碼的編碼過程中,每個編碼符號的鄰居節點都是從信息符號中隨機選取的,這種隨機選取的方式會使得某些信息符號參與編碼的次數很少或未參與編碼的情況,從而導致了傳統LT碼的差錯平臺現象(erasure-floor)[12-14]。文獻[12-14]在編碼端引入一個信息符號度值表來記錄編碼過程中每個信息符號參與編碼的次數,即信息符號的度值。每次編碼之前對信息符號度值表進行排序;每次編碼時在度值符號表中查找度值最小的信息符號進行編碼;每次編碼結束后,對信息符號度值表進行更新,以便下次編碼使用。這種編碼方式,在編碼端能夠確保信息符號參與編碼的次數相同,即度值相同,因此也稱為規則變量節點度LT碼。這種編碼方式能降低譯碼的差錯平臺,但是增加了編碼的復雜度,且信息符號個數越大,編碼過程越復雜;此外,采用RSD分布的規則變量節點度LT碼應用在刪除信道時,會導致解碼瀑布區域(雪崩區域)延后,相比于傳統LT碼增加了成功解碼所需的傳輸開銷。

本文給出一種新的RLT碼編碼方法,該方法在編碼端通過對3個數組的賦值和清空操作來實現信息符號度值規則化,不需要記錄信息符號的度值,省去了對信息符號度值查找表的排序、查找和更新過程,從而降低了編碼復雜度。表1給出了該方法的具體實現過程。其中數組c_set中元素表示待選信息符號序號,數組h_set中元素表示已參與當前編碼的信息符號序號,temp_set數組中元素為臨時符號序號。

2.2度分布修正

編碼符號節點度分布q(x)是決定LT碼性能的關鍵因素。文獻[5]中設計了ISD分布,用ρ(i)表示ISD分布中編碼符號度值為i的概率,ρ(·)定義為

(7)

表1　規則變量節點度LT codes編碼方法

(8)

通過將τ(·)和ρ(·)疊加,并進行歸一化,得到RSD分布。用μ(·)表示RSD分布中編碼符號度值為i的概率,RSD分布表達式為

(9)

在編碼符號節點度分布的設計中,較大的度值是為了使所有的信息符號都能夠參與編碼,而較小的度值是為了加快解碼的開始和維持解碼過程的連續性。解碼瀑布區域主要由度分布中較小度值的概率決定。由于RLT碼的編碼方式保證了所有的信息符號都能夠參與編碼且參與編碼的次數幾乎相等,因此可以通過增加度分布中較小度值的概率來使解碼瀑布區域提前。本文以最常見的RSD分布為例,通過對RSD分布的修正來提高較小度值在度分布中所占的比重。由于度值為1和2的概率對解碼瀑布區域起非常關鍵的作用,本文考慮增加RSD分布中度值為1和2的概率。本文通過對式(8)中的τ(1)和τ(2)進行加權來增加RSD分布中度值為1和2概率,引入參數θ1和θ2,得到加權后的函數τ′(x):

(10)

將加權后的函數τ′(x)代入式 (9)得到修正后的RSD分布。文獻[16]討論了θ2與θ1之間的關系,通過多次實驗得到兩者之間的近似關系:θ2=2θ1;通過改變θ1的值,可以有效的改變規則變量節點度LT碼解碼瀑布區域的開始點;11≤θ1≤16時,解碼瀑布區域開始點對應的傳輸開銷值最小。

3基于RLT碼的協作傳輸

圖1　三端協作系統模型

下面分別對采用傳統LT碼和采用RLT碼的三端協作通信系統的誤符號率進行分析。設需要傳輸的數據包個數為k,信源發送符號總數目為Ns,中繼發送符號總數目為Nr,目的端實際接收到的符號數目為Nd,則有

(11)

為簡化分析,假設中繼接收到k個編碼包就能成功解碼,且不考慮中繼解碼和編碼造成的時延(因為數字噴泉碼采用信息累積方式解碼,中繼造成的時延主要會造成接收端解碼的時延,而對接收端解碼的成功率和誤符號率影響不大),可得到Ns與Nr之間的關系為

(12)

根據式(11)和式(12)可得Nd與Ns之間的關系為

(13)

3.1基于傳統LT碼的協作傳輸誤符號率分析

信源和中繼編碼端都采用傳統LT碼時,目的端接收到的信息符號的度分布服從泊松分布[16],其平均度為α=εβ=βNd/k。當編碼長度k→∞時,信息符號節點度分布v(x)表示如下:

(14)

編碼符號邊度分布函數ω(x)和信息符號的邊度分布函數λ(x)可根據式(3)和式(14)求出。將ω(x)和λ(x)帶入式(9)可求得k→∞時基于LT碼的協作傳輸誤符號率。

(15)

3.2基于RLT碼的協作傳輸誤符號率分析

信源和中繼編碼端都采用RLT碼時,目的端接收到的信息符號的度分布不再服從泊松分布,需要重新分析。設整個傳輸過程中系統的丟包數目為Ne,則

(16)

RLT碼在編碼過程中使得編碼端所有的信息符號度相等。當信道丟包率為0時,接收端接收到的編碼符號中信息符號度和發送端相同。信息符號的平均度為α,由于度值為正整數,因此每個信息符號的度為|α|或|α|-1,信息符號的度分布為

(17)

式中，h=|α|,vh-1和vh可根據式(18)計算:

(18)

當信道丟包率不為0時,由于規則變量節點度LT碼各個編碼符號之間存在一定的關聯性,接收端信息符號的度分布不再服從式(17),接收端信息符號度分布可由定理1得出。

定理 1設信源發送符號數目為Ns,中繼發送符號數目為Nr,信道丟包數目為Ne,接收端信息符號節點度分布為

(19)

式中

(20)

(21)

推廣到更一般的情況,即編碼端信息符號節點度分布如式(17)所示時,將式(21)推廣即可得式(19)。

證畢

根據定理1得到的接收端信息符號節點度分布后,再利用式(3)求出對應的信息符號邊度分布λ(x),代入式(9)即可求出基于RLT的協作傳輸誤符號率。

圖2　基于不同編碼方法的協作傳輸方案的誤符號率理論分析比較

4仿真結果及分析

本節分別從編解碼時間,誤符號率和目的端譯碼所需信源平均傳輸次數3個方面在k取有限值的條件下將本文方法(MRLT)與文獻[16]中方法(RLT)以及傳統LT碼進行比較。度分布采用RSD分布,c=0.03,δ=0.5。

4.1編解碼時間比較

傳統LT碼編碼復雜度只要由編碼符號的異或運算次數決定,即由編碼符號平均節點度決定。文獻[16]中的RLT和傳統LT碼均采用RSD分布,而本文采用的MRLT編碼方法對RSD度分布進行了修正,增加了小度值編碼符號的概率,因此本文采用的MRLT編碼符號的平均度最小。另一方面,文獻[16]中RLT編碼過程中還需對信息符號度值表進行排序、查找和更新操作,在一定程度上增加了編碼復雜度。本文編碼方法省去了對信息符號度值表的排序和查找操作,只需對3個數組進行賦值和讀取操作,因此與文獻[16]中RLT相比降低了一定的復雜度。與傳統的LT碼相比,本文編碼方法多了對3個數組的操作,因此復雜度稍高。表2比較了不同信息符號長度k時上述3種編碼方法所需的編碼時間。編碼時間在配置為Intel(R)Core(TM)2CPU2.93GHz,內存為2GB的電腦上測得,編程語言環境為Matlab,編碼符號的總數均為10 000。

由于RLT和LT解碼過程都采用BP算法,其復雜度都主要由所有參與解碼的編碼符號的平均節點度決定,因此在編碼端度分布相同的前提下,兩者所需的解碼時間相差不大。

表2　編碼時間比較　s

4.2誤符號率比較

圖3給出了不同信道條件下基于傳統LT碼、RLT碼和MRLT碼的三端協作傳輸的誤符號率仿真性能比較,其中傳輸的數據包數分別取k=1 000和k=5 000,蒙特卡羅仿真105次。從圖中可以看出,采用本文編碼方法MRLT的協作傳輸誤符號率曲線收斂速度明顯優于基于傳統LT碼和基于文獻[16]中RLT編碼的協作傳輸。另外,相同信道條件下,k值越大,譯碼所需的譯碼開銷相對較小,這一點與傳統的LT碼的性質一致;k值相同時,信道條件的變化對誤符號率曲線的影響不大。需要說明的是,圖2中誤符號率理論分析曲線中,在k趨于無窮大時基于RLT編碼的方法改善了傳統LT碼帶來的差錯平臺現象,但當k值較小時這一優勢并不明顯,另外其性能優勢在誤符號率數量級小于10-6時才能體現出來,因此從圖3中并不能體現RLT方法比LT碼的性能提升。

圖3　基于不同編碼方法的協作傳輸方案的誤符號率仿真曲線

4.3信源平均傳輸次數比較

圖4給出了分別采用傳統LT碼、RLT碼和MRLT碼編碼方法時,三端協作傳輸系統中目的端成功譯碼時所需的信源平均傳輸次數與SD鏈路的丟包率之間的關系。對不同信道條件下k=1 000和k=5 000時信源平均傳輸次數進行了仿真,蒙特卡羅仿真次數為10 000次。從圖中可以看出,隨著信道丟包率的增加,目的端成功譯碼時所需的信源平均傳輸次數隨之增加;在兩種不同信道條件下,基于MRLT碼編碼方法所需信源傳輸次數最少,基于傳統LT碼其次,基于文獻[16]中RLT碼編碼方法所需信源傳輸次數最多;另外信道條件的變化對這一性能影響不大。因此,采用本文提出的MRLT編碼方法在有效改善差錯平臺現象的同時減少了譯碼所需信源平均傳輸次數。

圖4　基于不同編碼方法的協作傳輸中譯碼所需信源平均傳輸開銷比較

5結論

數字噴泉碼自適應的實現碼率與時變信道容量的匹配特點使得它非常適合于無線中繼網絡中的協作通信。為了解決基于數字噴泉碼的協作傳輸中的差錯平臺問題,本文提出了一種新的實現規則變量節點度LT的編碼方法,降低了現有規則變量節點度LT碼的編碼復雜度,加快了誤符號率曲線的收斂速度,并利用對度分布的修正來改善解碼瀑布區域,在此基礎上又提出了基于規則變量節點度LT碼的協作傳輸方案并對誤符號率進行了分析。理論分析和仿真結果表明,與現有方法相比,本文方法在有效改善差錯平臺現象的同時減少了譯碼所需信源平均傳輸次數。本文后續研究重點是進一步研究規則變量節點度LT碼在多用戶分布式協作通信中的應用,進一步提高無碼率協作傳輸的有效性和可靠性。

參考文獻：

[1] Byers J W, Luby M, Mitzenmacher M. A digital fountain approach to asynchronous reliable multicast[J].IEEEJournalonSelectedAreasinCommunications, 2002, 20(8):1528-1540.

[2] Tran T, Anpalagan A, Hyung Y K. Multi-hop cooperative transmission using fountain codes over Rayleigh fading channels[J].JournalofCommunicationsandNetworks,2012,14(3):267-272.

[3] James A, Madhukumar A S, Kurniawan E, et al. Performance analysis of fountain codes in multihop relay networks[J].IEEETrans.onVehicularTechnology,2013,62(9):4379-4391.

[4] Zhu K Y, Wang H Y, Sun W Z. Rateless cooperative transmission based on network coding and relay selection[J].SystemsEngineeringandElectronics, 2013, 35(11):2439-2444.(祝開艷,王洪玉,孫文珠. 基于網絡編碼和中繼選擇的無碼率協作傳輸[J]. 系統工程與電子技術, 2013, 35(11):2439-2444.)

[5] Luby M. LT codes[C]∥Proc.ofthe43rdAnnualIEEESymposiumonFoundationsofComputerScience, 2002:271-280.

[6] Yen K K, Liao Y C, Chen C L, et al. Modified robust soliton distribution(MRSD)with improved ripple size for LT codes[J].IEEECommunicationsLetters, 2013, 17(5):976-979.

[7] Khaled F H, Shahram Y. Improved systematic fountain codes in AWGN channel[C]∥Proc.ofthe13thCanadianWorkshoponInformationTheory, 2013:148-152.

[8] Sorensen J H, Popovski P, Ostergaard J. Design and analysis of LT codes with decreasing ripple size[J].IEEETrans.onCommunications, 2012, 60(11):3191-3197.

[9] Yue G S, Uppal M M, Wang X D. Doped LT decoding with application to wireless broadcast service[C]∥Proc.oftheIEEEInternationalConferenceonCommunications, 2011:1-5.

[10] Sorensen J H, Popovski P, Ostergaard J. UEP LT codes with intermediate feedback[J].IEEECommunicationsLetters, 2013, 17(8):1636-1639.

[11] Namjoo E, Aghagolzadeh A, Museviniya J. A new rateless code with unequal error protection property[J].ComputersandElectricalEngineering, 2013,(39):1980-1992.

[12] Hussanin I, Ming X, Rasmussen L K. Error floor analysis of LT codes over the additive white Gaussian noise channel[C]∥Proc.oftheIEEEGlobalTelecommunicationsConference,2011:1-5.

[13] Hussanin I, Ming X, Rasmussen L K, et al. Design of spatially-coupled rateless codes[C]∥Proc.oftheIEEE23rdInternationalSymposiumonPersonalIndoorandMobileRadioCommunications, 2012:1913-1918.

[14] Hussanin I, Ming X, Rasmussen L K. Design of LT codes with equal and unequal erasure protection over binary erasure channels[J].IEEECommunicationsLetters,2013,17(2):261-264.

[15] Luby M, Mitzenmacher M, Shokrollahi M A. Analysis of random processes via and-or tree evaluation[C]∥Proc.ofthe9thAnnualACM-SIAMSymposiumonDiscreteAlgorithms,1998:364-373.

[16] Sun W Z, Wang H Y, Zhu K Y, et al. A novel encoding scheme for regular variable-node degree LT codes[J].ActaElectronicaSinica,2014,42(10):1918-1924.(孫文珠,王洪玉,祝開艷,等. 一種規則變量節點度LT codes編碼方案[J].電子學報,2014,42(10):1918-1924.)

祝開艷(1980-),女,講師,博士研究生,主要研究方向為協作通信、網絡編碼技術、數字噴泉碼編碼技術。

E-mail:zkycat@126.com

王洪玉(1968-),男,教授,博士研究生導師,博士,主要研究方向為無線協作通信技術,自組織網絡及無線傳感器網絡技術等。

E-mail:whyu@dlut.edu.cn

孫文珠(1982-),男,博士研究生,主要研究方向為信源信道聯合編碼技術、數字噴泉碼。

E-mail:sunwenzhu@mail.dlut.edu.cn

宋維波(1981-),男,講師,碩士，主要研究方向為機器人控制技術。

E-mail:swb@dlou.edu.cn

網絡優先出版地址：http://www.cnki.net/kcms/detail/11.2422.TN.20141031.1029.005.html

Cooperative transmission with regular variable-node degree LT codes

ZHU Kai-yan1,2, WANG Hong-yu1, SUN Wen-zhu3, SONG Wei-bo2

(1.FacultyofElectronicsInformationandElectronicalEngineering,DalianUniversityofTechnology,

Dalian116024,China; 2.CollegeofInformationEngineering,DalianOceanUniversity,

Dalian116023,China; 3.CollegeofComputerScienceandTechnology,

ShangdongUniversityofTechnology,Zibo255049,China)

Abstract:Regular variable-node degree Luby transform (LT)codes can reduce the erasure floor of traditional LT codes, which are caused by choosing neighbor nodes randomly in the encoding process. A novel encoding scheme for regular variable-node degree LT codes is proposed. Compared with existing methods, the proposed scheme utilizes assignments and empty operation for arrays to realize the regulation of information symbol value, reducing the complexity of existing methods. Meanwhile, by modifying the degree distribution, the waterfall area(avalanche area)in decoding regular variable-node degree LT codes is improved. Finally, the proposed coding method is applied to the cooperative communication system, and the symbol error rate is analyzed. Experimental results show that this scheme can save system coding time, effectively reduce the symbol error rate erasure floor, and decrease the average transmission overhead required for the successful decoding.

Keywords:cooperative communications; fountain codes; regular variable-node degree Luby transform (LT) codes; erasure floor; degree distribution

作者簡介：

中圖分類號：TN 925

文獻標志碼：ADOI:10.3969/j.issn.1001-506X.2015.05.29

基金項目：國家自然科學基金(61172058)資助課題

收稿日期：2014-07-02；修回日期：2014-10-22；網絡優先出版日期：2014-10-31。