基于改進型UMP BP-Based算法的LDPC譯碼研究

張天瑜

(無錫市廣播電視大學 機電工程系，江蘇 無錫 214011)

在研究Turbo碼的譯碼過程中，MacKay、Neal和Wiberg等人發現Gallager早在1962年提出的低密度校驗LDPC(Low-Density Parity-Check)碼是一種性能卓越具有漸進特性的非常好碼，在加性高斯白噪聲AWGN(Additive White Gaussian Noise)信道下的譯碼性能可以逼近Shannon信道容量的極限。由于LDPC碼的校驗矩陣為稀疏矩陣，實現譯碼的復雜度比Turbo碼要低，在中長碼長時的譯碼性能超過Turbo碼，能夠實現并行譯碼以及具有譯碼錯誤可檢測的特點，并且比Turbo碼更適合于高速無線數據業務，因此已逐漸被IEEE802.3an、IEEE 802.16e等標準所采納。目前在國外LDPC碼在下一代衛星數字視頻廣播標準DVB-S2(Digital Video Broadcasting-Satellite Second Generation)以及下一代移動通信LTE中得到了廣泛的應用。在國內，中國移動多媒體廣播 CMMB(ChinaMobileMultimediaBroadcasting)的信道編碼技術的一個亮點就是采用了LDPC編碼方案[1-7]。本文提出一種改進型UMP BP-Based譯碼算法，利用最小均方誤差準則來計算該算法中的參數，能夠在一定程度上彌補UMP BP-Based譯碼算法的性能缺陷。

1 LDPC碼簡介

LDPC碼一般是用Tanner圖來表示，Tanner圖中的變量節點和校驗節點對應于LDPC碼校驗矩陣H的列和行，Tanner圖中的連線對應于LDPC碼校驗矩陣H的非零元素。校驗矩陣H中每行非零元素的個數稱為行重，每列非零元素的個數稱為列重，所有行重相等并且所有列重也相等的碼稱為規則LDPC碼；否則，稱為非規則LDPC碼。設LDPC碼的校驗矩陣為H如式(1)所示。根據H矩陣得到與之對應的Tanner圖，如圖1所示。圖中 C1～C6表示校驗節點，B1～B9表示變量節點。

圖1 H矩陣對應的Tanner圖

由于非規則LDPC碼的行重和列重不相等，因此在其對應的Tanner圖中變量節點和校驗節點的度數也就不完全相等，非規則LDPC碼的譯碼性能較規則LDPC碼的譯碼性能要高。這里節點的度數是指與該節點相連接的邊的條數。為了表示非規則LDPC碼，分別用序列λ=（λ1，λ2，…，λdv）和 ρ=（ρ1，ρ2，…，ρdc）表示變量節點和校驗節點的邊次數分布，其中，λi和 ρi分別表示 Tanner圖中度數為i的變量節點和校驗節點的邊數在總邊數中所占的比例，這里的下標dv和dc分別表示變量節點和校驗節點的最大度數。非規則LDPC碼的變量節點和校驗節點的邊次數分布除了用上述的序列表示之外，還可以表示為：

2 UMP BP-Based譯碼算法

UMP BP-Based譯碼算法和LLR BP譯碼算法的原理是相同的，都是通過迭代計算出校驗節點和變量節點之間傳遞的信息，然后根據這些信息進行判決[8-12]?；贖矩陣的UMP BP-Based譯碼算法的原理圖如圖2所示。

設編碼器的輸出碼字為 c=(c1，c2，…，cn)，通過二進制相移鍵控BPSK(Binary Phase Shift Keying)調制后變為xi=2ci-1，經過AWGN信道，譯碼器的輸入序列為r=(r1，r2，…，rn)，其中，ri=2ci-1+ni，ni為均值為 0、方差為σ2的高斯白噪聲。設N(m)={n|Hmn=1}為所有與校驗節點Cm相連的變量節點；M(n)={m|Hmn=1}為所有與變量節點Bn相連的校驗節點；N(m) 表示 N(m)中除去變量節點Bn所剩下的變量節點的集合；M(n)m表示M(n)除去校驗節點 Cm所剩下的校驗節點的集合；qij(b)，b=0，1表示變量節點i傳遞給校驗節點j的外部概率信息；rji(b)，b=0，1表示校驗節點j傳遞給變量節點i的外部概率信息。UMP BP-Based譯碼算法的具體步驟如下：

圖2 基于H矩陣的UMP BP-Based譯碼算法的原理圖

(1)初始化

計算信道傳遞給變量節點的初始概率似然比信息L(Pi)，i=1，2，…，n。 對于變量節點 i以及與其相鄰的校驗節點j∈M(i)而言，在AWGN信道中得到變量節點傳遞給校驗節點的初始信息為：

(2)節點信息的迭代處理

①校驗節點的信息傳遞

對所有的校驗節點j以及與其相鄰的變量節點i∈N(j)，在第k次迭代中，變量節點傳遞給校驗節點的信息為：

②變量節點的信息傳遞

對所有的變量節點i以及與其相鄰的校驗節點j∈M(i)，在第k次迭代中，校驗節點傳遞給變量節點的信息為：

(3)判決譯碼

對所有的變量節點計算判決信息：

(4)停止

3 改進型UMP BP-Based譯碼算法

在LLR BP譯碼算法中，變量節點傳遞給校驗節點的信息為：

這樣就得到式(5)所描述的UMP BP-Based譯碼算法。由于是利用式(10)來近似代替式(9)，本文可以大大簡化運算，但是兩者之間的誤差將導致譯碼性能有所下降。為了減少這種誤差，通常采用Normalized BP-Based譯碼算法和Offset BP-Based譯碼算法。Normalized BPBased譯碼算法是通過引入歸一化因子來減小誤差，而Offset BP-Based譯碼算法是通過引入偏移因子來減小誤差。這兩種譯碼算法雖然能在一定程度上減小了誤差，但是誤差減小的程度有限，并且引入的因子只能通過仿真確定，具有偶然性。

本文提出一種改進型UMP BP-Based算法，利用最小均方誤差準則，通過引入參數 α、β、γ使得校驗節點的信息的均方誤差最小。為了敘述方便，將式(5)記為L2，式(9)記為 L1，改進型 UMP BP-Based算法中校驗節點的信息記為L3。這里用含有L2的表達式來表示L3，即設定|L3|=α+β|L2|+γ|L2|2，通過改變參數 α、β、γ，使得|L3|和|L1|的均方誤差最小。 設 g(α，β，γ)為 L3和 L1的均方誤差，則：

為了求出參數 α、β、γ，使得 g(α，β，γ)達到最小值，分別對式(11)中的 α、β、γ 求偏導數：

將式(11)代入式(12)，可得：

4 仿真實驗與結果分析

首先在Matlab軟件中構造碼長為1 806、碼率為1/2、列重為3、行重為3的規則LDPC碼，即變量節點的度數為 3，校驗節點的度數也為 3，λ(x)=ρ(x)=x2。 采用BPSK調制，經過AWGN信道，每次譯碼算法中的最大迭代次數都設置為80次，然后通過蒙特卡羅算法求解出式(15)中相關參數的數學期望 E[·]，通過仿真得到 α=212.32，β=0.93，γ=0.12。 改進型 UMP BP-Based譯碼算法以及UMP BP-Based譯碼算法、NormalizedBP-Based譯碼算法和OffsetBP-Based譯碼算法的性能曲線如圖3所示。

圖3 4種譯碼算法的性能比較曲線

從圖3可以看出，在相同誤碼率BER(Bit Error Rate)(BER=10-5)的情況下，改進型UMP BP-Based譯碼算法的信噪比 SNR(Signal-to-Noise Ratio)比 UMP BP-Based譯碼算法的SNR節省將近0.4 dB，比Normalized BPBased譯碼算法和Offset BP-Based譯碼算法的SNR分別節省0.1 dB和0.2 dB。由此說明改進型UMP BP-Based譯碼算法在上述的4種譯碼算法中具有更好的性能。

由于UMP BP-Based譯碼算法中校驗節點的信息傳遞公式是對LLR BP算法中校驗節點的信息傳遞公式的近似，所以UMP BP-Based譯碼算法的性能在一定程度上有所下降。本文提出一種改進型UMP BP-Based譯碼算法，該算法的創新之處在于，利用最小均方誤差準則推導出了一個更加近似的公式，能夠進一步降低由于近似計算帶來的誤差，并且對所有的LDPC碼的譯碼具有通用性。這在LDPC碼的應用領域，具有一定的實用價值。

[1]YANG K， FELDMAN J， WANG X D.Nonlinear programming approaches to decoding low-density parity-check codes[J].IEEE Journal on Selected Areas in Communications， 2006，24(8)∶1603-1613.

[2]SWAMY R， BATES S， BRANDON T L， et al.Design and test of a 175-Mb/s， rate-1/2(128，3，6)low-density paritycheck convolutional code encoder and decoder[J].IEEE Journal of Solid-State Circuits， 2007，42(10)∶2245-2256.

[3]LIU L， SHI C J R.Sliced message passing∶high through-put overlapped decoding of high-rate low-density paritycheck codes[J].IEEE Transactions on Circuits and Systems I∶Regular Papers， 2008，55(11)∶3697-3710.

[4]HONG S N， KIM S， SHIN D J， et al.Quasi-cyclic lowdensity parity-check codes for space-time bit-interleaved coded modulation[J].IEEE Communications Letters， 2008，12(10)∶767-769.

[5]CHEN H Y， LIN M C， UENG Y L.Low-density paritycheck coded recording systems with run-length-limited constraints[J].IEEE Transactions on Magnetics， 2008，44(9)∶2235-2242.

[6]GONG C， LIU Q， CUI H J， et al.Switch-type hybrid hard decision decoding algorithms for regular low-density parity-check codes[J].IEEE Transactions on Information Theory， 2008，54(7)∶3181-3188.

[7]RAZAGHI P，YU W.Bilayer low-density parity-check codes for decode-and-forward in relay channels[J].IEEE Transactions on Information Theory， 2007，53(10)∶3723-3739.

[8]PISHRO-NIK H，FEKRI F.Results on punctured lowdensity parity-check codes and improved iterative decoding techniques[J].IEEE Transactions on Information Theory，2007，53(2)∶599-614.

[9]HONARY B， MOINIAN A， AMMAR B.Construction of well-structured quasi-cyclic low-density parity check codes[J].IEE ProceedingsofCommunications， 2005，152(6)∶1081-1085.

[10]SADEGHI M R， BANIHASHEMI A H， PANARIO D.Low-density parity-check lattices∶construction and decoding analysis[J].IEEE Transactions on Information Theory，2006，52(10)∶4481-4495.

[11]KIM N， KIM J， PARK H， et al.An improvement of UMP-BP decoding algorithm using the minimum mean square error linear estimator[J].ETRI Journal，2004，26(5)∶432-436.

[12]KIM N，PARK H.Modified UMP-BP decoding algorithm based on mean square error[J].Electronics Letters，2004， 40(13)∶816-817.