一种快速编码的半随机LDPC码构造研究
本文提出一种采用准双对角线结构来构造半随机LDPC码奇偶校验矩阵的方法，在IEEE 802.16e标准LDPC码的基础上，对基础矩阵[Hb]和扩展因子[z]的大小不作任何具体限制，可以更加灵活地实现不同码率和码长组合的编码设计。采用这种方法构造出的是一种混合结构的奇偶校验矩阵，矩阵的左半部分是随机构造的基础矩阵，能够确保编码的优异性能；矩阵右半部分采用准双对角线结构，确保了编码的低复杂度。这种构造方法面向快速迭代编码，可以不经高斯消元由校验矩阵[H]直接编码，在大码长高速率的情况下具有更好的译码性能。本文以（16 384，8 192）LDPC码为例进行验证，并给出快速编码算法，以期在LDPC译码器设计中实现低复杂度和高速率。
1 准双对角线结构校验矩阵的构造方法
定义LDPC码的奇偶校验矩阵[H]大小为[m×n]，信息比特长度[k=n-m。]定义基础校验矩阵[Hb]大小为[mb×nb，][Hb]中的元素对应于[H]的子矩阵[P，]则[H]可以表示为：
[H=P0，0P0，1P0，2???P0，nb-2P0，nb-1P1，0P1，1P1，2???P1，nb-2P1，nb-1P2，0P2，1P2，2???P2，nb-2P2，nb-1??????Pmb-1，0Pmb-1，1Pmb-1，2???Pmb-1，nb-2Pmb-1，nb-1]
式中：[Pi，j]是一个[z×z]大小的循环单位矩阵，或是一个[z×z]大小的全零矩阵。[Hb]中的元素扩展后得到[H。]此处，[n=nb×z，][m=mb×z，][z]表示扩展因子。扩展时，将[Hb]中的“1”用一个[z×z]大小的循环单位矩阵[Pi，j]替换，将[Hb]中的“0”用一个[z×z]大小的全零矩阵[Pi，j]替换。
通常循环单位矩阵[Pi，j]都是由单位矩阵简单地循环右移得到的，不同的循环右移矩阵可以用不同的移位步数来表示，得到归一化的基础校验矩阵[Hbm，]其大小和二进制基础校验矩阵[Hb]相同。[Hb]中每一个“0”用“[-1]”替代，表示一个[z×z]的全零矩阵；其中的每一个“1”用一个非负整数的循环移位次数[Pi，j]表示。这样归一化的基础校验矩阵[Hbm]可以直接扩展为奇偶校验矩阵[H。]
[Hb]可以分成两部分，写成[Hb=[Hb1Hb2]]的形式。其中：[Hb1]表示系统比特部分，尺寸为[mb×kb，][kb=nb-mb；][Hb2]表示校验比特部分，尺寸为[mb×mb。][Hb2]可以进一步分解为两部分，[hb]有奇数的重量，[H′b2]是一个双对角线结构，第[i]行第[j]列的矩阵元素满足[i=j]和[i=j+1]时为“1”，其他时候均为“0”。
[Hb2=hbH′b2=hb0hb1?hbm-110111??1101]
式中：[hb]有固定的[hb0=1，][hbmb-1=1]及[hbj=1，][0 下面，选定[12]码率的（16 384，8 192）LDPC码采用上述准双对角线结构构造出它的奇偶校验矩阵[H。]首先设定扩展因子[z=1 024，]则基础校验矩阵[Hb]的尺寸为[8×16，]即[mb=8，][nb=16。]其中的元素为[1 024×1 024]的循环单位矩阵或全零矩阵。将[Hb]中的所有元素进行[z×z]矩阵的替换，就得到[12]码率（16 384，8 192）LDPC码的奇偶校验矩阵[H，]如图1所示。
2 快速迭代编码算法
利用上述构造方法中LDPC码基础校验矩阵[Hb]的准双对角线结构，直接由校验矩阵[H]进行迭代编码，可以简化编码复杂度，具体步骤描述如下：
首先，将奇偶校验矩阵[H]的基础校验矩阵写成[Hb=[Hb1Hb2]]的形式。定义其中的矩阵[Zq，]即若[q]为非负整数，[Zq]是大小为[z×z]的置换矩阵，由单位矩阵右移[q]位得到，若[q]为[-1]，则[Zq]为全零矩阵。其中[Hb2]除第一列外，其余部分是双对角线结构。
[Hb1=ZHb1（1，1）ZHb1（1，2）…ZHb1（1，kb）ZHb1（2，1）ZHb1（2，2）…ZHb1（2，kb）????ZHb1（mb，1）ZHb1（mb，2）…ZHb1（mb，kb）]
[Hb2=Zh（1）Z0Z-1Z0Z0Z-1?Z0Z0Z-1Z0?Zh（r）??Z-1?Z0?Z0Z0Z-1Z-1Z0Z0Zh（mb）Z0]
定义编码器输出行向量为[c，]其长度为[n=k+m，]信息位向量为[s，]校验位向量为[p，]则[c=sp]。
将[sT]和[pT]进行分段，每段长度为[z]，则有：
[sT=[sT1sT2…sTkb]pT=[pT1pT2…pTmb]]
其中，
[si=si-1z+1si-1z+2…sizT，i=1，2，…，kb] [pi=pi-1z+1pi-1z+2…pizT，i=1，2，…，mb] 根据校验等式[H?cT=0]，可得[H2?pT=H1?sT。]定义基础校验矩阵[Hb]的子矩阵[Hb1]中位于[i，j]位置的元素为[Hb1i，j，]根据[Zq]的定义和[Hb2]的形式可得：
[Zh1Z0Z-1Z0Z0Z-1?Z0Z0Z-1Z0?Zhr??Z-1?Z0?Z0Z0Z-1Z-1Z0Z0ZhmbZ0?p1p2?pmb]
[=ZHb11，1ZHb11，2…ZHb11，kbZHb12，1ZHb12，2…ZHb12，kb????ZHb1mb，1ZHb1mb，2…ZHb1mb，kb?s1s2?skb] 本文提出一种采用准双对角线结构来构造半随机LDPC码奇偶校验矩阵的方法，在IEEE 802.16e标准LDPC码的基础上，对基础矩阵[Hb]和扩展因子[z]的大小不作任何具体限制，可以更加灵活地实现不同码率和码长组合的编码设计。采用这种方法构造出的是一种混合结构的奇偶校验矩阵，矩阵的左半部分是随机构造的基础矩阵，能够确保编码的优异性能；矩阵右半部分采用准双对角线结构，确保了编码的低复杂度。这种构造方法面向快速迭代编码，可以不经高斯消元由校验矩阵[H]直接编码，在大码长高速率的情况下具有更好的译码性能。本文以（16 384，8 192）LDPC码为例进行验证，并给出快速编码算法，以期在LDPC译码器设计中实现低复杂度和高速率。
1 准双对角线结构校验矩阵的构造方法
定义LDPC码的奇偶校验矩阵[H]大小为[m×n]，信息比特长度[k=n-m。]定义基础校验矩阵[Hb]大小为[mb×nb，][Hb]中的元素对应于[H]的子矩阵[P，]则[H]可以表示为：
[H=P0，0P0，1P0，2???P0，nb-2P0，nb-1P1，0P1，1P1，2???P1，nb-2P1，nb-1P2，0P2，1P2，2???P2，nb-2P2，nb-1??????Pmb-1，0Pmb-1，1Pmb-1，2???Pmb-1，nb-2Pmb-1，nb-1]
式中：[Pi，j]是一个[z×z]大小的循环单位矩阵，或是一个[z×z]大小的全零矩阵。[Hb]中的元素扩展后得到[H。]此处，[n=nb×z，][m=mb×z，][z]表示扩展因子。扩展时，将[Hb]中的“1”用一个[z×z]大小的循环单位矩阵[Pi，j]替换，将[Hb]中的&
ldquo;0”用一个[z×z]大小的全零矩阵[Pi，j]替换。
通常循环单位矩阵[Pi，j]都是由单位矩阵简单地循环右移得到的，不同的循环右移矩阵可以用不同的移位步数来表示，得到归一化的基础校验矩阵[Hbm，]其大小和二进制基础校验矩阵[Hb]相同。[Hb]中每一个“0”用“[-1]”替代，表示一个[z×z]的全零矩阵；其中的每一个“1”用一个非负整数的循环移位次数[Pi，j]表示。这样归一化的基础校验矩阵[Hbm]可以直接扩展为奇偶校验矩阵[H。]
[Hb]可以分成两部分，写成[Hb=[Hb1Hb2]]的形式。其中：[Hb1]表示系统比特部分，尺寸为[mb×kb，][kb=nb-mb；][Hb2]表示校验比特部分，尺寸为[mb×mb。][Hb2]可以进一步分解为两部分，[hb]有奇数的重量，[H′b2]是一个双对角线结构，第[i]行第[j]列的矩阵元素满足[i=j]和[i=j+1]时为“1”，其他时候均为“0”。
[Hb2=hbH′b2=hb0hb1?hbm-110111??1101]
式中：[hb]有固定的[hb0=1，][hbmb-1=1]及[hbj=1，][0 下面，选定[12]码率的（16 384，8 192）LDPC码采用上述准双对角线结构构造出它的奇偶校验矩阵[H。]首先设定扩展因子[z=1 024，]则基础校验矩阵[Hb]的尺寸为[8×16，]即[mb=8，][nb=16。]其中的元素为[1 024×1 024]的循环单位矩阵或全零矩阵。将[Hb]中的所有元素进行[z×z]矩阵的替换，就得到[12]码率（16 384，8 192）LDPC码的奇偶校验矩阵[H，]如图1所示。
2 快速迭代编码算法
利用上述构造方法中LDPC码基础校验矩阵[Hb]的准双对角线结构，直接由校验矩阵[H]进行迭代编码，可以简化编码复杂度，具体步骤描述如下：
首先，将奇偶校验矩阵[H]的基础校验矩阵写成[Hb=[Hb1Hb2]]的形式。定义其中的矩阵[Zq，]即若[q]为非负整数，[Zq]是大小为[z×z]的置换矩阵，由单位矩阵右移[q]位得到，若[q]为[-1]，则[Zq]为全零矩阵。其中[Hb2]除第一列外，其余部分是双对角线结构。
[Hb1=ZHb1（1，1）ZHb1（1，2）…ZHb1（1，kb）ZHb1（2，1）ZHb1（2，2）…ZHb1（2，kb）????ZHb1（mb，1）ZHb1（mb，2）…ZHb1（mb，kb）]
[Hb2=Zh（1）Z0Z-1Z0Z0Z-1?Z0Z0Z-1Z0?Zh（r）??Z-1?Z0?Z0Z0Z-1Z-1Z0Z0Zh（mb）Z0]
定义编码器输出行向量为[c，]其长度为[n=k+m，]信息位向量为[s，]校验位向量为[p，]则[c=sp]。
将[sT]和[pT]进行分段，每段长度为[z]，则有：
[sT=[sT1sT2…sTkb]pT=[pT1pT2…pTmb]]
其中，
[si=si-1z+1si-1z+2…sizT，i=1，2，…，kb] [pi=pi-1z+1pi-1z+2…pizT，i=1，2，…，mb] 根据校验等式[H?cT=0]，可得[H2?pT=H1?sT。]定义基础校验矩阵[Hb]的子矩阵[Hb1]中位于[i，j]位置的元素为[Hb1i，j，]根据[Zq]的定义和[Hb2]的形式可得：
[Zh1Z0Z-1Z0Z0Z-1?Z0Z0Z-1Z0?Zhr??Z-1?Z0?Z0Z0Z-1Z-1Z0Z0ZhmbZ0?p1p2?pmb]
[=ZHb11，1ZHb11，2…ZHb11，kbZHb12，1ZHb12，2…ZHb12，kb????ZHb1mb，1ZHb1mb，2…ZHb1mb，kb?s1s2?skb] 展开后可以推得：
[p1=（Zh（1）+Zh（r）+Zh（mb））-1?i=1mbj=1kbZHb1（i，j）?sTj]
将[p1]代回到上式，可得：
[p2=j=1kbZHb1（1，j）?sj+Zh（1）?p1]
以此方法类推，可得出求[p]各个分量[pi]的迭代公式：
[pr+1=pr+j=1kbZHb1（r，j）?sTj+Zh（r）?p1pi=pi-1+j=1kbZHb1（i-1，j）?sTj，i=3，4，…，r，r+2，r+3，…，mb]
对于选定的（16 384，8 192）LDPC码，其奇偶校验矩阵[H]为[16 384×8 192]的准循环矩阵，由8×16个1 024×1 024的循环子矩阵构成，每个子矩阵是单位循环移位矩阵或全零矩阵。
首先，将待编码的大小为1×8 192的信息向量[s]分成8个1×1 024的子向量[s=s1…s8。]
然后，由[pi]的迭代公式依次计算出[p1～p8，]如下面的式子所示，由此得出[p=p1…p8。]
[p1=i=18j=18ZHb1（i，j）?sTjp2=j=18ZHb1（1，j）?sj+Zh（1）?p1p3=p2+j=18ZHb1（2，j）?sTjp4=p3+j=18ZHb1（3，j）?sTjp5=p4+j=18ZHb1（4，j）?sTj+Zh（4）?p1p6=p5+j=18ZHb1（5，j）?sTjp7=p6+j=18ZHb1（6，j）?sTjp8=p7+j=18ZHb1（7，j）?sTj]
最后，组合[s]和[p，]得到码字[c，]完成编码。
由于在编码的过程中只涉及到向量的移位运算和加法运算，故在存储校验矩阵[H]时不需要存储整个矩阵，只需存储一个[8×16]的基础校验矩阵[Hb，]简化了编码复杂度。
3 译码性能仿真
在对准双对角线结构LDPC码的构造方法和快速迭代编码算法描述的基础上，本节主要通过系统仿真验证采用这种构造方法的LDPC码的纠错性能，为下一步译码器的硬件设计提供理论依据。
首先，通过仿真对采用准双对角线结构的IEEE 8.2.16e标准LDPC码和采用简单的双对角线结构的DVB?S2标准LDPC码的误码性能进行分析比较。选取码长为16 200、码率为[12]的LDPC码，采用归一化最小和（NMS）算法进行译码，设置最大迭代次数为15次，归一化因子[α]取0.85。性能仿真图如图2所示。
由图2可以看出，IEEE 802.16e标准LDPC码的误码率性能要远远好于DVB?S2标准LDPC码，采用准双对角线结构能获得更加优异的误码性能。
以下仿真主要以本文选取的（16 384，8 192）LDPC码为例进行误码性能的分析验证。
从图3可以看出，在误比特率为[10-6]时，采用准双对角线结构的（16 384，8 192）LDPC码的性能与无编码时相比有9.5 dB的增益，具有优异的误码率性能。同时，与图2的结果对比可知，本文所描述的LDPC码构造方法与IEEE 802.16e标准中的构造方法具有同样优异的误码率性能，而且能够在实际设计中增加灵活性，为LDPC译码器硬件实现提供了更多的设计方案。
4 结 语
本文介绍了一种采用准双对角线结构构造半随机LDPC码奇偶校验矩阵的方法，并以（16 384，8 192）LDPC码为例完成了快速迭代编码。通过对IEEE 802.16e标准LDPC码编码方法的改进，增强了译码器设计的灵活性，确保了低编码复杂度和高译码性能。最后，基于归一化最小和译码算法进行了
仿真验证，得到了理想的译码性能。通过本文的研究，以期在下一步LDPC译码器硬件实现中获得更优异的译码性能和更低的译码复杂度。
参考文献
. IEEE Transactions on Information Theory， 2001， 47（2）： 599?618.
. IEEE Transactions on Information Theory， 2001， 47（7）： 2711?2736.
[3] 贺鹤云.LDPC码基础与应用[M].北京：人民邮电出版社，2009.
[4] 肖扬.Turbo与LDPC编解码及其应用[M].北京：人民邮电出版社，2010.
[5] 袁东风，张海刚.LDPC码理论与应用[M].北京：人民邮电出版社，2008.
[6] 张仲明.高速数传中LDPC码关键技术研究[D].长沙：国防科学技术大学，2009.
[7] 雷菁，高永强，王建辉，等.基于串行消息传递机制的QC?LDPC码快速译码算法研究[J].电子与信息学报，2008，30（12）：2938?2942.
[8] 张庆林，文思群，胡旭洋，等.基于CCSDS标准的LDPC编译码应用技术研究[J].计算机光盘软件与应用，2013（15）：65?66.