一種基于互信息最大化的Raptor碼優(yōu)化設(shè)計方法

楊 瑋, 趙彥曉, 姚博旭

(北京信息科技大學(xué)信息與通信工程學(xué)院，北京 100101)

信道編碼是提高信息傳輸可靠性的重要手段之一，通過對發(fā)送信息進(jìn)行抗干擾處理來降低誤碼率，提高通信質(zhì)量。針對大規(guī)模網(wǎng)絡(luò)數(shù)據(jù)分發(fā)和可靠傳輸，研究者提出了一種新的信道編碼方法——噴泉碼，它具有線性的編譯碼復(fù)雜度，信道容量接近香農(nóng)極限[1]。最初設(shè)計噴泉碼主要針對刪除信道，尤其是廣播信道，近年來，噴泉碼在無線衰落噪聲信道中的性能也得到了廣泛關(guān)注和深入研究[1-4]。無線通信信道具有不同的衰落特性、存在各種固有的噪聲，而研究表明噴泉碼在這些信道中性能優(yōu)越。由于噴泉碼的優(yōu)越性能，其應(yīng)用已經(jīng)從應(yīng)用層擴(kuò)展到物理層上，在多源下載、無線協(xié)作等網(wǎng)絡(luò)通信中都已有應(yīng)用[1]。

Raptor碼是一種級聯(lián)結(jié)構(gòu)、性能優(yōu)良的噴泉碼，由高效率的預(yù)編碼和LT(luby transform)編碼兩部分組成，對信道有較強(qiáng)的適應(yīng)性[5]。使用高效率的糾錯碼作為外碼(預(yù)編碼)，可以保證Raptor碼在低復(fù)雜度下仍具有良好的糾錯能力；以平均度數(shù)較小的弱LT碼作為內(nèi)碼，則保證Raptor碼具有噴泉碼的特性，例如，實(shí)時碼率調(diào)節(jié)、可生成無限編碼包等[5]。通過利用外碼的糾錯能力，Raptor碼可以恢復(fù)傳統(tǒng)LT碼無法恢復(fù)的信息，降低誤比特率，因此這種級聯(lián)編碼的方式有效解決了LT碼編譯碼復(fù)雜度和可靠性之間的矛盾。文獻(xiàn)[6-7]研究IEEE 802.16e(Wi-Max)標(biāo)準(zhǔn)中采用Raptor碼，并在高斯白噪聲信道(additive white Gaussian noise, AWGN)下進(jìn)行誤碼性能分析，結(jié)果表明：Raptor碼有更好的突發(fā)錯誤消除能力，編碼方法簡單，硬件實(shí)現(xiàn)成本低，可以很好地改善錯誤平層問題，但譯碼的復(fù)雜度相對較高。文獻(xiàn)[8]研究了中等長度消息塊的物理層Raptor編碼，以實(shí)現(xiàn)低譯碼復(fù)雜度，吞吐量略有下降；文獻(xiàn)[9]提出了一種基于DDE(discretized density evolution)的Raptor碼優(yōu)化方法，在不同的碼率下提高信道容量。

近年來，研究者將Raptor碼應(yīng)用于衛(wèi)星通信實(shí)現(xiàn)大容量文件的高效率傳輸[10],在中繼信道傳輸優(yōu)化中也采用Raptor碼提高信道容量利用率和信息的可靠傳輸[11],在P2P流媒體應(yīng)用中基于Raptor碼來實(shí)現(xiàn)穩(wěn)定的視頻流服務(wù)[12]，以及基于Raptor碼的適用于無線網(wǎng)絡(luò)中視頻廣播通信的應(yīng)用層前向糾錯方案等[13]。

在對Raptor碼的優(yōu)化設(shè)計中，多以最大化碼率來設(shè)計校驗(yàn)節(jié)點(diǎn)度分布，從而達(dá)到信道容量，但是這種設(shè)計沒有考慮迭代譯碼的收斂速度，要達(dá)到預(yù)期性能需要很多次迭代，復(fù)雜度較高。文獻(xiàn)[14]證明了在譯碼迭代復(fù)雜度和容量逼近香農(nóng)極限之間折中的可行性；文獻(xiàn)[15]采用外部信息轉(zhuǎn)移圖EXIT(extrinsic information transfer)，對二進(jìn)制對稱信道下的LDPC碼進(jìn)行了漸進(jìn)收斂分析，并給出了譯碼迭代次數(shù)最小的LDPC碼，相比一般LDPC碼能夠減少40%的譯碼迭代次數(shù)；文獻(xiàn)[16]基于EXIT圖的漸進(jìn)收斂分析，在給定碼率約束下，得出譯碼復(fù)雜度與譯碼迭代次數(shù)之間的關(guān)系，并在此基礎(chǔ)上優(yōu)化譯碼復(fù)雜度，進(jìn)而得到度分布的優(yōu)化設(shè)計，可以有效降低誤碼率，但沒有考慮性能損失。

為了解決Raptor譯碼迭代次數(shù)過多的問題，本文提出了基于互信息最大化的Raptor碼設(shè)計，利用EXIT圖進(jìn)行漸進(jìn)收斂分析，并對迭代次數(shù)進(jìn)行約束，優(yōu)化編碼校驗(yàn)節(jié)點(diǎn)的度分布，使互信息最大化。該設(shè)計相比于其他優(yōu)化方法，迭代譯碼次數(shù)更少，復(fù)雜度更低。

1 Raptor碼的EXIT圖分析

Brink[17]在1999年首次提出了基于互信息計算的外部信息轉(zhuǎn)移圖(EXIT)，可以用來分析級聯(lián)碼迭代譯碼算法的收斂性[18-19]。EXIT 圖計算精度高并且很實(shí)用，可以跟蹤譯碼迭代過程中互信息的更新，可以較好地分析譯碼器的收斂性能，因此被廣泛應(yīng)用于對譯碼問題的研究。

Raptor碼在刪除信道的譯碼判決采用的是有錯誤就丟棄的方式，但這種方式并不適用于噪聲信道和衰落信道，此時譯碼算法采用的是增量冗余譯碼機(jī)制，即當(dāng)譯碼不成功時，接收端則繼續(xù)接收冗余信息進(jìn)行譯碼，為了提高譯碼成功率，就需要進(jìn)行多次的迭代譯碼。因此，迭代譯碼和增量冗余機(jī)制使得Raptor碼的譯碼不僅需要很多次迭代，而且迭代時延較大。針對這種情況，可以使用EXIT圖來跟蹤譯碼迭代過程中的互信息，來判定迭代譯碼是否收斂和大致收斂范圍。Raptor碼的迭代譯碼是通過兩類譯碼器之間進(jìn)行外部信息傳遞實(shí)現(xiàn)的，譯碼器結(jié)構(gòu)如圖1所示。

圖1 Raptor碼譯碼器結(jié)構(gòu)Fig.1 Structure of Raptor decoder

Raptor碼的譯碼器有兩個部分：變量節(jié)點(diǎn)譯碼器VND(variable node decoder)、校驗(yàn)節(jié)點(diǎn)譯碼器CND(check node decoder)，對應(yīng)兩類EXIT曲線：IE,VND-IA,VND和IA,CND-IE,CND曲線[20]。當(dāng)信源等概時，采用文獻(xiàn)[21]的研究方法，可以得到Raptor碼內(nèi)碼的兩條EXIT曲線對應(yīng)的函數(shù)表達(dá)式：

(1)

(2)

式中：i為變量節(jié)點(diǎn)的度；j為校驗(yàn)節(jié)點(diǎn)的度；ρj表示校驗(yàn)節(jié)點(diǎn)的度分布概率；IE,VND表示變量節(jié)點(diǎn)的輸出互信息；IA,VND表示其先驗(yàn)輸入互信息；IE,CND表示校驗(yàn)節(jié)點(diǎn)的輸出互信息；IA,CND表示其先驗(yàn)輸入互信息；J(·)為傳輸?shù)姆柵c接收符號(log likelihood ratio，LLR)之間的互信息：

(3)

式(3)中：J(·)是定義在[0,+∞)上的連續(xù)單調(diào)遞增函數(shù)，其中J(0)=0，J(+∞)=1，且存在反函數(shù)。Raptor碼內(nèi)碼的EXIT圖，是將IA,CND、IE,VND作為橫坐標(biāo)，IE,CND、IA,VND作為縱坐標(biāo)，分別繪制的兩條曲線，如圖2所示，當(dāng)CND的EXIT曲線位于VND的EXIT曲線上方且不能相交時，才能正確譯碼。

圖2 Raptor碼的EXIT圖Fig.2 Exit graph of Raptor code

2 Raptor碼的編碼度分布設(shè)計

下面首先介紹以最大化碼率為目標(biāo)的Raptor碼設(shè)計方法，然后給出本文提出的基于互信息最大化的Raptor碼優(yōu)化設(shè)計方法。

2.1 最大化碼率的設(shè)計

(4)

s.t.IE,CND>IA,VND

(5)

式(5)中：第一個約束條件表明校驗(yàn)節(jié)點(diǎn)的輸出互信息要大于變量節(jié)點(diǎn)的先驗(yàn)輸入互信息，才能成功譯碼。第二個約束條件表明至少有一個校驗(yàn)節(jié)點(diǎn)的度為1，這是LT譯碼的開始條件。約束條件是線性的，屬于線性規(guī)劃問題，任何線性規(guī)劃問題都是凸優(yōu)化問題。求解式(5)可以使用MATLAB軟件的CVX工具箱，得到最大化碼率設(shè)計的校驗(yàn)節(jié)點(diǎn)度分布。在噪聲標(biāo)準(zhǔn)差為σ=0.67的AWGN信道下，最大化碼率優(yōu)化的校驗(yàn)節(jié)點(diǎn)度分布為

ρ(x)=0.052 296+0.786 032x+0.161 672x19

(6)

最大化碼率Raptor碼的碼字性能與碼長和譯碼迭代次數(shù)有關(guān)，當(dāng)碼長越長或者迭代次數(shù)越多性能才會越好，所以譯碼復(fù)雜度較高。在實(shí)際應(yīng)用中，由于碼長和譯碼迭代次數(shù)不可能趨于無限，所以理論上的最大碼率無法實(shí)現(xiàn)。

2.2 最大化互信息的設(shè)計

在實(shí)際應(yīng)用中，譯碼的迭代次數(shù)常受到限制，可以考慮在有限次譯碼迭代的約束下優(yōu)化誤碼率(BER)性能。本文設(shè)計的最大化互信息Raptor碼就是在譯碼迭代次數(shù)的約束下進(jìn)行優(yōu)化得到的，基本思路是：通過分析EXIT圖找出迭代收斂的大致范圍，得到校驗(yàn)節(jié)點(diǎn)度分布的數(shù)學(xué)模型，求解該模型就可以得到一種在有限迭代次數(shù)下的校驗(yàn)節(jié)點(diǎn)度分布。

文獻(xiàn)[22]給出Raptor碼內(nèi)碼在進(jìn)行L次迭代后的平均BER為

(7)

式(7)中：Q(·)定義為

(8)

y(L)=f(x(L))，x(L)=w(y(L-1))

(9)

y(L)=RL(y(0))=RL[f(0)]

(10)

式(10)中：R(y)=f[w(y)]，在y=f[w(y)]=R(y)時，譯碼器會在這個點(diǎn)收斂。所以，優(yōu)化問題轉(zhuǎn)換為固定譯碼迭代次數(shù)下，最大化校驗(yàn)節(jié)點(diǎn)的輸出互信息，具體如下：

s.t.IE,CND>IA,VND

(11)

通過上述分析可知，所有約束條件都是校驗(yàn)節(jié)點(diǎn)度ρi的線性函數(shù)。對于任意的L，都可以通過求解線性規(guī)劃得到優(yōu)化的校驗(yàn)節(jié)點(diǎn)度分布，求解式(11)也選擇使用MATLAB的CVX工具箱。選取信道容量為C=3/4bit/symbol的BIAWGN信道作為傳輸信道，最大化互信息傳遞在不同譯碼迭代次數(shù)限制下的校驗(yàn)節(jié)點(diǎn)度分布如表1所示。

表1 最大化互信息的校驗(yàn)節(jié)點(diǎn)度分布

3 性能仿真分析

在噪聲標(biāo)準(zhǔn)差為σ=0.67的BIAWGN信道下進(jìn)行仿真，將未優(yōu)化Raptor碼、采用BIAWGN最大化碼率優(yōu)化Raptor碼和最大化互信息優(yōu)化Raptor碼進(jìn)行性能比較，得到誤碼率隨信噪比變化曲線，如圖3所示。其中，預(yù)編碼碼率都采用1/2；采用最大化碼率優(yōu)化設(shè)計Raptor碼和最大化互信息優(yōu)化Raptor碼時，最大譯碼迭代次數(shù)均設(shè)定為20；選取的未優(yōu)化Raptor碼中LT編碼采用度分布：

ρ(x)=0.007 696x+0.492 57x2+0.166 22x3+0.072 646x4+0.082 558x5+0.056 058x8+

0.037 229x9+0.055 59x19+0.025 023x65+0.000 313 5x66

(12)

從圖3可以看到，最大化互信息Raptor碼的性能明顯優(yōu)于其他兩種Raptor碼。當(dāng)誤碼率達(dá)到10-5時，采用最大化碼率Raptor碼和最大化互信息Raptor碼能使系統(tǒng)性能分別提高約0.35、0.6 dB。由于最大化碼率優(yōu)化Raptor碼的前提是碼長足夠長或者譯碼迭代次數(shù)足夠大，當(dāng)?shù)螖?shù)很大時，譯碼復(fù)雜度就會很高，不能滿足低復(fù)雜度、高可靠性傳輸系統(tǒng)的性能需求。

圖3 三種Raptor碼性能比較Fig.3 Performance comparison of three Raptor codes

圖4為在不同迭代次數(shù)下，最大化碼率Raptor碼與最大化互信息Raptor碼的性能對比圖。仿真結(jié)果表明：①在相同信道條件下，隨著譯碼迭代次數(shù)增加，系統(tǒng)誤碼率減??；②當(dāng)譯碼迭代次數(shù)一定時，最大化互信息Raptor碼的性能優(yōu)于最大化碼率Raptor碼，而且當(dāng)?shù)螖?shù)比較少時，性能優(yōu)勢明顯，隨著迭代次數(shù)增加，優(yōu)勢逐漸減小，這是因?yàn)橄闰?yàn)信息越來越可靠，譯碼逐漸收斂；③在滿足一定誤碼性能(10-5)時，當(dāng)?shù)螖?shù)為20次時，相比最大化碼率，最大化互信息Raptor碼能使系統(tǒng)性能提升約0.25 dB；當(dāng)?shù)螖?shù)為50次時，最大化互信息Raptor碼能使系統(tǒng)性能提升約0.1 dB。

圖4 最大化碼率Raptor碼與最大化互信息Raptor碼的性能對比Fig.4 Performance comparison between maximum rate and maximum mutual information Raptor code

4 結(jié)論

研究了高斯白噪聲信道下，Raptor碼編碼校驗(yàn)節(jié)點(diǎn)度分布的優(yōu)化設(shè)計方法。利用EXIT圖進(jìn)行漸進(jìn)收斂分析，得到編碼校驗(yàn)節(jié)點(diǎn)度分布的數(shù)學(xué)模型，通過求解該線性規(guī)劃問題，分別獲得最大化碼率和最大化互信息優(yōu)化設(shè)計的校驗(yàn)節(jié)點(diǎn)度分布，從而設(shè)計性能較好的Raptor碼。

最大化互信息設(shè)計的校驗(yàn)節(jié)點(diǎn)度分布是在固定譯碼迭代次數(shù)下進(jìn)行的，因此該優(yōu)化方案可為要求低譯碼復(fù)雜度的系統(tǒng)提供技術(shù)參考。仿真結(jié)果表明，當(dāng)譯碼迭代次數(shù)一定時，與最大化碼率設(shè)計的Raptor碼相比，最大化互信息設(shè)計的Raptor碼的誤碼性能更好，并且在較小的譯碼迭代次數(shù)情況下，優(yōu)勢更為明顯。