LDPC码稀疏校验矩阵的重建方法

包 昕，周磊砢，何 可，游 凌



LDPC码稀疏校验矩阵的重建方法

包 昕，周磊砢，何 可，游 凌

(西南电子电信技术研究所 成都 610041)

针对LDPC码识别过程中的稀疏校验矩阵重建问题，研究并提出了3种算法。在分析和比较LDPC码与一般分组码识别模型的基础上，将LDPC码的识别问题定义为寻找码字对偶空间下某组稀疏基的数学问题。通过以校验向量行重作为优化对象，先后设计和实现了了2-阶行间线性变换、-阶行间线性变换、线性关系有限穷举的3种矩阵稀疏化算法，力求实现无误码条件下对适度码长长度LDPC码校验矩阵的有效重建。测试结果表明，该算法适用于包括802.16e、802.11n、DVB-S2、GJB7296、GB20600在内的多种LDPC码标准。

信道编码识别; LDPC识别; 校验矩阵; 稀疏化

信道编码识别即是根据解调后的比特流序列，辨识所采用的纠错编码类型及其对应参数，广义上还包括对交织和扰码的识别。

LDPC码虽属于分组码范畴，但由于其码长往往极长，构造方法多样且随机，故传统识别思路在可接受计算量内难以发挥作用。文献[10-12]通过计算后验概率对数似然比(LLR)，将软解调序列与LDPC码校验关系联系在一起。文献[13]在前者基础上，进一步完善了约束关系模型，推导并量化了相应统计学特征。

以上LDPC码的研究成果均将编码识别问题弱化为一种假设检验判决问题，是在已知集合内实现码型的准确匹配，仅能适用于闭集识别应用背景。本文重点关注无误码LDPC码的开集识别问题，力求在从无误码编码序列流中，重建LDPC码稀疏校验矩阵，最终实现非合作条件下的有效译码。

1 问题描述与分析

1.1 一般线性分组码识别问题

由于有限维线性空间中的每个线性无关向量组，都可以充当此空间一组基。因此，生成矩阵作为编码空间的一组基，并不唯一。若设定分组码采用系统结构，且信息前置，则生成矩阵必然满足形式，其中，为单位矩阵。通过对无误码码字做高斯消元线性变换，获得该形式的为：

综上，这种以恢复或测量码字空间的基为目标、获得编码生成矩阵或校验矩阵的编码识别思路，是几乎所有编码识别方法的理论基础。

1.2 LDPC码的识别

信道编码识别的本质目的不仅是获取一系列编码参数，而是在此基础上实现非合作条件下的信息获取。对于一般线性分组码，和的恢复问题等价，按照前述计算流程，在获取或的基础上，结合各种代数译码方法即可展开译码，识别工作基本完成。

然而，LDPC码的识别工作则相对不同。LDPC码稀疏校验矩阵的结构对该码译码性能具有决定性的影响。基于置信度传播的BP算法是LDPC码的常用译码算法，它建立在节点间信息传递具备统计独立性这一基本假设上。若所对应Tanner图中存在短环，则某一节点发出的信息经过短环传递回自身，则将破坏该统计独立性假设，进而影响译码性能。因此，LDPC码在构造稀疏校验矩阵时，总是力求减少甚至完全规避短环。

因此，直接按1.1节所述方法获取的校验矩往往不可能取得好的译码效果。以IEEE 802.16e的(576,288) LDPC码为例，图1a所示为标准中所定义的具备准循环结构的真实校验矩阵，图1b所示为根据式(2)所得的具备结构的等价校验矩阵。

综上，LDPC码识别问题与一般线性分组码识别问题不同，它不仅是寻找分组码码字零化空间的任意一组基，而且是在前者基础上，恢复所有基中某组具备稀疏特性的基。本文不限定LDPC码的具体构造方法，尝试仅利用码字空间的线性相关性，实现稀疏校验矩阵的重建，即对原非稀疏校验矩阵的稀疏化，用以实现无误码条件下的LDPC码识别。

2 矩阵的稀疏化

2.1 2-阶行间线性变换算法

5) 返回步骤1)。

6) 直至再也没有行可替换，迭代终止。

图2记录了IEEE 802.16e (576，288)LDPC码使用该算法所得的历次迭代后的行重分布图。原始待稀疏校验矩阵，平均行重58.5，最大行重68，最小行重48，经过12次稀疏化迭代后，行重降为6或7。

最终的稀疏化结果如图3所示。由图可见，其与图1a所示的真实校验矩阵是等价的，算法成功。

图2 (576,288)LDPC码历次迭代的行重分布

2.2 仿真测试

当前，LDPC码已广泛应用于卫星、深空、无线等通信领域，具有代表性的公开标准包括IEEE 802.16e[14]、IEEE 802.11n[15]及DVB-S2[16]、GJB 7296[17]，各种私有标准也层出不穷。本文使用2-阶行间线性变换算法，对它们展开测试。

图4针对IEEE 802.16e标准进行，参数(2 112, 1 056)。图4a为待稀疏校验矩阵，图4b为稀疏化后的结果。由图可见，稀疏化后校验矩阵已具备明显的准循环结构，经比对，与标准中描述的真实校验矩阵完全相同。

同理，图5是针对IEEE 802.11n的(1 944，1 620)LDPC码进行仿真结果，算法证实有效。

图6描述了针对GJB 7296-2011标准的试验情况。编码参数(992,744)，该系列LDPC码由清华大学设计，已成功应用于嫦娥探月工程。图6b为稀疏化结果，与真实矩阵完全一致。

以上3种LDPC标准，均属于准循环LDPC结构(QC, Quasi-Cyclic)，前两种的扩展矩阵由单位阵循环移位形成，后一种的扩展矩阵被定义为一个基于伽罗华域的伪随机交织阵。

DVB-S2的校验矩阵采用了另一种结构化设计思路。其左侧为若干带状化矩阵，可在码长极长的同时控制存储量，编码效率也获得提高。图7针对DVB-S2标准中(16 200,14 400)LDPC短码进行仿真，图7b的稀疏结果呈现明显的带状形态，非零元素比由最初的降为，经与真实矩阵比对后证实完全相同。

对于采用随机构造方式产生的LDPC码，本文选择了某商用卫星LDPC编码进行算法试验，结果如图8所示。该矩阵右侧保持双对角形式，左侧非零元素位置随机分布。经算法处理后，非零元素个数仅占，四环个数为0，可见本文的算法依然有效。

3 矩阵重建问题的解决

3.1 p-阶行间线性变换算法

更为全面的测试显示，前述算法在某些应用场合可能失效。

图9给出了GB20600[19]中编码参数为(7 493, 6 096)的LDPC码校验矩阵。该标准采用信息后置设定，构造方法虽属于QC结构(扩展因子127 bit)，但与以往明显不同的是，左侧规模为的校验区，并非由每行2个的单位阵组成双对角结构，而是由每行4个的循环移位阵组成不规则的4对角结构。

反观图9所示的GB20600校验矩阵，其校验区方阵为不规则4对角，若利用原有算法，的确难以实现矩阵恢复。将原2-阶行间线性变换，拓展为-阶行间线性变换，形成如下-阶行间线性变换算法。

6) 回到步骤2)。

7) 回到步骤1)。

8) 直至再也没有行可替换，迭代终止。

3.2 线性关系有限穷举算法

前述两种算法均可以从一定程度上，实现LDPC码的校验矩阵重建。前者基于2-阶行间线性变换这一手段，适用于采用双对角结构的LDPC码；后者是对前者的加强，将运算规则拓展为-阶行间线性变换，但仍未彻底解决稀疏校验矩阵的重建问题。

经过更为丰富的测试，本文发现：无论是2-阶行间线性变换算法还是-阶行间线性变换算法，其基本思想均是希望通过遍历原始待稀疏校验矩阵中若干种行线性变换，穷举出有限量级内可能的稀疏化校验向量；但在实际算法进行时，第层的校验节点将可能随机地等价为大于等于个原始矩阵的校验节点的线性组合；而所希望的个校验节点间的线性组合并未得到穷举，稀疏效果因此难以保证最优。这也解释了-阶行间线性变换算法仍未能彻底实现矩阵稀疏化的根本原因。

基于确保校验关系得到穷举这一目标，本文形成了矩阵稀疏化通用算法：

1) 足够稀疏；

综上所述，该算法为一种确定性算法，以确保重建结果存在并局部最优。算法复杂度约为，其中。

4 结 束 语

本文研究了无误码条件下LDPC码稀疏校验矩阵的重建问题。经过与一般分组码识别问题的分析与比较，将LDPC码识别问题等价为寻找LDPC码码字零化空间内某组稀疏基的数学问题，相继设计并实现了2-阶行间线性变换、-阶行间线性变换、线性关系有限穷举在内的3种矩阵稀疏化算法。以上算法均以线性变换作为工具，以非稀疏校验矩阵的行重作为优化对象，力求实现无误码条件下，对适度码长长度LDPC码校验矩阵的有效重建。针对包括802.16e、802.11n、DVB-S2、GJB7296在内的多种LDPC标准/协议的测试结果显示，本文算法所重建的稀疏矩阵与真实校验矩阵完全相同，实现了非合作条件下的等效译码，基本验证了该算法的有效性。

对于难度更大的误码条件下LDPC码重建问题，将在后续文章中提出相应的解决方案。

[1] VALEMBOIS A. Detection and recognition of a binary linear code[J]. Discrete Applied Mathematics, 2001, 111(1): 199-218.

Recognition of a code in a noisy environment [C]//Proceedings of IEEE International Symposium on Information Theory. Nice, USA: IEEE, 2007: 2211-2215.

[4] CLUZEAU M, TILLICH J. On the code reverse engineering problem[C]//Proceedings of IEEE International Symposium on Information Theory. Toronto, ON, USA: IEEE, 2008: 634-638.

[5] CLUZEAU M. Block code reconstruction using iterative decoding techniques[C]//Proceedings of 2006 IEEE International Symposium on Information Theory. Seattle, WA, USA: IEEE, 2006: 2269-2273.

[6] 昝俊军．低码率线性分组码的盲识别[J]．无线电技术，2009, 39(1): 19-24.

ZAN Jun-jun. Blind recognition of low code-rate binary linear block codes[J]. Radio Engineering, 2009, 39(1): 19-24．

[7] 张永光．信道编码及其识别分析[M]．北京：电子工业出版社, 2010.

ZHANG Yong-guang. Recognition and analyze the channel coding[M]. Beijing: Publishing House of Electronic Industry, 2010.

[8] 游凌, 朱中梁. Walsh函数在解二元域方程组上的应用[J]. 信号处理, 2000, 16: 27-30.

YOU Ling. The application of walsh function in resolving of GF(2) equations[J]. Signal Processing, 2000,16: 27-30.

[9] 陆佩忠.删除卷积码的盲识别[J].中国科学(E辑), 2005, 35(2): 173-185.

LU Pei-zhong. Blind recognition of punctured convolutional codes[J]. Science in China, Series E, 2005, 35(2): 173-185.

于沛东.一种利用软判决的信道编码识别新算法[J]. 电子学报, 2013 (2): 301-306.

YU Pei-dong. A norei algorithm for channei coding recognition using soft decision[J]. Acta Electronica Sinica, 2013(2): 301-306.

iori probability [C]//2012 12th International Conference on ITS Telecommunications (ITST). [S.l.]: IEEE, 2012: 12-16.

[13] 包昕. 基于软解调序列的LDPC码闭集识别方法[J]. 电讯技术, 2015, 55(1): 55-60.

BAO Xin. A finite set recognition algorithm of LDPC coding by using soft-demodulation sequence[J]. Telecommunication Engineering, 2015, 55(1): 55-60.

[14] LAN/MAN Standards Committee of IEEE Computer Society, IEEE Microwave Theory and Techniques Society. Draft IEEE standard for local and metropolitan area networks part 16: Air interface for fixed and mobile broadband wireless access systems amendment for physical and medium access control layers for combined fixed and mobile operation in licensed bands[S]. IEEE P802.16e. New York, USA: IEEE Standards Activities Department, 2005: 472-475.

[15] LAN/MAN Standards Committee of IEEE Computer Society. IEEE standard for information technology telecommunications and information exchange between systems-local and metropolitan area networks specific requirements part11: Wireless lan medium access control (MAC) and physical layer (PHY) specifications[S]. IEEE P802.11n. New York, USA: IEEE Standards Activities Department, 2009: 289-293.

[16] European Broadcasting Union. Digital video broadcasting (DVB): Second generation framing structure, channel coding and modulation systems for broadcasting, interactive services, news gathering and other broadband satellite applications[S]. DVB-S2. Europe: European Telecommunications Standards Institute, 2006: 21-23.

[17] 中国人民解放军总参谋部. 军用低密度奇偶校验码参数及编译码算法[S]. GJB-7296. 北京: 中国人民解放军总参谋部, 2011.

The General Equipment Department of the Chinese People’s Liberation Army. Parameters and algorithm of low density parity check code for military application[S]. GJB-7296. Beijing: Chinese People’s Liberation Army Press, 2011.

[18] 中国国家标准化管理委员会. 数字电视地面广播传输系统帧结构, 信道编码和调制[S]. GB 20600-2006. 北京: 中国标准出版社, 2007.

Standardization Administration of the People's Republic of China. Digital TV terrestrial broadcasting transmission system: Frame structure, channel encoding and modulation [S]. GB 20600-2006. Beijing: China Standard Press, 2007.

[19] QIN H, DIAO Q, LIN S, et al. Cyclic and quasi-cyclic LDPC codes on constrained parity-check matrices and their trapping sets[J]. IEEE Transactions on Communications, 2012, 58(5): 2648-2671.

编 辑 黄 莘

A Method of Restructuring LDPC Parity-Check Matrix

BAO Xin, ZHOU Lei-ke, HE Ke, and YOU Ling

(Southwest Electronics and Telecommunication Technology Research Institute Chengdu 610041)

To solve the problem of restructuring sparse parity-check matrix in low-density parity-check (LDPC) recognition processing, three algorithms are proposed. Through analyzing and comparing the LDPC recognition model with the tradition coding recognition models, the former one is defined as a problem of finding a group sparse-base which spans the dual-space of the coding. Then, by making the weight of check-vector as the optimized object, the 2-order linear transformation algorithm,-order linear transformation algorithm, and linear relationship exhaustive searching algorithm are proposed to restructure sparse parity-check matrix of a LDPC code with suitable code length in an error free environment. The result of simulations show that these algorithms fit most of LDPC standards, including 802.16e, 802.11n, DVB-S2, GJB7296, GB20600 and so on.

channel coding recognition; LDPC recognition; parity-check matrix ; sparse

TN911.22

A

10.3969/j.issn.1001-0548.2016.03.006

2014 - 12 - 10；

2015 - 11 - 06

国家自然科学基金(61172140)

包昕(1986 - )，男，博士生，主要从事盲信号处理、信道编码分析等方面的研究.