太原理工大学数学学院，山西 晋中

收稿日期：2021年1月23日；录用日期：2021年2月17日；发布日期：2021年2月26日

摘要

空间耦合LDPC (Spatially-Coupled LDPC, SC-LDPC)码由于阈值饱和特性，被证明是未来无线通信系统的有力候选码型。SC-LDPC码是一种卷积LDPC码，在二元无记忆对称信道下采用置信传播算法时具有逼近香农限的性能。本文提出了一种构造二进制和多进制空间耦合LDPC码的统一方法。基于有限域GF(q)上的本原元、加法子群、乘法子群，构造了6类二进制和多进制空间耦合准循环LDPC码(Spatially-Coupled Quasi­Cyclic LDPC, SC-QC-LDPC)，用此构造的LDPC码的围长至少为6。

关键词

空间耦合LDPC码，准循环LDPC码，有限域，围长

An Approach for Constructing Binary and Nonbinary Spatially-Coupled LDPC Codes Based on Finite Fields

Yu Liang, Weihua Yang^*, Yuying Li

School of Mathematics, Taiyuan University of Technology, Jinzhong Shanxi

Received: Jan. 23^rd, 2021; accepted: Feb. 17^th, 2021; published: Feb. 26^th, 2021

ABSTRACT

Spatially-coupled LDPC codes are demonstrated to strong candidates for future optical communications systems due to the threshold saturating property. Spatially-coupled LDPC code is a kind of convolutional LDPC code. It has the performance of approaching Shannon limit when using belief propagation decoding algorithm in binary memoryless symmetric channel. A unified approach for constructing binary and nonbinary spatially-coupled LDPC codes is presented in this paper. Six classes of binary and nonbinary spatially-coupled Quasi-Cyclic LDPC codes are constructed based on primitive elements, additive subgroups, multiplicative subgroups of finite fields. Moreover, the girth of these codes is greater than or equal to 6.

Keywords:Spatially-Coupled LDPC Codes, Quasi-Cyclic LDPC Codes, Finite Field, Girth

Copyright © 2021 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

空间耦合LDPC码源自于LDPC卷积码 [1]，由于其优良的阈值而受到人们的广泛关注。对于二元无记忆对称(Binary memoryless symmetric, BMS)信道，已经证明了规则LDPC码集 [2] 的最大后验概率(Maximum aposteriori probability, MAP)阈值可以通过空间耦合原始LDPC码集的生成码集的置信传播(Belief propagation, BP)阈值来逼近 [3] [4] [5] [6]，这就是所谓的阈值饱和现象。除了渐近性能分析外，SC­LDPC码的有限长性能特别是利用窗口译码方法进行译码，也成为研究的重点 [7] [8]。最近，多进制SC­LDPC码也开始受到研究人员的关注。多进制SC­LDPC码的阈值饱和现象在二元删除信道(Binary erasure channel, BEC)被研究 [9]。经典的SC­LDPC码构造，被分类为图覆盖结构，是基于展开LDPC码的校验矩阵来形成SC­LDPC码的校验矩阵 [1] [10]。

准循环LDPC码 [11] 由于其低复杂度和高度并行的编码 [12] 和译码 [13]，已被各种通信系统标准化，最近又应用于数据存储产品中。QC­LDPC码通常是由在有限域上相同大小的稀疏循环矩阵的阵列的零空间给出的 [15]。QC­LDPC码具有优良有限长性能和高效硬件实现的优点 [12] [13] [14]。广泛的仿真结果 [15] [16] [17] 已经表明设计良好的QC­LDPC码优于非结构化随机LDPC码。仿真结果还表明，非二进制原模图LDPC码的性能优于与其对应的二进制码 [18]。

由于QC­LDPC码和SC­LDPC码的优点，本文从理论上研究了在任意有限域上具有准循环结构的SC­LDPC码的构造，此类码称之为SC­QC­LDPC码。最近，二进制SC­QC­LDPC码的构造 [19] 使用了一种改进的渐进边缘增长(Progressive edge growth, PEG)算法 [20]。相反，本文构造SC­QC­LDPC码是基于有限域的确定性构造。这避免了耗时的计算机搜索，同时确保了校验矩阵的Tanner图的围长至少为6，这也通常保证了码的优良性能。

2. 预备知识

2.1. 有限域中元素的位置向量

考虑有限域 $GF\left(q\right)$，q为一个素数的幂。令 $\alpha$ 为 $GF\left(q\right)$ 的本原元，则 $\alpha$ 的q个幂次 ${\alpha }^{-\infty }=0$，${\alpha }^0=1$，$\alpha ,\cdots ,{\alpha }^{q-2}$ 表示出了 $GF\left(q\right)$ 的所有元素，且 ${\alpha }^{q-1}=1$。 $GF\left(q\right)$ 包含两个群：加法群和乘法群。 $GF\left(q\right)$ 的q个元素在加法运算下构成加法群， $GF\left(q\right)$ 的 $q-1$ 个非零元素在乘法运算下构成乘法群。

对于任意一个非零元素 ${\alpha }^i$，$0\le i<q-1$，我们定义一个 $GF\left(2\right)$ 上的 $q-1$ 维向量： $z_b\left({\alpha }^i\right)=\left(z_0,z_1,\cdots ,z_{q-2}\right)$，其中第i个分量 $z_i=1$，而其他 $q-2$ 个分量等于零。将这样只有一个1分量的 $GF\left(2\right)$ 上的 $q-1$ 维向量称为元素 ${\alpha }^i$ 的二进制位置向量(binary location­vector)。显然，域 $GF\left(q\right)$ 中两个不同非零元素的二进制位置向量的1分量在不同位置上。元素0的二进制位置向量定义为 $q-1$ 维全零向量 $z_b\left(0\right)=\left(0,0,\cdots ,0\right)$。类似地，对于任意一个非零元素 ${\alpha }^i$，$0\le i<q-1$，我们定义一个 $GF\left(q\right)$ 上的 $q-1$ 维向量 $z_q\left({\alpha }^i\right)=\left(z_0,z_1,\cdots ,z_{q-2}\right)$，其中第i个分量 $z_i={\alpha }^i$，而其他 $q-2$ 个分量等于零。将这样只有一个 ${\alpha }^i$ 分量的 $GF\left(q\right)$ 上的 $q-1$ 维向量称为元素 ${\alpha }^i$ 的q进制位置向量(q­ary location­vector)。元素0的q进制位置向量定义为 $q-1$ 维全零向量 $z_q\left(0\right)=\left(0,0,\cdots ,0\right)$。

2.2. 有限域中元素的矩阵散列

令 $\delta$ 为 $GF\left(q\right)$ 的一个非零元素。当 $0\le i<q-1$ 时， ${\alpha }^i\delta$ 的二进制位置向量 $z_b\left({\alpha }^i\delta \right)$ 是 ${\alpha }^{i-1}\delta$ 的二进制位置向量 $z_b\left({\alpha }^{i-1}\delta \right)$ 的循环移位(右移一位)。因为 ${\alpha }^{q-1}=1$，则 $z_b\left({\alpha }^{q-1}\delta \right)=z_b\left(\delta \right)$。因而， $z_b\left(\delta \right)$ 就是 $z_b\left({\alpha }^{q-2}\delta \right)$ 的循环移位。以元素 $\delta ,\alpha \delta ,\cdots ,{\alpha }^{q-2}\delta$ 的二进制位置向量作为行，可以得到一个 $GF\left(2\right)$ 上的 $\left(q-1\right)\times \left(q-1\right)$ 矩阵 $A_b\left(\delta \right)$。该矩阵是一个循环置换矩阵(Circulant permutation matrix, CPM)，其每一行都是上一行的循环移位，而第一行是最后一行的循环移位。将矩阵 $A_b\left(\delta \right)$ 称为元素 $\delta$ 在 $GF\left(2\right)$ 上的 $\left(q-1\right)$ 重二进制矩阵散列((q-1)­fold binary matrix dispersion)。类似地，我们以元素 $\delta ,\alpha \delta ,\cdots ,{\alpha }^{q-2}\delta$ 的q进制位置向量作为行，可以得到一个 $GF\left(q\right)$ 上的 $\left(q-1\right)\times \left(q-1\right)$ 矩阵 $A_q\left(\delta \right)$。该矩阵是一个q进制 $\alpha$ 倍循环置换矩阵(q­ary α­multiplied circulant permutation matrix)，其每一行都是上一行乘以 $\alpha$ 的循环移位，而第一行是最后一行乘以 $\alpha$ 的循环移位。将矩阵 $A_q\left(\delta \right)$ 称为元素 $\delta$ 在 $GF\left(q\right)$ 上的 $\left(q-1\right)$ 重q进制矩阵散列((q-1)­fold q­ary matrix dispersion)。

3. 基于有限域构造QC­LDPC码的一般方法

令 $\alpha$ 为 $GF\left(q\right)$ 的本原元。构造过程始于一个 $GF\left(q\right)$ 上的 $m\times n$ 矩阵

$B=\left[\begin{array}{c}{b}_0\\ b_1\\ ⋮\\ b_{m-1}\end{array}\right]=\left[\begin{array}{cccc}{b}_{0,0}& b_{0,1}& \cdots & b_{0,n-1}\\ b_{1,0}& b_{1,1}& \cdots & b_{1,n-1}\\ ⋮& ⋮& \ddots & ⋮\\ b_{m-1,0}& b_{m-1,1}& \cdots & b_{m-1,n-1}\end{array}\right]$

其行满足如下两个约束条件：1) 若 $0\le i<m$，$0\le k,l<q-1$，且 $k\ne l$，则 ${\alpha }^k{b}_i$ 与 ${\alpha }^l{b}_i$ 至多有一个对应位置上的值相同(即它们至少有 $n-1$ 个对应位置上的值不同)；2) 若 $0\le i,j<m$，$i\ne j$，且 $0\le k,l<q-1$，则 ${\alpha }^k{b}_i$ 与 ${\alpha }^l{b}_j$ 至少有 $n-1$ 个对应位置上的值不同。矩阵B的两个约束条件分别称为 $\alpha$ 乘行约束1和2 (α­multiplied row constraint 1 and 2)。

定理1：如果矩阵B的每一行至多有一个0元素且矩阵B的任意一个 $2\times 2$ 子矩阵是非奇异的，则矩阵B满足 $\alpha$ 乘行约束1和2。

证明：因为当且仅当 $b_{i,s}=0$ 时， ${\alpha }^k{b}_{i,s}={\alpha }^l{b}_{i,s}$，其中 $0\le i<m$，$0\le k,l<q-1$，且 $k\ne l$，所以当且仅当矩阵B的每一行至多有一个0元素，矩阵B满足 $\alpha$ 乘行约束1。假设矩阵B不满足 $\alpha$ 乘行约束2，则 ${\alpha }^k{b}_{i,s}={\alpha }^l{b}_{j,s}$，${\alpha }^k{b}_{i,t}={\alpha }^l{b}_{j,t}$，其中 $0\le i,j<m$ 且 $i\ne j$，$0\le k,l<q-1$，$0\le s,t<n$ 且 $s\ne t$。因此 ${\alpha }^k{b}_{i,s}\cdot {\alpha }^l{b}_{j,t}={\alpha }^l{b}_{j,s}\cdot {\alpha }^k{b}_{i,t}$，由此推得 $b_{i,s}\cdot b_{j,t}-b_{i,t}\cdot b_{j,s}=0$ 即矩阵B存在 $2\times 2$ 奇异子矩阵，矛盾。

定理2：如果矩阵B满足 $\alpha$ 乘行约束1和2，则矩阵B满足 $2\times 2$ 子矩阵约束，即矩阵B中任意 $2\times 2$ 子矩阵至少有一个0元素或是非奇异的。

证明：如果B满足 $\alpha$ 乘行约束1和2，则 ${\alpha }^k{b}_{i,s}={\alpha }^l{b}_{i,s}$ 或 ${\alpha }^k{b}_{i,s}\ne {\alpha }^l{b}_{i,s}$ 且 ${\alpha }^k{b}_{i,s}={\alpha }^l{b}_{j,s}$ 或 ${\alpha }^k{b}_{i,s}\ne {\alpha }^l{b}_{j,s}$，其中 $0\le i,j<m$ 且 $i\ne j$，$0\le k,l<q-1$，$0\le s,t<n$ 且 $s\ne t$。

情况1：当 ${\alpha }^k{b}_{i,s}={\alpha }^l{b}_{i,s}$ 且 ${\alpha }^k{b}_{i,s}={\alpha }^l{b}_{j,s}$ 时，因为 ${\alpha }^k{b}_{i,s}={\alpha }^l{b}_{i,s}$，所以 $b_{i,s}=0$ ；又因为 ${\alpha }^k{b}_{i,s}={\alpha }^l{b}_{j,s}$，所以 $b_{j,s}=b_{i,s}=0$。因此 $B_{2\times 2}=\left[\begin{array}{cc}{b}_{i,s}& b_{i,t}\\ b_{j,s}& b_{j,t}\end{array}\right]=\left[\begin{array}{cc}0& b_{i,t}\\ 0& b_{j,t}\end{array}\right]$，故B满足 $2\times 2$ 子矩阵约束。

情况2：当 ${\alpha }^k{b}_{i,s}={\alpha }^l{b}_{i,s}$ 且 ${\alpha }^k{b}_{i,s}\ne {\alpha }^l{b}_{j,s}$ 时，因为 ${\alpha }^k{b}_{i,s}={\alpha }^l{b}_{i,s}$，所以 $b_{i,s}=0$ ；又因为 ${\alpha }^k{b}_{i,s}\ne {\alpha }^l{b}_{j,s}$，所以 $b_{j,s}\ne 0$。因此 $B_{2\times 2}=\left[\begin{array}{cc}{b}_{i,s}& b_{i,t}\\ b_{j,s}& b_{j,t}\end{array}\right]=\left[\begin{array}{cc}0& b_{i,t}\\ b_{j,s}& b_{j,t}\end{array}\right]$，$\det \left(B_{2\times 2}\right)=-b_{i,t}{b}_{j,s}\ne 0$，故B满足 $2\times 2$ 子矩阵约束。

情况3：当 ${\alpha }^k{b}_{i,s}\ne {\alpha }^l{b}_{i,s}$ 且 ${\alpha }^k{b}_{i,s}={\alpha }^l{b}_{j,s}$ 时，因为 ${\alpha }^k{b}_{i,s}={\alpha }^l{b}_{i,s}$ 且 ${\alpha }^k{b}_{i,s}={\alpha }^l{b}_{j,s}$，所以 ${\alpha }^k{b}_{i,s}{\alpha }^l{b}_{j,t}\ne {\alpha }^k{b}_{i,t}{\alpha }^l{b}_{j,s}$，即 $b_{i,s}{b}_{j,t}\ne b_{i,t}{b}_{j,s}$。因此 $B_{2\times 2}=\left[\begin{array}{cc}{b}_{i,s}& b_{i,t}\\ b_{j,s}& b_{j,t}\end{array}\right]$，$\det \left(B_{2\times 2}\right)=b_{i,s}{b}_{j,t}-b_{i,t}{b}_{j,s}\ne 0$，故B满足 $2\times 2$ 子矩阵约束。

情况4：当 ${\alpha }^k{b}_{i,s}\ne {\alpha }^l{b}_{i,s}$ 且 ${\alpha }^k{b}_{i,s}\ne {\alpha }^l{b}_{j,s}$ 时，因为 ${\alpha }^k{b}_{i,s}\ne {\alpha }^l{b}_{i,s}$ 且 ${\alpha }^k{b}_{i,s}\ne {\alpha }^l{b}_{j,s}$，所以 ${\alpha }^k{b}_{i,s}{\alpha }^l{b}_{j,t}\ne {\alpha }^k{b}_{i,t}{\alpha }^l{b}_{j,s}$，即 $b_{i,s}{b}_{j,t}\ne b_{i,t}{b}_{j,s}$。因此 $B_{2\times 2}=\left[\begin{array}{cc}{b}_{i,s}& b_{i,t}\\ b_{j,s}& b_{j,t}\end{array}\right]$，$\det \left(B_{2\times 2}\right)=b_{i,s}{b}_{j,t}-b_{i,t}{b}_{j,s}\ne 0$，故B满足 $2\times 2$ 子矩阵约束。

因此如果矩阵B满足 $\alpha$ 乘行约束1和2，则矩阵B满足 $2\times 2$ 子矩阵约束。

将矩阵B的每一项 $b_{i,j}$ 用其相应的 $\left(q-1\right)$ 重二进制矩阵散列 $A_b\left(b_{i,j}\right)$ 替换后，可以得到一个 $m\times n$ 阵列 $H_b$ ：

$H_b=\left[\begin{array}{cccc}{A}_b\left(b_{0,0}\right)& A_b\left(b_{0,1}\right)& \cdots & A_b\left(b_{0,n-1}\right)\\ A_b\left(b_{1,0}\right)& A_b\left(b_{1,1}\right)& \cdots & A_b\left(b_{1,n-1}\right)\\ ⋮& ⋮& \ddots & ⋮\\ A_b\left(b_{m-1,0}\right)& A_b\left(b_{m-1,1}\right)& \cdots & A_b\left(b_{m-1,n-1}\right)\end{array}\right]$

其中，若 $b_{i,j}\ne 0$，则 $A_b\left(b_{i,j}\right)$ 是 $GF\left(2\right)$ 上的一个 $\left(q-1\right)\times \left(q-1\right)$ CPM；若 $b_{i,j}=0$，则 $A_b\left(b_{i,j}\right)$ 是一个全零矩阵。 $H_b$ 是 $GF\left(2\right)$ 上的一个 $m\left(q-1\right)\times n\left(q-1\right)$ 矩阵。

类似地，将矩阵B的每一项 $b_{i,j}$ 用其相应的 $\left(q-1\right)$ 重q进制矩阵散列 $A_q\left(b_{i,j}\right)$ 替换后，可以得到一个 $m\times n$ 阵列 $H_q$ ：

$H_q=\left[\begin{array}{cccc}{A}_q\left(b_{0,0}\right)& A_q\left(b_{0,1}\right)& \cdots & A_q\left(b_{0,n-1}\right)\\ A_q\left(b_{1,0}\right)& A_q\left(b_{1,1}\right)& \cdots & A_q\left(b_{1,n-1}\right)\\ ⋮& ⋮& \ddots & ⋮\\ A_q\left(b_{m-1,0}\right)& A_q\left(b_{m-1,1}\right)& \cdots & A_q\left(b_{m-1,n-1}\right)\end{array}\right]$

其中，若 $b_{i,j}\ne 0$，则 $A_q\left(b_{i,j}\right)$ 是 $GF\left(q\right)$ 上的一个 $\alpha$ 倍循环置换矩阵；若 $b_{i,j}=0$，则 $A_b\left(b_{i,j}\right)$ 是一个全零矩阵。

$H_b$ 和 $H_q$ 分别是 $GF\left(2\right)$ 、 $GF\left(q\right)$ 上的一个 $m\left(q-1\right)\times n\left(q-1\right)$ 矩阵，将其分别称矩阵B的 $\left(q-1\right)$ 重二进制和q进制阵列散列((q-1)­fold binary and q­ary array dispersions)。

对于任意整数对 $\gamma$ 和 $\rho$，$1\le \gamma \le m$ 且 $1\le \rho \le n$，令 $H_b\left(\gamma ,\rho \right)$ 和 $H_q\left(\gamma ,\rho \right)$ 分别表示 $H_b$ 和 $H_q$ 的一个 $\gamma \times \rho$ 子阵列，则 $H_b\left(\gamma ,\rho \right)$ 和 $H_q\left(\gamma ,\rho \right)$ 分别是 $GF\left(2\right)$ 、 $GF\left(q\right)$ 上的一个 $\gamma \left(q-1\right)\times \rho \left(q-1\right)$ 矩阵。 $H_b\left(\gamma ,\rho \right)$ 在 $GF\left(2\right)$ 上的零空间给出了一个二进制QC­LDPC码 $C_b$，类似地， $H_q\left(\gamma ,\rho \right)$ 在 $GF\left(q\right)$ 上的零空间给出了一个q进制QC­LDPC码 $C_q$，其码长均为 $\left(q-1\right)\rho$。若 $H_b\left(\gamma ,\rho \right)$ 和 $H_q\left(\gamma ,\rho \right)$ 均不包含全零矩阵，则其具有固定的行重 $\gamma$ 和列重 $\rho$，码 $C_b$ 和 $C_q$ 均是规则的，反之，它们均为非规则的。

定理3：如果矩阵B满足 $2\times 2$ 子矩阵约束，则 $H_b$ 、 $H_q$ 满足RC­约束(Row­column constraint)，即 $H_b$ 、 $H_q$ 中任意两行(或两列)至多有一个对应位置都为非零项。

证明：假设 $H_b$ 不满足RC­约束。因为 $H_b$ 是一个循环置换矩阵的阵列，所以存在 $i,j,s,t,k,l$，其中 $0\le i,j<m$ 且 $i\ne j$，$0\le s,t<n$ 且 $s\ne t$，$0\le k,l<q-1$，使得 $A_b\left(b_{i,s}\right)$ 的第k行与 $A_b\left(b_{j,s}\right)$ 的第l行相等，即 $z_b\left({\alpha }^k{b}_{i,s}\right)=z_b\left({\alpha }^l{b}_{j,s}\right)$ ；且 $A_b\left(b_{i,t}\right)$ 的第k行与 $A_b\left(b_{j,t}\right)$ 的第l行相等，即 $z_b\left({\alpha }^k{b}_{i,t}\right)=z_b\left({\alpha }^l{b}_{j,t}\right)$。因为在 $GF\left(q\right)$ 上不同的元素有不同的位置向量，所以 ${\alpha }^k{b}_{i,s}={\alpha }^l{b}_{j,s}$ 且 ${\alpha }^k{b}_{i,t}={\alpha }^l{b}_{j,t}$。因此 ${\alpha }^k{b}_{i,s}{\alpha }^l{b}_{j,t}={\alpha }^k{b}_{i,t}{\alpha }^l{b}_{j,s}$，即 $b_{i,s}{b}_{j,t}=b_{i,t}{b}_{j,s}$，与矩阵B满足 $2\times 2$ 子矩阵约束矛盾，故 $H_b$ 满足RC­约束。同理，可证 $H_q$ 也满足RC­约束。

4. 基于有限域构造SC­QC­LDPC码的一般方法

考虑 $GF\left(q\right)$ 上一个满足 $2\times 2$ 子矩阵约束 $m\times n$ 矩阵 $B={\left[b_{i,j}\right]}_{0\le i<m,0\le j<n}$，复制矩阵B形成B的一个二维半无限阵列 $B_{rep}$ ：

$B_{rep}={\left[b_{rep,i,j}\right]}_{0\le i,j<\infty }=\left[\begin{array}{cc}\begin{array}{cc}B& B\\ B& B\end{array}& \begin{array}{cc}B& \dots \\ B& \dots \end{array}\\ \begin{array}{cc}B& B\\ ⋮& ⋮\end{array}& \begin{array}{cc}B& \dots \\ ⋮& \ddots \end{array}\end{array}\right],$

其中对于任意 $i,j\ge 0$ ； $b_{rep,i,j}=b_{\left(i\mathrm{mod}m\right),\left(j\mathrm{mod}n\right)}$。其次，构造一个具有带对角线结构的 $s\times t$ 修饰矩阵 $W_{base}={\left[w_{base,i,j}\right]}_{0\le i<s,0\le j<t}$，使用 $W_{base}$ 修饰 $B_{rep}\left(s,t\right)$ 形成一个SC基矩阵 $B_{sc}=B_{rep}\left(s,t\right)\circ W_{base}$。最后，利用 $B_{sc}$ 的二进制阵列散列形成一个 $GF\left(2\right)$ 上的 $s\left(q-1\right)\times t\left(q-1\right)$ 矩阵 $H_{sc,qc,b}$，其零空间给出一个二进制SC­QC­LDPC码 $C_{sc,qc,b}$ ；类似地，利用 $B_{sc}$ 的q进制阵列散列形成一个 $GF\left(q\right)$ 上的 $s\left(q-1\right)\times t\left(q-1\right)$ 矩阵 $H_{sc,qc,q}$，其零空间给出一个q进制SC­QC­LDPC码 $C_{sc,qc,q}$。

在原模图构造中，我们可以把修饰矩阵 $W_{base}$ 看作是与SC原模图相对应的原模矩阵(每对变量节点(Variable node, VN)和校验节点(Check node, CN)之间的边数不超过1)。此外，上述结构等价于提升 $W_{base}$ 相对应的SC原模图，其提升因子为 $q-1$。然而，提升(边的置换)是使用代数方法进行的。更一般地，这种构造也可以看作是SC­LDPC码的叠加构造 [21]，叠加基矩阵与修饰矩阵 $W_{base}$ 完全相同。

对于给定的修饰矩阵 $W_{base}$，我们可以得出最终的SC­QC­LDPC码的校验矩阵 $H_{sc,qc}$ 完全取决于B的选择。下面的定理是关于B的选择如何影响最终的SC­QC­LDPC码的围长性质。

定理4：假设B是 $GF\left(q\right)$ 上一个满足 $2\times 2$ 子矩阵约束的 $m\times n$ 矩阵，且 $B_{sc}=B_{rep}\left(s,t\right)\circ W_{base}$。对于任意的 $i_1,i_2,j_1,j_2$ 使得 $w_{base,i_1,j_1}=w_{base,i_1,j_2}=w_{base,i_2,j_1}=w_{base,i_2,j_2}=1$，若 $i_1-i_2$ 、 $j_1-j_2$ 分别不能被m、n整除，则 $B_{sc}$ 满足 $2\times 2$ 子矩阵约束。

证明：假设 $B_{sc}$ 不满足 $2\times 2$ 子矩阵约束，则存在 $i_1,i_2,j_1,j_2$，使得 $B_{sc,i_1,j_1}{B}_{sc,i_2,j_2}=B_{sc,i_2,j_1}{B}_{sc,i_1,j_2}$，且 $w_{base,i_1,j_1}=w_{base,i_1,j_2}=w_{base,i_2,j_1}=w_{base,i_2,j_2}=1$。再根据B和 $B_{rep}\left(s,t\right)$ 的关系，可得出 $i_1-i_2$ 、 $j_1-j_2$ 分别能被m、n整除，矛盾。因此， $B_{sc}$ 满足 $2\times 2$ 子矩阵约束。

上述二进制和多进制SC­QC­LDPC码的结构是基于 $GF\left(q\right)$ 上基矩阵B的 $\left(q-1\right)$ 重二进制矩阵散列或q进制矩阵散列和修饰矩阵 $W_{base}$ 构造，其中基矩阵B满足 $2\times 2$ 子矩阵约束。现在的问题是如何构造基矩阵B和修饰矩阵 $W_{base}$。接下来的三节将研究上述问题。

5. 基于有限域本原元的SC­QC­LDPC码构造

基矩阵B的构造：

对于 $0<u<q-1$，当且仅当u和 $q-1$ 互素， $GF\left(q\right)$ 上的非零元素 ${\alpha }^u$ 是一个本原元。 $GF\left(q\right)$ 中本原元的个数K可由下式给出的欧拉函数确定，其中 $p_1,p_2,\cdots ,p_k$ 是 $q-1$ 的不同素因子。

$K=\left(q-1\right){\displaystyle {\prod }_{i=1}^k\left(1-\frac{1}{p_i}\right)}$

设 $\left\{{\alpha }^{u_1},{\alpha }^{u_2},\cdots ,{\alpha }^{u_K}\right\}$ 是 $GF\left(q\right)$ 中K个本原元组成的集合，令 $u_0=0$。构造 $GF\left(q\right)$ 上的 $\left(K+1\right)\times \left(K+1\right)$ 矩阵：

$B^{\left(1\right)}=\left[\begin{array}{c}{b}_0\\ b_1\\ ⋮\\ b_{m-1}\end{array}\right]=\left[\begin{array}{cccc}{\alpha }^{u_0-u_0}-1& {\alpha }^{u_1-u_0}-1& \cdots & {\alpha }^{u_K-u_0}-1\\ {\alpha }^{u_0-u_1}-1& {\alpha }^{u_1-u_1}-1& \cdots & {\alpha }^{u_K-u_1}-1\\ ⋮& ⋮& \ddots & ⋮\\ {\alpha }^{u_0-u_K}-1& {\alpha }^{u_1-u_K}-1& \cdots & {\alpha }^{u_K-u_K}-1\end{array}\right]$ (5.1)

由上式，可以看出，矩阵 $B^{\left(1\right)}$ 具有以下结构性质：1) 每一行(列)的所有元素在 $GF\left(q\right)$ 上是不同的元素；2) 每一行(列)包含一个有且仅有一个零元素；3) 任何两行(列)对应位置上的元素均不同；4) $K+1$ 个0元素均位于矩阵的主对角线上。

推论1：矩阵 $B^{\left(1\right)}$ 满足 $2\times 2$ 子矩阵约束。

证明：基于定理1和定理2，对于矩阵 $B^{\left(1\right)}$ 的任意 $2\times 2$ 子矩阵 $B_{2\times 2}^{\left(1\right)}$，其元素属于第 $i_1$ 行、第 $i_2$ 行和第 $j_1$ 列、第 $j_2$ 列，其中 $0\le i_1,i_2,j_1,j_2\le K+1$ 且 $i_1\ne i_2$ 、 $j_1\ne j_2$，其行列式 $\det \left(B_{2\times 2}^{\left(1\right)}\right)=\left({\alpha }^{u_{j_1}-u_{i_1}}-1\right)\left({\alpha }^{u_{j_2}-u_{i_2}}-1\right)-\left({\alpha }^{u_{j_2}-u_{i_1}}-1\right)\left({\alpha }^{u_{j_1}-u_{i_2}}-1\right)=\frac{\left({\alpha }^{u_{i_1}}-{\alpha }^{u_{i_2}}\right)\left({\alpha }^{u_{j_1}}-{\alpha }^{u_{j_2}}\right)}{{\alpha }^{u_{i_1+}{u}_{i_2}}}\ne 0$，因此，矩阵 $B^{\left(1\right)}$ 满足 $2\times 2$ 子矩阵约束。

因此， $B^{\left(1\right)}$ 可作为进行 $\left(q-1\right)$ 重阵列散列的基矩阵来构造二进制和多进制SC­QC­LDPC码。

修饰矩阵 $W_{base}$ 的构造：

基于定理4，选取一个具有SC结构原模图的原模矩阵 [22] 作为修饰矩阵来修饰基矩阵B。

$B=\left[\begin{array}{cc}3& 3\end{array}\right]\Rightarrow B_0=B_1=B_2=\left[\begin{array}{cc}1& 1\end{array}\right]$

下面以几个例子来说明基于有限域本原元的SC­QC­LDPC码的构造。

5.1. 一类二进制SC­QC­LDPC码

例5.1.

基矩阵B的选取：将 $GF\left(2^8\right)$ 作为构造码的域。注意到 $2^8-1=255$ 可分解为 $3\times 5\times 17$。根据欧拉方程可知 $GF\left(2^8\right)$ 有 $K=255\times \left(1-1/3\right)\left(1-1/5\right)\left(1-1/17\right)=128$ 个本原元。利用式(5.1)，我们可以构造一个128 × 128基矩阵B。

修饰矩阵 $W_{base}$ 的选取：选择 $L=40$，$a=3$，$b=2$，$c=1$，且选择40个分量规则矩阵 $\left\{{\Delta }_k\right\}\left(0\le k\le 4\right)$ 为全一矩阵。

二进制SC­QC­LDPC码的构造：利用算法1给出的构造方法，可形成一个 $GF\left(2\right)$ 上的5334 × 10,160矩阵 $H_{sc,qc,b}$，其零空间给出一个二进制SC­QC­LDPC码 $C_{sc,qc,b}$。

5.2. 一类多进制SC­QC­LDPC码

例5.2.

基矩阵B的选取：将 $GF\left(2^6\right)$ 作为构造码的域。注意到 $2^6-1=63$ 可分解为 $3\times 3\times 7$。根据欧拉方程可知 $GF\left(2^8\right)$ 有 $K=63\times \left(1-1/3\right)\left(1-1/7\right)=36$ 个本原元。利用式(5.1)，我们可以构造一个36 × 36基矩阵B。

修饰矩阵 $W_{base}$ 的选取：选择 $L=40$，$a=3$，$b=2$，$c=1$，且选择40个分量规则矩阵 $\left\{{\Delta }_k\right\}\left(0\le k\le 4\right)$ 为全一矩阵。

多进制SC­QC­LDPC码的构造：利用算法2给出的构造方法，可形成一个 $GF\left(q\right)$ 上2646 × 5040矩阵 $H_{sc,qc,q}$，其零空间给出一个q进制SC­QC­LDPC码 $C_{sc,qc,q}$。

6. 基于有限域的加法子群构造SC­QC­LDPC码

基矩阵B的构造：令 $q=p^m$，其中p为素数且m为正整数。设 $GF\left(q\right)$ 是素域 $GF\left(q\right)$ 扩域， $\alpha$ 是 $GF\left(q\right)$ 的本原元，则 ${\alpha }^0,{\alpha }^1,\cdots ,{\alpha }^{m-1}$ 在 $GF\left(q\right)$ 上线性无关，它们构成了 $GF\left(q\right)$ 的一组基。 $GF\left(q\right)$ 的任意元素 ${\alpha }^i$ 都可以表示为 ${\alpha }^0,{\alpha }^1,\cdots ,{\alpha }^{m-1}$ 的线性组合，即 ${\alpha }^i=c_{i,0}{\alpha }^0+c_{i,1}\alpha +\cdots +c_{i,m-1}{\alpha }^{m-1}$，其中， $c_{i,j}\in GF\left(p\right)$。当 $1\le t<m$ 时，设 $G_1=\left\{{\beta }_0=0,{\beta }_1,\cdots ,{\beta }_{P^t-1}\right\}$ 是由 ${\alpha }^0,{\alpha }^1,\cdots ,{\alpha }^t$ 的线性组合生成的 $GF\left(q\right)$ 上的加法子群，即 ${\beta }^i=c_{i,0}{\alpha }^0+c_{i,1}\alpha +\cdots +c_{i,t}{\alpha }^t$，其中， $c_{i,j}\in GF\left(p\right)$。设 $G_2=\left\{{\gamma }_0=0,{\gamma }_1,\cdots ,{\gamma }_{P^{m-t}-1}\right\}$ 是由 ${\alpha }^t,{\alpha }^{t+1},\cdots ,{\alpha }^{m-1}$ 的线性组合生成的 $GF\left(q\right)$ 上的加法子群，即 ${\gamma }^i=c_{i,t}{\alpha }^t+c_{i,t+1}{\alpha }^{t+1}+\cdots +c_{i,m-1}{\alpha }^{m-1}$，其中， $c_{i,j}\in GF\left(p\right)$。显然， $G_1\cap G_2=\left\{0\right\}$。当 $0\le i<p^{m-t}$ 时，定义如下元素集合：

${\gamma }_i+G_1=\left\{{\gamma }_i,{\gamma }_i+{\beta }_1,\cdots ,{\gamma }_i+{\beta }_{P^t-1}\right\}$

该集合其实就是以 ${\gamma }_i$ 为陪集首的 $G_1$ 的陪集，包括其自身。这 $P^{m-t}$ 个陪集构成了有限域 $GF\left(q\right)$ 中q个元素的一个划分。 $G_1$ 的两个陪集是不相交的。

构造 $GF\left(q\right)$ 上大小为 $p^{m-t}\times p^t$ 的矩阵：

$B^{\left(2\right)}=\left[\begin{array}{c}{b}_0\\ b_1\\ ⋮\\ b_{m-1}\end{array}\right]=\left[\begin{array}{cccc}0& {\beta }_1& \cdots & {\beta }_{p^t-1}\\ {\gamma }_1& {\gamma }_1+{\beta }_1& \cdots & {\gamma }_1+{\beta }_{p^t-1}\\ ⋮& ⋮& \ddots & ⋮\\ {\gamma }_{p^{m-t}-1}& {\gamma }_{p^{m-t}}+{\beta }_1& \cdots & {\gamma }_{p^{m-t}}+{\beta }_{p^t-1}\end{array}\right]$ (6.1)

这里对于 $0\le i<P^{m-t}$，第i行由 $G_1$ 的第i个陪集的元素组成。 $GF\left(q\right)$ 的每一个元素在 $B^{\left(2\right)}$ 中出现且仅出现一次。除第一行， $B^{\left(2\right)}$ 中的每一行 $b_i$ 都由 $GF\left(q\right)$ 的非零元素组成。 $B^{\left(2\right)}$ 的第一行第一个位置为 $GF\left(q\right)$ 上的0元素。除第一列， $B^{\left(2\right)}$ 中的每一行都由 $GF\left(q\right)$ 的非零元素组成。 $B^{\left(2\right)}$ 的第一列第一个位置为 $GF\left(q\right)$ 上的0元素。由于 $G_1$ 的任意两个陪集互不相交，故 $B^{\left(2\right)}$ 任意不同两行对应位置的元素也互不相同。

推论2：矩阵 $B^{\left(2\right)}$ 满足 $2\times 2$ 子矩阵约束。

证明：基于定理1和定理2，对于矩阵 $B^{\left(2\right)}$ 的任意 $2\times 2$ 子矩阵 $B_{2\times 2}^{\left(2\right)}$，其元素属于第 $i_1$ 行、第 $i_2$ 行和第 $j_1$ 列、第 $j_2$ 列，其中 $0\le i_1,i_2\le P^{m-t}$ 、 $0\le j_1,j_2\le P^t$ 且 $i_1\ne i_2$ 、 $j_1\ne j_2$，其行列式 $\det \left(B_{2\times 2}^{\left(2\right)}\right)=\left({\gamma }_{i_1}+{\beta }_{j_1}\right)\left({\gamma }_{i_2}+{\beta }_{j_2}\right)-\left({\gamma }_{i_1}+{\beta }_{j_2}\right)\left({\gamma }_{i_2}+{\beta }_{j_1}\right)=\left({\gamma }_{i_1}-{\gamma }_{i_2}\right)\left({\beta }_{j_1}-{\beta }_{j_2}\right)\ne 0$，因此，矩阵 $B^{\left(2\right)}$ 满足 $2\times 2$ 子矩阵约束。

修饰矩阵 $W_{base}$ 的构造：

基于定理 ，选取一个码率为1⁄3的结构化不规则LDPC码的原模图，其相对应的原模矩阵为：

$V=\left[\begin{array}{cc}\begin{array}{ccc}1& 1& 1\\ 0& 1& 1\\ 0& 1& 1\end{array}& \begin{array}{cc}\begin{array}{cc}1& 0\\ 0& 0\\ 0& 1\end{array}& \begin{array}{ccc}0& 0& 0\\ 0& 0& 0\\ 0& 0& 0\end{array}\end{array}\\ \begin{array}{ccc}0& 1& 1\\ 0& 1& 0\\ 0& 0& 1\end{array}& \begin{array}{cc}\begin{array}{cc}1& 0\\ 1& 1\\ 1& 0\end{array}& \begin{array}{ccc}1& 0& 0\\ 0& 1& 1\\ 1& 1& 1\end{array}\end{array}\end{array}\right],$

为了保持原结构化不规则分组码的度分布，使用展开技术(unwrapping technique)来构造修饰矩阵 $W_{base}$。将V分解为两个矩阵 $V_1$ 和 $V_2$，使得 $V=V_1+V_2$，其中

$V_1=\left[\begin{array}{cc}\begin{array}{ccc}1& 0& 1\\ 0& 1& 0\\ 0& 1& 0\end{array}& \begin{array}{cc}\begin{array}{cc}0& 0\\ 0& 0\\ 0& 0\end{array}& \begin{array}{ccc}0& 0& 0\\ 0& 0& 0\\ 0& 0& 0\end{array}\end{array}\\ \begin{array}{ccc}0& 1& 0\\ 0& 1& 0\\ 0& 0& 1\end{array}& \begin{array}{cc}\begin{array}{cc}1& 0\\ 0& 1\\ 0& 0\end{array}& \begin{array}{ccc}0& 0& 0\\ 0& 1& 0\\ 1& 0& 1\end{array}\end{array}\end{array}\right],$

$V_2=\left[\begin{array}{cc}\begin{array}{ccc}0& 1& 0\\ 0& 0& 1\\ 0& 0& 1\end{array}& \begin{array}{cc}\begin{array}{cc}1& 0\\ 0& 0\\ 0& 0\end{array}& \begin{array}{ccc}0& 0& 0\\ 0& 0& 0\\ 0& 0& 0\end{array}\end{array}\\ \begin{array}{ccc}0& 0& 1\\ 0& 0& 0\\ 0& 0& 0\end{array}& \begin{array}{cc}\begin{array}{cc}0& 0\\ 1& 0\\ 1& 0\end{array}& \begin{array}{ccc}1& 0& 0\\ 0& 0& 1\\ 0& 1& 0\end{array}\end{array}\end{array}\right],$

则

$W_{base}=\left[\begin{array}{cccccc}{V}_1& & & & & \\ V_2& V_1& & & & \\ & V_2& V_1& & & \\ & & V_2& & & \\ & & & & \ddots & \\ & & & & \ddots & V_1\\ & & & & & V_2\end{array}\right]$ (6.2)

下面以几个例子来说明基于有限域的加法子群SC­QC­LDPC码的构造。

6.1. 一类二进制SC­QC­LDPC码

例6.1.

基矩阵B的选取：将 $GF\left(2^8\right)$ 作为构造码的域。令 $\alpha$ 为 $GF\left(2^8\right)$ 的本原元( $GF\left(2\right)$ 的一个扩域)。设 $t=5$，则 $m-t=3$。设 $G_1$ 和 $G_2$ 是 $GF\left(2^8\right)$ 上加法群的两个子群，分别由 $\left\{{\alpha }^0,{\alpha }^1,{\alpha }^2,{\alpha }^3,{\alpha }^4\right\}$ 和 $\left\{{\alpha }^5,{\alpha }^6,{\alpha }^7\right\}$ 张成。因此 $G_1=\left\{{\beta }_0=0,{\beta }_1,\cdots ,{\beta }_{31}\right\}$，$G_2=\left\{{\gamma }_0=0,{\gamma }_1,\cdots ,{\gamma }_7\right\}$。利用式(6.1)，我们可以构造一个8 × 32基矩阵B。

修饰矩阵 $W_{base}$ 的选取：选择 $L=26$，利用式(6.2)，我们可以构造一个162 × 208修饰矩阵 $W_{base}$。

二进制SC­QC­LDPC码的构造：利用算法1给出的构造方法，可形成一个 $GF\left(2\right)$ 上20,574 × 26,416矩阵 $H_{sc,qc,b}$，其零空间给出一个二进制SC­QC­LDPC码 $C_{sc,qc,b}$。

6.2. 一类多进制SC­QC­LDPC码

例6.2.

基矩阵B的选取：将 $GF\left(2^6\right)$ 作为构造码的域。令 $\alpha$ 为 $GF\left(2^6\right)$ 的本原元( $GF\left(2\right)$ 的一个扩域)。设 $t=4$，则 $m-t=2$。设 $G_1$ 和 $G_2$ 是 $GF\left(2^6\right)$ 上加法群的两个子群，分别由 $\left\{{\alpha }^0,{\alpha }^1,{\alpha }^2,{\alpha }^3\right\}$ 和 $\left\{{\alpha }^4,{\alpha }^5\right\}$ 张成。因此 $G_1=\left\{{\beta }_0=0,{\beta }_1,\cdots ,{\beta }_{15}\right\}$，$G_2=\left\{{\gamma }_0=0,{\gamma }_1,{\gamma }_2,{\gamma }_3\right\}$。利用式(6.1)，我们可以构造一个4 × 16基矩阵B。

修饰矩阵 $W_{base}$ 的选取：选择 $L=26$，利用式(6.2)，我们可以构造一个162 × 208修饰矩阵 $W_{base}$。

多进制SC­QC­LDPC码的构造：利用算法2给出的构造方法，可形成一个 $GF\left(q\right)$ 上10,206 × 13,104矩阵 $H_{sc,qc,q}$，其零空间给出一个q进制SC­QC­LDPC码 $C_{sc,qc,q}$。

7. 基于有限域的乘法子群构造SC­QC­LDPC码

基矩阵B的构造：令 $\alpha$ 是 $GF\left(q\right)$ 的本原元。假设 $q-1$ 不是素数。令 $\beta ={\alpha }^k$，$\gamma ={\alpha }^m$，其中k、m互素且 $q-1=km$，则 $M_1=\left\{{\beta }^0=1,\beta ,\cdots ,{\beta }^{m-1}\right\}$ 和 $M_2=\left\{{\gamma }^0=1,\gamma ,\cdots ,{\gamma }^{k-1}\right\}$ 构成了 $GF\left(q\right)$ 上的两个循环乘法子群，且 $M_1\cap M_2=\left\{1\right\}$。当 $0\le i<k$，集合 ${\gamma }^i{M}_1=\left\{{\gamma }^i,{\gamma }^i\beta ,\cdots ,{\gamma }^i{\beta }^{m-1}\right\}$ 是 $M_1$ 的一个乘法陪集。循环子群 $M_1$ 共有k个乘法陪集，包括其自身。当 $0\le j<m$，集合 ${\beta }^j{M}_2=\left\{{\beta }^j,{\beta }^j\gamma ,\cdots ,{\beta }^j{\gamma }^{k-1}\right\}$ 是 $M_2$ 的一个乘法陪集。循环子群 $M_2$ 共有m个乘法陪集，包括其自身。构造 $GF\left(q\right)$ 上大小为 $k\times m$ 的矩阵：

$B^{\left(3\right)}=\left[\begin{array}{c}{b}_0\\ b_1\\ ⋮\\ b_{m-1}\end{array}\right]=\left[\begin{array}{cccc}0& \beta -1& \cdots & {\beta }^{m-1}-1\\ \gamma -1& \gamma \beta -1& \cdots & \gamma {\beta }^{m-1}-1\\ ⋮& ⋮& \ddots & ⋮\\ {\gamma }^{k-1}-1& {\gamma }^{k-1}\beta -1& \cdots & {\gamma }^{k-1}{\beta }^{m-1}-1\end{array}\right]$ (7.1)

其中，第i行的分量可通过将 $M_1$ 的第i个乘法陪集中每一个元素减去 $GF\left(q\right)$ 中的元素1得到的；第j行的分量可通过将 $M_2$ 的第j个乘法陪集中每一个元素减去 $GF\left(q\right)$ 中的元素1得到的。

由上式，可以看出，矩阵 $B^{\left(1\right)}$ 具有以下结构性质：1) 有且仅有一个0元素，其位于左上角，其余 $km-1$ 个元素均是 $GF\left(q\right)$ 上的非零元素；2) 任意两行的m个对应位置上的元素均不相同；3) 任意两列的k个对应位置上的元素均不相同；4) 所有元素均是 $GF\left(q\right)$ 上的不同元素。

推论3：矩阵 $B^{\left(3\right)}$ 满足 $2\times 2$ 子矩阵约束。

证明：基于定理1和定理2，对于矩阵 $B^{\left(3\right)}$ 的任意 $2\times 2$ 子矩阵 $B_{2\times 2}^{\left(3\right)}$，其元素属于第 $i_1$ 行、第 $i_2$ 行和第 $j_1$ 列、第 $j_2$ 列，其中 $0\le i_1,i_2\le k$ 、 $0\le j_1,j_2\le m$ 且 $i_1\ne i_2$ 、 $j_1\ne j_2$，其行列式 $\det \left(B_{2\times 2}^{\left(3\right)}\right)=\left({\gamma }^{i_1}{\beta }^{j_1}-1\right)\left({\gamma }^{i_2}{\beta }^{j_2}-1\right)-\left({\gamma }^{i_1}{\beta }^{j_2}-1\right)\left({\gamma }^{i_2}{\beta }^{j_1}-1\right)=\left({\gamma }^{i_1}-{\gamma }^{i_2}\right)\left({\beta }^{j_2}-{\beta }^{j_1}\right)\ne 0$，因此，矩阵 $B^{\left(3\right)}$ 满足 $2\times 2$ 子矩阵约束。