一种基于有限域本原元的准循环LDPC码的构造方法

摘要

本发明涉及通信技术中的信道编码技术领域，具体为一种基于有限域本原元的准循环LDPC码的构造方法。所述方法可大体分为以下五步：确定码的参数，选择有限域中的两个本原元、基于本原元的基矩阵的构造、基矩阵的扩展和选择分块矩阵的子矩阵作为校验矩阵。其中，对二元域和多元的构造，共享第三步产生的基矩阵。区别体现在第四步扩展操作后的矩阵元素属于二元域或是多元域。由于构造的码为准循环码，故其生成矩阵具有系统循环的形式，能够实现线性的编码。

说明书

技术领域

本发明涉及通信技术中的信道编码技术领域，具体为一种基于有 限域本原元的准循环LDPC码的构造方法。

背景技术

LDPC码是一种接近香农限的好码，1962年由Gallager发现，在1995 重新被发现而回到人们的视线。随后，关于这种码的设计、构造、译 码、高效编码、性能分析和其在数字通信与存储系统中的应用成为了 研究的热点。根据构造方式的不同，可将LDPC码分成两类，随机或伪 随机的LDPC码与结构的LDPC码。其中，随机或伪随机的LDPC码利用 计算机寻找得到，搜索算法要参照特定的设计准则和一些Tanner图结构 特性，包括围长、度分布和停止集等。设计良好的随机构造的LDPC码 能够实现优秀的误比特性能，有研究表明，在高斯信道下，设计良好 的码长10⁷的随机LDPC码，距香农限仅0.0045dB。虽然这个码的码长由 于太长而不会应用于显示系统中，但是，这足以证明随机LDPC优秀的 误码性能。与此同时，由于随机或伪随机LDPC码构造的随机性，使得 其校验矩阵不具有结构上的规律而在编码和译码的实现中具有较高的 复杂度，且随机构造的LDPC码由于不能够保证所构造码字的最小距离， 而容易有不理想的差错平底。

与之相比，基于组合理论构造了一类结构的LDPC码，该构造利用 有限几何中超平面的相交、平行等几何特点或者利用有限域中的加群 或乘群的特点，结合行列分解、掩蔽等操作，产生了一类具有较为规 则结构特性的LDPC码。结构LDPC码的校验矩阵往往具有循环或准循 环的结构特点，这些结构特点使得其可以通过简单的循环移位寄存器 就可以实现线性复杂度的编码，这在硬件的实现中与随机LDPC码编码 相比具有很大的优势，且准循环的结构使其硬件译码实现可以采用准 循环的译码架构，这为译码器的速度和译码复杂度间提供了很大的折 中。与长的随机码相比，结构LDPC码在误比特性能方面往往略逊与经 良好设计的随机LDPC码，但结构LDPC码可以通过约束条件保证较大 的最小距离，而使其具有良好的收敛特性和极低的差错平底。

发明内容

(一)要解决的技术问题

本发明的目的旨在利用有限域中两个本原元构造一系列的结构 LDPC码，该码兼具随机和传统结构LDPC码的优点，既保证了该码的 误比特性能与设计良好的随机LDPC码相当，同时该码的准循环结构 也保证了该码在硬件实现中的低复杂度优势，同时具有低差错平底和 快速收敛的特性。

(二)技术方案

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

确定所要构造的码字的码长和码率的参数；

根据所要构造的码字的码长和码率的参数确定要进行码构造的有 限域GF(q)，基于GF(q)所能构造的码字最大长度(q—1)²大于将要构 造的码字长度L，构造列重M_C和行重N_C的M_C×N_C校验矩阵时，要 满足M_C+N_C<<(q—1)；

确定有限域GF(q)中的本原元，并随机选择任意两个本原元进行后 续的码构造；

将随机选择到的两个本原元，构造一个能唯一的标识一类LDPC 码的(q—1)×(q—1)的基矩阵W，所述基矩阵W的元素属于有 限域GF(q)；

对所述基矩阵W进行扩展操作：

当需要得到二元准循环LDPC码时，将基矩阵W中的每个非零元 素扩展为(q—1)×(q—1)的具有循环置换形式的二元矩阵，每个 零元素扩展成为(q—1)×(q—1)的零矩阵，形成具有分块形式的 校验矩阵H；根据所要构造的码字的码长和码率确定分块的行数γ与 列数ρ；取任意γ行ρ列的分块子矩阵形成所要构造码字的校验矩阵 H(γ，ρ)；所述要构造码字的校验矩阵H(γ，ρ)为γ(q—1)×ρ(q —1)的二元矩阵，所述γ(q—1)×ρ(q—1)的二元矩阵的零空间形 成所要构造的LDPC码；

当需要得到二元以上的多元准循环LDPC码时，将基矩阵W中的 每个非零元素扩展为(q—1)×(q—1)的具有广义循环置换形式的 二元以上的多元矩阵，每个零元素扩展成为(q—1)×(q—1)的零 矩阵，形成具有分块形式的校验矩阵H；根据所要构造的码字的码长 和码率确定分块的行数γ与列数ρ；取任意γ行ρ列的分块子矩阵形成 所要构造码字的校验矩阵H(γ，ρ)；所述要构造码字的校验矩阵H(γ， ρ)为γ(q—1)×ρ(q—1)的二元以上的多元矩阵，所述γ(q—1) ×ρ(q—1)的二元以上的多元矩阵的零空间形成所要构造的LDPC码。

优选地，构造一个能唯一的标识一类LDPC码的(q—1)×(q— 1)的基矩阵W的方法分为如下步骤：

用i和j分别标记基矩阵W中的元素的行和列的位置，位置取值 0到(q—1)间的整数；

将所述被随机选择任意两个本原元标记为本原元1和本原元2；

对所述本原元1和本原元2进行基矩阵构造；

所述本原元1的i次幂与所述本原元2的j次幂相乘并减1，将获 得的结果表示成特定的本原元幂的形式；

将所述被表示成特定的本原元幂的形式的结果作为基矩阵的第i 行第j列的元素。

优选地，若待处理的校验矩阵被要求具有列重γ和行重ρ，在分块 子矩阵的选取中需要避开零子矩阵。

(三)有益效果

本发明的有益效果是：本发明所述方法给出的具有分块形式的校 验矩阵H(γ,ρ)的零空间给出了一个码长为γ(q-1)，码率至少为(ρ- γ)/ρ的码，该码兼具随机和传统结构LDPC码的优点，既保证了该码 的误比特性能与随机LDPC码相当，而且该码校验矩阵的分块循环置换 子矩阵形式，保证了该码能够实现线性的编码和准并行架构译码，从 而降低了该码硬件实现复杂度,同时该码具有最小码间距离γ，只要保 证码间距离充分大，则所构造的码字具有快速收敛、低误码平台等优 点。

附图说明

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

图1是本发明一种基于有限域本原元的准循环LDPC码的构造方 法的操作流程图；

图2是基于本发明一种基于有限域本原元的准循环LDPC码的构 造方法的一个实施例所构造的两个QC-LDPC码(4080,2040)(8160,7159) 在AWGN信道条件下利用迭代译码所得到的误码性能示意图。

具体实施方式

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

本发明提供了一种基于有限域本原元的准循环LDPC码的构造方 法，所述方法包括如下步骤：

确定所要构造的码字的码长和码率的参数；

根据所要构造的码字的码长和码率的参数确定要进行码构造的有 限域GF(q)，基于GF(q)所能构造的码字最大长度(q—1)²大于将要构 造的码字长度L，构造列重M_C和行重N_C的M_C×N_C校验矩阵时，要 满足M_C+N_C<<(q—1)；

确定有限域GF(q)中的本原元，并随机选择任意两个本原元进行后 续的码构造；

将随机选择到的两个本原元，构造一个能唯一的标识一类LDPC 码的(q—1)×(q—1)的基矩阵W，所述基矩阵W的元素属于有 限域GF(q)；

对所述基矩阵W进行扩展操作：

当需要得到二元准循环LDPC码时，将基矩阵W中的每个非零元 素扩展为(q—1)×(q—1)的具有循环置换形式的二元矩阵，每个 零元素扩展成为(q—1)×(q—1)的零矩阵，形成具有分块形式的 校验矩阵H；根据所要构造的码字的码长和码率确定分块的行数γ与 列数ρ；取任意γ行ρ列的分块子矩阵形成所要构造码字的校验矩阵 H(γ，ρ)；所述要构造码字的校验矩阵H(γ，ρ)为γ(q—1)×ρ(q —1)的二元矩阵，所述γ(q—1)×ρ(q—1)的二元矩阵的零空间形 成所要构造的LDPC码；

当需要得到二元以上的多元准循环LDPC码时，将基矩阵W中的 每个非零元素扩展为(q—1)×(q—1)的具有广义循环置换形式的 二元以上的多元矩阵，每个零元素扩展成为(q—1)×(q—1)的零 矩阵，形成具有分块形式的校验矩阵H；根据所要构造的码字的码长 和码率确定分块的行数γ与列数ρ；取任意γ行ρ列的分块子矩阵形成 所要构造码字的校验矩阵H(γ，ρ)；所述要构造码字的校验矩阵H(γ， ρ)为γ(q—1)×ρ(q—1)的二元以上的多元矩阵，所述γ(q—1) ×ρ(q—1)的二元以上的多元矩阵的零空间形成所要构造的LDPC码。

若待处理的校验矩阵被要求具有列重γ和行重ρ，在分块子矩阵的 选取中需要避开零子矩阵。

构造一个能唯一的标识一类LDPC码的(q—1)×(q—1)的基 矩阵W的方法分为如下步骤：

用i和j分别标记基矩阵W中的元素的行和列的位置，位置取值 0到(q—1)间的整数；

将所述被随机选择任意两个本原元标记为本原元1和本原元2；

对所述本原元1和本原元2进行基矩阵构造；

所述本原元1的i次幂与所述本原元2的j次幂相乘并减1，将获 得的结果表示成特定的本原元幂的形式；

将所述被表示成特定的本原元幂的形式的结果作为基矩阵的第i 行第j列的元素。

确定有限域GF(q)中的本原元的方法分为如下步骤：

从被任意确定的有限域GF(q)中得到位于其中的所有非零元；

将被任意确定的有限域GF(q)中所有非零和非1的元素表示为所述 特定本原元幂次方的形式，幂值的大小为1到(q—2)间所有的整数；

找寻所有幂值中与(q—1)互质的幂值构成集合；

所述集合中的元素所对应的GF(q)中的元素即为有限域GF(q)中的 本原元。

将基矩阵W中的每个非零元素扩展为(q—1)×(q—1)的具有 循环置换形式的二元矩阵的方法分为如下步骤：

生成(q—1)维的行向量，所述(q—1)维的行向量的(q—1) 个元素分别用0到(q—2)间的整数进行位置标记；

记基矩阵中的第i行与第j列交叉的元素为特定本原元的幂次方形 式，幂值为k，所述k为0到(q—2)间的整数；

将所述(q—1)维的行向量的位置标记k处取值为1，将所述(q —1)维的行向量的其余的(q—2)个位置取值为0，得到(q—1)维 向量；

对得到的(q—1)维向量进行(q—2)次循环移位操作；

将循环移位操作前的所述(q—1)维向量与循环移位操作得到的 (q—2)个循环移位向量排成一列，形成(q—1)×(q—1)的扩展 矩阵；

用所述(q—1)×(q—1)的扩展矩阵替换基矩阵中第i行与第j 列交叉的元素。

将基矩阵W中的每个非零元素扩展为(q—1)×(q—1)的具有 广义循环置换形式的二元以上的多元矩阵的方法分为如下步骤：

生成(q—1)维的行向量，所述(q—1)维的行向量的(q—1) 个元素分别用0到(q—2)间的整数进行位置标记；

记基矩阵中的第i行与第j列交叉的元素为特定本原元的幂次方形 式，幂值为k，所述k为0到(q—2)间的整数；

将所述(q—1)维的行向量的位置标记k处取值为特定本原元的k 次方，将所述(q—1)维的行向量的其余的(q—2)个位置取值为0；

对在基矩阵中的第i行与第j列交叉的元素进行乘以本原元幂次方 的操作，本原元的幂依次取{1，2，…，q—2}；

将基矩阵中的第i行与第j列交叉的元素与其(q—2)次的乘积所 对应的(q—1)个(q—1)维向量依次排成一列，得到(q—1)×(q —1)的扩展矩阵；

用所述(q—1)×(q—1)的扩展矩阵替换基矩阵中第i行与第j 列交叉的元素。

具体实施例如下：

图1所示，采用本发明一种基于有限域本原元的准循环LDPC码 的构造方法构造基于有限域本原元的准循环LDPC码的校验矩阵按如 下步骤进行：

步骤1：确定码参数，主要是指码长与码率，并根据码参数确定 GF(q)域的大小q和分块校验矩阵的行分块和列分块等参数。

步骤2：确定有限域中的两个本原元，GF(q)为步骤1中确定的有 限域，q值为质数或者它的幂次方，设α为GF(q)的本原元，则GF(q) 中的元素均可表示成α的幂的形式，集合{α^∞＝0，α⁰＝1，α，…，α^q-2} 构成GF(q)的q个元素。如果αⁱ中的指数i与(q—1)互质，则αⁱ也是 GF(q)的本原元，根据欧拉公式可以计算GF(q)中本原元的个数。从这 写本原元中任意选取两个，标记为α^ul与α^uk。

步骤3：基矩阵的构造，利用步骤2中得到的α^ul与α^uk，对基矩阵 的元素做如下操作：

其中，α的指数取模q-1操作。我们可以发现或证明W具有如下 性质：

1)每一行(列)只有一个0元素；

2)每一行(列)中的元素都不相同；

3)任意两行的所有(q-1)个位置都不相同。我们可以证明W满足α 幂次乘积的行距约束：对任意0≤i，j＜(q-1)，i≠ji≠j和0≤e，f＜(q-1)‐1)， 两个行向量α^ew_i和α^fw_j至少存在q—2个不同。

步骤4：基矩阵的扩展，利用步骤3中得到的基矩阵，将其中的每 个元素扩展成为(q—1)×(q—1)的循环置换矩阵，

我们得到如下的(q—1)×(q—1)的分块矩阵：

具体的扩展过程按如下操作进行：

基矩阵中的任意元素可以表示为本原元α幂的形式，比如αⁱ，如 果对非零元素αⁱ进行二元域上的扩展操作，则设一个二元q-1维行向 量(v₀，v₁，…，v_q-2)，将第i位标记为1，其余q—2位标记为0，则称 此向量为非零元αⁱ的定位向量，记做v(αⁱ)。将如下的q-1个定位向量， v(αⁱ)，v(αⁱ⁺¹)，v(αⁱ⁺²)，…，v(α^i+q-2)，按列排列，得到一个(q—1)× (q—1)循环置换矩阵，我们称其为αⁱ的扩展矩阵。如果对零元素进 行二元域上的扩展，则其扩展矩阵为一个(q—1)×(q—1)的零矩 阵。

如果对非零元素αⁱ进行多元域上的扩展操作，则设一个多元q-1 维行向量(v₀，v₁，…，v_q-2)，将第i位标记为αⁱ，其余q—2位标记为0， 则称此向量为非零元αⁱ的q元定位向量，记做q(αⁱ)。将如下的q-1个q 元定位向量，q(αⁱ)，q(αⁱ⁺¹)，q(αⁱ⁺²)，…，q(α^i+q-2)，按列排列，得到一 个(q—1)×(q—1)类广义循环置换矩阵，我们称其为αⁱ的q元扩 展矩阵。如果对零元素进行二元域上的扩展，则其扩展矩阵为一个(q —1)×(q—1)的零矩阵。

经过以上的操作，我们得到了一个(q—1)×(q—1)分块校验 矩阵H，分块为(q—1)×(q—1)的循环置换矩阵(或广义循环置 换矩阵)和零矩阵。

步骤5：选择分块矩阵H的子矩阵，根据码长与码率确定分块矩 阵H分块的维度γ和ρ，使得ρ(q—1)接近所要构造的码字长度L， 而(ρ-γ)/ρ要小于码字的码率R，并使得所构造校验矩阵的秩K接近 (1-R)ρ(q—1)。取分块矩阵H中行分块列分块分别为γ和ρ的分块子 矩阵作为校验矩阵，由此生成所要求构造码的校验矩阵H(γ，ρ)。

我们由校验矩阵H(γ，ρ)得到码长为ρ(q—1)，码率为1-K/ρ (q—1)，最小码间距离至少为γ的QC-LDPC码，若H(γ，ρ)中不 包含零子矩阵，则其有恒定的列重γ和行重ρ，得到的码也为规则LDPC 码。

应用举例:

GF(q)上的二元LDPC码的构造

1、确定码参数：

将GF(2⁸)作为码构造域，设定α为GF(2⁸)的本原元。

2、有限域中2个本原元的确定：

在所有的[1,254]满足与2⁸-1＝255互质的整数集合中，取13与71， 即选α¹³、α⁷¹作为GF(2⁸)的本原元。

3、基于两个本原元的基矩阵的设计：

基于上述的构造基矩阵的方法，确定了255×255的基矩阵，基矩 阵的元素属于GF(2⁸)。

4、基矩阵的扩展：

针对所取得的基矩阵进行二元域上的扩展，得到一255×255的分 块矩阵H，其子矩阵为255×255的循环置换矩阵和零矩阵。

5、取扩展矩阵中的分块子矩阵作为校验矩阵：

(1)此处取γ＝8，ρ＝16，避开分块矩阵中的零子矩阵，得到一8 ×16的分块子矩阵H(8,16)，子矩阵为255×255的循环置换矩阵，设 定掩蔽矩阵Z(8,16)，此矩阵由两个8×8的循环矩阵G₀、G₁排成一行 得到，两循环矩阵的生成向量分别为g₀＝(00010101)、g₁＝(00100011)， 掩蔽后的矩阵表示为用掩蔽后的矩 阵作为校验矩阵。此矩阵给出一(4080,2040) 的准循环LDPC码，码率为0.5，其误比特性能曲线和对应的香农限如 图2所示。

该码对应的基矩阵元素本原元的指数如下：

-1-1-148-1128-1104-1-118-1-1-1224170

147-1-1-159-114-1246-1-1130-1-1-1139

-146-1-1-1114-114718072-1-1119-1-1-1

174-1102-1-1-1133-1-154254-1-1222-1-1

-1182-12-1-1-1174-1-1179161-1-130-1

248-1192-1177-1-1-1-1-1-143247-1-1143

-1219-1113-1142-1-195-1-1-120710-1-1

-1-1240-181-1101-1-1138-1-1-1136248-1

其中，α^-1＝0。

(2)此处取γ＝4，ρ＝32，避开分块矩阵中的零子矩阵，得到一4 ×32的分块子矩阵H(4,32)，子矩阵为255×255的循环置换矩阵，用 H(4,32)作为校验矩阵。此矩阵的零空间给出一(8160,7159)的准循环 LDPC码，码率为0.877，其误比特性能曲线和对应的香农限如图2所 示。

该码对应的基矩阵本原元的指数如下：

3713330465425417611422214718072245591191484246163

2472001741431021791613713330465425417611422214718072

207101918224424324720017414310217916137133304654

14213624895192551772071019182244243247200174143102

48130128171104139156181311226224170

24559119148424616348130128171104139

25417611422214718072245591191484246

17916137133304654254176114222147180

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