基于存儲機制的LT碼編譯碼方法

姚渭箐, 易本順,2

(1. 武漢大學電子信息學院, 湖北 武漢 430072; 2. 武漢大學深圳研究院, 廣東 深圳 518057)

0 引 言

數(shù)字噴泉碼是一種實現(xiàn)二進制刪除信道(binary erasure channel, BEC)可靠傳輸?shù)牟铄e控制編碼技術(shù)[1]。首先,將源信息均分為k個輸入包,每個包長為lbit。隨后,編碼器源源不斷產(chǎn)生編碼包發(fā)送給接收端。接收端只需從中接收足夠數(shù)量的編碼包,就能實現(xiàn)高效譯碼,而無需反饋重傳。Luby變換(Luby transform, LT)碼[2]是數(shù)字噴泉碼的第一種實現(xiàn)方案,具有碼率不受限和編譯碼復雜度低等特點,現(xiàn)已廣泛應用于廣播通信、數(shù)據(jù)分發(fā)[3]、認知無線電網(wǎng)絡、無線傳感器網(wǎng)絡[4]、云存儲[5]等領域。

國內(nèi)外諸多學者和科研機構(gòu)在LT碼的設計和優(yōu)化上做了大量研究工作,并取得一定研究成果。目前的研究主要可歸納為以下幾個方面。

一是設計度分布:文獻[6-7]基于可譯集理論來設計LT碼度分布;文獻[8]采用啟發(fā)式算法對LT碼進行度分布優(yōu)化;文獻[9]通過調(diào)整左度分布來設計更適用BEC的短碼長LT碼。

二是提出新型噴泉碼:文獻[10]提出一種部分恢復LT碼(partial recovery Luby transform code, PR-LTC),并基于I-SDF(iterative and small degree first)分析方法進行優(yōu)化；文獻[11]提出SC-LT(spatially coupled LT)碼,并對其置信傳播(belief propagation, BP)譯碼的漸進性能進行研究。

三是優(yōu)化編譯碼方法:文獻[12]提出一種獨立窗口LT碼(independent window LT, IW-LT)不等差錯保護方案,采用LT碼對不同重要等級的數(shù)據(jù)分別進行獨立選窗和編碼;文獻[13]基于算術(shù)編碼理論,提出一種低冗余LT碼,并對其保密機制進行優(yōu)化。

綜上所述,合適的度分布和編譯碼方法可以有效降低譯碼開銷,提高無線通信網(wǎng)中的信息傳輸可靠性。

本文提出一種基于存儲機制的(memory-based, MB)LT碼的編譯碼方法。該方法通過改進LT碼的編譯碼算法,來實現(xiàn)信息在BEC中可靠高效傳輸。首先,編碼器采用泊松魯棒孤子分布(Poisson-robust soliton distribution, PRSD)[14]編碼并構(gòu)造編碼矩陣?；谳斎氚鼣?shù)量與編碼矩陣行數(shù)相同這一特性,按照一定規(guī)則將源信息存儲于編碼矩陣中。接著,源源不斷發(fā)送編碼包和“存儲包”。經(jīng)過BEC,如果全部“存儲包”都未被刪除,則通過重構(gòu)矩陣中的存儲信息可直接得到源信息,無需進行譯碼過程。否則,如果部分或全部“存儲包”被刪除,則需結(jié)合BP算法進行譯碼。仿真結(jié)果表明,相比LT碼的傳統(tǒng)編譯碼方法,采用PRSD-MB編譯碼方法可以大大降低誤比特率(bit error rate, BER),并加快了編譯碼速度。

1 LT碼在BEC中傳輸原理

1.1 LT碼編譯碼過程

假設k個輸入包S=(s1,s2,…,sk)通過以下方法編碼生成n個編碼包C=(c1,c2,…,cn),n=1,2,3,…。

步驟1從度分布中隨機選擇一個編碼包cn的度d；

步驟2隨機且均勻地選取d個輸入包作為該編碼包的“鄰接”；

步驟3將這d個“鄰接”進行異或(XOR)生成一個編碼包cn。

通過重復步驟1～步驟3,生成n個LT碼編碼包。

由于LT碼是一種稀疏隨機線性噴泉碼,編碼過程也可表示為

C=S·Gk×n

(1)

式中,S=[s1,s2,…,sk]T表示輸入包矢量；C=[c1,c2,…,cn]T表示編碼包矢量；Gk×n表示編碼包到輸入包的連接關系,通過特定方式傳輸給接收端[2],例如,可以將這些連接關系放到編碼包的頭部位置,或者將產(chǎn)生度和“鄰接”的偽隨機數(shù)發(fā)生器的種子事先告知接收端,收發(fā)雙方可以通過同步來實現(xiàn)成功譯碼。

當在BEC中傳輸,一些編碼包可能不能被接收到,圖1中灰色部分表示刪除的編碼包以及相應的編碼矩陣列。

圖1 LT碼編譯碼過程Fig.1 LT encoding and decoding process

步驟1度數(shù)為1(d=1)的編碼包直接譯碼。

步驟3重復步驟1和步驟2,直至譯碼完成。

1.2 度分布

根據(jù)LT碼編譯碼過程可知,度分布對LT碼的性能影響至關重要。文獻[2]指出,一個好的度分布需滿足兩個設計目標:①譯碼成功所需的平均編碼包數(shù)量盡可能少,確保LT譯碼成功的編碼包數(shù)量對應于確保輸入包全部譯出的編碼包數(shù)量；②編碼包的平均度數(shù)盡可能小,平均度數(shù)是生成一個編碼包所需的平均XOR運算次數(shù),因此平均度數(shù)決定了編碼復雜度,而譯碼復雜度則是平均度數(shù)乘以譯碼成功所需編碼包數(shù)量。常見的LT碼度分布有理想孤子分布(ideal soliton distribution, ISD)和魯棒孤子分布(robust soliton distribution, RSD)[2]。

(1) ISD

ISD表示的是一種理想情況,即在每次譯碼迭代中,只有一個度為1的編碼包,并且在每次迭代譯碼之后,只出現(xiàn)一個新的度為1的編碼包。其度分布函數(shù)為

(2)

式中,d為每個編碼包的度；k為輸入包數(shù)量。

然而,這種度分布的實際性能很差,一個很小的偏差就會導致度為1的編碼包消失從而造成譯碼終止。

(2) RSD

首先,定義一個函數(shù)

(3)

然后,將ρ(d)和τ(d)相加,并做歸一化處理得到RSD為

(4)

式中,d為每個編碼包的度。

盡管RSD優(yōu)于ISD,但采用RSD進行LT編碼所產(chǎn)生的編碼包多為度數(shù)較大的編碼包,在譯碼過程中可能會由于缺少足夠的度數(shù)較小的編碼包而導致譯碼中斷。

2 MB機制的LT碼編譯碼方法

2.1 MB編碼方法

根據(jù)式(1)可知,編碼矩陣Gk×n的列數(shù)對應產(chǎn)生的編碼包的數(shù)量n,每一列中的元素“1”可以看作該列對應的編碼包與輸入包之間存在連接關系;編碼矩陣的行數(shù)對應輸入包的數(shù)量k,每一行中的元素“1”可以看作該行對應的輸入包與編碼包之間存在連接關系。也就是說,編碼矩陣中每個為“1”的元素Gi,j表示第i個輸入包與第j個編碼包之間的連接關系?？梢钥闯?輸入包的數(shù)量與編碼矩陣行數(shù)相同?；谶@一特性,按照一定規(guī)則將源信息存儲于編碼矩陣中來改進編碼算法。

首先,將輸入包組成一個k×l的矩陣Sk×l,將其每一列依次作為編碼矩陣Gk×n的附加列,生成新的編碼矩陣Gk×(n+l)。此時,新編碼矩陣的行數(shù)仍為k,而列數(shù)增加了l列。

隨后,為了區(qū)分附加列和原編碼矩陣列,考慮在編碼矩陣Gk×(n+l)的第k行后增加幾行作為“標志行”。經(jīng)過BEC以后,編碼包在傳輸過程中的順序被打亂,為了能夠?qū)⑤斎氚拿縝it信息正確恢復到各自原始的位置,采用十進制數(shù)字對矩陣Sk×l的列順序進行從低到高標注,然后將十進制轉(zhuǎn)換為二進制?！皹酥拘小钡男袛?shù)由二進制標志的位數(shù)確定,將這些二進制標志分別存儲于各個“存儲列”對應的“標志行”中,而其他列對應的“標志行”的每個元素設置為0。

最后,通過上述存儲機制,產(chǎn)生新的編碼矩陣G(k+num)×(n+l),其中,num為二進制標志的位數(shù)?！皹酥拘小敝黄鸬綐俗⒆饔?而不參與實際編碼,也就是說,原來基于Gk×n產(chǎn)生的編碼序列保持不變。為了在編碼序列中增加“存儲列”對應的編碼包,直接假設“存儲列”對應的編碼包中每bit都為1。

為更清楚說明,如圖2所示,以輸入包長度l=3 bit為例,改進的編碼算法如下:

步驟1從度分布中隨機選擇一個編碼包的度d。隨機且均勻地選取d個輸入包作為該編碼包的“鄰接”。將這d個“鄰接”進行XOR生成一個編碼包。同時,這個編碼包到輸入包的連接關系表示為編碼矩陣的對應列。

步驟2重復步驟1產(chǎn)生n個編碼包和編碼矩陣Gk×n。

(5)

步驟4將“1”“2”“3”作為標志對“存儲列”進行排序,其他列標志為“0”。首先,將十進制“0”“1”“2”“3”轉(zhuǎn)換為二進制“00”“01”“10”“11”。然后,將這些二進制標志存儲于編碼矩陣的附加行,生成新的編碼矩陣為

(6)

式中,第k+1行和第k+2行為“標志行”。[G(k+1),m,G(k+2),m]=[0,1]；[G(k+1),(m+1),G(k+2),(m+1)]=[1, 0]；[G(k+1),(m+2),G(k+2),(m+2)]=[1,1],而“標志行”的其他元素設置為0。

步驟5對應于“存儲列”的每個編碼包中的3 bit都設置為1,稱為“存儲包”。

2.2 MB譯碼方法

經(jīng)過BEC傳輸,編碼數(shù)據(jù)包的順序被打亂,一些編碼包可能不能被接收到?！按鎯Π北厝灰惨媾R被刪除的可能性,盡管“存儲包”不用參與譯碼,但是“存儲包”中的存儲信息可以恢復輸入包中某些bit。

圖2 MB編譯碼方法Fig.2 MB encoding and decoding method

改進的譯碼算法如下:

步驟4如果所有標志未被檢測出,則表示所有“存儲包”丟失,采用BP算法進行譯碼。

2.3 系統(tǒng)開銷分析

接收端的譯碼器根據(jù)“存儲包”全部接收、部分接收以及全部丟失的不同情況,分別采取3種不同的方式對輸入包進行譯碼恢復。因此,MB譯碼復雜度也是隨實際情況發(fā)生變化。然而,MB編碼過程中增加“存儲列”和“標志行”的操作增加了稍微的編碼復雜度,必會產(chǎn)生一定的耗時。輸入包采用RSD-MB方法(參數(shù):k=100,c=0.1,δ=0.5)進行編碼,平均一次編碼耗時隨附加列數(shù)增加的變化情況如圖3所示。可以明顯看出,隨著附加列數(shù)的增加,平均一次編碼耗時也隨之略微增大。

圖3 RSD-MB算法平均編碼耗時Fig.3 Average consuming time per encoding process ofRSD-MB algorithm

另一方面,當k與l的比例較大時,僅需少量“存儲包”就能存儲大量甚至全部源信息,MB編譯碼方法的差錯控制性能更強。因此,為獲得較高的譯碼成功率,發(fā)送端的編碼器需要將源信息均分為盡可能多的輸入包。但過多的輸入包數(shù)量會導致編譯碼XOR運算次數(shù)增多,即編譯碼復雜度升高,從而犧牲了譯碼效率,降低編譯碼速度。

綜上所述,為了在保證高譯碼成功率的同時,又能提高編譯碼效率,考慮采用文獻[14]中提出的PRSD作為編碼器的度分布。采用PRSD進行編碼能產(chǎn)生大量度數(shù)為1的編碼包。在譯碼過程中,度數(shù)為1的編碼包直接譯碼,而無需進行任何XOR操作,從而降低了譯碼復雜度,降低譯碼耗時。因此,基于存儲機制的編譯碼方法與PRSD相結(jié)合,能在譯碼成功率和編譯碼效率之間建立一個好的性能平衡。

2.4 PRSD

為進一步提高譯碼成功率和編譯碼效率,本文采用性能更優(yōu)的PRSD[14]。大量的研究工作證實,度分布中某些度數(shù)的比例對LT碼的可譯碼性起主導作用。LT碼可通過調(diào)整這些度數(shù)的比例獲得良好的性能。度2(d=2)在度分布中所占比例最高。文獻[15]研究了LT碼在BEC中的性能,并且推導出當BP譯碼器的誤碼率趨近于0時度2比例等于1/2。

因此,考慮通過合理地調(diào)整泊松分布(Poisson distribution, PD)中度2的比例來改進LT碼性能。改進的泊松分布(improved Poisson distribution, IPD)由θ(d)表示為

(7)

θ(d)與RSD中的函數(shù)τ(d)進行歸一化,得到PRSD函數(shù)表達式為

(8)

參數(shù)λ是θ(d)函數(shù)中的一個正常數(shù)。為了滿足一個好的度分布的設計需要[2],編碼包的平均度數(shù)越小越好。因為RSD由ρ(d)和τ(d)構(gòu)成,PRSD由θ(d)和τ(d)構(gòu)成,所以平均度數(shù)的問題可轉(zhuǎn)換為θ(d)和ρ(d)均值的問題。θ(d)和ρ(d)均值的表達式為

(9)

(10)

ISD表示的是一種理想情況,即在每次譯碼迭代中,只有一個度為1的編碼包,并且在每次迭代譯碼之后,只出現(xiàn)一個新的度為1的編碼包[2]。理想情況下,λ的參數(shù)值可通過θ(d)和ρ(d)均值相等來推出。ρ(d)均值將會隨k增加而增大?；赑D的數(shù)學特性,當k<20時，PD近似于二項分布。因此,從k=20點推導出λ的參數(shù)值。根據(jù)當k=20時E[θ(k=20)]=E[ρ(k=20)] =3.577,得到λ≈3.04。

RSD產(chǎn)生大量度較高的編碼包,能保證所有輸入包參與編碼,但可能由于度1的編碼包消失而導致譯碼過程某步中斷;IPD能夠產(chǎn)生足夠多的度1的編碼包來保證譯碼持續(xù)進行,但可能因為度較高的編碼包數(shù)量較少而致使輸入包不能全部被譯出。因此,基于結(jié)合RSD和IPD兩種度分布的特點,采用PRSD進行LT編碼,能同時提高LT碼編譯碼效率和譯碼成功率。

3 性能仿真及分析

本節(jié)對PRSD-MB的性能進行評估。根據(jù)表1選擇參數(shù),輸入包分別采用RSD-BP、PRSD-BP、RSD-MB和PRSD-MB進行編碼,然后基于10 000次迭代結(jié)果對這4種方法的性能進行分析和比較。

表1 源信息的參數(shù)選擇

當α=0.2(α為刪除概率)時,BER對應譯碼開銷(ε=(N-k)/k)的變化情況如圖4所示。

圖4 不同譯碼開銷下RSD-BP、PRSD-BP、RSD-MB和PRSD-MB的BER對比(α=0.2)Fig.4 BER versus overhead for RSD-BP, PRSD-BP, RSD-MB and PRSD-MB (α=0.2)

可以看出,相比RSD-BP、PRSD-BP和RSD-MB,PRSD-MB具有更好的差錯控制性能。不同k和l下,這4種方法的BER隨著ε增加而逐漸降低。當ε相同時,PRSD-MB的BER最低,其次是PRSD-BP和RSD-MB。而刪除概率對傳統(tǒng)RSD-BP的影響最大。例如,圖4(d)中,當ε=0.5時,參數(shù)為k=100和l=3 bit的PRSD-MB的BER僅為10-3,比其他3種方法低很多。尤其相比于RSD-BP,PRSD-MB的BER降低了53.5%。

當ε=0.5時,BER對應α的變化情況如圖5所示。很明顯,隨著α增加,BER逐漸升高。相比其他3種方法,PRSD-MB在不同α時,都能獲得更好的差錯控制性能。當α=0.2,ε=0.5時,編譯碼平均耗時對應k的變化情況如圖6所示。盡管PRSD-BP和PRSD-MB的性能表現(xiàn)很相似,但是他們都優(yōu)于RSD-BP 和RSD-MB。例如,參數(shù)為k=100和l=3 bit時,相比RSD-BP和RSD-MB,PRSD-MB編譯碼速度分別加快了44.0%和42.5%。

圖5 不同刪除概率下RSD-BP、PRSD-BP、RSD-MB和PRSD-MB的BER對比(ε=0.5) Fig.5 BER versus erasure probability for RSD-BP, PRSD-BP,RSD-MB and PRSD-MB (ε=0.5)

4 結(jié) 論

本文提出一種適用于BEC的基于存儲機制的LT碼的編譯碼方法。發(fā)送端的編碼器采用PRSD產(chǎn)生普通編碼包,同時通過將源信息存儲于編碼矩陣產(chǎn)生一些“存儲包”。經(jīng)過BEC后,接收端的譯碼器根據(jù)“存儲包”全部接收、部分丟失以及完全丟失的不同情況,分別采取不同方式進行譯碼。盡管添加和檢測存儲信息的操作會輕微增加運算量,但總體上對編譯碼復雜度的影響很小,提高了譯碼成功率和編譯碼效率。仿真結(jié)果表明,相比傳統(tǒng)方法,PRSD-MB能夠提高信息在BEC中傳輸?shù)目煽啃院托省?/p>

[1] MACKAY D J C. Fountain codes[J]. IEEE Proceedings-Communications, 2005, 152(6): 1062-1068.

[2] LUBY M. LT codes[C]∥Proc.of the 43rd Annual IEEE Symposium on Foundations of Computer Science, 2002: 271-280.

[3] LEE K, KIM C, LEE S H, et al. Rateless code based reliable multicast for data distribution service[C]∥Proc.of the IEEE International Conference on Big Data and Smart Computing, 2015: 150-156.

[4] DU W, LI Z, LIANDO J C, et al. From rateless to distanceless: enabling sparse sensor network deployment in large areas[C]∥Proc.of the 12th ACM Conference on Embedded Network Sensor Systems, 2014: 134-147.

[5] ANGLANO C, GAETA R, GRANGETTO M. Exploiting rateless codes in cloud storage systems[J]. IEEE Trans.on Parallel and Distributed Systems, 2015, 26(5): 1313-1322.

[6] YEN K K, LIAO Y C, CHANG H C. Design of LT code degree distribution with profiled output ripple size[C]∥Proc.of the IEEE Workshop on Signal Processing Systems, 2015: 1-6.

[7] 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.

[8] ZENG M, CALDERBANK R, CUI S. On design of rateless codes over dying binary erasure channel[J]. IEEE Trans.on Communications, 2012, 60(4): 889-894.

[9] HAYAJNEH K F, YOUSEFI S, VALIPOUR M. Improved finite-length Luby-transform codes in the binary erasure channel[J]. IET Communications, 2015, 9(8): 1122-1130.

[10] LIAO J, ZHANG L, LI T, et al. Design of optimised multiple partial recovery LT codes[J].IET Communications,2016,10(9):1053-1062.

[11] AREF V. Rateless codes from spatially coupled regular-LT codes[C]∥Proc.of the IEEE Workshop on Communication and Information Theory, 2015: 1-6.

[12] 陳英,顧術(shù)實,焦健,等.基于無碼率碼的獨立窗不等差錯保護方案[J]. 系統(tǒng)工程與電子技術(shù),2014,36(5):991-996.

CHEN Y, GU S S, JIAO J, et al. Independent window UEP scheme based on rateless codes[J]. Systems Engineering and Electronics, 2014, 36(5):991-996.

[13] 趙旦峰,司佳希,梁明珅,等. 基于算術(shù)編碼的低冗余LT碼及其在安全通信中的應用[J]. 系統(tǒng)工程與電子技術(shù),2016,38(2):409-414.

ZHAO D F, SI J X, LIANG M S, et al. Low redundancy LT code based on arithmetic coding and its application in secure communication[J]. Systems Engineering and Electronics,2016, 38(2):409-414.

[14] YAO W Q, YI B S, HUANG T Q, et al. Poisson robust soliton distribution for LT codes[J]. IEEE Communications Letters, 2016, 20(8): 1499-1502.

[15] ETESAMI O, SHOKROLLAHI A. Raptor codes on binary memoryless symmetric channels[J]. IEEE Trans.on Information Theory, 2006, 52(5): 2033-2051.