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

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

關(guān)鍵詞:低密度奇偶校驗(yàn)碼; Matlab; 快速仿真; 快速編碼算法

中圖分類號:TN911.22 文獻(xiàn)標(biāo)識碼: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碼是一類可以用非常稀疏的校驗(yàn)矩陣H或二分圖來描述的線性分組糾錯(cuò)碼[1]，在基于置信傳播的迭代譯碼條件下具有逼近Shannon極限的性能[2-3]。LDPC碼因優(yōu)異的性能成為近年信道編碼研究的熱點(diǎn)，眾多學(xué)者提出了各自的構(gòu)造法用于構(gòu)造各有特色的LDPC碼[4]。在研究LDPC碼的過程中，需要對構(gòu)建的LDPC碼進(jìn)行仿真，獲知其在不同信道下的性能。實(shí)用的LDPC碼往往具有較大規(guī)模的校驗(yàn)矩陣，并且對應(yīng)的生成矩陣不再是稀疏矩陣，按分組碼的矩陣相乘方式進(jìn)行編碼運(yùn)算量較大。在迭代譯碼過程中，因需要計(jì)算二分圖上眾多節(jié)點(diǎn)之間的信息傳遞，以及進(jìn)行迭代結(jié)束判決，需要進(jìn)行大量的循環(huán)及運(yùn)算。Matlab平臺是進(jìn)行通信算法仿真的一個(gè)良好平臺，但LDPC碼的編解碼涉及到大量的循環(huán)及運(yùn)算，直接用Matlab的M語言實(shí)現(xiàn)仿真速度較慢，如何在Matlab平臺上實(shí)現(xiàn)快速的LDPC碼編解碼算法，進(jìn)行快速的LDPC碼仿真，具有比較重要的應(yīng)用意義。

1 快速編碼算法

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

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

Gp1=Φ-1(-FT-1A+C)，Gp1即為p1的生成矩陣，然后根據(jù)pT1=Gp1#8226;sT，可求得校驗(yàn)向量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 近似下三角形式校驗(yàn)矩陣

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

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

因?yàn)榈蠼鈖2時(shí)需要依次使用到H矩陣從第1行開始的m-g行，而H矩陣本身為稀疏矩陣，里面為1的元素很少，為進(jìn)一步提高速度，減少算法查找非零元素的時(shí)間，先將H矩陣的前m-g行按行順序?qū)⑿兄性?的列位置查找出來，構(gòu)成一維矩陣序列V，并將其作為參數(shù)傳遞給迭代求解函數(shù)。迭代時(shí)每求解一個(gè)p2校驗(yàn)位，依次取出V序列里的元素，得到對應(yīng)行中元素1的列位置，然后將該位置的s信息向量位或p1校驗(yàn)向量位進(jìn)行GF(2)上的模2累加(可用異或?qū)崿F(xiàn))，直到取出的列位置到達(dá)當(dāng)前計(jì)算的p2校驗(yàn)位列位置為止，此時(shí)的模2累加值即為當(dāng)前計(jì)算的p2校驗(yàn)位的值，然后開始下一個(gè)p2校驗(yàn)位的計(jì)算。使用此算法，迭代時(shí)無需在整行中查找1的列位置，而直接從V序列中獲得對應(yīng)行中的1的列位置，因而可以減少循環(huán)查找次數(shù)，提高速度。

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

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

圖2 迭代譯碼算法示意圖

相應(yīng)的迭代公式可表示為:

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)

每次迭代過后，進(jìn)行碼比特判決，得到X′，若HT#8226;X′=0或者迭代次數(shù)到達(dá)最大迭代次數(shù)則結(jié)束，否則再次進(jìn)行迭代。

迭代譯碼涉及到大量的循環(huán)，因此該過程同樣用C語言進(jìn)行編寫。在迭代過程當(dāng)中，需要查找每個(gè)信息節(jié)點(diǎn)所連接的校驗(yàn)節(jié)點(diǎn)及每個(gè)校驗(yàn)節(jié)點(diǎn)連接的信息節(jié)點(diǎn)，如果每次都根據(jù)H矩陣的一行或一列來進(jìn)行搜索，將會耗費(fèi)大量的查找時(shí)間，所以設(shè)計(jì)了如下優(yōu)化的數(shù)據(jù)結(jié)構(gòu)及實(shí)現(xiàn)方法，便于快速查找相連的節(jié)點(diǎn):

(1) 為便于查找每個(gè)信息節(jié)點(diǎn)所連接的校驗(yàn)節(jié)點(diǎn)，先統(tǒng)計(jì)H矩陣每列1的總個(gè)數(shù)，構(gòu)成1×n的一維矩陣序列C，然后對整個(gè)H矩陣按列順序?qū)⒘兄性?的行位置查找出來，構(gòu)成一維矩陣序列J，其元素個(gè)數(shù)等于H矩陣中1的總個(gè)數(shù)，亦即二分圖中邊的總數(shù)。

(2) 為便于查找每個(gè)校驗(yàn)節(jié)點(diǎn)所連接的信息節(jié)點(diǎn)，先統(tǒng)計(jì)H矩陣每行1的總個(gè)數(shù)，構(gòu)成1×m的一維矩陣序列R，然后對整個(gè)H矩陣按行順序?qū)⑿兄性?在J的位置查找出來，構(gòu)成一維矩陣序列K。

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

3 仿 真

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

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

Eb/No /dB22.533.544.55

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

優(yōu)化算法 /s0.029 70.028 60.028 60.028 50.025 10.014 70.007 8

速度提升倍數(shù)56585858595952

4 結(jié) 語

Matlab是一個(gè)常用的通信仿真平臺，本文對在Matlab平臺上實(shí)現(xiàn)快速的LDPC碼編解碼算法，進(jìn)行快速的LDPC碼仿真進(jìn)行了研究。利用符合Matlab要求的mexFunction格式的C語言改寫編解碼算法，并優(yōu)化其中的數(shù)據(jù)結(jié)構(gòu)及實(shí)現(xiàn)方法，大幅提升了仿真速度，減小了仿真所用的時(shí)間，對進(jìn)一步研究不同LDPC碼的性能或?qū)ふ腋玫腖DPC碼具有較重要的意義。

參考文獻(xiàn)

[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ìn)及其應(yīng)用的研究[J].現(xiàn)代電子技術(shù)，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]王萼芳.高等代數(shù)教程(上)[M].北京:清華大學(xué)出版社，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].南京:南京郵電學(xué)院，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.