李騰飛,蘇偉偉,文 紅

(電子科技大學通信抗干擾國家級重點實驗室,四川成都611731)

分布式無標度LT碼*

李騰飛,蘇偉偉,文 紅

(電子科技大學通信抗干擾國家級重點實驗室,四川成都611731)

LT碼是噴泉碼的一種,在刪除信道中性能優(yōu)越,分布式噴泉碼多信源多中繼的特性適合用于深空通信中。無標度網(wǎng)絡(SF network)具有平均路徑(APL)長最小的特性,非常適合噴泉碼的度分布設計需求。首先介紹了LT碼的編譯碼算法,然后對無標度網(wǎng)絡和基于無標度網(wǎng)絡的SF-LT碼度分布設計進行了詳細分析和優(yōu)化,最后在刪除信道條件下,選取碼長較短、刪除概率較小的情形對分布式二信源SF-LT碼進行仿真分析,仿真結果表明,與LT碼相比,分布式SF-LT碼具有更好的性能。

噴泉碼 LT碼 分布式SF-LT碼

0 引 言

LT碼[1]是噴泉碼[2-3]的一種,度分布是其構造的關鍵,LT碼節(jié)點間平均路徑(APL)長度越短代表其譯碼效率越高,無標度網(wǎng)絡平均路徑長最小的特性,非常適合LT碼節(jié)點度分度設計的需求,對于固定的節(jié)點數(shù)和平均路徑長,無標度網(wǎng)絡可以提供最小的連線數(shù)目。本文將復雜網(wǎng)絡的無標度特性應用在LT碼的度分布設計中,設計一類網(wǎng)絡結構具有無標度特性的SF-LT碼,然后根據(jù)深空通信載體資源受限的特性,設計更具實用性的分布式SF-LT碼,最后在碼長500,刪除概率0.05的刪除信道條件下對SF-LT碼和分布式二信源SF-LT碼的譯碼性能進行仿真驗證,證明了分布式SF-LT碼比LT碼具有更好的性能。

LT碼是一種由K個源數(shù)據(jù)包根據(jù)自身的度分布進行編碼而生成的,而接收端只要接收到N(N稍大于K)個編碼數(shù)據(jù)包就可以高概率地譯碼,LT碼自身的度分布決定了其譯碼性能,度是指與該編碼包相連的源數(shù)據(jù)包數(shù)目,LT碼度分布用S(d)表示,其意義在于:對于所有的度d,編碼分組出現(xiàn)度為d的概率為S(d)。

LT碼的編碼就是根據(jù)度分布函數(shù)S(d),從k個數(shù)據(jù)包中隨機地選取d個源數(shù)據(jù)包,然后將這d個源數(shù)據(jù)包進行模二加,生成一個編碼數(shù)據(jù)包。

LT碼的譯碼過程為:找到一個度為1的編碼符號tn,令與之相連的源數(shù)據(jù)包sk=tn,然后將sk與所有和sk有聯(lián)系的編碼數(shù)據(jù)包進行異或,最后刪除所有與sk相連的編碼數(shù)據(jù)包。不斷重復上述過程,直到找不到度為1的編碼數(shù)據(jù)包。如果存在這樣的數(shù)據(jù)包,表明沒有全部譯碼。

1 LT碼無標度網(wǎng)絡

1.1 無標度網(wǎng)絡

網(wǎng)絡可以表示為G=(V,E),其中V表示給定點集,E表示邊集。點集中的元素稱為節(jié)點,節(jié)點間的連接稱為邊[4]。節(jié)點i的度ki定義為與節(jié)點i相連的邊數(shù)。定義網(wǎng)絡的平均路徑(APL)長度L為網(wǎng)絡中任意兩個節(jié)點間距離的平均值,也稱為網(wǎng)絡的特征路徑長度,

式中,N為網(wǎng)絡節(jié)點數(shù),dij為網(wǎng)絡中節(jié)點i與節(jié)點j之間連通的最小邊數(shù),也稱為節(jié)點對(i,j)之間的距離。

無標度網(wǎng)絡是目前較為常見的網(wǎng)絡結構之一,具有特殊拓撲結構,它的度分布服從冪方律分布,在給定規(guī)模的通信網(wǎng)絡中,無標度網(wǎng)絡的平均路徑長最小[5],典型的BA(Barabási-Albert)無標度網(wǎng)絡模型的構造算法如下[6]:

1)初始:開始給定一個有m0個節(jié)點的網(wǎng)絡。

2)增長:在每個時間步重復增加一個帶有m條邊的新節(jié)點,并且按照步驟3)中的擇優(yōu)概率選擇m個節(jié)點與新節(jié)點相連,其中m＜m0。

3)擇優(yōu)連接:按照擇優(yōu)概率:

選擇舊節(jié)點i與新節(jié)點相連,其中ki是舊節(jié)點i的度。

經(jīng)過t個時間步后,生成一個有t+m0個節(jié)點和mt條邊的BA無標度網(wǎng)絡。

1.2 LT碼無標度網(wǎng)絡模型

首先從一個簡單的譯碼例子出發(fā),圖1為LT碼的編碼tanner圖。

圖1 輸入數(shù)據(jù)包為10的LT碼的編碼Tanner圖Fig.1 Tanner graph of LT code which the input data packet is 10

si代表源數(shù)據(jù)包,ci代表編碼數(shù)據(jù)包。LT碼的譯碼過程是一個消息傳遞的過程。信息的傳輸依賴于Tanner圖中的節(jié)點連線。用一個網(wǎng)絡模型表示圖1,網(wǎng)絡節(jié)點表示編碼數(shù)據(jù)包ci,節(jié)點之間的連線遵循以下規(guī)則:如果兩個編碼數(shù)據(jù)包在Tanner圖中與同一個源數(shù)據(jù)包si相連,在網(wǎng)絡模型中這兩個節(jié)點之間相連。圖2為圖1匹配的網(wǎng)絡模型。

圖2 圖1所生成的將原始數(shù)據(jù)包節(jié)點移除的復雜網(wǎng)絡Fig.2 Complex network figure 1 generation which the original packet removed

在譯碼端,譯碼“信息”從度為1的節(jié)點開始,沿著圖2中的連線將信息傳輸給與之相鄰的節(jié)點,然后從圖2網(wǎng)絡中去除與之關聯(lián)的邊,不斷重復上述過程,直到網(wǎng)絡中不存在度為1的節(jié)點。如果圖2中的網(wǎng)絡節(jié)點關聯(lián)了所有源數(shù)據(jù)包,在譯碼端可以成功譯碼。

圖2中,兩個節(jié)點間的路徑長度代表著“譯碼信息”從一個節(jié)點更新到另一個節(jié)點的更新操作的次數(shù)。在一個給定規(guī)模的網(wǎng)絡中,節(jié)點間平均路徑(APL)越短,譯碼成功的概率越高,同時譯碼效率越高,基于無標度網(wǎng)絡的平均路徑長最小的特性,可以將無標度網(wǎng)絡引入LT碼度分布的設計中,構造一類網(wǎng)絡結構具有無標度特性的LT碼——SF-LT碼,同時根據(jù)深空通信載體資源受限的特性,可以將SF-LT碼引入分布式系統(tǒng)中,設計更具實用性的分布式SF-LT碼。無標度網(wǎng)絡的度分布有著冪方律特性,節(jié)點的度分布是λ(d)=Ad-γ,其中d是節(jié)點的度,λ是冪指數(shù)參數(shù),A是使得∑dλ(d)=1的歸一化參數(shù)。由于圖2映射到的編碼數(shù)據(jù)包和原始數(shù)據(jù)tanner圖并不是唯一的,所以要對度分布進行一定的改進。定義修正后的冪律分度為[7-8]:

式中,參數(shù)P1為度為1的編碼數(shù)據(jù)包概率,r為衰減因子,A為歸一化因子。

考慮到由式(3)構造的度分布,度高的編碼數(shù)據(jù)包的數(shù)量很少,會導致在接收編碼數(shù)據(jù)包較多的情況下譯碼性能降低,魯棒孤波分布(RSD)在接收編碼數(shù)據(jù)包較多的情況下可以高概率地譯碼[1],可以考慮將二者進行有效的結合,由此定義SF-LT碼的度分布,采用將無標度分布與魯棒分布相結合的方法,具體實現(xiàn)方法如下:

理想的孤波度分布ρ(·):

體現(xiàn)其魯棒性的分布τ(·):

式中,參數(shù)R=c·ln(k/σ)·,R則代表度為1編碼數(shù)據(jù)包在整個編碼數(shù)據(jù)包中的平均個數(shù),參數(shù)σ表示接收到n個編碼數(shù)據(jù)包后譯碼失敗的概率。參數(shù)0＜c＜1,SF-LT碼度分布μ(·)是理想孤波分布ρ(·)、子分布τ(·)和無標度分布λ(i)和的概率歸一化結果,這樣的結合使得其既有無標度特性又對實際信道有良好的適應性,最后SF-LT碼度分布μ(i)定義為:

雖然SF-LT碼子分布τ(i)在形式上與LT碼的RSD子分布相同,但由于受無標度網(wǎng)絡冪律分布影響,子分布參數(shù)選擇可能需要調整。不同信道條件下,μ(i)子分布對于譯碼性能的影響程度不同,例如在低刪除概率條件下,接近于理想信道,子分布ρ(·)對譯碼性能的影響程度最高,因為在理想信道條件下,ρ(·)的譯碼性能最好[1],因此,根據(jù)實際信道狀況可以通過仿真測試對ρ(i)、τ(i)、λ(i)選取適當?shù)臋嘀叵禂?shù)x1、x2、x3對μ(i)進行優(yōu)化,相應的,,通過這種方法使其譯碼性能達到較好的效果。

2 兩信源分布式SF-LT碼

深空通信中,通信實體距離遙遠,資源受限,傳播損耗較大,為了保證通信質量,在設計通信設備時有更高的要求,分布式噴泉碼多信源多中繼的特性,非常適合用于深空通信中,兩信源單中繼分布式通信系統(tǒng)模型如圖3所示。

圖3 兩信源單中繼分布式通信系統(tǒng)模型Fig.3 Model of two source and single relay communication system

2.1 分布式兩信源SF-LT碼度分布

考慮分布式兩信源情況,如圖3所示,信源s1和信源s2分別獨立發(fā)送k/2個數(shù)據(jù)包,我們的目標是選擇度分布p(·)使得中繼R到目的節(jié)點D的數(shù)據(jù)傳送服從SF-LT碼度分布μ(i)。

為了求出p(·)需要進行解卷積運算,若k≥2,求SF-LT碼度分布的解卷積按如下進行[9]:直接解卷積很復雜,而且還存在很多問題,例如,解出的p(k/s)可能為負值,類似于分布式LT碼的度分布構造方法[9],把μ(·)分布分解并做標準化處理,首先把μ(·)分解為兩個分布μ′(·)和μ″(·)的線性組合:

現(xiàn)在,定義新的函數(shù):

可以計算出:

SF-LT碼的參數(shù)優(yōu)化方案同樣適用于分布式系統(tǒng),針對實際的信道條件,可以考慮為μ(i)的子分布分配不同的權重系數(shù),提升分布式SF-LT碼的譯碼性能。

2.2 分布式兩信源SF-LT碼的編譯碼過程

編碼的第一步:圖3中的兩信源發(fā)送的數(shù)據(jù)X1和X2按照度分布p(·)各自獨立進行LT編碼,由

式中,于p(·)是f(·)、μ″(·)和參數(shù)λ的組合,我們可以認為某個數(shù)據(jù)包的度d的產(chǎn)生是以概率λ按照度分布f(·)產(chǎn)生或者以概率1-λ按照度分布μ″(·)產(chǎn)生。編碼的第二步:信源s1和s2編碼后形成的數(shù)據(jù)包在中繼需要進行處理操作,由于中繼知道兩個信源的度分布,處理方法如下:

1)如果兩個信源發(fā)出的數(shù)據(jù)包的度d都是以概率λ按照度分布f(·)產(chǎn)生,則在中繼進行異或后傳輸?shù)侥康墓?jié)點。

2)如果某個信源發(fā)出的數(shù)據(jù)包的度d是以概率1-λ按照度分布μ″(·)產(chǎn)生,則中繼將該信源的數(shù)據(jù)包傳輸?shù)侥康墓?jié)點,丟棄另外一個信源的數(shù)據(jù)包。

3)如果某個信源發(fā)出的數(shù)據(jù)包的度d都是以概率1-λ按照度分布μ″(·)產(chǎn)生,則中繼就隨機選取某個信源發(fā)生的數(shù)據(jù)包傳輸?shù)侥康墓?jié)點。

具體實現(xiàn)方法如下:中繼按下式產(chǎn)生二元變量b1和b2:

式中,di表示d1和d2,分別是X1和X2的度,Ui表示U1和U2,是中繼節(jié)點產(chǎn)生的兩個獨立隨機變量,兩變量U1,U2在區(qū)間[0,1]服從均勻分布。然后中繼經(jīng)過如下處理后發(fā)送到目的節(jié)點。

式中,flip(X1,X2)表示以相同的概率隨機取X1或X2的值。

數(shù)據(jù)包從中繼到目的節(jié)點的傳送服從SF-LT碼度分布,目的節(jié)點的數(shù)據(jù)包譯碼過程與LT碼的譯碼一樣。

3 分布式SF-LT碼性能仿真

本文在刪除信道模型下,選取刪除概率q= 0.05,源數(shù)據(jù)包(LT碼)長度K=1 000,以接收一定數(shù)目編碼包條件下,譯碼端的譯碼成功率為評價準則,對分布式SF-LT碼進行性能仿真,其中,LT碼選用度分布參數(shù)為c=0.05,δ=0.5,受無標度特性冪律分布的影響,SF-LT碼選用度分布參數(shù)為c= 0.02,δ=0.5。

LT碼與3種不同系數(shù)SF-LT碼的性能仿真結果比較如圖4所示。3種SF-LT碼均選擇參數(shù)P1= 0.08,r=2.1,其中,SF-LT碼選擇系數(shù)x1=0、x2=0、x3=1,SF-LT碼1選擇系數(shù)x1=0、x2=1、x3=1,SFLT碼2選擇系數(shù)x1=1、x2=1、x3=1,由仿真結果可以看到:SF-LT碼在接收數(shù)據(jù)包較少的情況下譯碼性能比LT碼好很多,但隨著譯碼端接收數(shù)據(jù)包的增多,SF-LT碼的譯碼性能開始下降,譯碼成功率低于LT碼,但此時SF-LT碼1和SF-LT碼2的譯碼性能依然高于LT碼,這是因為經(jīng)過優(yōu)化后的度分布既有無標度特性又保證了度高編碼包的數(shù)目,SF -LT碼2的譯碼性能最好。

圖4 碼長為1 000的4種LT碼的性能比較Fig.4 Performance comparison of four kinds of LT codes which length is 1 000

對SF-LT碼進行參數(shù)優(yōu)化,因為仿真選用的是低刪除概率,對子分布ρ(·)分配較大的權重系數(shù),參數(shù)選擇如表1所示。仿真結果如圖5所示,由仿真結果可以得知:通過適當?shù)母淖儏?shù),可以得到性能較好的SF-LT碼。

表1 不同種類SF-LT碼參數(shù)選擇Table 1 Parameters choice of different types of SF-LT code

圖5 碼長為1 000的4種SF-LT碼的性能比較Fig.5 Performance comparison of four kinds of SF-LT codes which length is 1 000

在兩信源情況下,4種編碼性能仿真結果比較如圖6所示。其中,兩種SF-LT碼均選擇系數(shù)x1= 1、x2=1、x3=1,參數(shù)選擇P1=0.08,r=2.1,由仿真結果看到:SF-LT碼的譯碼性能優(yōu)于LT碼,分布式SF-LT碼在接收數(shù)據(jù)包較少的情況下,譯碼性能最好,隨著接收數(shù)據(jù)包數(shù)目的增多,與分布式LT碼相比,譯碼性能雖然有所下降,但仍保持較高的譯碼成功率。整體而言,分布式SF-LT碼的譯碼性能優(yōu)于LT碼,與LT碼相比,在載體資源受限的深空通信系統(tǒng)中,分布式SF-LT碼更具實用價值。

圖6 碼長為1 000的LT碼、SF-LT碼的性能比較Fig.6 Performance comparison of LT codes and SF-LT codes which length is 1 000

4 結 語

本文分析了SF-LT碼和兩信源分布式SF-LT碼各自的度分布實現(xiàn)和編譯碼方法,并對刪除概率較小、短碼長的SF-LT碼和兩信源分布式SF-LT碼進行了仿真分析,仿真結果表明,與LT碼相比,分布式SF-LT碼具有更好的性能,在深空通信中更具實用價值,本文的結果還為SF-LT碼技術的應用提供了很好的參數(shù)選擇依據(jù)。

[1] LUBY M.LT Codes[C]//Foundations of Computer Science.United States:IEEE press,2002:271-280.

[2] 楊玲,宋時立,劉國超,等.LT碼的性能分析及仿真[J].通信技術,2012,45(05):1-3.

YANG ling,SONG Shi-li,LIU Guo-chao,et al.The Performance of LT Codes Analysis and Simulation[J].Communications Technology,2012,45(05):1-3.

[3] 劉國超,陳霄,蘇偉偉,等.短長度分布式噴泉碼的性能分析[J].通信技術,2012,45(08):5-8.

LIU Guo-chao,CHEN Xiao,SU Wei-wei,et al.The Performance of Short Length of Distributed LT Codes[J]. Communications Technology,2012,45(08):5-8.

[4] 汪小帆,李翔,陳關榮.復雜網(wǎng)絡理論及其應用[M].北京:清華大學出版社,2006:3-33.

WANG Xiao-fan,LI Xiang,CHEN Guan-rong.Complex Network Theory and Its Application[M].Version 1.Beijing:Tsinghua University Press,2006:3-33.

[5] BOLLOBáS B,RIORDAN O.Robustness and Vulnerability of Scale-free Random Graphs[J].Internet Math, 2003,1(01):1-35.

[6] BARABáSI A.L,ALBERT R.Emergence of Scaling in Random Networks[J].Science,1999,286(5439):509-512.

[7] HYYTI? E,TIRRONEN T,VIRTAMO J.Optimizing the Degree Distribution of LT Codes with an Importance Sampling Approach[C]//6th International Workshop on Rare Event Simulation.Bamberg:RESIM press,2006:64-73.

[8] CHEN C M,CHEN Y,SHEN T C,et al.Optimizing Degree Distributions in LT Codes by Using the Multiobjective Evolutionary Algorithmbased on Decomposition [C]//Evolutionary Computation(CEC),2010 IEEE Congress on.Shanghai:IEEE press,2010:1-8.

[9] PUDUCHERI S,KLIEWER J,FUJA T E.Didtributed LT Codes[C]//2006 IEEE International Symposium on Information Theory.United States:IEEE press,2006:987-991.

LI Teng-fei(1988-),male,M.Sci., majoring in channel coding,image processing.

蘇偉偉(1988—),男,碩士,主要研究方向為信道編碼;

SU Wei-wei(1988-),male,M.Sci.,majoring in channel coding.

文 紅(1969—),女,博士,教授,主要研究方向為編碼原理與技術、密碼學、信號處理、網(wǎng)絡安全通信。

WEN Hong(1969-),female,Ph.D.,professor,mainly working at coding theory and technology,cryptography,signal processing and network communication security.

Distributed Scale-free LT Codes

LI Teng-fei,SU Wei-wei,WEN Hong
National Key Lab of Communication of UESTC,Chengdu Sichuan 611731,China;

LT code is one of the fountain codes which performs well in erasure channel.The characteristics of multi sources and multi relays make distributed fountain codes fit for deep space communications.Scale -free network has the characteristic of the minimum average path length which makes it perfect for the design requirement of degree distribution in fountain codes.The encoding and decoding algorithm of LT codes is introduced in this paper first,then the design of degree distribution in scale-free networks and SF-LT codes based on the scale-free network is analyzed and optimized.At last,under the condition of erasure channel,the simulation of SF-LT codes with distributed binary sources under shorter code length and lower erasure probability is done.The result shows that distributed SF-LT codes have better performance than LT codes.

fountain codes,LT codes,distributed SF-LT codes

TN911.22

A

1002-0802(2014)08-0854-06

10.3969/j.issn.1002-0802.2014.08.003

李騰飛(1988—),男,碩士,主要研究方向信道編碼、圖像處理;

2014-05-20;

2014-07-03 Received date：2014-05-20;Revised date：2014-07-03

國家自然科學基金項目(No.61032003,No.61271172);高等學校博士學科點專項科研基金(No.20120185110030, No.20130185130002)和四川省國際合作研究項目(No.2013HH0005)聯(lián)合資助

Foundation Item:NSFC(No.61032003,61271172),RFDP(No.20120185110030,No.20130185130002),Sichuan International Corporation Project(No.2013HH0005)and SRF for ROCS,SEM.