基于IEEE802.16e协议的无短环的LDPC缩短码设计

フ 要:IEEE802.16e协议给出的低密度奇偶校验(LDPC)码是短码时，其校验矩阵存在大量的短环，针对这一问题，设计了一种新的LDPC缩短码方案。该方案在现有的IEEE802.16e协议的LDPC码的校验矩阵设计框架下，提出一种分块修正子校验矩阵的方法，该方法用准循环矩阵法和有限几何法联合优化的方法构造了扩展因子zf=48的校验矩阵，г擞猛步顺序搜索度数节点的方式，使缩短码情况下的校验矩阵无4环并且仅含有少量6环。在加性高斯白噪声(AWGN)信道下仿真实验表明，码率为0.5的情况下，改进后的码字不仅保持了IEEE802.16e协议编码的快速编码的性能，并且误码率性能仅比此时的香农限多了1.1@dB。

ス丶词:

低密度奇偶校验码；缩短码；IEEE802.16e协议；短环；编码算法

ブ型挤掷嗪: TP393 文献标志码:A

Abstract: The shortened LDPC codes, based on the current IEEE802.16e standard, have plenty of small girths. In order to resolve this problem, this paper proposed a new scheme of designing the shortened LDPC codes. In the proposed scheme, the design has modified the subparity check matrix under the frame of the IEEE802.16e Standard. The proposed check matrix with the spreading factor (zf=48) was constructed with quasicyclic matrix method and finite geometry method. Moreover, parity check points searched the node degree in synchronous sequence, and the proposed subparity check matrix has minor girth6 and no girth4. The results of simulation in the AWGN (Additive White Gaussion Noise) channels show that the improved short code with the code rate approaching to 0.5, can fast encode as excellently as the IEEE802.16e protocol. Moreover, a good BER (Bit Error Rate) performance of the proposed code is 1.1@dB more than the Shannon limit of this channel.

Key words: Low Density Parity Check (LDPC) code; shortened code; IEEE802.16e protocol; short cycle; encoding algorithm

0 引言

低密度奇偶校验(Low Density Parity Check, LDPC)码由Gallager［1］于1962年提出。1996年，MacKay和Neal的研究表明，采用长码长LDPC码可以达到Turbo码的性能［2］。这个研究成果吸引了几乎所有信道编码界学者的目光，从而使LDPC码的研究跨入了一个新的阶段。经过近十几年的发展LDPC码日渐成熟并且被各个主流的通信标准所采用，2005年全球微波互联接入(WiMax)技术将LDPC码作为可选信道编解码方案［3-4］，为了降低LDPC编码的复杂度，IEEE 802.16e协议中提供了一种具有准循环特性的LDPC码的监督矩阵。实际上IEEE 802.16e协议下的LDPC码在码长nА4B800@b时，存在大量的短环(称为girth或围长)。短环的存在一方面造成译码性能急剧下降，不利于迭代算法的收敛，另一方面最小环与码的最小距离有关，girth越大，最小距离也随之增大［5］。因此，构造girth较大的LDPC码已成为当前LDPC码的一个重要研究内容［2］。

本文用准循环矩阵法和有限几何法相结合的构造方法，改进IEEE802.16e的监督矩阵的子矩阵，调整右循环位数，缩小监督矩阵的运算量，并且运用顺序搜索度数节点的方式，使生成的校验矩阵无4环并且仅含有少量6环，大大提高了系统通信的性能。

1 基于IEEE 802.16e的LDPC码

IEEE 802.16e协议［3］中LDPC码可以采用移位寄存器的方式进行编码，大大降低了编码复杂度；避免了矩阵求逆运算，节约了监督矩阵的储存空间，使得编码过程简单化。其校验矩阵的设计采用一种准双对角结构子矩阵，在码率为1/2的情况下，准双对角结构子矩阵由单位移位矩阵和零矩阵组成。

文献［5］指出，准循环码的奇偶校验矩阵经过适当的列置换后，能使各子矩阵为循环矩阵，并且所需要的存储量大为减少，П湮原来的1/z。П疚奶致鄣LDPC码的校验矩阵就是由循环子矩阵构成的，所以这种LDPC码是准循环码。

1.1 IEEE 802.16e的校验矩阵

IEEE 802.16e协议中对于不同码率的LDPC码给定了不同的基本矩阵，每种码率的基本矩阵都是针对最大的码长H(n=2B304)定义的。对于码率为1/2的码，基本矩阵Hb,1/2如图1所示，在基本矩阵中-1表示zf×zf全0矩阵，用一个循环移位因子表示对单位阵循环移位后的矩阵。オ

Hb,12=T(Hb1)mb×kb(Hb2)mb×mb(1)お

其中:ЕИb1对应的是信息位，Ηb2对应的是校验位，Ηb2是准双对角线矩阵。基矩阵Ηb2采用了双对角和“z0z”结构由双对角线结构子矩阵Z和循环矩阵I构成。矩阵I(p(zf,I,1))(i=1,6,12)为单位矩阵循环右移p(zf,I,1)位，p(zf,I,1)表示I(p(zf,I,1))位于Hb的第i行第1列的子矩阵位置。オ

802.16e协议中规范了基矩阵ЕИb的右半部分Ηb2采用了双对角和“z0z”结构［4-6］。所谓“z0z”是指Hb2中的第一个重量为3的列向量，其首尾两个元素采用相同取值的移位参数z，然后在列向量中间位置设置一个0元素(单位阵)。随后的校验位置列向量的重量全部为2，并按照双对角结构排列，非负元素取值都是0，即单位阵，便于递推编码产生校验位。在基于“z0z”和双对角结构的编码过程中，产生编码辅助向量和递推相应的校验位编码比特，需要的异或运算次数和矩阵中的非零元素个数相当，编码运算的复杂度为O(n)。オ

1.2 基于IEEE 802.16e的LDPC码的短环检验

文献［7］指出，如果要使构造出的LDPC码具有良好的纠错性能，则必须满足3个条件，分别是无短环重码字、无低码重码字、码间最小距离要尽可能地大。

定理1［8］ 四环检测定理。Ц定校验矩阵H，设辅助矩阵O为Ο=HTH=［h(1) h(2) … h(N)］T［h(1) h(2) … h(N)］当且仅当，辅外的其他助矩阵O除了主对角线上元素以外的其他元素全为1或0时，校验矩阵H没有四环。オ

定理2 六环检测定理。任取校验矩阵H中的三个列向量h(m)、h(n)和h(k)(m,n,k∈{1,2,…,N}，m≠n≠k)，若校验矩阵H无四环，则H有六环的充分必要条件是列向量h(m)、h(n)和h(k)两两彼此有一个“1”在同一行上［8］，如图2，假定所在行分别为：オ

i1,i2,i3∈{1,2,…,M},i1≠i2≠i3，即：hT(m)h(n)=1,hT(m)h(k)=1,hT(n)h(k)=1オ

推论1

若校验矩阵H无四环，则H无六环的充分必要条件是定理2的条件不被满足［8］。オ

在一个校验矩阵中，如果两行含有两个相同位置上的“1”，则意味着出现了长度为4的循环；如果任意三列出现两两重叠的1，则意味着出现了形状不同长度为6的循环。若校验矩阵Hе械牧邢蛄慷杂ξ恢玫摹1”构成端点的图形分别满足图2(a)和图2(b)中的四边形和六边形的围线，г蛩敌Q榫卣H中含有四环和六环。オ

短环的存在使译码器不能快速收敛，本文分别用检验几何形状的方法检测四环，用文献［7-8］提出的一种基于Tanner图的方法来计算LDPC码短环分布的方法检测六环。

低码重码的存在也会使得原本为零的码字在译码时被误判，不过目前还没有直接的手段能准确地指出最小距离，所以本文把另外两条验证条件作为修改短环之后，检验矩阵性能的协助手段。

1.3 改进的LDPC缩短码的校验矩阵的设计

因为802.16e协议中每种码率的基本矩阵都是针对最大的码长H(n=2B304)定义的。比如802.16e定义的最短码长是576时，右移位数(p(zf, I, j)=96)远大于其扩展因子(zf=24)，得到的循环矩阵会产生大量的位置重叠。考虑到循环矩阵本身的周期性限制，本文尝试小幅度调整右移位数p(zf，I，j)，检验Hb是否非奇异，同时校验矩阵H是否无短环和低码重码。オ

仿真实验发现小幅度缩短IEEE802.16e中LDPC码的扩展模长p，г诼氤ご笥诨虻扔576时，可以获得无四环和低码重码的特性。以长度为1B152、码率为1/2的LDPC码为例说明所提出的方法。Ыp(zf, I, j)=96缩短为原先的1/2，然后利用Tanner图法修改准校验矩阵，得到新的基矩阵Hb。オ

802.16e中LDPC码定义的准循环矩阵Hb2У囊莆晃皇是7，因为扩展模长的缩小，导致Hb2П淞拷诘忝芗，使得新的信息位子矩阵Hb1和Hb2е间产生大量短环。

Ц据定理1和定理2计算出此时校验矩阵H的校验节点度数dc，Ы变量节点按照度数进行分组。顺序搜索度数节点法是将变量节点的度数从小到大排列，因为低度数的节点对于校验矩阵变量节点的度分布影响最小。式(4)的矩阵I是一种“z0z”结构，z可以任意取值，0上下变动。б蛭环长与QCLDPC码的其他码参数如码长N、行重dc、列重dv、码率R等无关［10-11］,采用顺序搜索法的思想，将z顺序取值，比较z不同取值和0不同位置时H的度分布，得到图3所示的子基矩阵Hb2。Ц梅椒可以推广到大于或等于576其他缩短码的设计。

具体步骤如下：

步骤1

а∪∷醵搪氲某ざ任N，N可被48整除，码速率R=1/2，信息码长度N/2，校验码长度N/2，基矩阵Hb,1/2是12×24的矩阵。 オ

步骤2

Ы图1中Hb,1/2对48取模；Hb,1/2′=mod(Hb,1/2，48)。オ

步骤3

式(1)中Hb,1/2′的第13列到24列是准校验矩阵Hb2，取Hb2的第一列I，查找不为-1的元素z(z≠0)和0。オ

步骤4

А0”不变，按照［0,1,2,3,4,5,6,7］的顺序增大z的值比较校验矩阵H的校验节点度数，找出最佳的一组。オ

步骤5

Ц谋洹0”在步骤4得到的新的I矩阵中的位置，再比较此时校验矩阵H的校验节点度数，检验步骤5得到的校验矩阵是否满足定理1、2，直到找到最佳的一组。オ

步骤6

检验步骤5得到的校验矩阵是否满足推论1，若满足则为所求，若不满足，增加缩短码的长度为N，е馗床街1~5，直到满足定理。

Ъ煅楦慕后的校验矩阵H的四环个数，如图4所示(N=1B152，R=1/2)，满足定理1，所以无四环。由定理2可以发现四环数量降低减少了250个，无低重码。オ

观察测试结果发现，改进后的基矩阵在中短码时具有较好的性能。

2 改进LDPC码的性能

本文以码率为0.5，码长为1B152的非规则LDPC码、IEEE802.16e协议LDPC码和IEEE802.16e协议的改进LDPC码这3种情况进行BER性能比较。

对3种LDPC码进行仿真，传输信道为AWGN信道，对信道编码进行BPSK调制，译码采用最小和译码算法，最大迭代次数20，每一个信噪比(Signal to Noise Ratio，SNR)数据点用20帧信息码进行实验。图6是BER仿真曲线，实验结果表明改进了的IEEE802.16eLDPC码与其他LDPC码相比，不仅具有显著的瀑布特性，在短码情况下，改进的IEEE802.16eLDPC的误码率明显降低了。Ф理1指出当且仅当HHT除对角线外的元素值为0或1，LDPC码无四环，由图5可以看出，改进后的校验矩阵是无四环的，顺序搜素校验节点发现六环个数大幅减少，而且此时码重分布在150~230，无低重码的问题；由于改进的码字是准循环码，能够进行快速编码，硬件实现也比较方便。

3 结语

现有IEEE802.16e协议中LDPC码设计未考虑其长码仿真和实现的复杂性问题，也未给出解决其缩短码中存在短环时的解决方案。本文提出了在现有IEEE802.16e中LDPC码的设计框架下，设计一种具有无短环和低码重码的缩短码的方案。本文对IEEE802.16e中LDPC码的基矩阵的部分子矩阵进行修改，解决了大幅度缩短码的检验矩阵存在四环和大量六环的问题，同时保证改进的校验矩阵无低重码。仿真实验表明，改进方案使得AWGN信道下，缩短的LDPC码在码率为0.5的情况下，距香农限仅有1.1@dB的差距。仿真实验结果发现：扩展因子较小时，IEEE802.16e协议的LDPC码的校验矩阵右移循环时会有重复，这样就产生了大量的短环，Х治銎渲卸袒返姆植季突岱⑾帜3z较短时，ё妓对角矩阵和信息子矩阵之间1的大量重叠，本文提出在扩展因子小时小幅缩短模值，同时优化准双对角矩阵，使之性能靠近双对角矩阵。

げ慰嘉南:

[1] GALLAGER R G. Lowdensity paritycheck codes［M］.Cambridge：MIT Press，1963.

[2] 周北望,韩小平.WiMAX宽带无线技术及其发展前景［J］.通信技术与应用,2008,15(3):67-70.

[3] MYUNG S, YANG K, KIM J. Quasicyclic LDPC codes for fast encoding［J］. IEEE Transactions on Information Theory, 2005, 51(8):2894-2901.

[4] IEEE802.16e2005. IEEE standard for local and metropolitan area networks, part 16［EB/OL］.［2011-02-20］. /getieee802/download/802.16e2005.pdf.

[5] 刘磊,周武D.码长连续变化的QCLDPC码的设计[J].电子与信息学报,2009,31(10):2523-2526.

[6] KORNAROS G. A soft multicorearchitecture for edge detection and data analysis of microarray images［J］.Journal of Systems Architecture：the EUROMICRO Journal，2010，56(1)：48-62.

[7] XIAO Y, LEE M H. Low complexity MIMOLDPC CDMA systems over multipath channels［J］. IEICE Transactions on Communications,2006,89(5):1713-1717.

[8] 赵莹，肖扬.Tanner码不存在四环的充要条件［J］.系统工程与电子技术，2009,31(5):300-304.

[9] 刘磊,周武D.码长连续变化的QCLDPC码的设计［J］.电子与信息学报,2009,31(10): 2523-2526.

[10] 包建荣,詹亚锋,殷柳国, 等.低SNR下基于LDPC译码的迭代SNR估计［J］.通信技术,2010,43(01):1-4.

[11] 毛倩,董德存,曾小清.一种AWGN信道下非规则LDPC码的优化方法［J］.计算机应用,2010,30(2):292-294.

[12] 许拔,张仲明,何英亮,等.GF(q)域上LDPC码的改进扩展最小和译码算法［J］.应用科学学报,2010,28(1)：9-13.