基于(17,9)平方剩余码的广义LDPC码构造及性能研究

李西亚，黎 勇

(重庆邮电大学 重庆市移动通信技术重点实验室，重庆 400065)

0 引 言

1960年代初，Gallager[1]首次提出了低密度奇偶校验(low-density parity check, LDPC)码的概念，它是一类优秀的纠错码，具有较好的译码性能。近年来，LDPC码的研究获得了较大关注，在迭代译码情况下，LDPC码性能可以逼近香农极限。传统LDPC码尽管有着较高的编码增益，但其错误地板和译码复杂度往往较高。为了获得更低的错误地板，1999年，Lentmaier 和Zigangirov首次构造了以汉明码作为分量码替换LDPC码中单奇偶校验(single parity-check, SPC)码的广义LDPC(generalized LDPC, GLDPC)码，其仿真性能相比同码率下的LDPC码表现更加优秀[2]。同时也在理论上证明了GLDPC码能够以较快的收敛速度取得较低的错误地板[2]。

GLDPC码是对LDPC码概念的进一步拓展。通过观察GLDPC码的Tanner图[3]发现，GLDPC码的变量节点和校验节点使用更为灵活，不再局限于传统的LDPC码的变量节点和SPC节点，这也使得GLDPC码的译码方式更为灵活[4]。目前常见的替换SPC码的分量码有BCH(Bose，Ray-Chaudhuri，Hocquenghem)，里德-所罗门(Reed-Solomon, RS)等码[5]，它们的纠错能力比SPC码强，构造出的GLDPC码的性能也比同码率下的LDPC码更加优秀。然而这种为了增强校验节点约束而引入了更多的校验方程的方式，使得GLDPC码的码率大大降低。为了减少码率损失，在设计 GLDPC码时就必须减少LDPC 母码(也称全局码)中被替换的校验节点的数量，但这反过来又会影响码字的性能。鉴于此，必须采用比传统的汉明码、BCH 码更强大的码型作分量码，从而使只替换母码中少部分校验节点即可设计出性能优异的GLDPC码。本文针对分量码为平方剩余(quadratic residue, QR)码的GLDPC码提出了一种构造方法，构造了一个QR-GLDPC码。

QR码是BCH码的一个子类，有着比传统的循环码更大的最小汉明距离。1957年，QR码由Prange[6]首次提出，因具有完美的代数结构，受到众多代数编码学家的青睐，这极大地加快了QR码用于纠错应用的研究进展。

1 GLDPC码和QR码介绍

1.1 GLDPC码的定义

GLDPC码的校验矩阵构造由2部分组成，分别是校验母矩阵HGLDPC和分量码校验矩阵HCPT，其中，HGLDPC有m0行n0列。基于以上2种矩阵扩展而成的GLDPC码的校验矩阵为HGLDPC,有M行N列，其中N=n0。如果HGLDPC是满秩的，则GLDPC码的码率R可表示为

(1)

1.2 GLDPC码的Tanner图表示

通过Tanner图可以直观地看出GLDPC码和LDPC码的不同以及两者之间的关系。图1是使用分量码替换SPC码扩展而成的GLDPC码的Tanner图。图1中，左边黑色圆圈表示变量节点，右边黑色实线方块表示SPC节点，右下方黑色虚线方块表示分量码。

图1 GLDPC码的Tanner图Fig.1 Tanner graph of GLDPC codes

1.3 QR码介绍

QR码是码率略大于1/2的BCH码的一个子类，在同等码长下，比RS码、汉明码等具有更优异的纠错性能。

考虑在伽罗华域GF(2m)上定义一个QR码(n,k,d)或(n,(n+1)/2,d)，其生成多项式为

g(x)=g0+g1X+…+gn-kXn-k

(2)

(2)式中：n是码字长度，k=(n+1)/2是码字信息位的长度；d是最小汉明距离。假设h(x)是QR码的校验多项式，由文献[7]可知Xn+1的一个因式是g(x)，即

g(x)·h(x)=Xn+1

(3)

(3)式中，h(x)可以表示为如下的多项式形式

h(X)=h0+h1X+…+hkXk

(4)

(4)式中，h0=hk=1。经计算，可以得到(n-k)个方程式。

(5)

(5)式中，vn-i-j表示码字中的一位。因此，可以推导出h(x)的反多项式，即

Xkh(X-1)hk+hk-1X+hk-2X2+…+h0Xk

(6)

不难看出Xkh(X-1)也是Xn+1的一个因式。假设把因式Xkh(X-1)看成一个生成多项式，它能够产生一个(n,n-k)循环码，相应的校验矩阵可以表示为

(7)

通过观察(5)式可知，QR码字集合中的所有码字与HQR的每一行相乘均为零，即HQR·vT=0。所以，矩阵HQR是QR码的校验矩阵。下文中所使用的替换SPC的分量码(17,9)QR码的校验矩阵便是利用以上方法求出，从文献[7]中我们可以知道，(17,9)QR码的生成多项式为

g(x)=x8+x5+x4+x3+1

(8)

由(3)—(6) 式计算，可以得到

x9h(x-1)=x9+x6+x5+x4+x3+1

(9)

多项式x9h(x-1)可以生成一个(17,9)循环码，则根据 (7) 式可知该码的校验矩阵为

该矩阵便是分量码(17,9)QR的校验矩阵。

2 GLDPC码构造和译码

2.1 GLDPC码的构造

假设使用参数(N,M,K,n,m,k)表示GLDPC码，其中，N为码长；M为校验矩阵的行数；K表示信息位长度。同样，n,m和k表示分量码的对应参数。特别地，M=p·m，这里p是个整数。K,k分别与GLDPC码校验矩阵和分量码校验矩阵的秩相关[8]。

构造GLDPC码的校验矩阵HGLDPC需要2个步骤。

步骤1构造母码LDPC码的校验矩阵HLDPC和分量码校验矩阵HCPT，且HLDPC的行重必须等于分量码码长。

步骤2对HLDPC逐行扩展，“0”位置使用长度为n-k的零向量替换，“1”位置使用HCPT中的某一列替换，注意每一列只能使用一次。

已知分量码QR的纠错能力强于SPC码，即分量码QR的置信值比SPC码的置信值更大，在纠正一个错误变量节点的过程中，只需要有一个来自QR码的置信值即可完成。相反，SPC码的置信值较低，即使一个变量节点有多个来自SPC码的置信值也未必能够实现纠错的目的。因此，确保变量节点接收到的信息至少有一个来自QR码是译码成功的关键。鉴于此，本文提出了一种基于(17,9)QR码的GLDPC码的构造方法，其中，母码LDPC码的校验矩阵的列重为2，具体构造方法如下。

步骤1在校验母矩阵中，任选M0个SPC码用QR码替换，初步构造出GLDPC码的校验矩阵，M0≤M。 然后通过分析GLDPC码的Tanner图发现，有如图2所示的3种类型的变量节点。图2中，变量节点var0，2条边分别连接SPC和QR；变量节点var1，2条边全部来自SPC；变量节点var2，2条边全部来自QR。

图2 3种类型的变量节点Fig.2 Three types of variable nodes

步骤2找出所有var1和var2类型的变量节点，然后对2种不同类型的变量节点进行边交换。图3为交换边的原理图，任意交换节点var1和var2的一条边，使它们成为节点var0的形式。

步骤3当步骤2中所有变量节点交换边的过程完成之后，即可得到一个新的GLDPC码。

图3 交换边的原理Fig.3 Principle of exchange sides

2.2 GLDPC码的译码

文献[2]中提出了一种GLDPC码的软判决迭代译码算法，其主体架构类似于LDPC码的置信传播译码算法，分量码采用最大后验概率APP译码[9]来计算外信息。然而该算法因为概率消息用似然比(likehood ratio, LR)表示，致使公式中出现了大量乘法运算，增加了运算复杂度。鉴于此，本文中概率消息采用对数似然比(log likehood ratio, LLR)表示，大量的乘法运算被简化为加法运算，从而降低了运算复杂度。

(10)

设迭代次数l=1,2,…,L,译码算法流程如下。

(11)

图4 变量节点i从第t个分量码获得的外信息Fig.4 External information obtained of the variable node ifrom the tcomponent code

步骤2若i≠N-1,对所有的变量节点计算置信值

(12)

该置信值作为下一次迭代中步骤1中的输入；T(i)表示与变量节点i相连的所有分量码节点的集合，其中，T(i) 表示去除t节点。

步骤3最后一次迭代，即l=L,计算变量节点上收到的所有置信值

(13)

步骤4软判决，输出：

(14)

2.3 分量码的APP译码算法

APP译码算法[9]是一种适用于线性分组码的最大后验概率译码算法。下面介绍该算法以及算法中相关符号的含义。

假设v=(v1,v2,…,vN)是[N,K]线性分组码中的一个码字，线性分组码的校验矩阵用H表示，则H的转置形式为

(15)

(15)式中，hn=(hn1,hn2,…,hn(N-K))，1≤n≤N。

如果定义符号v[1,n]=(v1,v2,…,vn)，

(16)

对于已给定的校验矩阵H，存在一个长度为N的网格图，μ(s,n)表示在状态s时，路径长度为n的度量值，其中，1≤n≤N。

码字v=(v1,v2,…,vN)通过AWGN信道传送，在接收端，信道的输出码字是r=(r1,r2,…,rN)。

输入：P(r1|v1)，P(r2|v2)，…，P(rn|vn)。

步骤2对n=1,…,N更新

μ(s,n)=μ(s,n-1)P(rn|vn=0)+

μ(s+hn,n-1)P(rn|vn=1)

步骤3对n=1,…,N，设

等号成立的条件是P(rn|vn=0)≠P(rn|vn=1)。

输出：P(v1=0|r,v),…,P(vN=0|r,v)。

3 仿真结果

本文采用(17,9)QR码作为分量码来研究GLDPC与LDPC码在不同码长和码率条件下的性能，仿真条件为AWGN信道，仿真平台VS2010，采用C/C++语言编程。LDPC码的校验矩阵与GLDPC码的校验矩阵相同，译码中最大迭代次数为50次。

利用边递增(progressive edge-growth, PEG)算法[10]构造规则的母码LDPC码的校验矩阵，其列是476，行是56，列重是2，行重是17。使用分量码(17,9)QR码对LDPC码进行扩展，生成(476,252,224,17,9,8)QR-GLDPC码，码率为0.471，仿真结果如图5所示。由仿真结果可知，QR-GLDPC码的性能优于同等码率下的LDPC码，即使我们选择最大迭代次数为5，GLDPC码性能依然超过LDPC码的性能。此外，可以看到在最大迭代次数为20时，GLDPC的性能得到显著提升，这意味着，GLDPC码经过20次迭代便可快速收敛。它也表明，GLDPC码的平均迭代次数低于LDPC码。因此，GLDPC码相比LDPC码，有着更快的收敛速度。

图5 GLDPC码与LDPC码性能Fig.5 Performance of GLDPC and LDPC

同样，利用PEG算法构造规则的母码LDPC码的校验矩阵，其列是952，行是112，列重和行重分别是2和17。用(17,9)QR码作为分量码进行扩展，得到(952,504,448,17,9,8)QR-GLDPC码，码率为0.471，仿真结果如图6所示。与LDPC码相比，QR-GLDPC码性能有明显优势。同时，在相等码率下，BER为4×10-5时，码长952的GLDPC码与码长476的GLDPC码相比，有近0.8 dB的性能增益。

在同等码长不同码率条件下，利用上文中码长为476的母矩阵构造出(476,238,238,17,9,8)GLDPC码，码率为0.5(仿真结果如图6所示)。码率为0.471的GLDPC码性能超过码率为0.5的GLDPC码性能。其中码率0.471的码字总共替换28个SPC节点，每个分量码对应17个变量节点，17×28=476，恰好保证每个变量节点有一条边来自QR，而码率为0.5的码字总共替换了26个SPC，17×26<476，即有部分变量节点的边全部来自SPC，导致译码性能大大降低。

4 结 论

本文提出了一种基于(17,9)QR码的GLDPC码的构造方法，并简化了基于线性分组码的GLDPC码的译码算法。仿真结果表明，在AWGN信道中，基于(17,9)QR码的GLDPC码相比同码率下的LDPC码，在错误比特率和译码收敛速度上都取得了更优异的表现。

图6 同码率不同码长、同码长不同码率GLDPC码性能比较Fig.6 Comparison of the performance of different length of GLDPC at the same rate and the same length of GLDPC at the different rate