基于新型隨機度分布的壓縮噴泉碼

陳月云 劉 偉

(北京科技大學計算機與通信工程學院 北京 100083)

1 引言

噴泉碼[1]是一類新穎的基于圖的信道編碼技術，無碼率特性使其在發送編碼之間無需等待反饋，因其性能優越被逐步推廣到無線廣播多播服務中[2]。

Luby等人于1998年首次提出噴泉碼概念，并在2002年提出了第1種現實可行的噴泉碼——LT碼[3]。之后，文獻[4]在LT碼的基礎上進行改進，使其譯碼時間有所提高，這種新型的噴泉碼后又被命名為Raptor碼。

在文獻[3]中給出兩種度分布，分別是理想孤子度分布和穩健孤子度分布。理想孤子度分布理論上使每一個編碼符號在任何一次譯碼迭代中釋放概率相同[3]，保證在譯碼迭代過程中總存在僅有一個輸入符號在預處理集中，使每完成一次迭代都能譯出一個輸入符號。但在實際中，由于度分布映射的隨機性使得極微小的波動誤差都能造成預處理集消失并致使譯碼失敗。穩健孤子度分布是在理想孤子度分布的基礎上做了改進，由兩部分組成，第1部分為上述的理想孤子度分布，另一部分加入了兩個調節參數c和δ，在結合了理想孤子度分布的優點基礎上，擴展了譯碼過程中的預處理集，使其消失概率充分小，提高譯碼成功概率，但同時由于編碼覆蓋的冗余度增加，造成譯碼效率降低。

文獻[5]提出多目標進化算法，以譯碼開銷和計算復雜度作為目標參數，采用不同度分布可獲得不同指標的高譯碼性能。文獻[6]提出噴泉碼優先級的概念，將高優先級的重要數據采用度1或2進行編碼，使重要數據能夠被快速譯碼。文獻[7]提出一種簡單的度分布，稱為二進制指數分布(Binary Exponential Distribution,BED)。但是該方法可能會過分增加度1的產生概率，降低了信源符號參與編碼的概率，增加度1斷層的出現概率[8]。

文獻[8,9]在文獻[7]的基礎上對簡單 BED 度分布加以改進，進一步優化了噴泉碼的性能。文獻[9]提出基于二項分布函數的度分布函數，增加原始符號參與編碼的概率；文獻[10]提出的轉換度分布是將BED度分布與穩健孤子度分布相結合，有效提高成功譯碼概率。但以上兩種改進度分布的編碼性能沒能在最大程度上逼近理想孤子度分布，在譯碼效率方面仍有可提升空間。在文獻[2]中對于噴泉碼譯碼給出兩種通用譯碼算法，即高斯消元譯碼算法及置信傳播(BP)譯碼算法。文獻[10]給出一種最大似然(ML)譯碼算法。高斯譯碼及ML譯碼算法較BP算法能夠提高效率但譯碼復雜度較高，且隨著信源符號數增加而迅速增加，但是由于BP算法受度1斷層的制約，一旦出現度1斷層則譯碼中斷[11]。

本文通過分析低的度值對編譯碼產生的影響，提出二進制指數隨機度分布(BERDD)，具有理想孤子度分布及BED分布的性能折中，不僅降低譯碼過程中出現度1斷層的概率而且譯碼復雜度低，譯碼開銷小，迭代效率高。噴泉碼的譯碼需要傳輸編碼生成矩陣，且一列生成矩陣中元素個數等于信息包的符號個數，在發送過程中占用大量帶寬，由此提出基于絕大多數生成矩陣的稀疏特性，采用碼本方式對生成矩陣進行壓縮的策略，有效壓縮發送數據幀長，提高系統吞吐量。

2 系統模型

蜂窩小區內用戶向基站發出多媒體業務請求，實現數據的實時傳輸，用戶隨機分布在小區內的不同位置，系統模型如圖1所示。基站將請求相同多媒體數據的M個用戶劃分為一個多播組 G roup(U1,U2,…,UM)，基站采用噴泉碼對所要發送數據包進行編碼。基站以信息包為單位發送多媒體數據，當多播組中的所有用戶都成功接收并完成一個信息包譯碼后，基站發送下一個信息包。由于多播組用戶在實際地理位置上是隨機分布的，因此每個用戶與基站間的信道狀況各不相同，所以信息的傳輸效率取決于多播組中信道條件最差的用戶。

系統原理如圖2所示。在信源端，將長為Kall個符號的信息分隔為n=Kall/K個信息包(即每個信息包大小為K個符號)。

圖1 系統模型

噴泉碼的編碼算法：

(1)根據給定的度分布函數ρ(d)隨機產生度d；

(2)在信息包中的K個符號中隨機選取d個不同的輸入符號；

(3)編碼后的輸出符號為(2)中d個不同輸入符號的異或和。

為避免因衰落信道產生傳輸差錯導致譯碼失敗，在發送端采用循環冗余校驗(Cyclic Redundancy Check,CRC)，在接收端刪除產生差錯數據幀。由于噴泉碼的無碼率特性，因此刪除錯誤幀不會對譯碼造成影響。在碼本壓縮模塊中，數據幀以碼本方式經過壓縮處理，即用不同位數的標志位表示生成矩陣中1的位置，以達到縮短發送幀長的目的。在接收端，多播組內用戶不斷接收編碼信息直至完成一個信息包的譯碼，當基站收到該多播組所有用戶譯碼成功的確認信息后對下一信息包進行編碼并發送。

圖2 系統原理框圖

3 二進制指數隨機度分布(BERDD)

度分布的設計影響噴泉碼的譯碼開銷與計算復雜度。由于在譯碼過程中譯碼器首先尋找度為1的編碼符號，即編碼符號只和唯一的信源符號相連，并將其還原為信源符號，則度為1的編碼可以最直接且最快速地還原信源符號。此后通過異或相加，刪除他們在生成圖中相連的邊[12]，降低未恢復編碼的度值，從而使某些度為 2的編碼的度值降為 1，通過迭代實現譯碼。但是，如果在譯碼過程中生成矩陣不能收斂到度1時，譯碼過程中斷，稱之為度1斷層。因此，度值較低的編碼符號特別是度為 1的編碼符號個數多時，降低產生編碼時輸出符號間的關聯性，則譯碼容易出現度1斷層，需要接收更多的編碼才能完成譯碼，導致譯碼開銷增加。相反，若度值較低的編碼符號特別是度為1的編碼符號個數太少，譯碼所需模二加次數增加，導致譯碼復雜度增加，譯碼速度降低。

因此，度為1的編碼個數應有合理取值，本文提出基于遞縮等比數列的改進型隨機度分布函數，叫做二進制指數隨機度分布(Binary Exponential Random Degree Distribution,BERDD)，為

ρ(d)為二進制指數分布(BED)[13]。BED分布是基于無窮遞縮等比數列，d=t(t=1,…,K- 2)的產生概率是d=t+ 1 產生概率的2倍。τ(d)為理想孤子度分布。在模型式(1)中，將BED分布與理想孤子度分布進行歸一化。BERDD分布既能彌補BED分布度1產生概率過高的缺陷，又能最大程度上保留理想孤子度分布的優良特性且有效避免度1斷層的出現。

圖3給出度1對譯碼過程產生的影響。圖中以4個輸出符號及5個編碼符號為例，根據穩健孤子度分布、BED及BERDD的度分布函數得到度1的產生概率分別為μ(1)=0 .1237[4],ρ(1)=0 .5,f(1)=0 .35，四舍五入分別取度1編碼符號個數為1,3,2，如圖3(a),3(b),3(c)所示。圖3(a)中，完成譯碼需6步迭代，8次異或運算。圖3(b)中，當譯碼進入狀態2時，出現度1斷層，導致譯碼中斷。圖3(c)所示譯碼過程，完成譯碼只需3步迭代，4次異或運算，相比度1編碼符號個數為3的情況，譯碼迭代次數減少。由此可見，BERDD度分布能夠在降低度1斷層出現概率的同時，提高譯碼速度，降低譯碼復雜度。

圖3 譯碼狀態轉移圖

4 基于碼本的壓縮噴泉碼設計

4.1 碼本壓縮編碼原理

根據BERDD度分布函數可知，低度值的產生概率遠高于高度值的產生概率，因此每進行一次編碼生成矩陣大多數為K×1的稀疏矩陣列，其中K為信息包大小。采用碼本方式進行壓縮，即用M個二進制比特來表示矩陣中1所在的位置，稱此M個二進制比特為標志位。當矩陣中1的個數L<

成功譯碼所需接收的編碼個數N=(1 +ε)K，其中ε為譯碼開銷，ε＜1。由于接收端需要編碼產生的生成矩陣進行二部圖重構以完成譯碼，因此，整個譯碼過程所需發送的符號總數為A=(1+K)N。采用碼本壓縮編碼，當生成矩陣度值滿足d＜D時，該生成矩陣可被壓縮，且壓縮后的符號數為M×d。有BERDD度分布函數f(d)可知N個編碼符號中度為d的個數是N×f(d)， 則整個譯碼過程所需發送符號總數為

得到壓縮率為

4.2 編碼效率及占用帶寬分析

定義E(K)為信源符號數為K時的編碼效率，即信源符號數與發送符號數之比。則編碼效率可表示為K/ (1 +K)N=1 /(1 +K)(1 +ε)。因此，編碼效率與信息包大小K近似成反比，即信息包越大，編碼效率越低。

應用碼本壓縮噴泉碼傳輸，設發送端信源符號數為Kall個，標志位的個數為M，則生成矩陣維數最大為2M，即參與一次LT編碼的信息包符號數最多為K=2M。發送所有信源符號所需的信息包個數為Kall/2M，則正確譯出一個信息包所需的編碼個數為N=K× (1 +ε)=2M× (1 +ε)。由式(4)得，正確譯出一個信息包所需接收的比特數為

由式(6)可以看出隨著M的增大，編碼效率有所下降。

由于碼本壓縮的原理是用標志位比特來表示稀疏生成矩陣中1的位置，因此產生編碼的度值越小其產生的生成矩陣的可壓縮度就越高。以K=32為例，其標志位個數M=l og232=5 ，其可被壓縮的度的最大值D=[2M/M]=[32/5]=6 ，則當d＞D時，發送一個編碼所附帶的生成矩陣列為 32 bit，當d=1時，壓縮后的生成矩陣列僅為5 bit，其壓縮率為15.6%。因此，度1產生的個數對壓縮效果起著至關重要的作用。

對編碼產生的生成矩陣采用碼本壓縮后，發送數據幀長縮短。設壓縮前發送數據幀長為Lbit，壓縮后發送數據幀長為Li(i=1,…,N)，且＜L，經噴泉碼編碼后碼率RB不變。需要注意的是，由于每次編碼產生的生成矩陣的稀疏度不同，因此壓縮后大小不定。由式(8)得＜R(i=1,…,N)，即經B數據壓縮后碼元速率降低，則發送每幀所占用的信道帶寬降低，其中為壓縮后的碼元速率。

綜上所述，對發送數據幀進行碼本壓縮后，平均占用帶寬降低，節省了帶寬資源，提高了帶寬利用率。

5 性能仿真及分析

在仿真中，采用 LT碼作為噴泉碼編碼，完成編碼后為每個分組加上校驗和，不考慮校驗和的漏檢概率，則近似將分組交換的邏輯信道等效為刪除信道，以BPSK作為調制方式，接收端采用置信傳播譯碼算法。圖4，圖5是單一用戶條件下對性能參數的仿真結果。圖6，圖7仿真多播環境下考察譯碼開銷，為簡化分析，取多播組用戶數為 5，數據分組經瑞利衰落信道且信道條件相互獨立。

表1給出不同度分布度值產生概率統計，仿真中原始數據包為100個符號，根據穩健孤子，BED和BERDD 3種度分布分別產生100×1000個編碼，對不同度值進行統計，表1給出度值分別為1,2,3,4,5,10,50,100的產生概率。可以看出，BERDD分布度值的產生概率介于穩健孤子度分布與 BED分布之間，與前文分析一致，且隨著度值的增大，其產生概率逐漸降低。另外，由表中數據知，對于3種度分布度值在 5以下的產生概率總和均接近或超過50%，說明編碼產生的生成矩陣絕大多數為稀疏矩陣，這為碼本壓縮提供了有利依據。

圖4 度分布覆蓋情況

圖5 譯碼復雜度

圖6 不同度分布完成譯碼所需編碼個數

圖4，圖5分別給出根據3種度分布函數產生編碼是對輸出符號的覆蓋情況曲線及譯碼復雜度曲線。如圖4所示，數據包大小K分別取30,50,80,100,120，計算在不同度分布函數下確保所有信息符號都參與編碼的最少編碼次數。BED度分布在編碼時要覆蓋到所有信息符號所需編碼次數較多，因為其小度值的產生概率過大，尤其是度 1的產生概率，Robust度分布的覆蓋性最好。由圖5可以看出，隨著信息包大小K值增加，成功譯碼所需模二加運算次數增加，且在相同條件下，BED度分布最優，BERDD度分布次優。因此，編碼時度分布對輸出符號覆蓋性越好，則譯碼復雜度越高。雖然Robust度分布的覆蓋性最好，但在譯碼過程中譯碼復雜度高，譯碼速度較慢。BERDD度分布取前兩者的折中，在提高低度值產生概率的同時，兼顧對輸出編碼的覆蓋。

表1 度值產生概率統計

圖7 采用碼本壓縮傳輸前后平均占用帶

圖6為3種度分布函數譯碼開銷性能曲線，通過統計成功譯碼所需編碼符號個數來衡量度分布性能。由前文分析知，K值越大譯碼復雜度越高，此處設定K為150以內數值。由圖6可知，在信息包大小一定情況下，采用BERDD分布函數完成譯碼所需編碼個數小于Robust度分布和BED度分布，且隨著信息包大小的增加，其性能優勢體現得更為明顯。

圖7為在不同信息包大小條件下采用碼本壓縮噴泉碼傳輸前后平均占用信道帶寬仿真曲線。其中，噴泉碼的度分布采用本文提出的BERDD度分布，且由前文分析可知，在碼本壓縮過程中當標志位分布取3,4,5,6,7 bit時，信息包大小為8,16,32,64,128 bit的壓縮率最高。因此，在仿真中取信息包大小分布為8,16,32,64,128 bit。由圖6可以看出，采用碼本壓縮噴泉碼傳輸后，在一定信息包大小條件下平均占用信道帶寬降低，節省了帶寬資源。若噴泉碼編碼后碼速率不變，隨信息包大小的增加，采用碼本壓縮噴泉碼傳輸，其帶寬利用率性能優勢更為明顯。

6 結論

本文通過分析度分布對噴泉碼編譯碼的影響，提出了 BERDD分布，將理想孤子度分布和 BED分布進行歸一化，折中兩者度值產生概率。仿真表明，對于符號數為100的信息包，采用BERDD度分布編碼度1的產生概率較穩健孤子度分布提高了23%，且譯碼復雜度較穩健孤子度分布大大降低。在多播傳輸環境下譯碼開銷低于穩健孤子度分布及BED分布，隨著信息包符號數的增多，其譯碼開銷性能優勢體現更為明顯。采用碼本壓縮噴泉碼傳輸方式，對編碼產生的生成稀疏矩陣壓縮，用標志位信息表示稀疏矩陣中1的位置，縮短發送數據幀長，節省了帶寬資源，提高了帶寬利用率，具有一定的實用價值。

[1]MacKay D.Fountain codes[J].IEEProceedings Communications,2005,150(6): 1062-1068.

[2]3GPP TS 26.346 V6.12.0.Multimedia Broadcast/Multicast Service (MBMS)[S].2008.

[3]Luby M.LT codes[C].Proceedings of the 43rd Annual IEEE Symposium on the Foundations of Computer Science,USA,Nov.19,2002,43,271-280.

[4]Shokrollahi A,et al..Raptor codes[J].IEEE Transactions on Information Theory,2007,58(4): 2551-2567.

[5]Chen Chi-ming and Chen Ying-ping.Optimizing degree distributions in LT codes by using the multiobjective evolutionary algorithm based on decomposition[C].Proceedings of Evolutionary Computation (CEC),Barcelona,Spain,July 18-23,2010: 1-8.

[6]Woo S and Cheng M.Prioritized LT codes[C].Proceedings of Information Sciences and Systems,Princeton,USA,Mar.19-21,2008: 568-573.

[7]Al Agha K and Kadi N.Fountain codes with XOR of encoded packets for broadcasting and source independent backbone in multi-hop networks using network coding[C].Proceedings of Vehicular Technology Conference,Barcelona,Spain,Apr.26-29,2009: 1-5.

[8]Zaman M S and RamaMurthy G.A new degree distribution for LT codes for broadcasting in Ad hoc network using network coding[C].First UK-India International Workshop on Cognitive Wireless Systems (UKIWCWS),Delhi,India,Dec.10-12,2009: 1-5.

[9]Kadi N and Al Agha K.New degree distribution to improve LT-code in network coding for broadcasting in Ad hoc wireless networks[C].Proceedings of IEEE International Symposium on Personal,Indoor and Mobile Radio Communications (PIMRC),Istanbul,Turkey,Sept.26-30,2010: 1820-1825.

[10]Schotsch B and Schepker H.The performance of short random linear fountain codes under maximum likelihood decoding[C].Proceedings of IEEE International Conference on Computer Communications(ICC),Kyoto,Japan,June 5-9,2011: 1-5.

[11]Huang Wei-zheng and Li Huan-lin.Fountain codes with message passing and maximum likelihood decoding over erasure channels[C].Proceedings of Wireless Telecommunications Symposium (WTS),New York,USA,Apr.13-15,2011: 1-5.

[12]Lin Guang-rong.Finite length analysis of fountain codes based on stopping set[J].Journal of Electronics＆Information Technology,2008,30(11): 2634-2637.