基于Matlab平臺的LDPC碼快速仿真研究

摘 要:對提高基于Matlab平臺的低密度奇偶校驗碼的仿真速度進行了研究，為加快仿真速度，編解碼核心過程用符合mexFunction格式的C語言編寫，并針對快速編碼算法及迭代譯碼算法進行了優化，然后編譯成動態鏈接庫文件在M語言中調用。仿真結果表明，優化后的仿真速度相比優化前獲得大幅提高，平均提升了57倍。

關鍵詞:低密度奇偶校驗碼; Matlab; 快速仿真; 快速編碼算法

中圖分類號:TN911.22 文獻標識碼:A

文章編號:1004-373X(2010)09-0121-02

Fast LDPC Codec Simulation Based on Matlab Platform

LIU Ying， ZHANG Zhi-liang

(Jincheng College， Sichuan University， Chengdu 611731， China)

Abstract: Accelerating LDPC codec simulation on Matlab platform is studied. In order to make the simulation run faster， the core process of coding and decoding uses C language that conform to mexFunction format， both fast coding algorithm and iterative decoding algorithm are optimized， then compiles into a dynamic-link library file in M language. The simulation result proves that the simulation speed runs 57 times faster than the one without optimization.

Keywords: LDPC; Matlab; fast simulation; fast codec algorithm

0 引 言

LDPC碼是一類可以用非常稀疏的校驗矩陣H或二分圖來描述的線性分組糾錯碼[1]，在基于置信傳播的迭代譯碼條件下具有逼近Shannon極限的性能[2-3]。LDPC碼因優異的性能成為近年信道編碼研究的熱點，眾多學者提出了各自的構造法用于構造各有特色的LDPC碼[4]。在研究LDPC碼的過程中，需要對構建的LDPC碼進行仿真，獲知其在不同信道下的性能。實用的LDPC碼往往具有較大規模的校驗矩陣，并且對應的生成矩陣不再是稀疏矩陣，按分組碼的矩陣相乘方式進行編碼運算量較大。在迭代譯碼過程中，因需要計算二分圖上眾多節點之間的信息傳遞，以及進行迭代結束判決，需要進行大量的循環及運算。Matlab平臺是進行通信算法仿真的一個良好平臺，但LDPC碼的編解碼涉及到大量的循環及運算，直接用Matlab的M語言實現仿真速度較慢，如何在Matlab平臺上實現快速的LDPC碼編解碼算法，進行快速的LDPC碼仿真，具有比較重要的應用意義。

1 快速編碼算法

Richardson和Urbanke給出了LDPC快速編碼的方法[5]，對于圖1所示的近似下三角形式校驗矩陣，相應的碼字向量x分成三部分，x=[s p1 p2];s為原輸入的信息向量;p1，p2為校驗向量。

令Φ = -FT-1B+D，設Φ可逆，則pT1=-Φ-1(-FT-1A+C)sT。可單獨計算出

Gp1=Φ-1(-FT-1A+C)，Gp1即為p1的生成矩陣，然后根據pT1=Gp1#8226;sT，可求得校驗向量p1。再對所有的i∈[1， m-g]，從小到大依次利用迭代方程

p2(i)=∑n-mj=1hi，j#8226;sj+∑gj=1hi，j+n-m#8226;p1(i)+∑i-1j=1hi，j+n-m+g#8226;p2(i)求得p2。

圖1 近似下三角形式校驗矩陣

實際使用的LDPC碼校驗矩陣不一定都是直接支持快速編碼的近似下三角形式，這可以通過聯合可逆行變換算法變換得到[6]。

在實際編碼中，先根據校驗矩陣計算出Gp1，然后利用Matlab的矩陣運算，根據pT1=Gp1#8226;sT可求得校驗向量p1。Matlab適于作矩陣運算，但因其屬于解釋性語言，處理循環迭代速度較慢。為提高速度，p2的迭代求解使用C語言進行編寫。為使C語言編寫的函數可以在Matlab的M語言中調用，C函數需要按照Matlab要求的mexFunction格式進行編寫，再在Matlab中使用mex命令，將其編譯成動態鏈接庫dll文件供M語言中調用[7]。

因為迭代求解p2時需要依次使用到H矩陣從第1行開始的m-g行，而H矩陣本身為稀疏矩陣，里面為1的元素很少，為進一步提高速度，減少算法查找非零元素的時間，先將H矩陣的前m-g行按行順序將行中元素1的列位置查找出來，構成一維矩陣序列V，并將其作為參數傳遞給迭代求解函數。迭代時每求解一個p2校驗位，依次取出V序列里的元素，得到對應行中元素1的列位置，然后將該位置的s信息向量位或p1校驗向量位進行GF(2)上的模2累加(可用異或實現)，直到取出的列位置到達當前計算的p2校驗位列位置為止，此時的模2累加值即為當前計算的p2校驗位的值，然后開始下一個p2校驗位的計算。使用此算法，迭代時無需在整行中查找1的列位置，而直接從V序列中獲得對應行中的1的列位置，因而可以減少循環查找次數，提高速度。

2 基于置信傳播的迭代譯碼算法

LDPC碼使用基于置信傳播的迭代譯碼算法，這是其性能優異的原因之一[8]。迭代譯碼算法過程如圖2所示:首先，根據信道接收值y計算每個碼元變量的后驗概率信息，即fj = LLR(xj | yj);在之后的每一輪迭代中，每個校驗節點i計算出相應的對數似然信息Rij(l)并傳遞給相鄰的變量節點j;每個變量節點j也計算出相應的信息Qij(l)并傳遞給相鄰的校驗節點i，其中l為迭代次數[9]。

圖2 迭代譯碼算法示意圖

相應的迭代公式可表示為:

Qij(l)=fj， l=0

fj+∑k≠i，k∈M(j)Rkj(l-1)，l>0

(1)

tanh(Rij(l)/2)=∏k≠j，k∈N(i)tanh(Qik(l)/2)

(2)

每次迭代過后，進行碼比特判決，得到X′，若HT#8226;X′=0或者迭代次數到達最大迭代次數則結束，否則再次進行迭代。

迭代譯碼涉及到大量的循環，因此該過程同樣用C語言進行編寫。在迭代過程當中，需要查找每個信息節點所連接的校驗節點及每個校驗節點連接的信息節點，如果每次都根據H矩陣的一行或一列來進行搜索，將會耗費大量的查找時間，所以設計了如下優化的數據結構及實現方法，便于快速查找相連的節點:

(1) 為便于查找每個信息節點所連接的校驗節點，先統計H矩陣每列1的總個數，構成1×n的一維矩陣序列C，然后對整個H矩陣按列順序將列中元素1的行位置查找出來，構成一維矩陣序列J，其元素個數等于H矩陣中1的總個數，亦即二分圖中邊的總數。

(2) 為便于查找每個校驗節點所連接的信息節點，先統計H矩陣每行1的總個數，構成1×m的一維矩陣序列R，然后對整個H矩陣按行順序將行中元素1在J的位置查找出來，構成一維矩陣序列K。

(3) 因為fj及Rij(l)，Qij(l)都只在邊上傳遞，因此只需要根據每條邊來計算，而邊的總數等于H矩陣里1的總數。為便于計算，fj及Rij(l)，Qij(l)都按J中的邊順序排列存儲，此時，查找J即可得到信息節點所在的列位置。計算Rij(l)的傳遞時，根據R可知與某校驗該節點相連的信息節點的個數，從而在K中取出對應的信息節點在J中的排列位置;計算Qij(l)的傳遞時，根據C可知與某信息節點相連的校驗節點的個數，從而在J中直接取出對應的校驗節點。使用這種方法不用每次迭代都去查找H矩陣中的非0元素，提高了運算速度。

3 仿 真

上述的優化只是針對數據結構及有效查找節點的優化，并沒有改變迭代譯碼算法本身，在相同輸入情況下，優化算法和原始算法兩者的譯碼過程一致。為了驗證上述優化算法的速度提升，在AWGN信道上作LDPC編碼BPSK調制的仿真，LDPC碼使用Hu Xiao-Yu的PEG方法構造的PEG Reg 504×1 008正則碼[10]，譯碼最大迭代次數設定為50。表1給出了不同信噪比下仿真1 000次編譯碼的平均每次編碼譯碼時間。可見，采用本文的優化數據結構及實現方法，仿真速度平均提高了57倍。

表1 不同信噪比下平均每次編碼譯碼時間

Eb/No /dB22.533.544.55

原始算法 /s1.663 41.659 51.646 21.640 11.484 60.866 10.407 4

優化算法 /s0.029 70.028 60.028 60.028 50.025 10.014 70.007 8

速度提升倍數56585858595952

4 結 語

Matlab是一個常用的通信仿真平臺，本文對在Matlab平臺上實現快速的LDPC碼編解碼算法，進行快速的LDPC碼仿真進行了研究。利用符合Matlab要求的mexFunction格式的C語言改寫編解碼算法，并優化其中的數據結構及實現方法，大幅提升了仿真速度，減小了仿真所用的時間，對進一步研究不同LDPC碼的性能或尋找更好的LDPC碼具有較重要的意義。

參考文獻

[1]GALLAGE R G. Low-density parity-check codes[J]. IRE Trans. on Information Theory， 1962: 21-28.

[2]MACKAY D J C， NEAL R M. Near Shannon limit performance of low density parity check codes[J]. Electronics Letters， 1997， 33: 457-458.

[3]MACKAY D J C. Good error-correcting codes based on very sparse matrices[J]. IEEE Trans. on Information The-ory， 1999， 45: 399-431.

[4]翁蕓，顏珂斐，郭引川，等.LDPC碼的改進及其應用的研究[J].現代電子技術，2005，28(1):49-51，57.

[5]RICHARDSON T J， URBANKE R L. Efficient encoding of low-density parity-check codes[J]. IEEE Trans. on， Information Theory， 2001，47: 638-656.

[6]王萼芳.高等代數教程(上)[M].北京:清華大學出版社，1997.

[7]MathWorks Inc.. Matlab R13 online help[M]. [S.l.]: MathWorks Inc.， 2002.

[8]HU Xiao-Yu， ELEFTHERIOU E. ARNOLD D M， et al. Efficient implementations of the sum-product algorithm for decoding LDPC codes[C]//Global Telecommunications Conference. [S.l.]: IEEE， 2001.

[9]程敏.LDPC碼的譯碼算法的研究[D].南京:南京郵電學院，2003.

[10]HU Xiao-Yu， ELEFTHERIOU E， ARNOLD D M. Progressive edge-growth Tanner graphs[C]//Proc. of IEEE Global Telecom. Conf.. [S.l.]: IEEE， 2001.