基于規則變量節點度和擴展窗噴泉碼的不等差錯保護算法

黃太奇 易本順 姚渭箐 方華猛 李衛中

?

基于規則變量節點度和擴展窗噴泉碼的不等差錯保護算法

黃太奇 易本順*姚渭箐 方華猛 李衛中

(武漢大學電子信息學院 武漢 430072)

該文提出了一種可適用于加性高斯白噪聲(AWGN)信道的融合擴展窗噴泉碼(Expanding Window Fountain, EWF)和規則變量節點度LT碼(Regularized variable-node Luby Transform, RLT)策略的不等差錯保護(UEP)算法，稱為EWF-RLT編碼算法。首先利用擴展窗口技術給不同重要等級的數據加窗，編碼時讓較高重要等級數據以更高的概率參與編碼；同時，結合規則變量節點度算法，改變傳統LT 碼編碼過程中隨機選取鄰居節點的編碼方式，使較高重要等級的數據具有較大的最小變量節點度，改善錯誤平層現象。分析和仿真結果表明，該文提出的EWF-RLT算法與傳統算法相比，能對較高重要等級數據進行更強的保護，提升網絡傳輸質量；在UEP方案設計中，加入RLT碼編碼參數，使得該文方案更加靈活與適用。

噴泉碼；加性高斯白噪聲信道；不等差錯保護；擴展窗噴泉碼；規則變量節點度

1 引言

噴泉碼作為一種無需反饋重傳的無速率碼，能有效在信道惡劣情況下完成數據的可靠傳輸，日益成為研究熱點[1,2]，數字噴泉碼在云存儲[3]、3D視頻應用[4]以及圖形壓縮傳輸[5]中獲得了越來越多的支持與采納。數字噴泉碼起初主要應用在刪余信道，后來被擴展應用到噪聲信道[6]，例如瑞利衰落信道[7]。

在一些實際應用中，有些數據比其他的數據需要更高等級的保護，例如，在無線網絡中，控制信號往往比負載的用戶數據更為重要。此時，等差錯保護(Equal Error Protection, EEP)編碼方案已經不再適用，而需要發展具有不等差錯保護(Unequal Error Protection, UEP)能力的編碼技術。2007年文獻[8]提出了一種基于“權重”(Weight Approach) 的編碼方法，通過讓較高重要等級的數據以更高的概率參與編碼來實現不等差錯保護。文獻[9]通過給不同重要等級的數據加“窗”，設計出一種基于“擴展窗”的噴泉碼編碼方法來實現不等差錯保護，該方法編碼更加靈活，UEP性能更優。文獻[10]提出一種改進的基于“權重”的編碼方式，即利用伯努利實驗的方法來選擇不同重要等級的鄰居節點，解決了傳統UEP方案中由于不能按照實際UEP需求拆分度(splitting degree)而造成的UEP性能下降的問題。文獻[11]從系統編碼冗余度和次重要等級數據譯碼成功率角度考慮，通過給發送端發送反饋信號，降低了系統冗余度，提高了次重要等級數據的譯碼成功率。文獻[12]通過給不同重要等級數據分配不同的度分布，設計了一種能滿足任意UEP需求的編碼方案。

上述算法都是基于刪余信道設計的，由于解碼方法不一樣，這些算法不能直接應用于噪聲信道中。文獻[13]利用模擬噴泉碼編碼方法，實現了噪聲信道上的不等差錯保護，但該方法編碼復雜度高，實際應用中不易推廣。文獻[15]在文獻[14]的研究基礎上，利用規則變量節點度LT碼(Regularized variable-node Luby Transform, RLT)的方法，在AWGN信道上對較高重要等級數據進行更強的保護，該編碼算法雖然復雜度不高，但在選擇鄰居節點進行編碼時，由于采用了傳統的基于權重的編碼算法，因此導致實現UEP方式不夠靈活[9]。

本文在分析現有UEP算法的基礎上，提出了一種融合擴展窗噴泉碼(Expanding Window Fountain (EWF))編碼算法和規則變量節點度變換算法并能應用于AWGN信道的UEP方案，簡稱為EWF-RLT編碼設計方案。該方案首先利用加窗技術，給不同重要等級數據分別加窗，再結合規則變量節點度變換(RLT)算法，在編碼時分別設置不同窗口數據的最小變量節點度。EWF-RLT編碼算法實現靈活，能在幾乎不增加編碼復雜度的基礎上，進一步加強對重要數據的保護。理論分析和仿真結果表明，本文提出的EWF-RLT算法與傳統算法比較，能對無線噪聲信道中較高重要等級數據加以更強的保護，從而提升多媒體通信質量。

2 傳統LT碼編譯碼算法

LT碼是一種不規則的非系統的具有低密度生成矩陣(LDGM)的碼[16]。假設bit的輸入信息符號為，度分布函數為，其中，且,為度為的概率，為最大的度值。要生成一個編碼符號，首先根據度分布函數選擇一個度，然后隨機等概率地選擇個信息符號，最后將所選擇的個信息符號異或求和得到一個編碼符號。發送端源源不斷地進行編碼，直到接收端能夠完全譯碼成功。

信號在AWGN信道傳輸的過程中會受到噪聲的影響，無法保證譯碼的準確性，尤其當信道條件較差時使用硬判決會引入很多錯誤，因此適合采用軟判決置信傳播迭代譯碼算法，以實現可靠譯碼。迭代過程是通過校驗節點到變量節點以及變量節點到校驗節點之間的信息傳遞來完成的，在第1次迭代時，除信道信息以外，其余所有似然值初始化皆為0。當第次迭代時，從校驗節點到變量節點(信息節點)的更新規則為

最后接收端通過似然值

來估計恢復出原始信息。

3 EWF-RLT編碼設計方案

3.1傳統EWF編碼算法

文獻[9]提出的是一種利用窗口技術實現UEP性能的噴泉碼設計方案，假設需要傳輸的數據是長度為bit的二進制符號，分為個不同的重要等級。按不同重要等級將這bit數據分為部分，每部分大小分別為，其中，部分為最重要等級數據，部分為次重要等級數據，依次類推，部分為第重要等級數據。

其中

圖1 EWF的編碼示意圖

其中

3.2本文EWF-RLT碼編碼設計方案

3.1節分析了將傳統EWF算法應用到AWGN信道上的可行性并給出了其在AWGN信道上的BER下界，但存在由于隨機選取鄰居節點方式導致的錯誤平層現象。文獻[14]和文獻[17]分析指出在AWGN信道中，隨著最小變量節點度值的增加，LT碼的BER值會降低，而文獻[15]在此基礎上通過規則變量節點度分布的方法，有效地降低了LT碼的誤碼率。受此啟發，為了解決傳統EWF算法存在的錯誤平層現象，結合EWF編碼算法特點，本文將規則變量節點度算法與EWF編碼算法結合，對于窗口，預先設置不同的窗最小變量節點度，通過這樣的處理，當大于時，中的最小變量節點度大于中的最小變量節點度，于是比得到更高等級的保護，且由于增加了編碼參數，本文算法可以通過改變更加靈活地實現不等差錯保護。其實現步驟為

(5)重復步驟(3)，步驟(4)，直到編碼完成。

3.3本文EWF-RLT碼漸進性能仿真

首先比較本文算法與文獻[9]和文獻[15]提出算法的漸進BER性能。假設信息數據包括MIB(Most Important Bit)和LIB(Least Important Bit)兩個重要等級的數據，其中MIB數據占整個數據的比重為=0.1, LIB數據占整個數據的比重為，校驗節點度分布函數將參考文獻[18]。本文算法和文獻[9]中第1個窗選取的概率=0.2，文獻[15]MIB數據被選擇參加編碼的概率為[15]。它們的漸進BER可分別由式(8)和式(10)計算，如圖2所示，其中，為信息比特能量，為單邊噪聲功率譜密度。

圖2 本文算法與傳統算法漸進性能比較

由圖2(a)可以看到，在冗余度為2時，MIB和LIB數據的BER都隨著的增大而減小。本文算法和文獻[9]，文獻[15]提出的算法相比，在對MIB數據的保護上，性能更優。例如當時，本文算法的MIB誤碼率為4.278e–06，文獻[9]和文獻[15]的MIB誤碼率為4.538e–05和8.442e–05。另一方面，如圖2(b)所示，在相同信噪比(設置為)，不同冗余度的情況下，隨著冗余度的增大，MIB數據和LIB數據的BER都下降，且同文獻[9]，文獻[15]算法相比，本文算法能對MIB數據進行更好的保護。

4 實際仿真結果與分析

本節通過仿真分析本文算法在AWGN信道下的UEP性能，并與傳統算法進行比較。為了便于比較分析，假設輸入的信息數據為=5000 bit且只包含兩個重要等級的數據，其中MIB數據比重為, LIB數據占整個數據的比重為，校驗節點度分布參照文獻[18]。

首先比較本文算法與文獻[9]和文獻[15]算法在冗余度為2，不同下的BER性能，其中在本文算法和文獻[9]提出算法中，第1個窗口選擇概率=0.2，在文獻[15]中，重要等級數據的選擇概率為[15]。在編碼時，本文算法第1個窗具有規則變量節點度，而當選擇第2個窗里的信息數據進行編碼生成一個編碼符號時，還是采用等概率隨機選取的原則。如圖3(a)所示，為了說明本文算法實現了不等差錯保護，這里將傳統EEP下的BER性能作為參考。從圖3(a)可以看到，本文算法在AWGN信道上能實現不等差錯保護，且相對傳統UEP算法，能對較高重要等級的數據進行更好的保護，例如當信噪比=2 dB時，本文算法的MIB誤碼率為5.6667e–04，而文獻[9]，文獻[15]算法MIB誤碼率分別為1.6200e–03和0.0577。另一方面，本文算法只是稍微降低了次重要等級數據的誤碼率性能，由于在通信系統中，MIB比LIB更為重要，故存在少量的性能差距仍可接受[9]。

圖3 本文算法與傳統算法UEP性能比較

圖4 不同窗口選擇概率對UEP性能的影響

5 結束語

本文在分析傳統EWF算法基礎上，提出了一種基于AWGN信道的不等差錯保護方案。該方案融合了傳統的EWF編碼技術和RLT編碼算法，在設計UEP方案時更加靈活，能對較高重要等級數據進行更強的保護。該算法首先利用EWF編碼技術，使較高重要等級的數據以更高的概率參與編碼；再結合RLT算法，使得較高重要等級的數據具有較大的最小變量節點，改善傳統UEP算法中的錯誤平層現象。理論分析和仿真結果表明，在AWGN信道上，本文算法能對高重要等級數據加以更強的保護，可提升無線網絡通信質量。

參考文獻

[1] Luby M. LT codes[C].Proceedings of the 43rd Annual IEEE Symposium on Foundations of Computer Science,Vancouver, Canada, 2002, 43: 271-280.

[2] Shokrollahi A. Raptor codes[J]., 2007, 58(4): 2551-2567.

[3] Anglano C, Gaeta R, and Grangetto M. Exploiting rateless codes in cloud storage systems[J]., 2014, (99): 1-11.

[4] Blatsas M, Politis I, Kotsopoulos S A,.. A performance study of LT based unequal error protection for 3D video streaming[C]. Digital Signal Processing (DSP) of the 18th International Conference, Santorini, Greece, 2013, 1(6): 1-3.

[5] 劉國, 于文慧, 吳家驥, 等. 基于系統Raptor碼不等差錯保護的圖像壓縮傳輸[J]. 電子與信息學報, 2013, 35(11): 2554-2559.

Liu Guo, Yu Wen-hui, Wu Jia-ji,.. Compressed image transmission based on systematic Raptor codes with unequal error protection[J].&, 2013, 35(11): 2554-2559.

[6] Palanki R and Yedidia J. Rateless codes on noisy channels[C]. Proceedings of the International Symposium on Information Theory (ISIT), Chicago, USA, 2004: 37.

[7] 陳月云, 劉偉. 基于新型隨機度分布的壓縮噴泉碼[J]. 電子與信息學報, 2012, 34(5): 1185-1190.

Chen Yue-yun and Liu Wei. Compressed fountian codes based on new random degree distribution[J].&, 2012, 34(5): 1185-1190.

[8] Rahnavard N, Vellambi B, and Fekri F. Rateless codes with unequal error protection property[J]., 2007, 53(4): 1521-1532.

[9] Sejdinovic D, Vukobratovic D, Doufexi A,.. Expanding window fountain codes for unequal error protection[J]., 2009, 57(9): 2510-2516.

[10] Tu Kun, Zhang Zhao-yang, Yao Chuang-mu,.. Rateless codes with unequal error protection based on improved weighted selection[C]. IEEE 24th International Symposium on Personal Indoor and Mobile Radio Communications (PIMRC), London, United Kingdom, 2013, 342(347): 8-11.

[11] Sorensen J H, Popovski P, and Ostergaard J. UEP LT codes with intermediate feedback[J]., 2013, 17(8): 1636-1639.

[12] Yue Jing, Lin Zi-huai, Ba Bao-ming,.. Performance analysis of unequal error protection distributed network coding based on fountain codes[J]., 2014, 3(3): 285-288.

[13] Mahyar Shirvanimoghaddam, Li Yong-hui, and Branka Vucetic. Analog fountain codes with unequal error protection[C]. Proceedings of the IEEE International Conference on Communications (ICC), Sydney, NSW, Australia, 2014: 2033-2038.

[14] Hussain I, Xiao M, and Rasmussen L K. Error floor analysis of LT codes over the additive white Gaussian noise channel[C]. Proceedings of the IEEE Global TelecommunicationsConference, Houston, USA, 2011: 1-5.

[15] Hussain I, Xiao M, and Rasmussen L K. Unequal error protection of LT codes over noisy channels[C]. Proceedings of the IEEE Communication Technologies Workshop (Swe- CTW), Lund, Sweden, 2012: 24-26.

[16] Garcia-Frias J and Zhong W. Approaching Shannon performance by iterative decoding of linear codes with low-density generator matrix[J]., 2003, 7(6): 266-268.

[17] Hussain I, Xiao M, and Rasmussen L K. Regularized variable-node LT codes with improved erasure floor performance[C]. Proceedings of the IEEE Information Theory and Applications (ITA) Workshop, San Diego, USA, 2013: 1-8.

[18] Hussain I, Xiao M, and Rasmussen L K. Serially concatenated LT code with DQPSK modulation[C]. Proceedings of the IEEE Wireless Communication and Networking Conference (WCNC), Cancun, Mexico, 2011: 1811-1816.

Novel Scheme of Unequal Error Protection Based on Regularized Variable-node and Expanding Window Fountain Codes

Huang Tai-qi Yi Ben-shun Yao Wei-qing Fang Hua-meng Li Wei-zhong

(,,430072,)

A novel scheme named EWF-RLT codes, which producesUnequal Error Protection (UEP) for Luby Transform (LT) codes over Additive White Gaussian Noise (AWGN) channel by using a windowing technique before regularizing variable-node distribution, is proposed in this paper. Firstly, the idea of “windowing” the data sets according to their protection requirements is applied to allow coded symbols to make more edge connections with more important parts of the information bit stream with high probability. Then, variable-node degree distribution is exploited to improve the error floor and ensure the more important class of information bit stream have a higher minimum variable-node degree by modifying the traditional method of choosing neighbor nodes randomly in encoding. Compared with the conventional UEP scheme, what is confirmed both theoretically and experimentally is that the proposed approach can provide significant performance improvement in themost important bits class and improve network transmission performance. Furthermore, the proposed scheme introduces additional parameters in the UEP LT code design, making it more general and flexible in terms ofthe realization of UEP scheme.

Fountain codes; Additive White Gaussian Noise (AWGN) channel; Unequal Error Protection (UEP); Expanding Window Fountain (EWF); Regularize variable-node

TN911.22

A

1009-5896(2015)08-1931-06

10.11999/JEIT141530

易本順 yibs@whu.edu.cn

2014-12-02收到，2015-03-09改回，2015-06-09網絡優先出版

國家自然科學基金(61371125)資助課題

黃太奇： 男，1988年生，博士生，研究方向為無線通信、多媒體網絡通信.

易本順： 男，1965年生，教授，博士生導師，主要從事多媒體網絡通信、信源信道編碼、無線通信等方面的研究.

姚渭箐： 女，1983年生，博士生，研究方向為無線通信、信源信道編碼.