一种基于本原多项式的LDPC码构建新算法✴

蔡黎，代妮娜，戴闽鲁，2

一种基于本原多项式的LDPC码构建新算法✴

蔡黎1，代妮娜1，戴闽鲁1，2

（1.重庆三峡学院电信学院，重庆万州404000；2.日本芝测株式会社，日本东京150000）

在分析传统LDPC编码方式的基础上，提出一种基于本原多项式实现LDPC编码的新方法。根据特定LDPC码长选择合适的本原多项式作为子矩阵，对子矩阵进行行列分解、组合，最终构建LDPC码校验矩阵H。仿真实验结果和工程应用证明：新算法构建的LDPC码在恶劣的通信环境下，误码率、误帧率优于传统Mackay-LDPC码，具有较好的性能。

LDPC；本原多项式；矩阵分解；校验矩阵

1 引言

低密度校验（LDPC）码是一种性能逼近Shannon容量极限的渐进好码，编码性能优越，其长码性能在某些时刻甚至能够超过Turbo码［1］，目前已成为4G时代重点研究的通信编码方式之一。

本原多项式是一种常见多项式，本质是四环循环编码，因为循环算法的硬件电路实现容易，所以在传统通信编码技术中，经常用到本原多项式编码。

如能将本原多项式循环算法易于硬件实现的优点与LDPC码长码时间性能良好的优势相结合，则可能构建一种性能更优的LDPC码。因此，本文提出一种基于本原多项式的LDPC构建新算法。

2 本原多项式

2.1 本原多项式的定义

一个n次不可约的多项式，如能整除1+Z2n-1，而不能整除其它1+Zl（l，2n-1），可称此不可约多项式为本原多项式［1］。

设有2m个符号的域为伽罗华域GF（2m），有2m个符号的算法如下：从有两个符号和一个m次多项式P（X）开始引入新符号，若P（X）=0，列出α的幂的表，在控制P（X）取值的情况下，α的幂一直到2m-2都可取得不同值（α2m-1除外），0，1，α，α2，…，α2m-2为2m个域元素的集合，因此，每个元素可以用1，α，α2，…，α2m-2之和表示。例如，当m=4，P（X）=x4+x+1，构建如下多项式集合：

集合中的元素α称为域GF（2m）的本原元，若GF（2m）任一元素的幂能够生成GF（2m）的全部非零元素，则称它为本原的。

2.2 本原多项式的存在性

综上，对任意m次既约多项式P（X），如可给出包含0和1在内的2m个不同符号的整表，则称其为本原多项式［2］。同理，对于m次既约多项式P（X），

若P（β）=0，β是GF（2）m的一个本原元素，则称此多项式是本原多项式。

对于任意正整数m，至少存在一个m次本原多项式。m次本原多项式的存在，为用其构造LDPC码提供了理论依据。

3 本原多项式LDPC码的构造

3.1 构造规则

LDPC码是一种校验矩阵为稀疏矩阵的编码，LDPC码定义为稀疏奇偶校验矩阵H的零空间，即有H*CT=0，其中C是码字序列。

本文提出如下的H矩阵的结构构造规则：

（1）设H矩阵每列含1的个数为较小的常数wc（wc≥3）；

（2）设H矩阵每行含1的个数为较小的常数wr（wr≥wc）；

（3）H矩阵任何两列之间同为1的行数不超过1，H矩阵中不含四角为1的小方阵，即无4线循环［3］，最小围线至少是6；

（4）wc和wr小于码字长度N，行数M（Nwc／wr）N→∞，则wr／N=wc／M→0时，可证明以上规则构造的H矩阵是稀疏矩阵。

3.2 构造算法

本原多项式的核心优势是利于循环，因此本构造算法仍然基于循环原理，结合矩阵的行列分解技术，易于硬件实现。具体构造步骤如下所述。

（1）根据实际应用系统标准中规定的码长N和信息位数M，确定校验矩阵H的参数：行数等于N -M，列数等于N。

（2）在域GF（2m-1）上选择合适的本原多项式P（X）。本原多项式中系数为1的项的个数与矩阵行重wr相等。m和wr须满足m=N／wr，且都为正整数。因为m越大，在GF（2m-1）中找寻本原多项式的运算就越复杂，所以计算时一般将m的取值范围控制在约定的范围内，以尽量减少循环次数。

（3）将P（X）的向量形式进行m-1次右循环得到m×m的子矩阵H′，再进行列分解，设列分解因子t=wr，得到列分解后的wr个m×m矩阵H′i1（i=1，2，…，wr），对H′i1进行列组合得到m×N矩阵H″1。

（4）若N-M＜m，则需要重新选择本原多项式；若N-M＞m，则需要重新选择本原多项式进行行扩展，此多项式来自伽罗华域GF（2m2-1），且m2＜m，m2=N-M-m，返回到第三步循环；若N-M=m，H″1即为所求的校验矩阵H，结构应如图1所示。

基本算法流程图如图2所示。

3.3 构造实例

设有伽罗华域GF（27）的本原多项式，表达式为P（X）=1+X3+X7，写成0、1的序列向量为（1，0，0，1，0，0，0，1），该向量经过m=7次循环移位得到8× 8矩阵H′7：

H′7校验矩阵的行重、列重为3，当且仅当列分解因子t=3时，才有w1=w2=w3=1，H′7能分解成3个8×8的子矩阵，子矩阵行重、列重都为1。可将分解后的子矩阵看作3个单位矩阵的随机变化排列结果，对H′7进行分解，得到新的8×24矩阵H7，H7行重、列重分别为3、1。

利用检验校验矩阵是否有4环的方法进行检验，可得矩阵H7没有Girth=4的环［4］。

同理，用上述方法也可得到利用其它本原多项式循环矩阵经过分解的子矩阵。多个这样的子矩阵进行组合就可以得到任意行重、列重的规则LDPC码校验矩阵［5］。

在组合得到LDPC码校验矩阵的过程中，若选择本原多项式P（X）=1+X+X6生成循环矩阵与H7组合，则需对多项式的向量进行填充处理，具体算法是在向量末尾加0补充至8项，再分解可得七阶本原多项式相似矩阵H6：

将H6和H7进行物理组合，得校验矩阵H：

显然，组合方法能够将校验矩阵H扩展为行重为3、列重为2的稀疏矩阵，矩阵无girth=4的环。

若需增加此校验的行重，则可选取阶数小于7的本原多项式进行横向组合，方法与上类似。

4 性能分析

4.1 仿真分析

将码率同为1／3、矩阵格式为（16，24，2）的采用传统Mackay算法构建的Mackay-LDPC码和用上述算法构造的本原LDPC码进行对比仿真实验。

实验采用常用的硬判决译码方式进行译码，在单输入单输出（Single-input Single-output，SISO）AWGN信道环境中进行信号传输，主要对比参数为误码率（BER）和误帧率（FER），用Matalab7.0仿真得到的结果如图3所示。

观察图3，以信噪比（SNR）等于8 dB为分界线，当SNR＜8 dB时，本原LDPC码与Mackay-LDPC码的误码率、误帧率性能相差不大；当SNR＞8 dB时，本原LDPC码的误码率性能、误帧率性能则优于Mackay-LDPC码，约大于0.5 dB。

实验证明：在误码率相同且SNR较小环境下，通过新算法得到的基于本原多项式的LDPC码性能更优，更能适应恶劣的通信环境。

4.2 工程应用分析

上述算法已经在中国移动多媒体广播（China Mobile Multimedia Broadcasting，CMMB）系统中投入工程应用。在实验系统中分别使用本原LDPC码和Mackay-LDPC码，采用同一计算时间对同一路径路测，统计路测结果文件得到表1。

表1说明：当网络覆盖范围小、发射端功率或信号强度正常、满足仿真条件SNR＜8 dB时，采用两种不同的编码方式得到的通信质量相近；当通信覆盖范围增大、通信环境恶化或发射端输出功率增大，满足仿真条件SNR＞8 dB时，基于本原多项式的LDPC码的通信质量则优于Mackay-LDPC码。

实际通信应用与仿真实验结论一致。

5 结论

（1）新算法能够通过对阶数为m的本原多项式进行循环、矩阵分解得到（m+1）×t（m+1）的校验矩阵；

（2）仿真和工程应用证明新算法构造方式简单，计算复杂度低，能够在通信恶劣的通信环境中取得较好的质量；

（3）新算法性能真实可靠，已经在CMMB系统投入商用，运行稳定。

由于可供选择的本原多项式非唯一，可深入探讨选择最优本原多项式的算法，使其性能进一步提高。

［1］邓炯.几种LDPC码的性能比较［J］.电讯技术，2009，49（5）：82-85. DENG Jiong.Performance Comparison for Several Kinds of LDPC Codes［J］.Telecommunication Engineering，2009，49（5）：82-85.（in Chinese）

［2］Yu Kou，Lin S，Marc P，etal.Low-Density Parity-Check Codes Based on Finite Geometrics：A Rediscovery and New Results［J］.IEEETransactionson Information Theory，2010，47（7）：2711-2736.

［3］Lan L，Zeng L，Tai Y.Construction of Quasi-Cyclic LDPC Codes for AWGN and Binary Erasure Channels：A Finite Field Approach［J］.IEEE Transactions on Information Theory，2007，53（7）：2429-2458.

［4］Jun Heo.Analysisof scaling soft information on low density parity check code［J］.Electronics Letters，2003，39（1）：325-326.［5］Lan Lan，Yin Yu Tai，Behshad.New Constructions Quasicyclic LDPC Codes Based on Special Classes of BIBD′s for the AWGN and Binary Erasure Channels［J］.IEEE Transactions on Communications，2008，56（1）：39-48.

CAILi was born in Wanzhou，Chongqing，in 1981.He received the M.S.degree in 2010.He is now a lecturer.His research concerns communication and control technology.

Email：wdjyzd＠126.com

代妮娜（1983—），女，重庆人，2008年获工学硕士学位，现为讲师，主要研究方向为通信与信号处理；

DAINi-na was born in Chongqing，in 1983.She received the M.S.degree in 2008.She is now a lecturer.Her research direction is communication and signal processing.

戴闽鲁（1954—），男，辽宁沈阳人，1998年获工学博士学位，现为教授，主要研究方向为无线通信技术。

DAIMin-lu was born in Shenyang，Liaoning Province，in 1954.He received the Ph.D.degree in 1998.He is now a professor.His research direction iswireless communication technology.

A New LDPC Code Construction Algorithm Based on Prim itive Polynom ial

CAILi1，DAINi-na1，DAIMin-lu1，2
（1.Electronic and Information Engineering College，Chongqing Three Gorges University，Wanzhou 404000，China；2.ShibaSoku Co.，Ltd.，Tokyo 150000，Japan）

A new LDPC（Low Density Parity Check）code constructed by primitive polynomial is proposed based on analysis of traditional LDPC.The appropriate primitive polynomials are selected as the sub-matrixes by the length of the specific LDPC.Then thematrixes are decomposed and combined to construct the check matrix. The simulation and engineering applications prove that the performance of LDPC code constructed by proposed algorithm is better than that of Mackay-LDPC.The BER（Bit Error Rate）and FER（Frame Error Rate）are both lower in the bad communication environment.

LDPC；primitive polynomial；matrix decomposition；checkmatrix

The Science and Technology Research Program of Chongqing Education Commission（KJ111112）；Young Fund Projects of Chongqing Three Gorges University（10QN-32）

TN911.22

A

10.3969／j.issn.1001-893x.2011.10.011

蔡黎（1981—），男，重庆万州人，2010年获工学硕士学位，现为讲师，主要研究方向为通信与控制技术；

1001-893X（2011）10-0051-04

2011-06-23；

2011-08-15

重庆市教委科技研究项目（KJ111112）；重庆三峡学院青年基金资助项目（10QN-32）