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

姚渭箐, 易本順,2

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

0 引 言

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

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

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

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

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

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

本文提出一種基于存儲機制的(memory-based, MB)LT碼的編譯碼方法。該方法通過改進LT碼的編譯碼算法,來實現信息在BEC中可靠高效傳輸。首先,編碼器采用泊松魯棒孤子分布(Poisson-robust soliton distribution, PRSD)[14]編碼并構造編碼矩陣。基于輸入包數量與編碼矩陣行數相同這一特性,按照一定規則將源信息存儲于編碼矩陣中。接著,源源不斷發送編碼包和“存儲包”。經過BEC,如果全部“存儲包”都未被刪除,則通過重構矩陣中的存儲信息可直接得到源信息,無需進行譯碼過程。否則,如果部分或全部“存儲包”被刪除,則需結合BP算法進行譯碼。仿真結果表明,相比LT碼的傳統編譯碼方法,采用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],例如,可以將這些連接關系放到編碼包的頭部位置,或者將產生度和“鄰接”的偽隨機數發生器的種子事先告知接收端,收發雙方可以通過同步來實現成功譯碼。

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

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

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

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

1.2 度分布

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

(1) ISD

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

(2)

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

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

(2) RSD

首先,定義一個函數

(3)

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

(4)

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

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

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

2.1 MB編碼方法

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

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

隨后,為了區分附加列和原編碼矩陣列,考慮在編碼矩陣Gk×(n+l)的第k行后增加幾行作為“標志行”。經過BEC以后,編碼包在傳輸過程中的順序被打亂,為了能夠將輸入包的每bit信息正確恢復到各自原始的位置,采用十進制數字對矩陣Sk×l的列順序進行從低到高標注,然后將十進制轉換為二進制。“標志行”的行數由二進制標志的位數確定,將這些二進制標志分別存儲于各個“存儲列”對應的“標志行”中,而其他列對應的“標志行”的每個元素設置為0。

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

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

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

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

(5)

步驟4將“1”“2”“3”作為標志對“存儲列”進行排序,其他列標志為“0”。首先,將十進制“0”“1”“2”“3”轉換為二進制“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譯碼方法

經過BEC傳輸,編碼數據包的順序被打亂,一些編碼包可能不能被接收到。“存儲包”必然也要面臨被刪除的可能性,盡管“存儲包”不用參與譯碼,但是“存儲包”中的存儲信息可以恢復輸入包中某些bit。

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

改進的譯碼算法如下:

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

2.3 系統開銷分析

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

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

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

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

2.4 PRSD

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

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

(7)

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

(8)

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

(9)

(10)

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

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

3 性能仿真及分析

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

表1 源信息的參數選擇

當α=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。而刪除概率對傳統RSD-BP的影響最大。例如,圖4(d)中,當ε=0.5時,參數為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的性能表現很相似,但是他們都優于RSD-BP 和RSD-MB。例如,參數為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 結 論

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

[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] 陳英,顧術實,焦健,等.基于無碼率碼的獨立窗不等差錯保護方案[J]. 系統工程與電子技術,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] 趙旦峰,司佳希,梁明珅,等. 基于算術編碼的低冗余LT碼及其在安全通信中的應用[J]. 系統工程與電子技術,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.