基于規(guī)則變量節(jié)點(diǎn)度和擴(kuò)展窗噴泉碼的不等差錯(cuò)保護(hù)算法

黃太奇 易本順 姚渭箐 方華猛 李衛(wèi)中

?

基于規(guī)則變量節(jié)點(diǎn)度和擴(kuò)展窗噴泉碼的不等差錯(cuò)保護(hù)算法

黃太奇 易本順*姚渭箐 方華猛 李衛(wèi)中

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

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

噴泉碼；加性高斯白噪聲信道；不等差錯(cuò)保護(hù)；擴(kuò)展窗噴泉碼；規(guī)則變量節(jié)點(diǎn)度

1 引言

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

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

上述算法都是基于刪余信道設(shè)計(jì)的，由于解碼方法不一樣，這些算法不能直接應(yīng)用于噪聲信道中。文獻(xiàn)[13]利用模擬噴泉碼編碼方法，實(shí)現(xiàn)了噪聲信道上的不等差錯(cuò)保護(hù)，但該方法編碼復(fù)雜度高，實(shí)際應(yīng)用中不易推廣。文獻(xiàn)[15]在文獻(xiàn)[14]的研究基礎(chǔ)上，利用規(guī)則變量節(jié)點(diǎn)度LT碼(Regularized variable-node Luby Transform, RLT)的方法，在AWGN信道上對(duì)較高重要等級(jí)數(shù)據(jù)進(jìn)行更強(qiáng)的保護(hù)，該編碼算法雖然復(fù)雜度不高，但在選擇鄰居節(jié)點(diǎn)進(jìn)行編碼時(shí)，由于采用了傳統(tǒng)的基于權(quán)重的編碼算法，因此導(dǎo)致實(shí)現(xiàn)UEP方式不夠靈活[9]。

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

2 傳統(tǒng)LT碼編譯碼算法

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

信號(hào)在AWGN信道傳輸?shù)倪^(guò)程中會(huì)受到噪聲的影響，無(wú)法保證譯碼的準(zhǔn)確性，尤其當(dāng)信道條件較差時(shí)使用硬判決會(huì)引入很多錯(cuò)誤，因此適合采用軟判決置信傳播迭代譯碼算法，以實(shí)現(xiàn)可靠譯碼。迭代過(guò)程是通過(guò)校驗(yàn)節(jié)點(diǎn)到變量節(jié)點(diǎn)以及變量節(jié)點(diǎn)到校驗(yàn)節(jié)點(diǎn)之間的信息傳遞來(lái)完成的，在第1次迭代時(shí)，除信道信息以外，其余所有似然值初始化皆為0。當(dāng)?shù)诖蔚鷷r(shí)，從校驗(yàn)節(jié)點(diǎn)到變量節(jié)點(diǎn)(信息節(jié)點(diǎn))的更新規(guī)則為

最后接收端通過(guò)似然值

來(lái)估計(jì)恢復(fù)出原始信息。

3 EWF-RLT編碼設(shè)計(jì)方案

3.1傳統(tǒng)EWF編碼算法

文獻(xiàn)[9]提出的是一種利用窗口技術(shù)實(shí)現(xiàn)UEP性能的噴泉碼設(shè)計(jì)方案，假設(shè)需要傳輸?shù)臄?shù)據(jù)是長(zhǎng)度為bit的二進(jìn)制符號(hào)，分為個(gè)不同的重要等級(jí)。按不同重要等級(jí)將這bit數(shù)據(jù)分為部分，每部分大小分別為，其中，部分為最重要等級(jí)數(shù)據(jù)，部分為次重要等級(jí)數(shù)據(jù)，依次類推，部分為第重要等級(jí)數(shù)據(jù)。

其中

圖1 EWF的編碼示意圖

其中

3.2本文EWF-RLT碼編碼設(shè)計(jì)方案

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

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

3.3本文EWF-RLT碼漸進(jìn)性能仿真

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

圖2 本文算法與傳統(tǒng)算法漸進(jìn)性能比較

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

4 實(shí)際仿真結(jié)果與分析

本節(jié)通過(guò)仿真分析本文算法在AWGN信道下的UEP性能，并與傳統(tǒng)算法進(jìn)行比較。為了便于比較分析，假設(shè)輸入的信息數(shù)據(jù)為=5000 bit且只包含兩個(gè)重要等級(jí)的數(shù)據(jù)，其中MIB數(shù)據(jù)比重為, LIB數(shù)據(jù)占整個(gè)數(shù)據(jù)的比重為，校驗(yàn)節(jié)點(diǎn)度分布參照文獻(xiàn)[18]。

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

圖3 本文算法與傳統(tǒng)算法UEP性能比較

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

5 結(jié)束語(yǔ)

本文在分析傳統(tǒng)EWF算法基礎(chǔ)上，提出了一種基于AWGN信道的不等差錯(cuò)保護(hù)方案。該方案融合了傳統(tǒng)的EWF編碼技術(shù)和RLT編碼算法，在設(shè)計(jì)UEP方案時(shí)更加靈活，能對(duì)較高重要等級(jí)數(shù)據(jù)進(jìn)行更強(qiáng)的保護(hù)。該算法首先利用EWF編碼技術(shù)，使較高重要等級(jí)的數(shù)據(jù)以更高的概率參與編碼；再結(jié)合RLT算法，使得較高重要等級(jí)的數(shù)據(jù)具有較大的最小變量節(jié)點(diǎn)，改善傳統(tǒng)UEP算法中的錯(cuò)誤平層現(xiàn)象。理論分析和仿真結(jié)果表明，在AWGN信道上，本文算法能對(duì)高重要等級(jí)數(shù)據(jù)加以更強(qiáng)的保護(hù)，可提升無(wú)線網(wǎng)絡(luò)通信質(zhì)量。

參考文獻(xiàn)

[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] 劉國(guó), 于文慧, 吳家驥, 等. 基于系統(tǒng)Raptor碼不等差錯(cuò)保護(hù)的圖像壓縮傳輸[J]. 電子與信息學(xué)報(bào), 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ī)度分布的壓縮噴泉碼[J]. 電子與信息學(xué)報(bào), 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網(wǎng)絡(luò)優(yōu)先出版

國(guó)家自然科學(xué)基金(61371125)資助課題

黃太奇： 男，1988年生，博士生，研究方向?yàn)闊o(wú)線通信、多媒體網(wǎng)絡(luò)通信.

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

姚渭箐： 女，1983年生，博士生，研究方向?yàn)闊o(wú)線通信、信源信道編碼.