基于改进LU分解的CMMB标准中LDPC编码器设计

张 鹏，杨 刚，杨 霏，刘昌银

（中国传媒大学 信息工程学院，北京 100024）

1 引言

近年来，LDPC码以其优异纠错性能和低译码复杂度备受关注，在通信、数字电视广播等领域得到了广泛应用。

CMMB标准[1]采用了1/2和3/4两种码率的LDPC码作为前向纠错技术。虽然它们具有一定的循环特性[2]，但不是准循环LDPC码[3]，需要采用通用的编码方法，其编码的硬件实现是CMMB调制器的技术难点。

第一个具有线性复杂度的通用编码方法是Neal提出的LU分解编码算法[4]，算法非常简单。笔者通过深入分析CMMB标准中LDPC码校验矩阵的特点，采用改进的LU分解编码算法，使用较少的存储器实现了这两种码率的LDPC编码器。

2 LU分解编码算法及其改进

2.1 LU分解编码算法

考虑一个q进制LDPC系统码，其码字、信息、校验向量的长度分别是 n，k，r（r=n-k）。 设码字向量为

式中：S=[si]（si是信息元，i=0，1，…，k-1）是 1×k 阶信息向量，P=[pi]（pi是校验元，i=0，1，…，r-1）是 1×r阶校验向量。令其r×n阶行满秩校验矩阵为

式中：A是r×k阶矩阵，B是r×r阶满秩矩阵。通过行列交换，B可分解成下三角矩阵L和上三角矩阵U的乘积，即

式中：V和W分别是初等行和列交换矩阵，L，U，V和W均是r×r阶。因为V和W都是初等矩阵，所以它们的转置与逆相等，即VT=V-1和WT=W-1。

作为一种特殊的线性分组码，LDPC码同样满足以下一般关系

将式（1）～（3）代入上式，整理可得

根据上述推导过程，可给出LU分解编码算法的步骤为：

1）计算向量 X：XT=VAST；

2）前向迭代计算向量Y：YT=L-1XT；

3）后向迭代计算向量Z：ZT=U-1YT。然后对Z重新排序，得到最终的编码结果PT=-WZT。PT=-WZT等价于P=-ZWT。

2.2 改进的LU分解编码算法

图1 H经行列交换后的结构示意图

图2 改进的LU分解编码算法示意图

经初等行列交换后，校验矩阵H的右上角可转化成一个全0的梯形矩阵，如图1所示。图中，灰色区域表示其中的元素可能是0也可能是非0。

利用梯形部分编码算法和H的前d行可求出校验向量的一部分P1，d是梯形部分编码算法的编码能力，其余校验元P2可通过LU分解编码算法和H的后r-d行求出，如图2所示。

改进的LU分解编码算法步骤为：

1）由梯形部分编码算法迭代求出P1；

2）计算向量 X′：X′T＝V′A′[S P1]T；

3）前向迭代计算向量 Y′：Y′T＝L′-1X′T；

4）后向迭代计算向量Z′：Z′T=U′-1Y′T，并对Z′重新排序，=-W′Z′T，得到最终的编码结果 P=[P1P2]。

2.3 LU分解

LU分解编码算法的关键是找出尽可能稀疏的LU分解矩阵L和U[5]。LU分解一个稀疏方阵得到的上下三角矩阵的非零元素总数要大于原方阵，方阵越大，分解结果的非零元素总数越

多。当原LU分解编码算法及其改进均采用相同的LU分解算法时，由于原算法的分解对象的尺寸要大于改进算法的分解对象，所以改进算法得到的上下三角矩阵的非零元素总数要少一些，这就意味着改进算法的存储量需求比原算法少。

3 CMMB标准的LU分解编码器

3.1 CMMB标准中的LDPC码

CMMB标准采用RS码（外码）和LDPC码（内码）级联的前向纠错方式。CMMB标准采用了1/2和3/4两种码率的二进制 LDPC 码，前者是（9216，3，6）规则码，后者是（9216，3，12）规则码。 它们都是系统码，但信息向量不是原封不动地集中放置在码字的前半部分，而是被打乱散布在码字中。标准中只给出了稀疏校验矩阵，而未给出生成矩阵。

两种码率的稀疏校验矩阵都具有一定的循环特性：对于 1/2（3/4）码率，整个校验矩阵是由前 18（9）行每隔18（9）行循环移动36位得到。这两种码都不是准循环LDPC码，只能采用通用的编码方法，其编码是技术难点。

3.2 CMMB标准的LDPC编码器

传统的LU分解编码算法将H分割成左右两部分，破坏了校验矩阵的行整体特性。因为梯形部分编码算法使用的是校验矩阵的整行，所以前面述及的改进算法能在一定程度上充分利用校验矩阵的固有特性，比如行重相等和行循环性，而CMMB标准中的LDPC码恰好具备这些特性。由此得出，改进的LU分解编码算法非常适用于CMMB标准中的LDPC码。

图3是CMMB标准的LDPC码的改进LU分解编码器，采用4级流水线结构，适用于1/2和3/4两种码率。图中，矩形框表示操作，圆圈表示FPGA片内存储器，其中存储的是矩阵中非零元素所在的行或列地址。与前面述及的算法步骤相比，实现方案多了一个重新排序的环节。这是因为CMMB标准的LDPC码的信息向量不是原封不动地连续放置在码字的前半部分，而是要按照一定映射方式乱序后放在码字中。

图3 改进LU分解编码器的结构框图

3.3 存储器耗用分析

预处理表明，1/2和3/4两种码率的d分别是2544和1776。1/2码率的矩阵L′和U′分别有22498和18240个“1”，3/4码率则为7640和3774。这些数字均小于文献[5]给出的数据。此外，提出的编码方案能利用校验矩阵的行循环性，从而在一定程度上压缩相关矩阵的存储。综上可见，提出的编码方案能有效降低存储器的消耗。

4 实验分析

实验中，在Altera公司的Cyclone III系列EP3C120 FPGA上实现了CMMB标准中两种码率LDPC码的改进LU分解编码器。编码过程中使用的矩阵和向量均存储在片内RAM中。表1比较了本文和文献[6]的资源消耗。文献[6]采用的是Altera公司的Stratix II系列EP2S90 FPGA。

表1 本文和文献[6]的资源消耗（绝对量/百分比）

由表1可知，两种方案都使用了少量的逻辑单元。但在RAM资源消耗方面，本文方案的优势非常明显。本文比文献[6]少用了1087 079 bit的片内RAM，这是非常可观的，从而使选用廉价的低端FPGA成为可能。

改进后的LU分解编码器的最高工作频率可达到177.25 MHz。当工作频率是100 MHz时，系统净荷数据率为 17.082 Mbit/s（1/2 码率）和 38.9 Mbit/s（3/4 码率），能够满足CMMB标准的最高指标：10.852 Mbit/s和16.243 Mbit/s。

5 小结

笔者设计了的改进LU分解编码器能满足CMMB标准系统指标，兼容两种码率。该编码结构能充分利用CMMB标准的LDPC码校验矩阵的行重相等和行循环性等固有特性。该编码器在Altera公司的EP3C120 FPGA上验证通过。实验结果表明，提出的设计方案大大减少了存储器资源需求，可选用低价位的FPGA芯片，从而降低了设备成本，具有良好的工程实用价值。

[1]国家广播电影电视总局.GY/T220.1-2006移动多媒体广播 第1部分∶广播信道帧结构、信道编码和调制[S].北京：中国标准出版社，2006.

[2]康亮，杨波，沈萌.符合CMMB标准的LDPC解码器设计[J].电视技术，2009，33（5）：40-42.

[3]WANG Z F,CUI Z Q.Low-complexity high-speed decoder design for quasi-cyclic LDPC codes[J].IEEE Trans.Very Large Scale Integration（VLSI）Systems，2007，15（1）：104-114.

[4]NEAL R M.Sparse matrix methods and probabilistic inference algorithm[EB/OL].[2009-12-20].http∶//www.ima.umn.edu/biology/wkshp_abstracts/neal1.html.

[5]SU J N，JIANG Z，LIU K，et al.An efficient low complexity LDPC encoder based on LU factorization with pivoting[EB/OL].[2009-08-20].http∶//d.wanfangdata.com.cn/NSTLHY_NSTL_HY12420269.aspx.

[6]WANG P，CHEN Y E.Low-complexity real-time LDPC encoder design for CMMB [EB/OL].[2009-08-20].http∶//ieeexplore.ieee.org/Xplore/login.jsp?url=http%3A%2F%2Fieeexplore.ieee.org%2Fiel5%2F4603986%2F4603987%2F04604260.pdf%3Farnumber%3D4604260&authDecision=-203.