基于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。可单独计算出

Gp1=Φ-1(-FT-1A+C),Gp1即为p1的生成矩阵,然后根据pT1=Gp1•sT,可求得校验向量p1。再对所有的i∈[1, m-g],从小到大依次利用迭代方程

p2(i)=∑n-mj=1hi,j•sj+∑gj=1hi,j+n-m•p1(i)+∑i-1j=1hi,j+n-m+g•p2(i)求得p2。

图1 近似下三角形式校验矩阵

实际使用的LDPC码校验矩阵不一定都是直接支持快速编码的近似下三角形式,这可以通过联合可逆行变换算法变换得到[6]。

在实际编码中,先根据校验矩阵计算出Gp1,然后利用Matlab的矩阵运算,根据pT1=Gp1•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计算出相应的对数似然信息Rij(l)并传递给相邻的变量节点j;每个变量节点j也计算出相应的信息Qij(l)并传递给相邻的校验节点i,其中l为迭代次数[9]。

图2 迭代译码算法示意图

相应的迭代公式可表示为:

Qij(l)=fj, l=0

fj+∑k≠i,k∈M(j)Rkj(l-1),l>0

(1)

tanh(Rij(l)/2)=∏k≠j,k∈N(i)tanh(Qik(l)/2)

(2)

每次迭代过后,进行码比特判决,得到X′,若HT•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及Rij(l),Qij(l)都只在边上传递,因此只需要根据每条边来计算,而边的总数等于H矩阵里1的总数。为便于计算,fj及Rij(l),Qij(l)都按J中的边顺序排列存储,此时,查找J即可得到信息节点所在的列位置。计算Rij(l)的传递时,根据R可知与某校验该节点相连的信息节点的个数,从而在K中取出对应的信息节点在J中的排列位置;计算Qij(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.