基于统计特性的LDPC码分析识别研究

张 俊

(同济大学电子与信息工程学院，上海 201804)

基于统计特性的LDPC码分析识别研究

张 俊

(同济大学电子与信息工程学院，上海 201804)

从统计角度出发，提出对LDPC码分析思路和初步方法，在仿真的情况下进行验证。利用LDPC码作为分组码的特性，通过统计和对统计特性的分析，在一定程度上克服传统方法——解高斯方程法的局限性，实现了对LDPC码部分特性分析。同样适用于其他分组码的分析识别。

信道编码分析识别;低密度奇偶校验码;统计特性

目前，有关智能通信(认知通信)领域的研究蓬勃发展。智能通信就是通信的发送方可以根据所处的地理、电磁环境、频谱约束等情况以及业务需求，选择最佳的通信体制、通信方式和通信参数与接收方进行可靠通信。也就是说智能通信系统的通信体制、通信方式和通信参数是随时地不断变化，这就要求智能通信系统的接收方必须能正确地对接收信号进行识别分析，包括对信道载频、信号参数、信道编码方式、编码参数等进行识别分析。

目前对信道编码的分析识别［1－4］主要停留在有限先验知识情况下的识别分析上，真正的全盲识别分析还不多。从研究对象来看，主要集中在卷积码的识别分析［5－7］上，对码长较短的分组码(包括 RS 码［8－9］)也有涉及，但由于 LDPC 可能成为下一代移动通信标准，目前尚未像其他码一样广泛应用(DVB－S||信号中采用LDPC码，)，同时受制于其较长的码长，传统的分析方法受到很大的局限，因此对LDPC码的分析识别有待于进一步的深入研究。

1 LDPC码及解高斯方程分析法

1.1 LDPC 码

LDPC(Low Density Parity Check) 码［10］是Gallager于1962年提出的一种具有稀疏校验矩阵的分组纠错码，亦称Gallager码。本文讨论的GF(2)域上的LDPC码C是一种(n，k)线性分组码，码长为n，信息序列长度为k，可以由其校验矩阵H唯一定义

H的维数是m×n，其中m=n－k，每一行对应一个校验方程，每一列对应码字的一位。每一行中非元素的个数为行重，每一列中非零的个数称为列重。LDPC码和其他分组码的最大区别在于其校矩阵中非零元素的个数远远小于零元素的个数，或矩阵的行重和列重与码长相比是很小的数，即在校验矩阵H中，每一行只有很少的1，同时每一列也只有很少的1。如果校验矩阵的各行中非零元素的个数是相同的，各列中非零元素的个数也相同，这样的LDPC码称为规则码。已经证明，当分组长度很大时，LDPC码的性能大大超过了卷积码。

1.2 解高斯方程法

信道编码识别中，分组码识别的重点在于生成多项式(或校验多项式)的识别，传统的识别方法为解高斯方程法［11－12］。线性分组码的数学模型可以描述为:C=M·G，其中 M=［M0，M1，…Mi…］表示以k比特为分组单位的输入信息序列，Mi=［mi，0，mi，1…mi，k－1］表示第 i时刻输入的 k 个比特信息;C=［C0，C1，…Ci…］表示以 n比特为分组单位的编码输出序列，Ci=［ci，0，ci，1，…ci，n－1］表示第i时刻输出的n个比特信息;G表示生成矩阵。对分组码进行识别分析重点在于仅知C而很少知道或完全未知其他信息的条件下如何估计生成矩阵G，进而成功恢复信息序列M。对编码输出序列C，有校验关系C·HT=0成立，若能通过识别分析求出HT，则由C·HT=0可求出生成矩阵G。当接收码字序列无误码时，有校验关系C·HT=0，其中 H=(h0，h1，…hn－k－1)，则有如下线性方程组:

求解上述方程的常规方法是高斯消元法，通过数学变化，可得到如下形式的增广矩阵:

其中d为解空间的维数。

方程组中 h0，h1，…hn－k－1解空间的标准基形式如下:

上述解中，只要d=n－k，则hi即可能为所求。

1.3 解高斯方程法局限性

对于码长较短的分组码(包括RS码)及卷积码，其约束关系都较短。分组码的约束长度和其分组长度相关，而卷积码的约束长度和其分组长度及存储深度有关。如在DVB－S标准中，(204，188)RS码约束长度为1632比特;对于广泛使用的(2，1，6)卷积码，其约束长度为14比特。一个典型信道噪声信道的比特误码率约为10－2至 10－3，因此，对于码长较短的分组码和卷积码，在典型信道噪声信道中总可以找到一段码字无误码，通过求解高斯方程的方法来确定其校验矩阵H(或生成矩阵G)。对于码长较长的LDPC码而言，求解高斯方程的主要有两个缺点，一是该方法不容错，即使在误码率为10－3情况下，其码长内不可避免出现误码，即使出现一个比特误码，都会导致求解高斯方程失败;其次是该方法运算量巨大，如 DVB－S||标准［13］中 LDPC码长为64800比特，求解方程的矩阵为64800×64800，解方程的运算次数约为8.389×109次。因此，正是由于很难同时满足这两个条件，因此用传统的解高斯方程法在对LDPC码的分析识别中受到很大的局限性。

2 基于统计特性的LDPC码分析研究

在信道编码的参数分析识别中，对纠错码而言，包括码型识别(分组码还是卷积码)、码率判断、码分组起点判断以及生成多项式(或校验多项式)的识别。本文中的统计方法主要解决在已知分组长度n的情况下，如何通过统计特性的分析，进行码率以及分组起点判断的问题。

2.1 按列0/1频次统计法

2.1.1 按列0/1频次统计方法

在通信过程中，信源编码主要利用信息冗余度进行压缩，来解决信息传输的效率问题;信道编码主要利用添加校验，来解决信息传输的可靠性问题。在现实通信过程中，很多信息(包括语音、图象、文本等)本身具有较大的冗余度。如果冗余度较大的信息不进行压缩，或者压缩率较小的情况下，如果按照特定的方法，对该信息进行统计，那么统计结果应该呈现出一定的不平衡特性。下面分别以64M字节的u率话音编码数据及512M字节符合G.733格式的一次群数据做按列0/1频次统计(统计帧长为48比特)，其结果如图1。从统计结果可以看出，这两种统计结果都呈现出明显的不平衡性。

图1 u率话音编码数据和G.733一次群数据按列0/1频次统计直方图

同样，对于(n，k)LDPC码，如果 k位信息是01非平衡的数据，那么信息位置经按列0/1频次统计后每一列的0/1比例是不平衡的，由LDPC码的生成方法可知，其(n－k)位校验是经过多个不平衡的信息位运算而得到的(在域GF(2)上是信息位的模2加)，所以趋于平衡，这样k位信息与(n－k)位校验在按列0/1频次统计下有不同的特性。

按列0/1频次统计是指在一定的帧长n下，统计每一列数据的0/1频次。统计方法如下:

如果数据随机，每一列数据按列1的频次的理论值为

程序及式(1)中，n为统计帧长，databegin为信息比特起点，dataover为信息比特终点，符号⌊.」表示下取整，下同。

2.1.2 分析特性

k位信息采用的是符合G.733格式的一次群信号，校验矩阵采用(96，3，6)规则LDPC码，按列0/1频次统计可以分析LDPC码的信息与校验位位置，图1是LDPC码编码之后的按列0/1频次直方图。

图2 规则LDPC码的按列0/1频次直方图

分析图1，前48位的1频次参差不齐，且大于平均频次，是信源G.733语音编码之间的相关性造成的;后48位的1频次趋于一致，且接近平均频次，是在约束关系之内，多个不平衡的信息位根据校验关系经过运算而得到，所以体现出相对较为平衡的现象。因此，通过按列0/1频次统计，可以直观得到信息位k，从而确定该分组码的码率k/n。

2.2 字符频次统计下的分析特性

2.2.1 字符频次统计

对于(n，k)LDPC码，由其生成方法可知，在大小为2n的符号空间中，只取2k个码字，如果无误码，应该出现(2n－2k)个零频。如果统计起点和码起点一致，以码长n做字符频次统计，那么将得到的2k个非零频和(2n－2k)个零频，与理论值一致;如果统计起点和真实码起点不一致，由于分组关系的错乱，即对不同分组的信息和校验位进行统计，显然得不到正确的统计关系。因此，通过不同起点下字符频次统计，可以对码长、分组起点等参数进行分析。

字符频次统计是统计数据中字符的频次，然后对频次出现的概率进行分析。

字符频次统计有两个统计参数，字符宽度n及字符统计移位起点codebegin，codebegin满足

记连续n比特为一个字符，每次移位n比特，再将连续n比特记为一个字符。统计方法如下:

程序中，databegin为信息比特起点，dataover为信息比特终点。字符统计的平均频次为:

式(2)中，符号⌊.」表示下取整。

2.2.2 分析特性

LDPC码是分组码，设生成矩阵为G，信息为M=(m0，m1，…，mk－1)。

如果数据是(n，k)LDPC码，则在大小为2n的符号空间中，只有2k个码字。用码字的准确起点对数据作字符长度为n的字符频次统计，将有2n－2k个字符是零频(出现频次为0)，2k个符号不是零频，且出现频次为

NUMS0=2k/2n=1/2n－k。 (4)

从码字的前一比特或后一比特开始作字符长度为n的字符频次统计。可以将n分为两部分(n－1，1)，其中前 n－1比特中仍将取自2n的符号空间中的2k个码字，而后面1比特则有21种情况，可以算出，在这种情况下将有2n个码字中，将有2n－2k+1个字符是零频(出现频次为0)，有2k×21=2k+1个符号不是零频，且出现频次为

以此类推，可以得出如表1所示的频次表。表1中的统计起点指距离LDPC码码字的起点多少比特，第一行是码空间内的码字的出现频次，其它起点出现的非零频码字也可能是码空间内的码字。

表1 在不同起点下LDPC码非零频字符的出现频次

为示意起见，对一个(10，2，4)LPDC码进行字符频次统计结果见表2。

表2 不同起点下(10，2，4)LDPC编码非零频字符的出现频次

续表

该码码长n为10比特，其中信息位为6比特，校验为4比特，则在大小为210的符号空间中，只有26个码字。从统计得出的表2情况看，如果统计起点为码分组起点的话，其中出现的非零字符频次为26，从码字的前一比特或后一比特做字符频次统计，其中出现的非零字符频次为27，以次类推。因此，在已知分组码长n的情况下，可以统计出在2n的符号空间中实际非零频字符出现概率，从而算出其信息位的个数，从而推导出码率;通过比较不同起点下非零频字符出现概率，从而确定该码的起点。

3 结论

由于传统方法——解高斯方程法在对LDPC码的分析识别上存在很大局限性，本文提出了基于统计特性的分析法，并对其中的按列0/1频次统计及字符频次统计法等方法进行介绍。基于统计特性的分析法利用了LDPC码作为分组码的特性，通过相关统计，并对其特性进行分析和研究，可以得到码率、起点位置以及分组长度等信息。相对解高斯方程法，这两种统计方法不对数据质量做很高的依赖，只需得到一个近似的结果就可以进行分析，一定程度上克服了解高斯方程法的局限性，解决了LDPC码部分特性的分析识别问题。

［1］柴先明，黄知涛.信道编码识别问题研究［J］.通信对抗，2008(2):6 －11.

［2］宋镜业.信道编码识别技术研究［D］.西安:西安电子科技大学，2009.

［3］张永元，楼才义，王挺.一种线性分组码编码参数的盲识别方法［P］.中国:CN101623224A.

［4］李艳斌.低码率二进制线性分组码的盲识别［J］.无线电工程，2009，39(1):37 －41.

［5］韩国宾.删除卷积码的识别技术［D］.西安:西安电子科技大学，2009.

［6］ WANG Feng Hua，HUANG Zhi Tao，ZHOU Yi Yu.A method for blind recogn－ition of convolution code based on Enclidean algorithm.IEEE International Conference on Wireless Communications［J］.IEEE Press，2007，22(3):1414－1417.

［7］JJ Chang，DJ Hwang，MC Lin.Some Extend Results on the Search for Good Convolutional Codes［J］.IEEE Trans.Inform Theory，2008，43(5):1682 －1697.

［8］刘健，谢浩，周希元.RS码的盲识别方法［J］.西安电子科技大学学报，2009，38(3):28－32

［9］陈卫东，刘健.一种容误码的RS码编码参数盲识别方法［P］.中国:CN101534168A.

［10］R G Gallager.Low －Density Parity －Check Codes［J］.IRE Transactions on Information Theory，1962，38(3):358－367.

［11］赵树杰，赵建勋.信号监测与估计理论［M］.北京:清华大学出版社，2007.

［12］朱中梁.Walsh函数在解二元域方程组上的应用［J］.信号处理，2008(B12):9 －13.

［13］BROWN，J SET AL.European Standard Digital Video Broadcasting(DVB)［S］.IEEE Press，2004，12(4):91－111.

Research on Identification of LDPC Code Based on Statistical Properties

ZHANG Jun
(School of Electronics and Information Engineering，Tongji University，Shanghai 201804，China)

In this Paper，the ideas and methods of the analysis of LDPC(Low Density Parity Check)code have been put forward from a statistical point，and they have been confirmed in the simulation conditions.The methods analyse some LDPC code’s properties in statistical view using the way taking LDPC code as a kind of block code.To a certain extent，the ideas and methods overcome the limitations of Gaussian equation method，a the traditional method，and solve some problems of achieving part characterization of the LDPC code.The ideas and methods are also applicable to the analysis and identification of other block codes.

identification of channel coding;LDPC;statistical properties

TN911.6

A

1009－315X(2012)01－0028－05

2011－09－29;最后

2011－11－09

张俊(1979－)，男，江西樟树人，助理研究员，主要从事信道编码、数字信号处理、网络协议等研究。

(责任编辑 刘敏)