一种基于本原域循环群生成元集的LDPC码构造方法

摘要

本发明公开了一种基于本原域循环群生成元集的LDPC码构造方法，所述方法包括步骤：S1.根据所要构造的LDPC码长L确定本原域GF(p)；S2.根据所述本原域GF(p)的循环群计算其生成元集合；S3.基于所述生成元集合构造基矩阵；S4.对所述基矩阵进行加性扩展操作，得到分块矩阵；S5.取所述分块矩阵的分块子矩阵构成校验矩阵；所述校验矩阵的零空间给出所要构造的LDPC码。利用本发明的方法构造LDPC码具有优秀的误码性能，在硬件实现中的具有低复杂度、低误码平台、快速收敛的译码性能，同时构造的校验矩阵可以结合现有技术，如掩蔽等，构造成全新的一类LDPC码。

说明书

技术领域

本发明涉及通信系统中的信道编码技术领域，更具体涉及一种基于本原域循环群生成元集的LDPC码构造方法。

背景技术

LDPC码(LowDensityParityCheckCode)在1962年由Gallager发现，后来在1995被重新发现并被证明是一种可以接近香农限的好码。随后，人们针对LDPC码的构造、编码、译码及硬件应用进行了大量的研究。根据构造方式的不同，LDPC码可以分为随机LDPC码和结构LDPC码。

随机LDPC码的构造过程是计算机搜索的过程，通过在算法中体现我们对期望的LDPC码的约束，如对应的Tanner图有较大的环长、期望的度分布、较大的停止集等，来搜索或者渐进的搜索符合期望的LDPC码。仿真表明，经良好设计的码长为10⁷的LDPC码，高斯信道下，距离香农限0.0045dB，这充分说明了随机LDPC码可以实现十分优秀的误码性能，尽管该码的长度不适合现实中的通信系统。同时，随机构造的LDPC码也不可避免的具有一些缺点。由于校验矩阵通过随机搜索的方式构造，故不具有明显的结构方面的特点，这在编码和译码实现中，特别是针对中长码的实现中，具有很大的复杂度，并且随机构造的LDPC码在最小码间距离中缺乏有效的约束，使得随机LDPC码往往具有较高的差错平底，使其在许多要求极低误码率的系统中不能应用。

与之相比，结构LDPC码的构造是基于组合理论构造的一类LDPC码，该码基于有限几何中的点、线、平面、超平面的相交或者平行等几何关系或者有限域中的本原元、加群、乘群等特性构造，结合掩蔽、行列分解、扩展等操作，得到了一类具有规则校验矩阵结构的LDPC码。这类LDPC码通常具有循环或者准循环等的结构特性。这使得此类LDPC码在硬件实现中具有较低的复杂度，循环或者准循环的结构使得编码器在硬件实现中通过循环移位寄存器即可实现，大大降低了编码复杂度；同时，准循环的LDPC码在译码实现中可以利用准并行的译码架构，这使得译码器在实现过程中在译码速度和复杂度之间有很大的选择空间，为LDPC码的译码实现在高性能高复杂度和译码器到低性能低复杂度之间提供了一系列的选择。在中长码长时，结构LDPC码往往略逊于随机LDPC码，但结构的LDPC码能够保证较大的最小码间距离，这使得该类码具有较低的误码平台。

发明内容

(一)要解决的技术问题

本发明要解决的技术问题是如何保证LDPC码具有优秀误码性能、低误码平台和快速收敛等的译码特性的同时在硬件实现中具有低复杂度。

(二)技术方案

为了解决上述技术问题，本发明提供了一种基于本原域循环群生成元集的LDPC码构造方法，所述方法包括以下步骤：

S1、确定码长L，并根据所述码长L确定本原域GF(p)，其中p表示本原域的大小，为质数；

S2、确定本原域GF(p)循环群的生成元集合；

对于所述本原域GF(p)的循环群的每一元素进行判断，如果其从0到p-2次幂构成所述本原域GF(p)的循环群的所有元素，则其为本原域GF(p)循环群的一个生成元；

S3、基于所述生成元集合构造基矩阵；

由所述步骤S2得到的生成元集合中元素个数为K，加入0作为所述生成元集合的第0个元素，形成新的生成元集合；

所述基矩阵的任一元素W_ij为所述新的生成元集合第i个元素和第j个元素的模p乘积；

S4、对所述基矩阵进行加性扩展操作，得到加性扩展的分块矩阵；

对所述基矩阵的每一元素扩展成为p×p的二元或广义循环置换矩阵；

S5、取所述分块矩阵的分块子矩阵构成校验矩阵；所述校验矩阵的零空间给出所要构造的LDPC码。

优选地，所述步骤S4具体为：

若构造二元LDPC码，对于所述基矩阵的一元素，设为l，，0≤l＜p，其二元域上的p维单位行向量为v₂(l)，所述v₂(l)的位置l处为1，剩余的p-1个位置为0，构成所述元素l的定位向量；将元素l，l+1，...，l+p-1的定位向量排成一列，得到所述元素l的二元循环置换矩阵；将所述基矩阵的每一个元素扩展成二元循环置换矩阵得到所述基矩阵的二元加性扩展矩阵；

若构造多元LDPC码，对于所述基矩阵的一元素，设为l，0≤l＜p，其多元域上的p维单位行向量为v_p(l)，若l≠0，在v_p(l)的位置l处为l，在剩余的p-1个位置为0；若l＝0，v_p(l)的位置0处为1，在剩余的p-1个位置为0，构成元素l定位向量；将元素l，l+1，...，l+p-1的定位向量排成一列，得到所述元素l的广义循环置换矩阵，将所述基矩阵的每一个元素扩展成广义循环置换矩阵，得到所述基矩阵的多元加性扩展矩阵。

优选地，所述步骤1中得到的本原域GF(p)，其构造的LDPC码的最大长度为(K+1)p，K表示本原域GF(p)循环群的生成元的个数，其通过欧拉函数计算得到。

优选地，所述本原域GF(p)的循环群为{1，2，...，p-1}。

优选地，所述步骤S5中校验矩阵的提取方法为：

取所述分块矩阵的γ行分块、ρ列分块的分块子矩阵作为校验矩阵，所述ρ列分块的参数ρ的选择标准是使得校验矩阵所给出码的码长ρp在所要构造的LDPC码长L的要求范围内；所述γ行分块的参数γ的选择标准是使得校验矩阵的秩接近(1-r)ρp的值，其中r表示所要构造的LDPC码的码率。

优选地，所述校验矩阵作为掩蔽操作的基矩阵进行掩蔽操作，进行掩蔽操作后的校验矩阵的零空间给出所要构造的LDPC码

优选地，所述基矩阵满足：

加性行约束1：所述基矩阵中的任意一行w_i，0≤i≤K，对于0≤e，f＜p，e≠f，满足向量(l_il₀+e，l_il₁+e，...，l_il_K+e)和向量(l_il₀+f，l_il₁+f，...，l_il_K+f)存在p处不同；

加性行约束2：对于基矩阵中的任意两行，w_i＝(r_ir₀，r_ir₁，...，r_ir_p-1)与w_j＝(r_jr₀，r_jr₁，...，r_jr_p-1)，0≤i，j≤K且i≠j，对于0≤e，f＜p，两向量(r_ir₀+e，r_ir₁+e，...，r_ir_p-1+e)和(r_jr₀+f，r_jr₁+f，...，r_jr_p-1+f)至多存在一处相同。

(三)有益效果

本发明提供了一种基于本原域循环群生成元集的LDPC码构造方法，本发明的方法利用基于本原域循环群的生成元集合构造的基矩阵，构造的校验矩阵，所述校验矩阵的零空间给出了一个准循环LDPC码，该类LDPC码具有优秀的误码性能，在硬件实现中的具有低复杂度、低误码平台、快速收敛的译码性能，同时构造的校验矩阵可以结合现有技术，如掩蔽等，构造成全新的一类LDPC码。

附图说明

为了更清楚地说明本发明实施例或现有技术中的技术方案，下面将对实施例或现有技术描述中所需要使用的附图作简单地介绍，显而易见地，下面描述中的附图仅仅是本发明的一些实施例，对于本领域普通技术人员来讲，在不付出创造性劳动的前提下，还可以根据这些附图获得其他的附图。

图1为传统的一种基于本原域循环群生成元集的LDPC码构造方法的流程图；

图2为本发明的一种基于本原域循环群生成元集的LDPC码构造方法的一个实施例所构造的(2656，1328)QC-LDPC码和(2407，2078)QC-LDPC码在AWGN信道条件下利用和积译码算法在50次最大迭代下所得到的误码性能示意图。

具体实施方式

下面结合附图和实施例对本发明作进一步详细描述。以下实施例用于说明本发明，但不能用来限制本发明的范围。

图1为传统的一种基于本原域循环群生成元集的LDPC码构造方法的流程图；所述方法包括以下步骤：

S1、根据通信需求确定码长L，并根据所述码长L确定本原域GF(p)，其中p表示本原域的大小，为质数；所述本原域GF(p)构造的LDPC码的最大长度为(K+1)p，要使基于所述本原域GF(p)构造的LDPC码的最大长度(K+1)p大于码长L，其中K表示本原域GF(p)循环群的生成元的个数，其通过欧拉函数计算得到：其中，P-1可以分解为质数幂次方的乘积，

S2、确定本原域GF(p)循环群的生成元集合；

所述本原域GF(p)的循环群为{1，2，...，p-1}；对于本原域GF(p)循环群中的任意元素a，如果a的i次幂aⁱ，0≤i＜p-1，给出了本原域GF(p)循环群中的所有元素，则该元素为本原域GF(p)循环群中的一个生成元；对本原域GF(p)循环群中的所有元素进行上述判断操作，形成所述循环群生成元的集合；

S3、基于所述生成元集合构造基矩阵；

(1)用1，2，...，K标记步骤S2中得到的生成元集合中的生成元，并加入第0个生成元记为0；

(2)构造一个(K+1)×(K+1)的基矩阵W，用i和j标记W的行和列，其中i和j取值为{0，1，...，K}；

(3)该基矩阵第i行第j列的元素为步骤(1)得到的更新后的生成元集合中的第i个元素和第j个元素的模p乘积，不难看出，基矩阵W中的元素属于GF(p)；

至此，我们构造了一个(K+1)×(K+1)的基矩阵W，如公式(1)所不，

基于的生成元的集合，可以构造一个能够唯一标识所构造LDPC码的(K+1)×(K+1)的基矩阵W。

从公式(1)中，我们得到W具有如下的性质：1)矩阵W的0行、0列中的所有元素都为0；2)W中除0行和0列外的任意行或列中的所有元素均不相同；3)W中的任意两行或两列在位置0处有相同元素0，在所有其他的K个位置的元素均不相同。

基于上述的性质，W满足如下约束：

加性行约束1：W中的任意一行w_i，0≤i≤K，对于0≤e，f＜p，e≠f，满足向量(l_il₀+e，l_il₁+e，...，l_il_K+e)和向量(l_il₀+f，l_il₁+f，...，l_il_K+f)存在p处不同；

加性行约束2：对于W中的任意两行，w_i＝(r_ir₀，r_ir₁，...，r_ir_p-1)与w_j＝(r_jr₀，r_jr₁，...，r_jr_p-1)，0≤i，j≤K且i≠j，对于0≤e，f＜p，两向量(r_ir₀+e，r_ir₁+e，...，r_ir_p-1+e)和(r_jr₀+f，r_jr₁+f，...，r_jr_p-1+f)至多存在一处相同；

S4、对所述基矩阵进行加性扩展操作，得到加性扩展的分块矩阵；

将W中的每个元素扩展成为p×p的循环置换矩阵或广义循环置换矩阵，得到一个(K+1)×(K+1)的分块矩阵H，如公式(2)所示，

其中，任意子矩阵P_i，j，0≤i，j≤K，为基矩阵元素l_il_j的p倍加性扩展矩阵，为p×p的循环置换矩阵，根据所构造的码为二元LDPC码或者多元LDPC码区分，我们分别进行如下的操作：

若构造二元LDPC码，

(1)对于基矩阵W中的任一元素l，0≤l＜p，有且仅有一个二元域上的p维单位行向量v₂(l)，在v₂(l)的位置l处为1，在剩余的p-1个位置为0，所述单位向量v₂(l)为元素l在GF(2)上的定位向量，本原域GF(p)中的任意两个不同元素的GF(2)上的定位向量不相同；

(2)从定位向量的定义可以看出元素l+1的定位向量是元素l的定位向量的循环右移，对基矩阵W中的任意元素l，将元素l，l+1，...，l+p-1的定位向量排成一列，我们得到一个p×p的循环置换矩阵，此矩阵为元素l的二元域上的p倍加性扩展矩阵；

(3)对基矩阵中的每个元素进行二元域上的加性扩展操作，得到一个(K+1)×(K+1)的分块矩阵，每个子矩阵为p×p的循环置换矩阵。

若构造多元LDPC码，

(1)对于基矩阵W中的任意元素l，0≤l＜p，有且仅有一个GF(p)上的p维单位行向量v_p(l)，若l≠0，在v_p(l)的位置l处为l，在剩余的p-1个位置为0；若l＝0，v_p(l)的位置0处为1，在剩余的p-1个位置为0，所述单位向量v_p(l)为元素l在GF(p)上的定位向量，基矩阵W中的任意两个不同元素的GF(p)上的定位向量不相同；

(2)对基矩阵W中的任意元素l，将元素l，l+1，...，l+p-1的定位向量排成一列，我们得到一个p×p的广义循环置换矩阵，我们称此矩阵为元素l的多元域上的p倍加性扩展矩阵；

(3)对基矩阵中的每个元素进行GF(p)上的加性扩展操作，得到一个(K+1)×(K+1)的分块矩阵，每个子矩阵为p×p的广义循环置换矩阵；

S5、取所述分块矩阵的分块子矩阵构成校验矩阵，取所述分块矩阵H的γ行分块、ρ列分块的分块子矩阵作为校验矩阵H(γ，ρ)，所述ρ列分块的参数ρ的选择标准是使得校验矩阵H(γ，ρ)所给出码的码长ρp在所要构造的LDPC码长L的要求范围内，即ρp的值等于或略大于所要构造的LDPC码长L；所述γ行分块的参数γ的选择标准是使得校验矩阵H(γ，ρ)的秩R接近(1-r)ρp的值，其中r表示所要构造的LDPC码的码率；

通过上述步骤，我们得到一个列重为γ、行重为ρ的校验矩阵，该矩阵零空间给出一个码长为ρp，码率为1-R/ρp的LDPC码，当γ为奇数时，该码的最小码间距离为γ+1；当γ为偶数时，该码的最小码间距离为γ+2。

步骤S5得到的校验矩阵还可以作为掩蔽操作的基矩阵进行掩蔽操作，进行掩蔽操作后的校验矩阵的零空间给出新的一类具有准循环结构的规则LDPC码。

实施例：

GF(p)上的二元LDPC码的构造：

(1)确定码参数与码构造的本原域

在此，选取本原域GF(83)作为码构造域。

(2)根据上述本发明的方法中步骤S2，确定本原域循环群的生成元，得到GF(83)的循环群中包含40个生成元，其中生成元集合为

{2，5，6，8，13，14，15，18，19，20，22，24，32，34，35，39，42，43，45，46，47，50，52，53，54，55，56，57，58，60，62，66，67，71，72，73，74，76，79，80}

(3)基于生成元集合构造基矩阵

基于上述本发明的方法中步骤S3的基矩阵的构造方法，我们构造了一个41×41的基矩阵W，W中的元素属于本原域GF(83)。

(4)加性扩展基矩阵

通过基于上述本发明的方法中步骤S4的二元域上加性扩展操作，我们得到一个41×41的满足行列约束的分块矩阵H，其子矩阵为83×83的循环置换矩阵。

(5)提取分块子矩阵作为校验矩阵，给出LDPC码

1)在此，我们取γ＝4、ρ＝29，从分块矩阵H中取出一个4×29的分块子矩阵H(4，29)作为奇偶校验矩阵，该校验矩阵具有恒定的列重4、行重29，其零空间给出(2407，2078)准循环LDPC码，该码为规则码，具有码长2407和码率0.8633，其误码性能如图2所示；该校验矩阵所对应的基矩阵的4×29子矩阵如下：

0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，0，

48，64，68，70，78，1，3，7，9，11，17，21，23，25，27，29，31，33，37，41，

37，77，4，9，29，44，49，59，64，69，1，11，16，21，26，31，36，41，51，61，

61，26，38，44，68，3，9，21，27，33，51，63，69，75，81，4，10，16，28，40，

0，0，0，0，0，0，0，0，0，

49，51，59，61，63，65，69，75，77，

81，3，23，28，33，38，48，63，68，

64，70，11，17，23，29，41，59，65

2)我们取γ＝16、ρ＝32，从分块矩阵H中取出一个16×32的分块子矩阵H(16，32)作为掩蔽操作的基矩阵，其子矩阵为83×83的循环置换矩阵，设掩蔽矩阵Z(16，32)由两个本原向量生成的循环置换矩阵排成一行分块矩阵得到，两本原向量分别为g₀＝[1010010000000000]、g₁＝[1000100000100000]，掩蔽后的校验矩阵可以表示为所述掩蔽后校验矩阵具有恒定的列重3、行重6，其零空间给出一个(2656，1328)准循环LDPC码，该码为规则码，具有码长2656和码率0.5，其误码性能如图2所示。该校验矩阵所对应的基矩阵的16×32子矩阵如下，其中，-1的扩展矩阵为83×83的零矩阵：

38，-1，44，-1，-1，68，-1，-1，-1，-1，-1，-1，-1，-1，-1，-1，25，-1，-1，-1，

-1，17，-1，37，-1，-1，9，-1，-1，-1，-1，-1，-1，-1，-1，-1，-1，26，-1，-1，

-1，-1，49，-1，26，-1，-1，68，-1，-1，-1，-1，-1，-1，-1，-1，-1，-1，4，-1，

-1，-1，-1，26，-1，23，-1，-1，4，-1，-1，-1，-1，-1，-1，-1，-1，-1，-1，41，

-1，-1，-1，-1，1，-1，40，-1，-1，61，-1，-1，-1，-1，-1，-1，-1，-1，-1，-1，

-1，-1，-1，-1，-1，61，-1，48，-1，-1，49，-1，-1，-1，-1，-1，-1，-1，-1，-1，

-1，-1，-1，-1，-1，-1，27，-1，49，-1，-1，26，-1，-1，-1，-1，63，-1，-1，-1，

-1，-1，-1，-1，-1，-1，-1，38，-1，27，-1，-1，16，-1，-1，-1，-1，77，-1，-1，

-1，-1，-1，-1，-1，-1，-1，-1，51，-1，25，-1，-1，37，-1，-1，-1，-1，68，-1，

-1，-1，-1，-1，-1，-1，-1，-1，-1，30，-1，7，-1，-1，44，-1，-1，-1，-1，61，

-1，-1，-1，-1，-1，-1，-1，-1，-1，-1，77，-1，38，-1，-1，4，-1，-1，-1，-1，

41，-1，-1，-1，-1，-1，-1，-1，-1，-1，-1，25，-1，38，-1，-1，-1，-1，-1，-1，

-1，59，-1，-1，-1，-1，-1，-1，-1，-1，-1，-1，10，-1，4，-1，68，-1，-1，-1，

-1，-1，1，-1，-1，-1，-1，-1，-1，-1，-1，-1，-1，40，-1，59，-1，44，-1，-1，

1，-1，-1，10，-1，-1，-1，-1，-1，-1，-1，-1，-1，-1，77，-1，-1，-1，51，-1，

-1，33，-1，-1，3，-1，-1，-1，-1，-1，-1，-1，-1，-1，-1，75，-1，-1，-1，65，

33，-1，-1，-1，-1，-1，61，-1，-1，-1，-1，-1

-1，51，-1，-1，-1，-1，-1，33，-1，-1，-1，-1

-1，-1，40，-1，-1，-1，-1，-1，29，-1，-1，-1

-1，-1，-1，30，-1，-1，-1，-1，-1，27，-1，-1

7，-1，-1，-1，41，-1，-1，-1，-1，-1，31，-1

-1，10，-1，-1，-1，81，-1，-1，-1，-1，-1，41

-1，-1，17，-1，-1，-1，1，-1，-1，-1，-1，-1

-1，-1，-1，26，-1，-1，-1，69，-1，-1，-1，-1

-1，-1，-1，-1，28，-1，-1，-1，78，-1，-1，-1

-1，-1，-1，-1，-1，9，-1，-1，-1，26，-1，-1

31，-1，-1，-1，-1，-1，7，-1，-1，-1，78，-1

-1，29，-1，-1，-1，-1，-1，9，-1，-1，-1，11

-1，-1，75，-1，-1，-1，-1，-1，44，-1，-1，-1

-1，-1，-1，3，-1，-1，-1，-1，-1，11，-1，-1

-1，-1，-1，-1，21，-1，-1，-1，-1，-1，26，-1

-1，-1，-1，-1，-1，30，-1，-1，-1，-1，-1，49

本发明的方法利用基于本原域循环群的生成元集合构造的基矩阵，构造的校验矩阵，所述校验矩阵的零空间给出了一个具有准循环结构的LDPC码，该类LDPC码具有优秀的误码性能，在硬件实现中的具有低复杂度、低误码平台、快速收敛的译码性能，同时构造的校验矩阵可以结合现有技术，如掩蔽等，构造成全新的一类LDPC码。

以上实施方式仅用于说明本发明，而非对本发明的限制。尽管参照实施例对本发明进行了详细说明，本领域的普通技术人员应当理解，对本发明的技术方案进行各种组合、修改或者等同替换，都不脱离本发明技术方案的精神和范围，均应涵盖在本发明的权利要求范围当中。