李騰飛,蘇偉偉,劉國超,文 紅

(電子科技大學(xué)通信抗干擾國家級(jí)重點(diǎn)實(shí)驗(yàn)室,四川成都611731)

分布式不等差錯(cuò)保護(hù)LT碼*

李騰飛,蘇偉偉,劉國超,文 紅

(電子科技大學(xué)通信抗干擾國家級(jí)重點(diǎn)實(shí)驗(yàn)室,四川成都611731)

LT碼是噴泉碼的一種,由于其優(yōu)異的性能得到了廣泛的應(yīng)用,其中,分布式LT碼在有中繼傳輸?shù)纳羁胀ㄐ胖刑貏e適用,但是它必須滿足各個(gè)信源發(fā)送的數(shù)據(jù)信息包長(zhǎng)度相等,在實(shí)際通信中,每個(gè)中繼傳輸?shù)男畔?shù)據(jù)量不一定相等,數(shù)據(jù)重要程度也會(huì)有所不同,本文針對(duì)這個(gè)問題設(shè)計(jì)出了分布式不等差錯(cuò)保護(hù)LT碼,在編碼時(shí)通過對(duì)信源包的選擇策略進(jìn)行調(diào)整實(shí)現(xiàn)對(duì)重要數(shù)據(jù)的保護(hù),仿真結(jié)果證實(shí)了我們提出策略的有效性。

LT碼 分布式 多信源 不等差錯(cuò)保護(hù)

0 引 言

噴泉碼是一種線性無速率碼,在刪除信道具有卓越的性能。LT碼是第一個(gè)前向糾錯(cuò)無速率碼的具體實(shí)現(xiàn)[1],它的編譯碼復(fù)雜度是o(K·ln(K)),其中K是原始數(shù)據(jù)包長(zhǎng)度。LT碼在刪除信道中以其極小的譯碼開銷被認(rèn)為是好碼,而且它可以在未知?jiǎng)h除概率的條件下譯碼成功,LT碼的性能主要由度分布決定[2]。文中我們提出了分布式不等差錯(cuò)保護(hù)LT碼以實(shí)現(xiàn)不等碼長(zhǎng)的多個(gè)信源間的數(shù)據(jù)傳輸問題。這種新的不等長(zhǎng)差錯(cuò)保護(hù)分布式編碼策略與分布式LT碼[3]相比有以下優(yōu)點(diǎn):

1)可以實(shí)現(xiàn)多個(gè)不等長(zhǎng)信源情況下的分布式編碼傳輸。

2)可以對(duì)不同信源提供不同的優(yōu)先級(jí)的重點(diǎn)保護(hù),通過修改參數(shù),可以動(dòng)態(tài)調(diào)整不同信源的錯(cuò)誤率,從而保護(hù)重要信源的數(shù)據(jù)信息包。

3)編碼和中繼節(jié)點(diǎn)處理的算法復(fù)雜度較低。

1 LT碼度分布及譯碼算法

LT碼的性能與度分布有直接關(guān)系[4],設(shè)計(jì)好的度分布至關(guān)重要[5],LT碼的編碼過程為:

1)根據(jù)度分布ρ(·)產(chǎn)生隨機(jī)數(shù)i。

2)從k個(gè)原始數(shù)據(jù)包中等概率地隨機(jī)選擇i個(gè)數(shù)據(jù)包。

3)將這i個(gè)數(shù)據(jù)包進(jìn)行異或,生成編碼后的數(shù)據(jù)包,不斷地重復(fù)該過程,生成編碼分組。

(1)理想孤波分布

理想的孤波度分布ρ(·),最早由Luby在其論文[1]中提出來了,具體定義如下:

理想孤波度分布在實(shí)際刪除信道中性能不是很理想,魯棒孤波分布隨之被提出。

(2)魯棒孤波分布

理想孤波分布中度為1的概率隨著k的變大而變小,為了保證初始度為1的編碼數(shù)據(jù)包個(gè)數(shù),考慮實(shí)際刪除信道條件,提出了魯棒孤波分布μ(·)[1],首先,定義一個(gè)子分布τ(·)

式中,參數(shù)R=c·ln(k/σ)·,R代表度為1編碼數(shù)據(jù)包的平均數(shù)量,參數(shù)σ表示接收到k個(gè)確知的數(shù)據(jù)包后允許譯碼失敗的概率,參數(shù)0＜c＜1,魯棒孤波分布μ(·)是子分布τ(·)和理想孤波分布ρ(·)和的標(biāo)準(zhǔn)化,具體如下所示:

(3)BP譯碼算法

如圖1所示LT碼的編碼tanner圖。si代表源數(shù)據(jù)包,ci代表編碼數(shù)據(jù)包。

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

BP譯碼算法詳細(xì)過程如下[1]:

1)首先找到度為1的編碼數(shù)據(jù)包c(diǎn)i,如果找不到則譯碼失敗。

2)恢復(fù)與度為1的編碼數(shù)據(jù)包c(diǎn)i相連的原始數(shù)據(jù)包si,并將二者的連線刪除。

3)將恢復(fù)出的原始數(shù)據(jù)包si與其相連的編碼數(shù)據(jù)包進(jìn)行異或并將之連線刪除。

4)全部原始數(shù)據(jù)包成功譯出則譯碼成功,否則重復(fù)進(jìn)行1)2)3)。

2分布式不等差錯(cuò)保護(hù)LT碼

分析分布式不等差錯(cuò)保護(hù)LT碼時(shí)[6],只考慮最簡(jiǎn)單的模型,即兩信源單中繼的情況,信源s1和s2各自獨(dú)立地發(fā)送數(shù)目分別為ρk和k的數(shù)據(jù)信息包,其中0≤ρ≤1,兩信源都采用魯棒孤波分布(RSD)進(jìn)行編碼,然后發(fā)送到中繼R,中繼接收到來自信源s1和s2的編碼數(shù)據(jù)包后,進(jìn)行如下算法[7]操作:

1)中繼節(jié)點(diǎn)R以概率p1選擇來自于信源s1的編碼數(shù)據(jù)包;以概率p2選擇來自于信源s2的編碼數(shù)據(jù)包;以概率p3=1-p1-p2異或來自于信源s1和s2的編碼數(shù)據(jù)包,形成新的異或數(shù)據(jù)信息包s1⊕s2。

2)中繼節(jié)點(diǎn)R將經(jīng)過(1)選擇處理后的數(shù)據(jù)信息包傳輸?shù)侥康墓?jié)點(diǎn)D。

在目的節(jié)點(diǎn),對(duì)接收到的數(shù)據(jù)信息包進(jìn)行BP譯碼處理。

圖2 兩信源不等差錯(cuò)保護(hù)分布式LT碼的編碼模型Fig.2 Two source code models of distributed LT codes with unequal error protection

當(dāng)參數(shù)ρ、k、p1、p2、p3、N(目的節(jié)點(diǎn)接收到的編碼數(shù)據(jù)包的數(shù)目)和度分布RSD確定后,不等差錯(cuò)保護(hù)的分布式LT碼就已經(jīng)確定了,其譯碼性能也確定了,根據(jù)編碼關(guān)系,將輸入節(jié)點(diǎn)和輸出節(jié)點(diǎn)連線組成一個(gè)二分圖,這樣可以定義一個(gè)矩陣G,可以用這個(gè)矩陣G來描述其編碼過程。

在下圖3所示的兩信源不等差錯(cuò)保護(hù)分布式LT碼的編碼過程中,信源s1、s2可以看作是向地球發(fā)送信息的兩個(gè)深空探測(cè)器,月球作為中繼節(jié)點(diǎn),在深空通信中,中繼節(jié)點(diǎn)資源有限,需要對(duì)接收的信息進(jìn)行處理操作,然后發(fā)送至目的節(jié)點(diǎn)。如圖3所示,輸入節(jié)點(diǎn)分為兩組:

1)信源s1發(fā)送的編碼數(shù)據(jù)包。

2)信源s2發(fā)送的編碼數(shù)據(jù)包。

輸出節(jié)點(diǎn)分為3類:

1)只來自于信源s1發(fā)送的編碼數(shù)據(jù)包。

2)只來自于信源s2發(fā)送的編碼數(shù)據(jù)包。

3)一部分來自于信源s1,另外一部分來自于信源s2發(fā)送的編碼數(shù)據(jù)包。

而且每一次生成輸出數(shù)據(jù)信息包的時(shí)候,這個(gè)數(shù)據(jù)包屬于1)、2)、3)類輸出數(shù)據(jù)信息包的概率分別為p1、p2、p3。從而可以通過優(yōu)化這些參數(shù)來降低誤碼率。

圖3 兩信源不等差錯(cuò)保護(hù)分布式LT碼編碼過程Fig.3 Two source of unequal error protection of distributed LT coding process

3 仿真結(jié)果分析

兩個(gè)不等長(zhǎng)信源信息經(jīng)過分布式編碼傳輸?shù)竭_(dá)目的節(jié)點(diǎn),目的節(jié)點(diǎn)接收到足夠多的編碼后的數(shù)據(jù)信息包后就可以恢復(fù)兩個(gè)信源的原始數(shù)據(jù)信息包,定義BER1、BER2分別為信源s1和s2錯(cuò)誤概率,每個(gè)輸入節(jié)點(diǎn)譯碼失敗的概率與參數(shù)p1、p2、p3有直接的關(guān)系,所以需要引入帕累托最優(yōu)狀態(tài)[8]的概念,可以選擇這個(gè)最優(yōu)狀態(tài)來控制兩個(gè)不等長(zhǎng)信源s1和s2的錯(cuò)誤概率,如果想重點(diǎn)保護(hù)信源s1的數(shù)據(jù)信息包,就把信源s1的錯(cuò)誤概率降低,使BER1＜BER2。反之,如果想重點(diǎn)保護(hù)s2的數(shù)據(jù)信息包,就把信源s2的錯(cuò)誤概率降低,使BER1＞BER2。

而且,不等差錯(cuò)保護(hù)分布式兩信源LT碼信源之間的錯(cuò)誤概率BER1、BER2是相互依賴的,為了重點(diǎn)保護(hù)某一個(gè)信源的數(shù)據(jù)信息包,要以犧牲另一個(gè)信源的錯(cuò)誤率為代價(jià)。

本文在刪除信道模型下,選取刪除概率q=0. 05,以接收一定數(shù)目編碼包條件下,譯碼端的數(shù)據(jù)包恢復(fù)率為評(píng)價(jià)準(zhǔn)則,對(duì)不等差錯(cuò)保護(hù)分布式兩信源LT碼進(jìn)行性能仿真,其中,LT碼選用度分布參數(shù)為c=0.05,δ=0.5。

選擇信源總數(shù)據(jù)包數(shù)目為1 400,其中信源s1數(shù)據(jù)包數(shù)目為600,信源s2數(shù)據(jù)包數(shù)目為800,分別在選擇概率p1=0.35、p2=0.3和p1=0.3、p2=0.5兩種條件下對(duì)兩信源的譯碼性能進(jìn)行仿真驗(yàn)證,仿真結(jié)果如圖4所示,由仿真結(jié)果看到,在參數(shù)p1=0.35,p2=0.3時(shí),信源s1的性能優(yōu)于信源s2,在參數(shù)p1=0.3,p2= 0.5時(shí),信源s2的性能好于信源s1,說明在不等長(zhǎng)信源條件下,中繼對(duì)信源的選擇概率相對(duì)比重越大,該信源信息的譯碼性能越好,可以動(dòng)態(tài)調(diào)整不同信源的選擇概率,實(shí)現(xiàn)對(duì)不同信源的保護(hù)。

圖4 信源總信息包數(shù)目為1 400的不等差錯(cuò)保護(hù)分布式噴泉碼的性能Fig.4 Performance of unequal error protection distributed fountain code under the total number of packets of information source 1 400

分別在選擇概率p1=0.3、p2=0.4和p1=0.36、p2=0.48兩種條件下對(duì)兩信源的譯碼性能進(jìn)行仿真驗(yàn)證,仿真結(jié)果如圖5所示,由仿真結(jié)果看到,在中繼對(duì)兩信源的單獨(dú)選擇概率比重相同的情況下,兩不等長(zhǎng)信源的譯碼性能基本一致,并且與參數(shù)p1=0.3、p2= 0.4的情況相比,在參數(shù)選擇p1=0.36、p2=0.48時(shí),信源s2、s1的譯碼性能均有所提升,說明在中繼對(duì)不等長(zhǎng)信源的單獨(dú)選擇概率比重相同的情況下,可以通過降低p3的概率,實(shí)現(xiàn)對(duì)譯碼性能的優(yōu)化。

圖5 信源總信息包數(shù)目為1 400的不等差錯(cuò)保護(hù)分布式噴泉碼的性能Fig.5 Performance of unequal error protection distributed fountain code under the total number of packets of information source 1 400

選擇信源總數(shù)據(jù)包數(shù)目為2 500,其中信源s1數(shù)據(jù)包數(shù)目為1 000,信源s2數(shù)據(jù)包數(shù)目為1 500,分別在選擇概率p1=0.3、p2=0.6和p1=0.4、p2=0.5兩種條件下對(duì)兩信源的譯碼性能進(jìn)行仿真驗(yàn)證,仿真結(jié)果如圖6所示,注意在p1=0.4、p2=0.5條件下,雖然p1＜p2,但考慮到兩信源的數(shù)據(jù)包數(shù)目不等,與信源s2相比,中繼對(duì)信源s1的選擇概率相對(duì)比重較大;分別在選擇概率p1=0.26、p2=0.39和p1=0.3、p2=0.45兩種條件下對(duì)兩信源的譯碼性能進(jìn)行仿真驗(yàn)證,仿真結(jié)果如圖7所示。

圖6 信源總信息包數(shù)目為2 500的不等差錯(cuò)保護(hù)分布式噴泉碼的性能Fig.6 Performance of unequal error protection distributed fountain code under the total number of packets of information source 2 500

圖7 信源總信息包數(shù)目為2 500的不等差錯(cuò)保護(hù)分布式噴泉碼的性能Fig.7 Performance of unequal error protection distributed fountain code under the total number of packets of information source 2 500

同樣,由圖6、圖7仿真結(jié)果也可得到上述仿真結(jié)論,證實(shí)了通過適當(dāng)調(diào)整參數(shù),可以動(dòng)態(tài)調(diào)整不同信源的譯碼性能,實(shí)現(xiàn)對(duì)不同信源的保護(hù)。

4 結(jié) 語

本文針對(duì)在深空通信分布式數(shù)據(jù)傳輸中,每個(gè)信源中傳輸?shù)臄?shù)據(jù)量不等,數(shù)據(jù)重要程度不同的特點(diǎn),設(shè)計(jì)了分布式不等差錯(cuò)保護(hù)LT碼,信源信息長(zhǎng)度可以不相等,而且可以動(dòng)態(tài)調(diào)整其長(zhǎng)度,編碼靈活性比較強(qiáng);同時(shí)該編碼策略采用中繼異或操作的編碼復(fù)雜度比通常的分布式噴泉碼低。仿真結(jié)果也證實(shí)了通過適當(dāng)調(diào)整參數(shù),可以動(dòng)態(tài)調(diào)整不同信源的誤碼率,實(shí)現(xiàn)對(duì)不同信源的保護(hù)。表明我們?cè)O(shè)計(jì)的分布式不等差錯(cuò)保護(hù)LT碼編碼策略非常適合深空通信中分布式數(shù)據(jù)的傳輸。

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

[2] 楊玲,宋時(shí)立,劉國超等.LT碼的性能分析及仿真[J].通信技術(shù),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] 劉國超,陳霄,蘇偉偉等.短長(zhǎng)度分布式噴泉碼的性能分析[J].通信技術(shù),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] MACKAY D.J.C.Fountain codes[J].Communications, IEE Proceedings,2005,152(06):1062-1068.

[5] LI Liang,ZHAO Jia-xiang.LT Codes with a New Degree Distribution[C]//2010International Conference on. Nanjing:IEEE press,2010:531-535.

[6] WOO S.S,CHENG M.K.Prioritized LT codes[C]// 42nd Annual Conference on.Princeton:IEEE press, 2008:568-573.

[7] TALARI A,RAHNAVARD N.Distributed rateless codes with UEP property[C]//2010 IEEE International Symposium on.Austin:IEEE press,2010:2453-2457.

[8] DEB K,PRATAP A,AGARWAL S,et al.A fast and elitist multiobjective genetic algorithm:NSGA-II[J].Evolutionary Computation,IEEE Transactions on,2002,6 (02):182-197.

LI Teng-fei(1988-),male,M.Sci., mainly working at channel coding and image processing.

蘇偉偉(1988—),男,碩士,主要研究方向?yàn)樾诺谰幋a;

SU Wei-wei(1988-),male,M.Sci.,mainly working at channel coding.

劉國超(1986—),男,碩士,主要研究方向?yàn)樾诺谰幋a;

LIU Guo-chao(1986-),male,M.Sci.,mainly working at channel coding.

文 紅(1969—),女,博士,教授,主要研究方向?yàn)榫幋a原理與技術(shù)、密碼學(xué)、信號(hào)處理、網(wǎng)絡(luò)安全通信。

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

Distributed Unequal Error Protection LT Code

LI Teng-fei,SU Wei-wei,LIU Guo-chao,WEN Hong
(State Key Lab of Communication of UESTC,Chengdu Sichuan 611731,China)

LT code,as one of the fountain codes,is now widely used for its excellent performance.Distributed LT code is particular suitable for the deep-space communication with relay transmission,however it must meet the requirement of equal length for data packets of each source.Under actual circumstance,the information data size of each relay transmission differs whereas the importance of data is not the same as well.In the light of this,the distributed unequal error protection LT code is proposed,which could achieve the protection of important data through adjusting the source packet selection strategy in the encoding.Simulation results indicate the effectiveness of this strategy.

LT code;distributed;multi-source;unequal error protection

TN911.22

A

1002-0802(2014)10-1121-04

10.3969/j.issn.1002-0802.2014.10.003

李騰飛(1988—),男,碩士,主要研究方向?yàn)樾诺谰幋a、圖像處理;

2014-07-05;

2014-08-21 Received date：2014-07-05;Revised date：2014-08-21

國家自然科學(xué)基金項(xiàng)目(No.61032003,No.61271172);高等學(xué)校博士學(xué)科點(diǎn)專項(xiàng)科研基金(No.20120185110030,No.

20130185130002);四川省國際合作研究項(xiàng)目(No.2013HH0005)

Foundation Item:The work is supported by the NSFC(Grant No.61032003,61271172),RFDP(Grant No.20120185110030, 20130185130002),Sichuan International Corporation Project(Grant No.2013HH0005)and SRF for ROCS,SEM.