李 超，石 磊

(中国电子科技集团公司第20研究所通信事业部，陕西西安 710068)

1962年Gallager［1］在对纠错编码的研究中提出了LDPC码，但是由于当时的硬件条件不足，直到90年代末随着超大规模集成电路的推广才真正为人们所重视［2］。虽然在高斯信道中 LDPC(Low Density Parity Check，低密度奇偶校验码)码相比其他编码方法具有更优良的性能，但是由于其逼近香农限的性能是在较长的码长情况下才能得到体现，使得实现起来具有相当大的复杂度，即便是当今的超大规模集成电路也很难直接实现较长码长的编码和解码。于是如何构造和改进LDPC码成为目前研究的热点，而准循环低密度奇偶校验码的发现，为LDPC编译码的硬件实现提供了可能。QC－LDPC码具有更好的结构性与随机性，在保证码的信道性能不变的前提下，极大的简化了编码和译码电路，是目前实现LDPC编译码器的主流算法。正是由于这些优势，LDPC码已被 WIMAX(IEEE802.16e［3－4］)、WLAN(IEEE802.11n)、DVB－T等标准选定为信道编码的备选编码，并且极有可能成为第四代无线通信的编码标准。

1 IEEE802.16e标准中对LDPC码的规定

IEEE802.16e标准中 LDPC 码［5］的校验矩阵为

其中，Pij被定义为z×z的单位变换矩阵或零矩阵，单位变换矩阵是通过对单位矩阵循环右移得到的。LDPC码是由的效验矩阵H定义，其中m是校验位的长度，n是码长的长度。基本矩阵中的移位集{p(i，j)}是用来决定相同码率不同码长的移位大小，对于码率 1/2、3/4A、3/4B、2/3B和 5/6的各种码，p(i，j)p(i，j)由式(2)决定。

其中，⎿x」表示不大于x的最大整数。(⎿x」为取整函数)。

在IEEE802.16e标准中各种码长和码率的校验矩阵H都是由基本矩阵Hb膨胀得到的，每个基本矩阵有24列，膨胀因子 z=n/24(n为码长)。IEEE802.16e标准支持码长从576到2304共19种码长。

IEEE802.16e中对于不同码率的 LDPC码给定了不同的基本矩阵，以码率为1/2的码为例，基本矩阵Hb如图1所示。

图1 IEEE802.16e标准中1/2码率的基本矩阵

图1中－1为全零阵;0为单位阵，其余标号为相应右移次数的单位阵。

2 基于IEEE802.16e的LDPC码的快速编码算法

高编码复杂度是LDPC码需要解决的主要问题，LDPC编码器直接实现具有和码长成二次方的时间复杂度，而Turbo码可以在线性时间内编码。于是如何使得LDPC码能够在与码长成线性时间内编码就成为一个非常关键的问题。

IEEE802.16e标准中规定的LDPC码是一种结构性码，其算法大大的降低了 LDPC码的编码复杂度。但是如果采用传统的编码方法，其编码复杂度仍令人难以接受。校验矩阵H得到的生成矩阵是一个稀疏矩阵，所以可以根据校验矩阵H的稀疏性以及准循环特性［6］来进行快速编码。

IEEE802.16e标准中给出了3种LDPC快速编码的算法［7－8］。由于第 3 种编码方式［4］是最常用的，而且已经比较成熟，现只对第3种编码方式进行说明。

为了说明效验矩阵结构，现将其分割为6个子矩阵表示

设膨胀因子为z，码字x=(kb，p1，p2)，其中kb=(u1，u2，…，ukb)，p1=(p1)1*2，p2=(v1，v2，…，vmb－1)，而 ui(i=1，…，kb)，vj(j=1，…，mb－1)为1×z的矢量。

则

所以效验位p1和p2可由以下公式得到

基于IEEE802.16e标准的LDPC码的编码算法［9］可以转化为以下6个步骤:

(1)计算 f1=A和 f2=C。

(2)计算 f3=T－1f1和 f4=Ef3。

(3)计算 p1=f4+f2。

(4)计算 f5=B。

(5)计算 f6=f1+f5。

(6)计算 p2=T－1f6。

3 LDPC编码算法的实现

根据上述编码算法，FPGA程序实现了0.5码率，码长为2304 bit，信息位为1152 bit数据流的编码。每帧送入1152 bit原始数据流，经过编码后产生1152 bit效验位，因为是系统码，所以将原始信息位后紧跟效验位就可以合并成所要发送的编码码流。编码器的硬件总体结构如图1所示。

图2 LDPC编码器总体结构图

从图2可以看出，LDPC编码器中主要包含矩阵乘法模块［10］，前项置换模块，矢量加法模块，以及生成码字模块。现对矩阵乘法模块，前项置换模块和码字生成模块进行介绍。

(1)矩阵乘法器模块:主要由循环移位器和模二加法器组成。由于FPGA运算的并行特点，编码器在计算矩阵乘法时可按行并行操作。输入的原始信息比特流与效验矩阵Hb的每一行进行相乘运算时，首先按照RAM中存储的非零列号找到相对应的信息位中的矢量，并对该矢量进行循环右移，循环右移的次数依照IEEE802.11e标准的规定进行控制，然后把这一行中的所有非零元素和信息位相乘所得结果做一次异或操作，这就是矩阵的一行与信息位相乘的结果。该过程可以并行执行，同时完成矩阵中每一行与信息位的相乘运算。

(2)前项置换器模块:IEEE802.16e标准中规定，LDPC码的效验矩阵T是双对角矩阵，所以对于乘矩阵T的逆的操作采用前项置换方法，其原理如下:

设 f3=(u1，u2，…，umb－1)，f1=(v1，v2，…，vmb－1)，则

所以在FPGA中进行乘矩阵T的逆的计算，不必进行求逆和相乘运算，仅用异或运算就能完成。

(3)生成码字模块:主要作用是将原始信息位与效验位p1和p2合成。在IEEE802.16e标准中规定LDPC码为系统码，所以将原始信息位与效验位p1和p2按顺序依次拼接起来，就是实际编码后数据。

4 FPGA仿真结果分析

在QuartusⅡ软件下进行编译和综合，器件选择为Altera公司STRATIXII系列的EP2S90F1020C3，整个LDPC编码器最高工作时钟214 MHz，逻辑资源占用3027 LE。LDPC码编码仿真结果如图3所示。

图3 LDPC码编码器仿真结果

code_rden:编码器使能标志，高电平说明LDPC编码器正在工作。

matlab_code:LDPC编码的Matlab仿真结果输出。

ldpc_code:LDPC编码的FPGA仿真结果输出。

result_out:比对Matlab与FPGA仿真结果，输出码流进行相减一直为零，说明仿真结果正确。

5 结束语

文中分析了基于IEEE802.16e标准的LDPC码的校验矩阵H，然后在QuartusⅡ平台下根据分块矩阵的快速编码算法设计了一种编码器，满足IEEE802.16e标准的码长为 2304，码率为 1/2的LDPC码的编码要求，并仿真验证了LDPC编码器的性能。仿真结果证明通过合理的构造LDPC码的校验矩阵以及选择合适的编码算法，可以有效降低编码复杂度，并实现了线性编码。

［1］ GALLAGER R G.Low density parity－ check codes［J］.IRE Trans.Inf.Theory，1962，IT －8(1):21 －28.

［2］ MACKAY D J C，NEAL R M.Near shannon limit performance of Low －density Parity－check codes［J］.Electronic Letters，1996，32(4):1645 －1646.

［3］ 苗忠良，宛斌，张孝林.WiMAX协议的体系结构研究［J］.计算机技术与发展，2007，17(6):42－45.

［4］ IEEE Organization.Air interface for fixed broadband wireless access systems IEEE802.16e － 2005［S］.USA:IEEE Organization，2005.

［5］ IEEE Organization.IEEE P802.16e/d8 IEEE standard for local and metropolitan area networks［S］.USA:IEEE Organization，2005.

［6］ 李水平，刘玉君，邢庆君，等.LDPC码的环分析［J］.信息工程大学学报，2003，12(4):82－84.

［7］ RICHARDSON T J，URBANKE R L.Efficient encoding of Low－Density－Parity－Check codes［J］.IEEE Transactions on Information Theory，2001，47(2):585 －597.

［8］ 彭立，朱光喜.一种LDPC码编码器设计方案的研究［J］.现代电子技术，2004(10):11－13.

［9］ ZAHID K，TUGHRUL A，SCOTT M D.A real time programmable encoder for Low－Density Parity－Check－Code as specified in the IEEE P802.16e PD7 standard and its efficient implementation on a DSP processor［C］.England:Freescale Semiconductor，Inc，2006.

［10］陈志凯，韩泽耀.基于IEEE802.16e的LDPC编码器设计与实现［J］.电子技术应用，2007(2):119－122.