一种CMMB系统中LDPC编码改进方法

王　莉，周长征，任丙印

（中国洛阳电子装备试验中心，河南洛阳　471003）



一种CMMB系统中LDPC编码改进方法

王莉，周长征，任丙印

（中国洛阳电子装备试验中心，河南洛阳471003）

摘要：针对CMMB系统中LDPC码长较长，传统LDPC编码方法复杂度较高的问题，研究了两种常用的基于LU分解的LDPC编码算法，并在此基础上对LU分解算法进行改进。仿真结果表明，改进算法能更有效地降低编码复杂度，节省存储空间，提高编码速率，更适合硬件实现。

关键词：移动多媒体广播；LDPC码；LU分解；编码

0　引言

1962年，Gallager首次提出了LDPC码（Low Density Parity Check，LDPC）的概念[1]，但由于受当时技术水平的限制，并未受到重视。直到1996年，MacKay等人研究发现LDPC码性能和Turbo码纠错性能类似，接近香农极限[2]。Chung等研究发现码率为1/2，码长为107的非规则LDPC码在误码率为10-6时距离香农极限仅为0.004 5 dB，进一步验证了LDPC码的优异性能[3]。

中国移动多媒体广播（China Mobile Multimedia Broadcasting，CMMB）标准于2006年发布，其信道传输核心技术StiMi中采用了LDPC编码，提高了通信系统的抗干扰能力[4]。由于CMMB系统中采用的LDPC码的码长较长，传统的编码方式计算量太大，为降低编码复杂度，Wang等将LU分解用于CMMB系统中的LDPC编码，有效降低了编码复杂度[5]。谭太秋等提出了一种基于贪心策略的LU分解算法，进一步降低了LDPC编码复杂度，节省了存储空间[6]。刘宴华等将三种不同的LU分解方法进行对比分析，给出了复杂度更低，更为节省存储空间的最小行重乘列重法[7]。Qin提出了一种改进的LU分解算法，分别与最小行重法和最小列重法进行了比较分析，表明改进的LU分解算法能更有效地降低编码复杂度[8]。

本文主要介绍CMMB系统中LDPC码常用编码方法，并在此基础上对编码算法进行改进，通过仿真和对比分析，证明改进算法能够有效降低编码复杂度，节省存储空间，提高编码速率。

1　CMMB系统中LDPC码校验矩阵生成

LDPC码的传统编码方法与线性分组码类似[9]，但并不适用于CMMB系统。在CMMB系统中，定义的LDPC码长为9 216 b，根据信息比特长度不同分为1/2和3/4两种码率。文献[4]给出了CMMB系统中LDPC码的映射向量为：

其中：COL_ORDER(i)表示码字比特映射向量；k表示信息比特长度。对应的编码后输出码字为，输入信息比特和校验比特分别表示为

这时的输出码字C是码字向量映射后得到的非系统码。对于非系统码C，其信息比特和校验比特是混在一起的。但此时的非系统码C仍满足：

以1/2码率为例，对应的校验矩阵H中1的分布如图1所示。

图1　LDPC码校验矩阵H中1的分布

为了使信息比特和校验比特分离，在编码时，首先要将原始校验矩阵H按照COL_ORDER(i)向量进行映射，即将H矩阵的第i列交换到第COL_ORDER(i)列，令得到的新校验矩阵为H′。新校验矩阵对应的码字为系统码，用表示[10]，两者满足关系式：

图2给出了调整后的新校验矩阵H′中1的分布情况。

图2　新校验矩阵H′中1的分布

2　LDPC编码的LU分解算法

因为矩阵H′在GF（2）域上，因此满足：

从H′矩阵中分离出来的矩阵Hp仍满足稀疏矩阵，因此可通过对Hp进行LU分解简化编码过程。

常用的LU分解方法有三种：最小行重法、最小行重中最小列重法和最小行重乘列重法。由于最小行重法和后两种方法相比计算量仍然较大，因此本文主要讨论后两种LU分解算法。

2.1最小行重中最小列重法

最小行重中最小列重法是寻找行重最小的一行，完成行交换后确定为主行。接着在主行中寻找列重最小的元，进行列交换确定为主元，随后进行分解和高斯消元。算法具体步骤可描述为：

（1）初始化。令L =I，U =Hp，其中I为单位矩阵，定义和Hp维数相同的矩阵P和Q，分别用来记录行变换和列变换。

（2）寻找主行。假设当前需确定第i行为主行，对矩阵U从第i行到最后一行计算行重，选出行重最小的行，设为j。当i≠j时交换U中第i行和第j行的值，同时交换矩阵P中的第i行和第j行。

（3）寻找主元。统计第i行为1的列中每列的列重，选出列重最小的列，设为t。当i≠t时交换U中的第i列和第t列，同时交换矩阵Q的第i列和第t列。

（4）高斯消元。从i+ 1行到最后一行，满足矩阵U的第i列为1时，则矩阵L对应位置赋1。将矩阵U中第i列中i行下面的1通过和第i行进行模二运算消去。

（5）循环。i值加1，判断是否到最后一行，如果等于则循环结束，否则跳至步骤（2）。

2.2最小行重乘列重法

最小行重乘列重法每次统计每行和每列的重量，寻找行重和列重乘积最小的1确定为主元，然后进行行列变换和高斯消元，算法具体步骤可描述为：

（1）初始化。令L =I，U =Hp，其中I为单位矩阵，定义和Hp维数相同的矩阵P和Q，分别用来记录行变换和列变换。

（2）统计行重和列重。统计矩阵U中所有行的行重和所有列的列重。

（3）寻找主元。假设当前需确定第i行为主行，计算矩阵中所有1所在位置的行重和列重乘积，选出乘积最小的1为主元，设其行为j，列为t。当i≠j时交换U中第i行和第j行的值，同时交换矩阵P中的第i行和第j行。当i≠t时交换U中的第i列和第t列，同时交换矩阵Q的第i列和第t列。

（4）高斯消元。从i+ 1行到最后一行，满足矩阵U的第i列为1时，则矩阵L对应位置赋1。将矩阵U第i列中i行下面的1通过和第i行进行模二运算消去。

（5）循环。i值加1，判断是否到最后一行，如果等于则循环结束，否则跳至步骤（2）。

上述两种分解算法中均包含行变换和列变换，因此满足：

将式（6）代入式（5）中得到：

令Hsnew=P×Hs，则：

令r=Q-1×p，则：

令y =U×r，z=Hsnew×s，具体编码过程如下：

（1）计算z=Hsnew×s得到z。

（2）根据式（9）可知L×y =z，用前向迭代方法计算y。

（3）根据U×r=y，用后项迭代计算r。

（4）根据Q-1×p =r，得到校验比特p =Q×r。

2.3对两种LU分解算法的改进

在最小行重中最小列重算法中，确定主行后，在寻找主元的过程中是对矩阵的整列进行统计的，改进算法将列重统计改为统计第i行为1的列中i行以下的列重，即统计剩余矩阵的列重。

在最小行重乘列重算法中，将统计所有行的行重和列重改为统计剩余矩阵的行重和列重。假设当前需确定第i行为主行，只统计第i行以下所有1对应的行重。统计列重时，只统计i行以下所有1对应的从i行到最后一行的列重。

改进算法只统计剩余矩阵的行重和列重，是因为已经计算完成的步骤对应量不会发生改变，对后续的消元不会产生任何影响。

3　仿真分析

3.1两种LU分解算法结果对比

按照上述两种分解方法对Hp矩阵进行LU分解，得到的三角矩阵中非零元素的分布如图3和图4所示。从图中可以看出进行LU分解后，L和U均为三角矩阵，矩阵中非零元素的数目大幅减少，降低了LDPC编码的复杂度。

3.2LU分解算法改进前后对比

统计图3和图4中LU分解后得到的三角矩阵中1的个数，为方便描述分别用算法1和算法2来表示两种分解算法。统计图5和图6中LU分解后得到的三角矩阵中1的个数，为方便描述分别用改进算法1和改进算法2来表示两种分解算法，统计结果如表1所示。

图3　最小行重中最小列重法LU分解后非零元素分布

图4　最小行重乘列重法LU分解后非零元素分布

图5　改进后最小行重中最小列重法LU分解后非零元素分布

图6　改进后最小行重乘列重法LU分解后非零元素分布

表1　两种算法及改进算法LU分解结果比较

进行LU分解的目的是为了得到稀疏矩阵，一方面

编码时可以大幅降低计算量；另一方面，考虑硬件实现时可以节省大量存储空间。因此LU分解后1的数目成为评价算法性能的重要指标。

将表1中算法1和算法2比较可以看出，算法2分解后1的数目更少。虽然算法2需要统计矩阵中所有行重和列重，计算较耗时，但LU分解可以离线完成后存储起来直接用，因此对实时编码而言，算法2更节省存储且编码速率更高。

将算法1，2分别和改进后的算法1，2相比，可以看出改进算法LU分解后得到的1的数目更少，能够进一步降低编码复杂度。

4　结语

本文介绍了CMMB系统中LDPC编码的两种常用LU分解算法，对算法性能进行了对比分析。在此基础上，对LU分解算法进行改进，仿真分析表明，改进后算法所需的存储量更少，编码复杂度更低，能更有效地满足系统实时性要求，对降低CMMB系统中LDPC编码的硬件实现复杂度有一定意义。

参考文献

[1] GALLAGER R G. Low⁃density parity⁃check codes [J]. IEEE Transactions on Information Theory，1962，1（1）：21⁃28.

[2] MACKAY D C J，NEAL R M. Near Shannon limit performance of low⁃density parity check codes [J]. Electronic Letter，1996，32（18）：456⁃458.

[3] CHUNG S Y，FORNEY G D，RICHARDSON T J，et al. On the design of low⁃density parity check codes within 0.0045 dB of the Shannon limit [J]. IEEE Communications Letters，2001，5（2）：58⁃60.

[4]国家广播电影电视总局.GY/T220.1⁃2006.移动多媒体广播第一部分：广播信道帧结构、信道编码和调制[S].北京：国家广播电影电视总局，2006.

[5] WANG P，CHEN Y E. Low⁃complexity real⁃time LDPC encoder design for CMMB [C]// Proceedings of 2008 IEEE International Conference on Intelligent Information Hiding and Multimedia Signal Processing. Harbin，China：IEEE，2008：1209⁃1212.

[6]谭太秋，李玉柏，武畅.基于CMMB标准的高效LDPC编码研究[J].电子测量技术，2010，33（2）：56⁃59.

[7]刘宴华，雷菁，文磊.CMMB标准中LDPC码编码方法研究[J].通信技术，2010，43（10）：8⁃10.

[8] QIN G C，YAN M，HU G R. An efficient LDPC encoding scheme for CMMB based on improved LU decomposition [C]// Proceedings of 2013 IET International Conference on Informa⁃tion and Communication Technologies Science. Beijing，China：IET，2013：440⁃445.

[9]郭永富，周傲松.LDPC编译码方法综述[J].航天器工程，2008，17（3）：118⁃122.

[10]周红君.CMMB系统中LDPC编译码算法研究[D].北京：北京邮电大学，2010.

An improved method of LDPC encoding in CMMB system

WANG Li，ZHOU Changzheng，REN Bingyin
（Luoyang Electronic Equipment Test Center of China，Luoyang 471003，China）

Abstract：For LDPC code in CMMB system is long，and complexity of the traditional LDPC encoding method is high，two commonly⁃used LDPC encoding algorithms based on LU decomposition were studied，and on this basis，the LU decomposition algorithm was improved. The simulation results show that the improved algorithm can reduce the encoding complexity effective⁃ly，save the storage space and improve the encoding rate. The algorithm is suitable for hardware implementation.

Keywords：mobile multimedia broadcasting；LDPC code；LU decomposition；encoding

作者简介：王莉（1988—），女，河南新郑人，硕士，助理工程师。研究方向为通信信号处理。

收稿日期：2015⁃06⁃01

doi：10.16652/j.issn.1004⁃373x.2016.01.020

中图分类号：TN919.3+1⁃34

文献标识码：A

文章编号：1004⁃373X（2016）01⁃0072⁃04