一种基于速率兼容的LDPC的删除算法

开篇：润墨网以专业的文秘视角，为您筛选了一篇一种基于速率兼容的LDPC的删除算法范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！

【摘要】本文中，我们提出了一种基于RC-LDPC码的有效删除算法。该算法是基于最大平均围长（girth）准则，通过分组算法删除在Tanner图中相互远离的比特，从而删除具有最大平均围长的比特。通过仿真验证，基于最大围长的删除算法性能优于随机删除算法并且易于节约了系统资源。和PEG直接构造算法相比，性能相近，复杂度大大降低，同时可以用于自适应调制编码中。

【关键词】RC-LDPC；删除；最大平均围长

1.引言

在文献[1]中Hagenauer首次提出速率兼容删除型卷积码的概念，母码经过删除后得到高码率的码字，扩展后得到低码率的码字，这样使用一个编码器就可以获得不同码率的码字，接收端根据删除矩阵只需要一个译码器就可以对接收的码字进行译码，从而做到速率兼容。速率兼容的BCH码和卷积码很容易实现，但是它们不能提供足够的吞吐量。Turbo[2]码虽然性能良好，但是译码具有高的复杂度。速率兼容的ldpc码（RC-LDPC）是在2002年由Li J等[3]提出来的，删余是一种很好的方法，根据信道的状况，选择发送的奇偶校验位数量，从而打孔和扩展结合构造出了一系列速率的LDPC码。LDPC码删余方案的设计和分析已经被许多学者研究，但是都是基于无限码长的展开讨论的。文献[4，5]选择了一个在所需码率范围的固定码率的码字作为母码，来减小由于删余带来的过量的失真，使用随机删除来获得高码率，而低码率是通过使用一个新颖的PEG方案来扩展的。通过优化得到不规则的LDPC码字作为母码，通过剪切和扩展得到一系列速率为8/10，8/11，…，8/19的码字。随机删除可能会丢失一些重要的位，当高码率时码字可能不可恢复，为了克服这个问题，Ha和McLaughlin等[6，7]理论上讨论了删余LDPC码的收敛性，研究了译码过程中删除节点的恢复过程，发现了未删除节点的个数和成功译码概率的正比关系，指出了在迭代译码过程中，误码率仅依赖母码度数的分布以及删除后冗余的分布，当删余度数分布设计适当时，随着迭代译码次数的增加，额外的删余度会收敛到0。从上面的叙述可以看出，这些研究都是基于码长无限长和迭代次数无穷次的情况下，可是在现实系统中，由于硬件和业务要求等条件制约，码长都是有限码长，即中、短码长。

本文内容安排如下，首先介绍了常用的RC-LDPC码删除算法，然后详细介绍所提出的算法，最后给出了实验结果与结论。

2.RC-LDPC码删除算法

随机删除方法是目前自适应调制编码系统中最常用的的处理LDPC矩阵的方法。给定低码率的LDPC母码，经过编码后随机选择删除码字的位置，构造出不同高码率的码字。

对于一个码长为N，信息位长度为K的LDPC母码，码率为，想要得到码率为的码字，将要删除的变量节点个数为：

（1）

随机删除N母码中个比特，从而将码率从提高到的方法叫做随机删除。

随机删除是最佳删除的一种特例，最佳删除是在对编码的码字进行删除之前，以度数的分布对变量节点进行分组，集合为与条边相连的节点，其中是变量节点最大度数，为中删除的比特部分，根据所要得到的码率而优化的分布，定义为各个度数节点删除后占总变量结点的比例，，p表示删除的变量节点个数。

（2）

其中表示度数为j的变量节点个数，对于度数分布为的码来说，可以用来表示最佳删除的度数分布。

如图1为最佳删除的系统框图，先对码字按照度数的分布进行分组，之后经过信道加入噪声，根据译码门限来设计的分布，接收端根据发送端的删余分布重构码字，之后再把码字r进入到译码器中进行迭代译码。不同码率的译码门限不同，为了得到所需码率的最佳删除矩阵，就需要使构造的LDPC码的译码门限尽量接近目标门限。由随机删除LDPC码的译码门限相同于由最佳删除得到的RC-LDPC码。

图1 最佳删除的系统框图

3.基于最大围长的删除方法

规则码的girth和最小汉明距离之间成正比关系，对于码率为R的LDPC码，码块的错误概率与最小汉明距离、最小重量的码字数量有如下关系[9]：

（3）

式中，。

由式（3）可知，码块的错误概率随着最小汉明距离的减小反而越大；又通过围长girth的大小和最小汉明距离之间的关系可知，码块的错误概率随着girth的增大反而减小。因此，围长对于有限长度的LDPC码来说是个非常重要的性能参数。每个顶点u都有一个相应的girth，其度的分布为，其中是所有节点的最大的girth。则平均girth为[10]：

（4）

计算每个节点girth的方法是：从一个随机的根节点u出发，按照Tanner图的节点向下延伸。在此过程中，如果展开的第k层和第k-1层至少有两个节点相连，则节点u的girth为2k。接着用公式（4）来计算出平均围长。

本删除的思想是先对所有的变量节点进行分组，挑选出不能删除的节点，根据这些节点间信息的传递可以知道所有的变量节点的信息，在其他冗余节点中进行删除操作，根据所需要达到的码率来决定删除节点的个数。对于这些节点的删除操作并不是随机的，而是计算删除某个节点之后最小环长即围长girth，选择最大的平均围长的节点进行删除。这样既可以避免像随机删除那样传输删除矩阵浪费频带资源，降低了系统的复杂度，同时也避免了断环的产生，避免了低板效应。

具体算法阐述如下：

1）已知一个校验矩阵H。初始化：

设：，，。

2）从中随机选择一个顶点u。

3）设，，，其中是节点u的在图G中的所有邻居节点。

4）继续从中选择第二个顶点，重复步骤2）和3），直到。

5）再次初始化：设。

6）计算中每个节点被删除后剩余节点的girth，根据式子（4）算出平均围长。

7）把中的节点按照的大小降序排列。

8）根据所需要的码率删除中前面的节点。

此外步骤6）需要依次计算出删除后的平均girth，计算量很大，复杂度高通过大量仿真中发现，经过某个变量节点的循环和此节点girth的大小呈正比例关系。若此节点所通过的环的数目比较多，则其girth就会比较大，相应的，girth小的节点经过该变量点的环的个数就少，因为我们的目的不是为了计算girth的具体数值，而是为了找到删除哪个节点后的平均girth最大，因此用计算每个节点经过的环的个数来代替计算每个节点删除后的平均girth，这样既不影响整体性能又降低了运算的复杂度，同样得到预期的效果。

图2 系统仿真图

4.仿真结果

本仿真系统搭建如图2所示，信息比特经过加校验比特LDPC编码后，用上面所提出的基于最大围长的删除方案进行删除，得到所需要的码率。经过QPSK调制后，加入高斯白噪声。接收机在译码之前，首先要对接收的码字进行解调，解调得到的波形符号插入“0”符号后，送入译码器进行BP迭代译码，从而得到所要传递的信息数据。

AWGN信道码率为1/2的优良度分布[8]：

图3给出了基于最大围长的删除与随机删除的性能比较。观察可知，随机删除的误码率曲线比基于最大围长删除方案的误码率曲线整体右移，说明本方案优于随机删除，具有更好的纠错性能，特别在当码率越高的时候，基于最大围长的删除方案优于随机删除更明显。图4给出了基于最大围长的删除与PEG直接构造的性能比较。可以看出，在低码率时两者性能相近，在高码率时，PEG直接构造的LDPC性能好于基于最大围长的删除方案，但两者相差并不大，仍可以使用本删除方法达到相应的性能要求。图5给出了母码为码率为1/2的非规则LDPC码时，通过随机删除和基于最大围长删除方法删除不同的母码长度为1008，504和252的非规则LDPC码来得到码率为3/4的删余码的性能。码长越长，误码率性能更好，这符合LDPC码在长码时具有优越性的特点。可以看出，本方案删除可以实用于不同的码长，是一种具有通用性的删除方法。

图3 基于最大围长删除和随机删除误码率比较

图4 基于最大围长的删除与PEG直接构造LDPC码性能

图5 不同码长的性能比较

5.结论

本章首先了概述了RC-LDPC码，然后介绍了现在最常用的RC-LDPC码构造方法随机删除，针对随机删除的缺陷提出了一种新的删除方法——基于最大围长删除方法，最后搭建了仿真模型，验证了本删除方法的性能优于随机删除，并和PEG构造做了比较，同时又仿真了码长不同时的性能比较。基于最大围长的删除方法实现容易，复杂度低，误码率性能优良，将用于后来的自适应调制编码系统中。

参考文献

[1]J.Hagenauer.Rate-compatible punctured convolutional codes（rcpccodes）and their applications[J].IEEE Trans.On Commun.，vol.36，No.4，pp.389-399，Apr.1988.

[2]F.Babich，G.Montorsi，and F.Vatta.Design of rate-compatible punctured turbo（RCPT）codes[J].in Proc.IEEE Int.Conf.on Commun.（ICC 2002），vol.3，pp.1701-1705，May 2002.

[3]J.Li，K.Narayanan.Rate-compatible low density parity check codes for capacity-approaching ARQ schemes in packet data communications[J].in Proc.Int.Conf.on Commun.Internet and Information Technology（CIIT），US Virgin Islands，pp.201-206，Nov.2002.

[4]M.R.Yazdani，A.H.Banihashemi.On construction of rate-compatible low-density parity-check codes[J].IEEE Commun.Letters，vol.8，No.3，pp.159-161，Mar.2004.

[5]A.Dholakia，S.Olcer.Rate-compatible low-density parity-check codes for digital subscriber lines[J].IEEE Commun.Society，Paris，France，pp.415-419，2004.

[6]J.Ha，S.W.Mclaughlin.Optimal puncturing of irregular low-density parity-check codes[J].IEEE ICC，Alaska，USA，vol.5，pp.3110-3114，2003.

[7]J.Ha，S.W.Mclaughlin.Rate-compatible puncture low-density parity-check codes[J].IEEE Trans.On Info.Theory，50（11），pp.2824-2836，2004.

[8]J.Ha，J.Kim，D.Klinc，and S.W.McLaughlin.Rate-compatible punctured low-density parity-check codes with short block lengths[J].IEEE Trans.Inform.Theory，vol.52，No.2，pp.728-738，Feb.2006.

[9]P.Hossein，F.Farmarz.Results on Punctured LDPC Codes[J].ITW2004，San Antonio，pp.215-219，Oct.2004.

[10]W.Lei.“Several properties of short LDPC codes[J].IEEE Trans.on Commun.，52（5），pp.721-727，2004.

作者简介：

陈希元（1986—），女，黑龙江绥化人，硕士研究生，现供职于国家知识产权局专利局专利审查协作北京中心通信部。

王成（1985—），男，河北保定人，硕士研究生，现供职于61565部队。

董克（1984—），男，山东滨州人，大学本科，现供职于国家知识产权局专利局专利审查协作北京中心机械部。

李文浩（1983—），男，湖北黄冈人，硕士研究生，现供职于国家知识产权局专利局专利审查协作北京中心电学部。

姜峰（1985—），男，黑龙江齐齐哈尔人，硕士研究生，现供职于国家知识产权局专利局专利审查协作北京中心电学部。

注：其余作者对本文贡献等同第一作者。