一種基于互信息最大化的Raptor碼優化設計方法

楊 瑋, 趙彥曉, 姚博旭

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

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

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

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

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

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

1 Raptor碼的EXIT圖分析

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

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

圖1 Raptor碼譯碼器結構Fig.1 Structure of Raptor decoder

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

(1)

(2)

式中：i為變量節點的度；j為校驗節點的度；ρj表示校驗節點的度分布概率；IE,VND表示變量節點的輸出互信息；IA,VND表示其先驗輸入互信息；IE,CND表示校驗節點的輸出互信息；IA,CND表示其先驗輸入互信息；J(·)為傳輸的符號與接收符號(log likelihood ratio，LLR)之間的互信息：

(3)

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

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

2 Raptor碼的編碼度分布設計

下面首先介紹以最大化碼率為目標的Raptor碼設計方法，然后給出本文提出的基于互信息最大化的Raptor碼優化設計方法。

2.1 最大化碼率的設計

(4)

s.t.IE,CND>IA,VND

(5)

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

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

(6)

最大化碼率Raptor碼的碼字性能與碼長和譯碼迭代次數有關，當碼長越長或者迭代次數越多性能才會越好，所以譯碼復雜度較高。在實際應用中，由于碼長和譯碼迭代次數不可能趨于無限，所以理論上的最大碼率無法實現。

2.2 最大化互信息的設計

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

文獻[22]給出Raptor碼內碼在進行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)時，譯碼器會在這個點收斂。所以，優化問題轉換為固定譯碼迭代次數下，最大化校驗節點的輸出互信息，具體如下：

s.t.IE,CND>IA,VND

(11)

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

表1 最大化互信息的校驗節點度分布

3 性能仿真分析

在噪聲標準差為σ=0.67的BIAWGN信道下進行仿真，將未優化Raptor碼、采用BIAWGN最大化碼率優化Raptor碼和最大化互信息優化Raptor碼進行性能比較，得到誤碼率隨信噪比變化曲線，如圖3所示。其中，預編碼碼率都采用1/2；采用最大化碼率優化設計Raptor碼和最大化互信息優化Raptor碼時，最大譯碼迭代次數均設定為20；選取的未優化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碼的性能明顯優于其他兩種Raptor碼。當誤碼率達到10-5時，采用最大化碼率Raptor碼和最大化互信息Raptor碼能使系統性能分別提高約0.35、0.6 dB。由于最大化碼率優化Raptor碼的前提是碼長足夠長或者譯碼迭代次數足夠大，當迭代次數很大時，譯碼復雜度就會很高，不能滿足低復雜度、高可靠性傳輸系統的性能需求。

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

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

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

4 結論

研究了高斯白噪聲信道下，Raptor碼編碼校驗節點度分布的優化設計方法。利用EXIT圖進行漸進收斂分析，得到編碼校驗節點度分布的數學模型，通過求解該線性規劃問題，分別獲得最大化碼率和最大化互信息優化設計的校驗節點度分布，從而設計性能較好的Raptor碼。

最大化互信息設計的校驗節點度分布是在固定譯碼迭代次數下進行的，因此該優化方案可為要求低譯碼復雜度的系統提供技術參考。仿真結果表明，當譯碼迭代次數一定時，與最大化碼率設計的Raptor碼相比，最大化互信息設計的Raptor碼的誤碼性能更好，并且在較小的譯碼迭代次數情況下，優勢更為明顯。