QC－LDPC码的截短技术研究

刘晓健， 汪 烜

（上海无线电设备研究所，上海200090）

0 引言

LDPC（low－density parity check code）码属于传统的线性分组码，在使用软判决迭代译码算法时可以达到了渐进香农限的译码性能，此外它还具有较灵活的编译码方案和误码率基底较低的特点。其中一类校验矩阵具有准循环结构的LDPC（QC－LDPC）码，由于其编码器设计方便，并且利于解码器的并行化设计，目前已被IEEE 802．16e，IEEE 802．11n和数字电视广播DVB2－S20等标准采纳［1－3］。

QC－LDPC码虽然有以上优点，然而在码长和码率上的灵活性比较有限。在无线通信传输系统中，如果只采用几个固定码率的码字进行传输，会影响系统的整体传输吞吐率。因此需要根据实际的信道状况，动态地配置传输码率。在目前的一些通信标准中，往往通过给出一系列不同码长和码率的QC－LDPC码来满足以上需求，然而要更加灵活地对码长和码率进行调整，就需要求助于其他的一些方法。本文结合PEXIT分析方法［4］，给出了一种优化地选取截短比特的方法。

1 背景知识介绍

1．1 QC－LDPC码简介

QC－LDPC码的校验矩阵H是由一系列尺寸相同的循环置换矩阵（CPM）和零矩阵（ZM）构成的。通常H可以由如下所示的基矩阵扩展得到：

式中：Ai，j，1≤i≤m，1≤j≤n，表示一个CPM或ZM。Ai，j的取值由具体的构造方法确定。以IEEE 802．16 e中给出的1／2码率的 QC－LDPC码为例，该码的校验矩阵的基矩阵尺寸为12×24。当Ai，j＝－1时，它代表一个24×24的ZM；当Ai，j＝ω，－1＜ω＜24时，它对应的CPM 具有如下形式：第一行的唯一一个非零单元位置在第ω列，第二行的唯一一个非零单元在第（ω＋1）mod 24行，其他各行依次类推。为了避免在Tanner图上出现圈四的情况，Hb中任意两行和任意两列中不能包含超过两个相同的非零元素。QC－LDPC码的高速的译码器设计方便。采用BP或者MS算法时，将各个CPM中非零元素对应的变量节点（校验节点）信息存储在独立的RAM中，通过一定的时序安排便可以实现半并行的译码方式。基于QC－LDPC码的高速译码算法研究及硬件设计，有兴趣的读者可以参考文献等［5－7］。

1．2 PEXIT分析方法

QC－LDPC码是一类特殊的基于原型图（prototype）方法构造的LDPC码，通过把（1）式中的非负元素替换成“1”，并画出对应的Tanner图即可得到它们的原型图。用PEXIT来分析QCLDPC码的收敛门限相比直接用EXIT来分析主要具有两大优点：运算量少和通用性高。

运算量的减少主要源于原型图的尺寸远远小于校验矩阵H；通用性高，是由于在IEEE 802．16 e等标准中，同一种码率条件下，不同长度的QCLDPC码具有相同的原型图，因此对一个原型图进行分析得到的结果可以适用于该原型图对应的所有码长的QC－LDPC码。PEXIT的原理及相关步骤可以参考相关文献［4］。

2 非规则QC－LDPC码的截短技术

所谓截短，指的是发送端在编码时在信息序列的某些特定位置插入预设的比特（比如都插入比特“1”），且这些特定的位置是发送端和接收端预先约定的。在发送端输出的序列中，这些预设的比特可以不用发送，因而缩短了码长，同时由于这些比特占用了一部分信息比特的位置，并且它们不包含有效信息，所以截短后的码字码率更低。在接收端译码时，译码器可以将预设的比特的置信度设为无限大。考虑到置信度无限大的比特在迭代译码过程中作用不大，为了减少运算量，通常可以将这些比特对应的校验矩阵中的列删除，用于对截短的码字序列进行译码。

截短技术对于规则QC－LDPC码的作用在文献［8］中已经有较为详细的分析，这种技术可以增加给定的规则QC－LDPC码的girth，即Tanner图上最短圈的长度。由于girth是影响规则QCLDPC码译码性能的主要因素之一，较大的girth通常可以使码字在瀑布区取得更好的性能。对于目前无线通信系统中常用的非规则QC－LDPC码，通常设计人员更关心的是码字在瀑布区的性能，即译码算法能否在较低的信噪比条件下收敛。决定译码器收敛门限的主要因素是校验矩阵的行列重量分布，因此对于非规则QC－LDPC码，用于规则码的截短比特选择方法不再适用，因而在选择合适的截短位置时必须将校验矩阵的重量分布考虑在内。下面本文以非规则QC－LDPC码为对象，给出一种优化选择截短位置的算法。

在软判决迭代译码的过程中，变量节点vj输出信息的可靠度与它的度数λ（j）成正比，而校验节点ci在低信噪比区域输出信息的可靠度与它的度数ρ（i）成正反比，因此在截短后的Tanner图中，应该尽量保留那些度数比较大的变量节点，同时减少与这些变量节点相连的校验节点的度数。这样，这些变量节点便可以得到更加可靠的外信息，同时由于它们的度数比较大，因而能够使得相对更多的校验节点收到可靠的外信息，从而加快算法的收敛。变量节点vj收到的外信息来自与它相连的各个校验节点ci，i∈A（j）。这些校验节点输出给该变量节点的信息则来自于除vj以外与它们相连的变量节点。因此可以用下面的式子来近似计算与变量节点vj的外信息相关的变量节点数量：

式中：ρ（i）表示校验节点ci的度数。由上式可以看到，SE（j）受到两个因素的影响：该变量节点vj的度数λ（j）；与该变量节点相连的校验节点的度数。

利用式（2）提供的信息作为辅助，可以按照如下方法来选择截短的非规则QC－LDPC码的变量节点：首先，选择原型图上度数最小的变量节点构成候选节点集合，接着用式（2）计算这些候选节点的SE（j），最后选取SE（j）最大的变量节点作为被截短的节点。选择度数最小的变量节点是为了尽量保留度数较大的变量节点，而在这些节点中选择SE（j）最大的节点截短可以尽可能地减少截短后得到的校验矩阵中度数比较大的校验节点的度数。根据这样的选择方式，截短后的码字在译码时能够更快地收敛，从而得到更好的瀑布区性能。有时候会遇到不止一个候选变量节点都具有最大的SE（j），这时候应用上一节中介绍的PEXIT分析方法，对于将这些候选节点截短后的原型图逐个进行分析，从中选取能够得到最低门限的候选节点。

根据以上叙述，具体的搜索算法如下所示：

a）初始化：令λ＝［λ（1），λ（2），…，λ（K）］表示信息位对应的原型图上变量节点的度数分布，G∞＝｛1，2，…，K｝表示可用的变量节点集合，T表示需要被截短的变量节点总数；

b）寻找候选节点：从所有可用的变量节点中找出最小的度数cdmin＝min｛λ（j），j∈G∞｝，如果λ（j）＝cdmin，则将变量节点vj设为候选节点；

c）用式（2）计算所有候选节点的SE（j）；

d）选择候选节点中SE（j）最大的节点作为进一步的候选节点，如果这些候选节点不止一个，则用PEXIT分析方法分别求将它们截短后的原型图的收敛门限，从中选取门限最低的作为该次迭代的输出；

e）如果节点vJ最终被选中，则G∞＝G∞＼｛J｝，对于所有的i∈A（J），ρ（i）＝ρ（i）－1。

f）T＝T－1，如果T＝0，中止迭代，否则回到步骤2继续执行。

以上给出的截短节点选择算法也适用于普通的非规则LDPC码，这时只要将以上在原型图上进行的操作移植到Tanner图上，同时把PEXIT分析方法更换为普通的EXIT分析方法或密度演变算法即可。

3 仿真结果与分析

这一节以IEEE 802．16 e和IEEE 802．11 n中给出的QC－LDPC码为对象，分析比较截短算法的效果。仿真环境为AWGN信道，信号采用BPSK调制，译码算法为BP算法，最大迭代次数设为100。本文用A－X的字母对基矩阵的列从左到右进行编号，表1截短图案中的字母分别表示被截短的变量节点对应的基矩阵中列的位置。

本文分别选取IEEE 802．16 e中码率为1／2，码长为2 304的 QC－LDPC码和IEEE 802．11 n中码率为1／2，码长为1 944的QC－LDPC码作为对象，原型图上的截短节点数设为4，截短后的码率为0．4。下表中给出了采用不同的截短图案时用PEXIT分析方法计算出的收敛门限，并分析了截短以后校验矩阵的girth。表中第一栏的截短图案（A，B，E K）和（C，D，F，G）是用上一节介绍的方法得到的，其他两栏的图案是穷举搜索得到的，旨在提高校验矩阵的girth。与规则QC－LDPC码的截短不同，girth的增加并不会改善码字的收敛门限，而通过本文给出的方法寻找的截短图案则能给出更好的结果。

表1 不同截短方案用PEXIT分析方法计算得到的收敛门限

在下面两张仿真曲线图中，分别对应表1中的各种截短方案，给出了对应的仿真曲线，由这两张图可以看到，通过优化得到的截短图案相比表1中的其他截短图案都取得了更好的性能。其中图1中，优化选取的图案1相比图案2和3，在误帧率为10－3时，分别取得了约0．2 dB和0．35 dB的增益；图2中，优化选取的图案1相比图案2和3，在误帧率为10－3时，分别取得了约0．25 dB和0．5 d B的增益。

图1 （2 304，1152）QC－LDPC码各种截短方案的误帧率比较

4 结论

本文讨论了如何在给定的QC－LDPC码的基矩阵上通过截短技术来获得可变速率的QC－LDPC码的构造方法。这种方法可以在一定范围内，提高QC－LDPC码在码长和码率方面的灵活性，从而使之在实际应用中能够更加灵活地适应各种场景。结合PEXIT分析方法，本文分别给出了如何优化地选择截短位置的方法。数据分析和仿真结果显示，本文的选择方法能够给出较为理想的解决方案。

图2 （1 944，972）QC－LDPC码各种截短方案的误帧率比较

［1］ IEEE Standard for Local and Metropolitan Area Networks Part 16．Air Interface for Fixed Broadband Wireless Access Systems［J］．IEEE Std 802，16TM－2004，2004．

［2］ IEEE 802．11－Wireless LAN Medium Access Control（MAC）and Physical Layer（PHY）Specifications［J］．IEEE，2007．

［3］ ETSI EN302 307 V1．1．1－2005 DVB．Second Generation Framing Structure，Channel Coding and Modulation System for Broadcasting，Interactive Service，News Gathering and Other Broadband Satellite Applications［S］．2005．

［4］ Liva G andChiani M．Protograph LDPC Codes Design Based on Exit Analysis［C］．GLOBECOM′07．IEEE，2007，（11）：3250－3254．

［5］ 赵春明，许恩杨，姜明，黄鹤．双涡轮结构低密度奇偶校验码解码器［P］．专利号ZL 2006100965359．

［6］ 单鸣．LDPC码编解码技术研究及实现 ［D］．硕士论文，东南大学，2004．

［7］ Yongmei Dai；Zhiyuan Yan and Ning Chen．Optimal Overlapped Message Passing Decoding of Quasi－Cyclic LDPC Codes［J］．IEEE Transactions on VLSI Systems，2008，16（5）：1063－8210．

［8］ M．P．C．Fossorier．Quasi－cyclic Low－density Parity－check Codes from Circulant Permutation Matrices［J］．IEEE Trans．Inform．Theory，Aug．2004，50（8）：1788－1794．