2 　 通信与信息技术 2 2 《现代电子技术》2010 年第 9 期总第 320 期 基于 Matlab 平台的 LDPC 码快速仿真研究 刘 　英 , 张志亮 (四川大学 锦城学院 , 四川 成都 　611731) 摘 　要 :对提高基于 Matlab 平台的低密度奇偶校验码的仿真速度进行了研究 ,为加快仿真速度 ,编解码核心过程用符合 mexFunction 格式的 C 语言编写 ,并针对快速编码算法及迭代译码算法进行了优化 ,然后编译成动态链接库文件在 M 语言 中调用 。仿真结果表明 ,优化后的仿真速度相比优化前获得大幅提高 ,平均提升了 57 倍 。 关键词 :低密度奇偶校验码 ; Matlab ; 快速仿真 ; 快速编码算法 中图分类号 : TN911. 22 　　　　　文献标识码 :A 　　　　　文章编号 :1004 373X(2010) 09 0121 02 Fast LDPC Codec Simulation Based on Matlab Platform L IU Ying , ZHAN G 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 p rocess 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 p roves that the simulation speed runs 57 times faster than the one without optimization. Keywords : LDPC ; Matlab ; fast simulation ; fast codec algorithm 3 ] 。 　　LDPC 码是一类可以用非常稀疏的校验矩阵 H 或 二分图来描述的线性分组纠错码[ 1 ] ,在基于置信传播的 迭代译码条件下具有逼近 Shannon 极限的性能[ 2 LDPC 码因优异的性能成为近年信道编码研究的热点 , 众多学者提出了各自的构造法用于构造各有特色的 LDPC 码[ 4 ] 。在研究 LDPC 码的过程中 ,需要对构建的 LDPC 码进行仿真 ,获知其在不同信道下的性能 。实用 的 LDPC 码往往具有较大规模的校验矩阵 ,并且对应 的生成矩阵不再是稀疏矩阵 ,按分组码的矩阵相乘方式 进行编码运算量较大 。在迭代译码过程中 ,因需要计算 二分图上众多节点之间的信息传递 ,以及进行迭代结束 判决 ,需要进行大量的循环及运算 。Matlab 平台是进 行通信算法仿真的一个良好平台 ,但 LDPC 码的编解 码涉及到大量的循环及运算 ,直接用 Matlab 的M 语言 实现仿真速度较慢 ,如何在 Matlab 平台上实现快速的 LDPC 码编解码算法 ,进行快速的 LDPC 码仿真 ,具有 比较重要的应用意义 。 1 　快速编码算法 Richardson 和 U rbanke 给出了 LDPC 快速编码的 方法[ 5 ] ,对于图 1 所示的近似下三角形式校验矩阵 , 相 应的码字向量 x分成三部分 , x = [ s 　p1 　p2 ] ; s为原输 入的信息向量 ; p1 , p2 为校验向量 。令 Φ = - FT- 1 B + 收稿日期 :2009 12 21 D , 设Φ可逆 ,则 pT 1 = - Φ- 1 ( - FT- 1 A + C) s T 。可单独计 算出 Gp1 = Φ- 1 ( - FT- 1 A + C) , Gp1 即为 p1 的生成矩阵 , 然后根据 pT 1 = Gp1 ·s T ,可求得校验向量 p1 。再对所有 的 i ∈[1 , m - g ] ,从小到大依次利用迭代方程 p2 ( i) = hi , j ·s j + ∑ hi , j + n- m ·p1 ( i) + ∑ hi , j + n- m+ g ·p2 ( i) 求 i- 1 j = 1 n- m ∑ j = 1 得 p2 。 g j = 1 图 1 　近似下三角形式校验矩阵 实际使用的 LDPC 码校验矩阵不一定都是直接支 持快速编码的近似下三角形式 ,这可以通过联合可逆行 变换算法变换得到[ 6 ] 。 在实际编码中 ,先根据校验矩阵计算出 Gp1 , 然后 利用 Matlab 的矩阵运算 ,根据 pT 1 = Gp1 ·s T 可求得校验 向量 p1 。Matlab 适于作矩阵运算 ,但因其属于解释性 语言 ,处理循环迭代速度较慢 。为提高速度 , p2 的迭代 求解使用 C 语言进行编写 。为使 C 语言编写的函数可 以在 Matlab 的 M 语言中调用 ,C 函数需要按照 Matlab 要求的 mexFunction 格式进行编写 ,再在 Matlab 中使 用 mex 命令 ,将其编译成动态链接库 dll 文件供 M 语 121 

信 号 处 理 言中调用[ 7 ] 。 刘 　英等 :基于 Matlab 平台的 LDPC 码快速仿真研究 因为迭代求解 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 计算每个码元变量的后 验概率信息 ,即 f j = LL R ( x j | y j ) ;在之后的每一轮迭 代中 , 每个校验节点 i 计算 出相 应的 对数 似然信 息 R ij ( l) 并传递给相邻的变量节点 j ;每个变量节点 j 也计 算出相应的信息 Qij ( l) 并传递给相邻的校验节点 i , 其 中 l 为迭代次数[9 ] 。 图 2 　迭代译码算法示意图 相应的迭代公式可表示为 : Qij ( l) = f j , 　　　　　　　　　l = 0 f j + ∑ R kj ( l - 1) , l > 0 k ≠i , k ∈M ( j) k ≠j , k ∈N ( i) (2) tanh ( Qik ( l) / 2) tanh ( Rij ( l) / 2) = ∏ 　　每次迭代过后 ,进行码比特判决 , 得到 X′, 若 HT ·X′= 0 或者迭代次数到达最大迭代次数 则结束 , 否则再次进行迭代 。 迭代译码涉及到大量的循环 ,因此该过程同 样用 C 语言进行编写 。在迭代过程当中 ,需要 221 查找每个信息节点所连接的校验节点及每个校验节点连 接的信息节点 ,如果每次都根据 H 矩阵的一行或一列来 进行搜索 ,将会耗费大量的查找时间 ,所以设计了如下优 化的数据结构及实现方法 ,便于快速查找相连的节点 : (1) 为便于查找每个信息节点所连接的校验节点 , 先统计 H 矩阵每列 1 的总个数 ,构成 1 ×n 的一维矩阵 序列 C ,然后对整个 H 矩阵按列顺序将列中元素 1 的行 位置查找出来 ,构成一维矩阵序列 J , 其元素个数等于 H 矩阵中 1 的总个数 ,亦即二分图中边的总数 。 (2) 为便于查找每个校验节点所连接的信息节点 , 先统计 H 矩阵每行 1 的总个数 ,构成 1 ×m 的一维矩阵 序列 R ,然后对整个 H 矩阵按行顺序将行中元素 1 在 J 的位置查找出来 ,构成一维矩阵序列 K。 (3) 因为 f j 及 R ij ( l) , Qij ( l) 都只在边上传递 ,因此 只需要根据每条边来计算 ,而边的总数等于 H 矩阵里 1 的总数 。为便于计算 , f j 及 R ij ( l) , Qij ( l) 都按 J 中的边 顺序排列存储 , 此时 , 查找 J 即可得到信息节点所在的 列位置 。计算 Rij ( l) 的传递时 , 根据 R 可知与某校验该 节点相连的信息节点的个数 , 从而在 K 中取出对应的 信息节点在 J 中的排列位置 ;计算 Qij ( l) 的传递时 , 根 据 C 可知与某信息节点相连的校验节点的个数 ,从而 在 J 中直接取出对应的校验节点 。使用这种方法不用 每次迭代都去查找 H 矩阵中的非 0 元素 ,提高了运算 速度 。 3 　仿 　真 上述的优化只是针对数据结构及有效查找节点的 优化 ,并没有改变迭代译码算法本身 ,在相同输入情况 下 ,优化算法和原始算法两者的译码过程一致 。为了验 证上 述 优 化 算 法 的 速 度 提 升 , 在 A W GN 信 道 上 作 LDPC编码 B PS K 调制的仿真 ,LDPC 码使用 Hu Xiao Yu 的 PE G 方 法构 造的 PE G Reg 504 ×1 008 正则 码[ 10 ] ,译码最大迭代次数设定为 50 。表 1 给出了不同 信噪比下仿真 1 000 次编译码的平均每次编码译码时 间 。可见 ,采用本文的优化数据结构及实现方法 ,仿真 速度平均提高了 57 倍 。 (1) 　 　　　　　　　表 1 　不同信噪比下平均每次编码译码时间 　　　　　　　　　　 Eb/ N o/ dB 2 2. 5 3 3. 5 4 4. 5 5 原始算法 / s 1. 663 4 1. 659 5 1. 646 2 1. 640 1 1. 484 6 0. 866 1 0. 407 4 优化算法 / s 0. 029 7 0. 028 6 0. 028 6 0. 028 5 0. 025 1 0. 014 7 0. 007 8 速度提升 倍数 56 58 58 58 59 59 52 (下转第 128 页) 　 

2 2 2 2 2 2 2 2 2 2 2 2 测 控 技 术 王红玲等 :基于 A T89C51 的多点温度检测系统设计 按键处理程序实现键盘的输入按键的识别及相关处理 ; 温度测试程序主要完成由温度芯片传送数据的处理 ,并 进行判断和显示 ;数码管显示程序完成向数码的显示送 数 ,控制系统的显示部分 ;中断控制程序则实现循环显 示功能 。 系统程序流程图如图 8 所示 。 的可扩展接口芯片相连 ,则可实现更多路温度的测量与 控制 ,以适应工业生产的需要 。 参 　考 　文 　献 [1 ] 黄章华 ,陆华忠 ,李灌辉. 基于 CAN 总线和 PID 算法的多点 水温控制系统[J ]. 仪表技术与传感器 ,2007 (10) :44 45. [ 2 ] 袁新娣 ,杨汉祥. 单总线温度传感器在多点温度测量系统中 的应用[J ]. 科技广场 ,2009 (1) :189 191. [ 3 ] 曹海平. 基于单片机和 DS18B20 的分布式多点温度检测系 统的设计[J ]. 自动化技术与应用 ,2008 ,27 (11) :90 92. [ 4 ] 吕昌江 ,段晨旭 ,罗婷. 基于 CAN 总线的粮库多点温度检测 系统的设计[J ]. 信息技术与信息化 ,2008 (11) :63 64. [ 5 ] 李冉琦 ,陆二庆 ,杨祥. 智能化家庭多点温度检测的设计方 法[J ]. 桂林工学院学报 ,2008 ,28 (2) :265 269. [ 6 ] 朱奕丹 ,倪浩如. 基于单片机控制的高精度多点温度检测显 示系统[J ]. 自动化仪表 ,2008 ,29 (8) :58 61. [ 7 ] 周月霞 ,孙传友. DS18B20 传感器及其测温方法的改进 [J ]. 石油仪器 ,2002 ,16 (1) :36 38. [ 8 ] DALL AS 公司. DS18B20 数据手册 [ M ]. 美国 :DALL AS 公 司 ,2001. [ 9 ] 胡汉才. 单片机原理及系统设计 [ M ]. 北京 :清华大学出版 社 ,2002. [ 10 ] 忠梅. 单片机的 C 语言应用程序设计[ M ]. 北京 :北京航空 航天大学出版社 ,1997. 图 8 　系统程序流程图 4 　结 　语 利用 A T89C51 单片机和 DS18B20 数字温度传感 器可以实现多点温度的检测与控制 。系统具有信号数 字化 、硬件简单化和抗干扰能力强等特点 , 如果与相应 作者简介 : 王红玲 　女 ,1962 年出生 ,河南许昌人 ,副教授 。主要从事电力电子方面的教学与研究工作 。 (上接第 122 页) 4 　结 　语 Matlab 是一个 常用 的 通 信 仿 真 平 台 , 本 文 对 在 Matlab 平台上实现快速的 LDPC 码编解码算法 ,进行 快速的 LDPC 码仿真进行了研究 。利用符合 Matlab 要求的 mexFunction 格式的 C 语言改写编解码算法 , 并优化其中的数据结构及实现方法 ,大幅提升了仿真速 度 ,减小了仿真所用的时间 ,对进一步研究不同 LDPC 码的性能或寻找更好的 LDPC 码具有较重要的意义 。 参 　考 　文 　献 [ 1 ] GALL A GE R G. Low density parity check codes [J ]. IRE Trans. on Information Theory , 1962 : 21 28. [ 2 ] MAC KA Y D J C , N EAL R M. Near Shannon limit per formance of low density parity check codes [J ]. Electronics Letters , 1997 , 33 : 457 458. [ 3 ] MAC KA Y 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 ] RIC HARDSON T J , U RBAN KE R L . Efficient encoding of IEEE Trans. on , Infor check codes[J ]. density parity low mation 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 , EL EF T H ERIOU E. ARNOLD D M , et al. Efficient implementations of the sum p roduct algorithm for decoding LDPC codes [ C ]/ / Global Telecommunications Conference. [ S. l. ] : IEEE , 2001. [ 9 ] 程敏. LDPC 码的译码算法的研究 [ D ]. 南京 : 南京邮电学 院 ,2003. [ 10 ] HU Xiao Yu , EL EF T H ERIOU E , ARNOLD D M. Pro growth Tanner graphs [ C ]/ / Proc. of IEEE gressive edge Global Telecom. Conf . . [ S. l. ] : IEEE , 2001. 作者简介 : 刘 　英 　女 ,1983 年出生 ,山西省忻州人 ,硕士研究生 ,助教 。主要研究方向为测试计量技术及仪器 。 821