In this paper, a scheme to construct the high-rate regular quasi-cyclic low-density parity-check (QC-LDPC) codes is developed based on the finite geometry low-density parity-check (LDPC) codes. To achieve this, we first decompose the EG-LDPC code into a set of the block submatrices with each of them being cyclic. Utilizing the decomposed structure, we then construct an auxiliary matrix to facilitate us for identifying and eliminating 6-cycles of the block submatrices. In the simulation, seven regular QC-LDPC codes with code rates being 4/5, 7/8, 10/11, 11/12, and 12/13 of moderate code lengths are constructed with this scheme. The performances of these codes demonstrate the effectiveness of the proposed scheme.
Notes
Authors’ information
QM is a graduate student at the College of Electronic Information and Optical Engineering at Nankai University. His research interests include digital signal processing and error control coding.
JXZ is a professor at the College of Electronic Information and Optical Engineering at Nankai University. His research interests include biological signal processing, high-speed digital transmission algorithm, and error control coding.
WX is a professor at Tianjin Polytechnic University. Her research interests include digital signal processing and error control coding.
LL is serving as a communications engineer in IP Technology Research Department at Huawei Technologies Co., Ltd.
Abbreviations
BER
Bit error rate
CDFs
Cyclic difference families
EG-LDPC
Euclidian geometry low-density parity-check
FER
Frame error rate
FG-LDPC
Finite geometry low-density parity-check
LDPC
Low-density parity-check
PG-LDPC
Projective geometry low-density parity-check
QC-LDPC
Quasi-cyclic low-density parity-check
1 Introduction
Low-density parity-check (LDPC) codes [1], which is one of the main error-correcting codes, has been widely used in various practical applications [2, 3]. However, the high-rate regular QC-LDPC codes which are prone to the hardware implementation [4] and particularly suited for many practical applications can be constructed only for very restricted code parameters, such as code rate and code length. This is primarily due to the fact that for a given code length, especially short or moderate code lengths, the parity-check matrices of high-rate codes are far more dense than those of low-rate codes, which could lead to making more short cycles. Therefore, it is imperative to research on the schemes that offer a flexibly choosing the code rate and length of the high-rate regular QC-LDPC codes.
Although both QC-LDPC and turbo codes [5, 6] are capable of achieving the near Shannon limit performances, the QC-LDPC codes in general are easier to implement in practices [7, 8]. For this reason, many schemes have been developed for designing regular QC-LDPC codes, such as FG-LDPC codes [9, 10] and LDPC codes of combinatorial designs [11]. These schemes are also employed in constructing the high-rate regular QC-LDPC codes [12, 13].
Advertisement
However, the high-rate regular QC-LDPC codes constructing from the above schemes usually have very restricted code parameters. That is, for a given coding rate, the above schemes only offer extremely limited choices of the code length. Some examples of these are the class-I circulant EG-LDPC codes [9, 12] and cyclic difference families (CDFs) [14].
In this paper, we utilize the construction of the FG-LDPC codes [9, 10] to develop a scheme for designing the high-rate regular QC-LDPC codes. The designing procedure proceeds as follows: We first decompose the EG-LDPC or PG-LDPC code into a set of the block submatrices with each of them being cyclic. We then construct a φ transformation which acts on the first line of the obtained block submatrices to yield an auxiliary matrix \(\mathcal {T}\left (\hat {\mathbf {h}}\right)\) for identifying and cancelling 6-cycles of the block submatrices. In the simulation, we use this scheme to construct four regular QC-LDPC codes with the code rates being 11/12 and 12/13 which have the code lengths 7560, 1092 and 4095, 8190, respectively. Furthermore, we also employ the same scheme to construct three regular QC-LDPC codes with code rates being 4/5, 7/8, and 10/11 whose lengths are 2925, 7280, and 6930. The performances of these codes demonstrate the effectiveness of the proposed scheme.
2 A review of cyclic finite geometry LDPC codes
This section gives a brief review of FG-LDPC codes and introduces some definitions as well as notations that are used throughout the rest of the paper.
An m-dimensional finite Euclidean geometry over the field GF(2s) with m and s being the two positive integers, denoted EG(m,2s), is a set of 2sm-tuples (a0,a1,⋯,am−1) where ai∈GF(2s) for each i=0,1,…,m−1.
Advertisement
Defining the entry-wise addition and multiplication for m-tuples of EG(m,2s), the set EG(m,2s) forms a vector space over GF(2s). There are 2ms points in EG(m,2s). Therefore, let α be a primitive element of EG(m,2s). All the elements of EG(m,2s) can be represented as the power of α, i.e., \(0=\alpha ^{-\infty }\,,\,1=\alpha ^{0}\,,\,\alpha \,,\,\ldots \,,\,\alpha ^{2^{ms}-2}\). For any point α∈EG(m,2s) and any nonorigin point β∈EG(m,2s), the line Lα(β) through α parallel to β comprised of 2s points is:
lines passing through it. The lines of EG(m,2s) can be partitioned into k cosets where any two lines of EG(m,2s) belong to the same coset if and only if they are parallel to each other.
Recall that α is a primitive element of EG(m,2s). The parity-check matrix HEG of the Euclidean geometry code is a k×(2ms−1) matrix whose columns correspond to the ordered \(1=\alpha ^{0}\,,\,\alpha \,,\,\ldots \,,\,\alpha ^{2^{ms}-2}\phantom {\dot {i}\!}\). The rows of HEG correspond to the cosets in EG(m,2s) which do not contain the lines passing through the origin. That is, the (i,j) entry in HEG is equal to 1 if the ith coset contains a line passing the jth point, and is equal to 0 otherwise.
3 Construction method
In this section, we proceed with the procedure of the construction of the high-rate regular (QC-LDPC) codes through the following three steps: (1) Construct an n×n EG code and transform it into a proper form. (2) Utilize the transformed EG code matrix to construct an auxiliary matrix for identifying 6-cycles of it. (3) Eliminate the 6-cycles.
3.1 Decomposition of EG code matrix
Following [9], we can construct a n×n Euclidean geometry code W over the field EG(m=2,2s), where n=2ms−1. The constructed matrix W which is cyclic can be expressed by its first row w=(ω0,ω1,…,ωn−1) as:
which implies that each row of the cyclic matrix W has the identical weight.
We assume that the positive integer n can be factored as n=c×b where b≠1 and c≠1 are positive integers with b being odd throughout the rest of this paper. Define the subset:
where we define π(0)+i={i,c+i,2c+i,…,(b−1)c+i} for i=0,1,…,c−1. We use π to denote the partition of the indices in \(\mathcal {L}\) defined in (7) for the rest of this paper. Using this partitioning, we obtain a b×n quasi-cyclic matrix Hqc as:
Let ri represent the row weight of Ψ(wi) for i=0,1,2,…,c−1 respectively. Choosing a positive integer 1≤λ< maxi=0,1,…,c−1{ri}, we eliminate all the Ψ(wk) (0≤k≤c−1) whose row weights are less than λ from the set:
It follows \(r_{i_{k}} \geq \lambda \) for 0≤k≤k1−1. Since the row weight of Hqc defined in (8) is 2s, we choose the parameter λ satisfying c<2s/λ that ensures the subset (10) is not a null set.
where the row weight ri of Ψ(vi) for each i satisfying 0≤i≤k−1 is at least λ which is described in the previous section. The vector vi with 0≤i≤k−1 is:
In order to eliminate 6-cycles, we transform matrix (12) into a new matrix of form (17). This leads us to introduce the operation φ which is defined as:
Examing (17), we see that the first row of \(\mathcal {T}(\hat {\mathbf {h}})\) is obtained through adding b−1 zeros to the end of the vector \(\hat {\mathbf {h}}\). Each of the rest rows of \(\mathcal {T}(\hat {\mathbf {h}})\) is the circular shift of the row above it.
The set \(L(\hat {\mathbf {h}})\) comprised of the indices corresponding to the nonzero entries of \(\hat {\mathbf {h}}\) in (16) is defined as:
where we have \(\rho = \sum \limits _{i=0}^{k-1}r_{i}\) with ri representing the row weight of Ψ(vi). We define an oblique line segment \(l_{p_{i}}\) which starts from pi and forms a descending diagonal from left to right in \(\mathcal {T}(\hat {\mathbf {h}})\),i.e., \(l_{p_{i}}\) constituting of the set of the entries of \(\mathcal {T}(\hat {\mathbf {h}})\) as follows:
From [15], it follows that the possible of 6-cycles appeared in a parity-check matrix is one of the following forms shown in Fig. 1.
Fig. 1
Six possible loops that yield 6-cycles
×
Case 1: Assume that 6-cycle is comprised of three oblique line segments from (20). Therefore, from (20), the total number of subsets comprised of three oblique line segments is \(\dbinom {\rho }{3}\). For each subset comprised of three oblique line segments \(\left \{l_{p_{i_{0}}}, l_{p_{i_{1}}}, l_{p_{i_{2}}}\right \}\) from (20), we employ (21) to compute:
If \({d_{0}\over {d_{1}}}\) is not equal to either \(1\over {2}\) or 2, then we delete such a subset comprised of these three oblique line segments. The remaining subsets constitute Ω3 which can be represented as:
Figure 2 shows that 6-cycles are constituted by three oblique lines.
Fig. 2
6-cycles constituted by three oblique line segments in (17)
×
Case 2: Assume that 6-cycle is comprised of four oblique line segments from (20). Therefore, from (20), the total number of subsets comprised of four oblique line segments is \(\dbinom {\rho }{4}\). For each subset comprised of four oblique line segments \(\{l_{p_{i_{0}}}, l_{p_{i_{1}}}, l_{p_{i_{2}}}, l_{p_{i_{3}}}\}\) from (20), we employ (21) to compute:
Figure 3 shows that 6-cycles are constituted by four oblique line segments.
Fig. 3
6-cycles constituted by four oblique line segments in (17)
×
Case 3: Assume that 6-cycle is comprised of five oblique line segments from (20). Therefore, from (20), the total number of subsets comprised of five oblique line segments is \(\dbinom {\rho }{5}\). For each subset comprised of five oblique line segments \(\{l_{p_{i_{0}}}, l_{p_{i_{1}}}, l_{p_{i_{2}}}, l_{p_{i_{3}}}, l_{p_{i_{4}}}\}\) from (20), we employ (21) to compute:
where Ω3, Ω4, and Ω5 are defined by (23), (27), and (30), respectively.
Step 2: Find the oblique line segment \(l_{p_{i_{0}}}\) that appears in the maximal number subsets of Γ. Delete all the subsets of Γ containing this oblique line segment \(l_{p_{i_{0}}}\) and collect all the remaining subsets of Γ to form an new subset Γ1. Repeat this process on the subset Γ1 to obtain \(l_{p_{i_{1}}}\) and Γ2. We continue this process till Γk for k being some positive integer becomes a null set. In this process, we also obtain an ordered set of oblique line segments which is:
Step 3: In view of (12), we construct k subsets Q0,Q1,…,Qk−1 with Qj for 0≤j≤k−1 being comprised of the oblique line segments \(l_{p_{i_{j}}}\) in Ωorder satisfying:
$$ \lfloor p_{i_{j}}/b\rfloor =j, $$
(33)
where ⌊·⌋ denotes the rounding down operation. Recall that rj for 0≤j≤k−1 is the row weight of Ψ(vj) in (12) and λ is the pre-chosen positive integer introduced above Eq. (9). If there are more than (rj−λ) oblique line segments of Ωorder satisfy (33), then only the first (rj−λ) oblique line segments appeared in the ordered set Ωorder are chosen to form Qj. If there are less than (rj−λ) oblique line segments of Ωorder satisfy (33), we arbitrarily choose oblique line segments satisfying (33) from (20) that do not belong to Ωorder.
Thus, Qj for 0≤j≤k−1 has the size of (rj−λ). We define 1×b vector sj:
In view of Hqc′ and S defined in (12) and (36), respectively, the quasi-cyclic encoding parity-check matrix \(\mathbf {H}_{\text {qc}}^{(1)}\) is therefore equal to:
The operator ⊕ in (37) is defined as the entry-wise XOR operations of matrices Hqc′ and S. From the construction procedure from (12) to (37), it follows that matrix \(\mathbf {H}_{\text {qc}}^{(1)}\) is regular and quasi-cyclic with its column and row weight being λ and kλ, respectively.
3.4 Another regular quasi-cyclic parity-check matrix
Substituting \(\mathbf {H}_{\text {qc}}^{(1)}\) for Hqc′ and proceeding the procedure from (12) to (36) with λ=0, we can get a new S(1) from (36). Then, we can construct another regular quasi-cyclic parity-check matrix \(\mathbf {H}_{\text {qc}}^{(2)}\) as follows:
\(\mathbf {H}_{\text {qc}}^{(2)}\) and \(\mathbf {H}_{\text {qc}}^{(1)}\) have the same row and column weight.
4 Result and discussion
In example 1 of this section, we utilize the procedure from (4) to (37) to construct a regular quasi-cyclic (4095,3781) LDPC code as well as (38) to construct regular quasi-cyclic (7560,6931) and (8190,7561) LDPC codes where the coding rates of all these three codes are 12/13.
In example 2, we utilize the procedure from (4) to (37) to construct a regular quasi-cyclic (2925,2341) LDPC code and a regular quasi-cyclic (4095,3781) LDPC code where the coding rates of all these two codes are 4/5 and 11/12, respectively.
In example 3 and example 4, the procedure of (4)–(38) is also employed to separately construct a regular quasi-cyclic (6930,6301) LDPC code and a regular quasi-cyclic (7280,6370) LDPC code with the coding rate 10/11 and 7/8, respectively. As a comparison of the performance, we also utilize the schemes from [16‐18] to construct six (4095,3771), (4095,3729), (16383,14923), (8176,7156), (1020,935), and (2850,2280) QC-LDPC codes. The simulation results in the following examples show that the procedure from (4) to (38) is an effective scheme to yield the high-rate regular QC-LDPC codes with moderate code lengths.
Example 1: Following the scheme of [9], we first construct a regular (4095,3367) EG-LDPC code over the field EG(2,26). Since we have 4095=c×b with c=13 and b=315, the procedure from (4) to (8) suggests that the parity-check matrix of the constructed (4095,3367) EG-LDPC code can be decomposed into 13 submatrices of size b×b shown in (8). Of the 13 submatrices of size b×b, choose the parameter λ=4 to perform (9) to (11) where parameter λ is introduced above Eq. (9). Then, we select the first k=13 submatrices and perform (12) to (37) and (38) separately which yields a regular quasi-cyclic 315×4095 parity-check matrix \(\mathbf {H}_{\text {qc}}^{(1)}\) defined in (37) as well as a 630×8190 parity-check matrix \(\mathbf {H}_{\text {qc}}^{(2)}\) defined in (38) respectively. The null spaces of \(\mathbf {H}_{\mathrm { qc}}^{(1)}\) and \(\mathbf {H}_{\text {qc}}^{(2)}\) render a regular quasi-cyclic (4095,3781) LDPC code as well as a (8190,7561) LDPC code with the coding rate 12/13. Similarily, we also choose the first k=12 submatrices and perform (12) to (38) which yields a regular quasi-cyclic 630×7560 parity-check matrix \(\mathbf {H}_{\text {qc}}^{(2)}\) defined in (38). The null space of this \(\mathbf {H}_{\text {qc}}^{(2)}\) also renders a regular quasi-cyclic (7560,6931) LDPC code with the coding rate 11/12. As a comparison, we also employ the procedure of [16] to construct the (4095,3771) QC-LDPC code with the coding rate being 0.92.
Figure 5 shows the performances of these codes where it (a) represents the bit error rate (BER) and (b) depicts the frame error rate (FER). In these figures, the circle, box, and diamond solid lines respectively represent the performances of the regular quasi-cyclic (4095,3781), (7560,6931), and (8190,5161) LDPC codes. The star dotted line corresponds to the performance of the (4095,3771) QC-LDPC code generated by [16].
Fig. 5
a The bit error rate and b frame error rate performances of four LDPC codes in example 1. In these figures, the circle, box, and diamond solid lines separately represent to the performances of the regular quasi-cyclic (4095,3781), (7560,6931), and (8190,5161) LDPC codes with coding rate 12/13 generated by the procedure from (4) to (38). The star dotted line corresponds to the (4095,3771) QC-LDPC code which is also shown in the example 4 of [16]. These 4 LDPC codes are all decoded with 50 iterations of the SPA (sum-product algorithm)
×
Example 2: Following the scheme of [9], we first construct a regular (4095,3367) EG-LDPC code over the field EG(2,26). Since we have 4095=c×b with c=7, b=585, and c=45, b=91, the procedure from (4) to (8) suggests that the parity-check matrix of the constructed (4095,3367) EG-LDPC code can be decomposed into 7 and 45 submatrices of size b×b shown in (8). Of 7 and 45 submatrices of size b×b, choose the parameters λ=4 and λ=3 to perform (9) to (11) where parameter λ is introduced above Eq. (9). Then, we select separately the first k=5 and k=12 submatrices then perform (12) to (37) which yields a regular quasi-cyclic 585×2925 and 91×1091 parity-check matrix \(\mathbf {H}_{\text {qc}}^{(1)}\) both defined in (37). As a comparison, we also employ the procedure of [17, 18] construct the (2850,2280) and(1020,935) QC-LDPC code with the coding rate being 4/5 and 11/12, respectively.
Figure 6 shows the performances of these codes where it (a) represents the bit error rate (BER) and (b) depicts the frame error rate (FER). In these figures, the circle and box solid lines respectively represent the performances of the regular quasi-cyclic (2925,2341) and (1092,1001) LDPC codes. The circle and box dotted line corresponds to the performance of the (2850,2280) and 1020,935 QC-LDPC code generated by [17, 18].
Fig. 6
a The bit error rate and b frame error rate performances of four LDPC codes in example 2. In these figures, the circle and box solid lines separately represent the performances of the regular quasi-cyclic (2925,2341) and (1092,1001) LDPC codes with coding rate 4/5 and 11/12 generated by the procedure from (4) to (37). The circle and box dotted lines correspond to (2850,2280) and 1020,935 QC-LDPC codes which are also shown in [17, 18]. These 4 LDPC codes are all decoded with 50 iterations of the SPA (sum-product algorithm)
×
Example 3: Following the scheme of [9], we first construct a regular (4095,3367) EG-LDPC code over the field EG(2,26). Since we have 4095=c×b with c=13 and b=315, the procedure from (4) to (8) suggests that the parity-check matrix of the constructed (4095,3367) EG-LDPC code can be decomposed into 13 submatrices of size b×b shown in (8). Of 13 submatrices of size b×b, choose the parameter λ=4 to perform (9) to (11) where parameter λ is introduced above Eq. (9). Then, we select the first k=11 submatrices and perform (12) to (38) which yields a regular quasi-cyclic 630×6930 parity-check matrix \(\mathbf {H}_{\text {qc}}^{(2)}\) defined in (38). The null space of \(\mathbf {H}_{\text {qc}}^{(2)}\) renders a regular quasi-cyclic (6930,6301) LDPC code with the coding rate 10/11. As a comparison, we also employ the procedure of [16] to construct the (4095,3729) and (16383,14923) QC-LDPC code with the coding rates of both codes being 0.91.
Figure 7 shows the performances of these codes where it (a) represents the bit error rate (BER) and (b) depicts the frame error rate (FER). In these figures, the circle solid line represents the performance of the regular quasi-cyclic (6930,6301) LDPC code constructed from the procedure from (4) to (38). The box and diamond dotted lines respectively correspond to the performances of the (4095,3729) and (16383,14923) QC-LDPC codes yielded from [16].
Fig. 7
a The bit error rate and b frame error rate performances of three LDPC codes in example 2. In these figures, the circle solid line represents the performance of the regular quasi-cyclic (6930,6301) LDPC code with coding rate 10/11 generated by the procedure from (4) to (38). The box and diamond dotted lines separately correspond to the (4095,3729) and (16383,14923) QC-LDPC codes which are constructed from the procedure of [16]. These 3 LDPC codes are all decoded with 50 iterations of the SPA
×
Example 4: Following the scheme of [9], we first construct a regular (4095,3367) EG-LDPC code over the field EG(2,26). Since we have 4095=c×b with c=9 and b=455, the procedure from (4) to (8) suggests that the parity-check matrix of the constructed (4095,3367) EG-LDPC code can be decomposed into nine submatrices of size b×b shown in (8). Of the nine submatrices of size b×b, choose the parameter λ=4 to perform (9) to (11) where parameter λ is introduced above Eq. (9). Then, we select the first k=8 submatrices and perform the procedure from (12) to (38) which yields a regular quasi-cyclic 910×7280 parity-check matrix \(\mathbf {H}_{\text {qc}}^{(2)}\) defined in (38). The null space of this \(\mathbf {H}_{\text {qc}}^{(2)}\) renders a regular quasi-cyclic (7280,6371) LDPC code with the coding rate 7/8. As a comparison, we also employ the procedure of [16] to construct the (8176,7156) QC-LDPC code with the coding rate being 0.875.
Figure 8 shows the performances of these codes where it (a) represents the bit error rate (BER) and (b) depicts the frame error rate (FER). In these figures, the circle solid line represents the performance of the regular quasi-cyclic (7280,6371) LDPC code yielded from the procedure of (4)–(38). The box dotted line corresponds to the performance of the (8176,7156) QC-LDPC code (example 7 of [16]) generated by the scheme of [16].
Fig. 8
a The bit error rate and b frame error rate performance of two LDPC codes in example 3. In these figures, the circle solid line represents the performance of the regular quasi-cyclic (7280,6371) LDPC code with coding rate 7/8 generated by the procedure from (4) to (38). The box dotted line corresponds to the performance of the (8176,7156) QC-LDPC code constructed by the scheme of [16]. These 2 LDPC codes are both decoded with 50 iterations of the SPA
×
5 Conclusion
We have presented a scheme to construct the high-rate regular quasi-cyclic low-density parity-check QC-LDPC codes. The construction procedure is based on the FG-LDPC codes in which we first decompose the EG-LDPC code into a set of the block submatrices with each of them being cyclic. Then, we exploit the decomposed structure to produce an auxiliary matrix to facilitate us for identifying and eliminating 6-cycles of the block submatrices. Three regular QC-LDPC codes with code rates being 7/8, 10/11, and 11/12 of moderate code lengths are constructed in the simulation. The performances of these codes demonstrate the effectiveness of the proposed scheme.
Acknowledgements
We would like to thank the anonymous reviewers for their insightful comments on the paper, as these comments led us to an improvement of the work.
Funding
This work was supported by the National Natural Science Funds for the Nankai University (No. 61771262).
Availability of data and materials
Not applicable.
Competing interests
The authors declare that they have no competing interests.
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
Authors’ information
QM is a graduate student at the College of Electronic Information and Optical Engineering at Nankai University. His research interests include digital signal processing and error control coding.
JXZ is a professor at the College of Electronic Information and Optical Engineering at Nankai University. His research interests include biological signal processing, high-speed digital transmission algorithm, and error control coding.
WX is a professor at Tianjin Polytechnic University. Her research interests include digital signal processing and error control coding.
LL is serving as a communications engineer in IP Technology Research Department at Huawei Technologies Co., Ltd.
