Decoding method of LDPC codes based on partial average residual belief propagation

Abstract

A decoding method of low-density parity-check (LDPC) codes based on partial average residual belief propagation includes the following steps: S1: calculating a size of a cluster π in a protograph based on a code length m and a code rate of a target codeword; S2: pre-computing an edge residual r.sub.c.sub.i.sub..fwdarw.v.sub.j corresponding to each edge from a variable node to a check node in a check matrix H; S3: calculating, based on π, a partial average residual (PAR) value corresponding to each cluster in the check matrix H; S4: sorting m/π clusters in descending order of corresponding PAR values, and updating an edge with a largest edge residual in each cluster; S5: updating edge information m.sub.c.sub.i.sub..fwdarw.v.sub.i from a check node c.sub.i to a variable node v.sub.j, and then updating a log-likelihood ratio (LLR) value L(v.sub.j) of the variable node v.sub.j; and S6: after the updating, making a decoding decision.

Claims

1. A decoding method of low-density parity-check (LDPC) codes based on partial average residual belief propagation (PARBP) executed in a computer system, the computer system comprising a memory, a processor, and a computer program stored in the memory and executable on the processor, wherein the processor is operable to execute the computer program so as to implement the decoding method of LDPC codes based on PARBP, wherein the decoding method comprises the following steps: S1: calculating a cluster size π of a base matrix in a protograph based on a code length m and a code rate of a target codeword; S2: pre-computing an edge residual r.sub.c.sub.i.sub..fwdarw.v.sub.j corresponding to each edge from a variable node to a check node in a check matrix H, wherein the check matrix H is obtained by lifting the base matrix based on a structural characteristic of the protograph; S3: calculating, based on π, a partial average residual (PAR) value corresponding to each cluster of m/π clusters in the check matrix H; S4: sorting the m/π clusters in descending order of corresponding PAR values, and updating an edge with a largest edge residual in each cluster of the m/π clusters; S5: updating edge information m.sub.c.sub.i.sub..fwdarw.v.sub.j from a check node c.sub.i to a variable node v.sub.j, and then updating a log-likelihood ratio (LLR) value L(v.sub.j) of the variable node v.sub.j; and S6: after the updating, making a decoding decision; and if the decoding decision is successful or a maximum number of iterations is reached, ending the decoding; or if the decoding decision is unsuccessful and the maximum number of iterations is not reached, going to step S2 to continue decoding; wherein a formula for calculating the cluster size π in the protograph in step S1 is as follows:
π=m÷b.sub.v wherein b.sub.v is a number of variable nodes in the base matrix and m denotes the code length.

2. The decoding method according to claim 1, wherein a calculation formula of the edge residual r.sub.c.sub.i.sub..fwdarw.v.sub.j is as a r.sub.c.sub.i.sub..fwdarw.v.sub.j equation listed below:
r.sub.c.sub.i.sub..fwdarw.v.sub.j=∥m.sub.c.sub.i.sub..fwdarw.v.sub.j.sup.pre−m.sub.c.sub.i.sub..fwdarw.v.sub.j∥ wherein m.sub.c.sub.i.sub..fwdarw.v.sub.i represents the edge information from the check node c.sub.i to the variable node v.sub.j, and is expressed as a m.sub.c.sub.i.sub..fwdarw.v.sub.i equation listed below: $\begin{array}{cc}{m}_{c_{i.fwdarw.v_j}}=2{\tanh }^{-1}\left\{\underset{v_b\in N\left(c_i\right)\backslash v_j}{.Math.}\tanh \left(\frac{m_{v_{b.fwdarw.c_i}}}{2}\right)\right\}& \end{array}$ wherein m.sub.v.sub.b.sub..fwdarw.c.sub.i represents a posterior probability LLR value.

3. The decoding method according to claim 2, wherein a formula for calculating the PAR value corresponding to each cluster is as follows: $=\frac{\underset{k=0}{\overset{z_0}{\Sigma }}.Math.r_k.Math.}{z_0}$ wherein r.sub.k represents a residual value of a k-th edge.

4. The decoding method according to claim 3, wherein an expression for updating the LLR value L(v.sub.j) of the variable node v.sub.j is as follows:
L(v.sub.j)=Σ.sub.c.sub.a.sub.∈M(v.sub.j.sub.)m.sub.c.sub.a.sub..fwdarw.v.sub.j+C.sub.v.sub.j wherein c.sub.v.sub.j represents original channel information of the variable node v.sub.j, and M(v.sub.j) represents all check nodes connected to the variable node v.

5. The decoding method according to claim 4, wherein in step S6, specifically, if the decoding decision is unsuccessful and the maximum number of iterations is not reached, edge information from the variable node v.sub.j to a check node c.sub.a is updated according to the following formula:
m.sub.c.sub.a.sub..fwdarw.v.sub.j=Σ.sub.c.sub.a′.sub.∈M(v.sub.j.sub.)\c.sub.am.sub.c.sub.a′.sub..fwdarw.v.sub.jC.sub.v.sub.j wherein M(v.sub.j)\c.sub.a represents all the check nodes connected to the variable node v.sub.j except the check node c.sub.a; and edge information is pre-computed for all check nodes c.sub.a∈M(v.sub.j)\c.sub.i according to the m.sub.c.sub.i.sub..fwdarw.v.sub.i equation, and then an edge residual is calculated according to the r.sub.c.sub.i.sub..fwdarw.v.sub.i equation for a next update iteration process.

6. A non-transitory computer-readable storage medium storing a computer program, wherein when the computer program is executed by a processor, the steps of the decoding method according to claim 1 are implemented.

Description

BRIEF DESCRIPTION OF THE DRAWINGS

(1) FIG. 1 is a flowchart of a prior-art RBP algorithm.

(2) FIG. 2 is a Tanner graph after expansion of a protograph in Embodiment 1.

(3) FIG. 3 is a flowchart of a method according to Embodiment 1.

(4) FIG. 4 is a comparison diagram of bit error rates (BERs) of different decoding algorithms for LDPC codes on a fading channel.

(5) FIG. 5 is a comparison diagram of frame error rate (FER) performance of different decoding algorithms for LDPC codes on a fading channel.

(6) FIG. 6 is a comparison diagram of convergence performance of different decoding algorithms for LDPC codes at a fixed signal-to-noise ratio of 3.0 dB as the number of iterations increases.

DETAILED DESCRIPTION OF THE EMBODIMENTS

(7) The present disclosure will be described in further detail below in conjunction with the accompanying drawings and specific embodiments.

Embodiment 1

(8) In this embodiment, a corresponding check matrix can be obtained by lifting a base matrix based on a structural characteristic of a protograph. The following is an example:

(9) $\begin{array}{cc}H=\left[\begin{array}{cccc}{\pi }_{00}& {\pi }_{01}& 0& {\pi }_{03}\\ 0& {\pi }_{11}& {\pi }_{12}& 0\\ {\pi }_{20}& 0& {\pi }_{22}& 0\end{array}\right]& \left(2\right)\end{array}$
wherein π.sub.ij is a unit permutation matrix or its right-shift matrix, that is, a cluster.

(10) FIG. 2 shows a Tanner graph after expansion of the protograph in the above example, where v.sub.i is a variable node of the base matrix, and c.sub.j is a check node of the base matrix.

(11) Combined with the Tanner graph structural characteristics of the base matrix shown in FIG. 2, this embodiment provides a decoding method of LDPC codes based on partial average residual belief propagation (PARBP). As shown in FIG. 3, the method includes the following steps.

(12) S1: Calculate a size of a cluster π in a protograph based on a code length m and a code rate of a target codeword. A calculation formula is as follows:
π=m÷b.sub.v  (2)
wherein b.sub.v is a number of variable nodes in the base matrix.

(13) S2: Pre-compute an edge residual r.sub.c.sub.i.sub..fwdarw.v.sub.j corresponding to each edge from a variable node to a check node in a check matrix H.

(14) A calculation formula of the edge residual r.sub.c.sub.i.sub..fwdarw.v.sub.j is as follows:
r.sub.c.sub.i.sub..fwdarw.v.sub.j=∥m.sub.c.sub.i.sub..fwdarw.v.sub.j.sup.pre−m.sub.c.sub.i.sub..fwdarw.v.sub.j∥  (4)
wherein m.sub.c.sub.i.sub.=v.sub.i represents edge information from a check node c.sub.i to a variable node v.sub.j, and is expressed as follows:

(15) $\begin{array}{cc}{m}_{c_{i.fwdarw.v_j}}=2{\tanh }^{-1}\left\{\underset{v_b\in N\left(c_i\right)\backslash v_j}{.Math.}\tanh \left(\frac{m_{v_{b.fwdarw.c_i}}}{2}\right)\right\}& \left(5\right)\end{array}$
wherein m.sub.v.sub.b.sub.=c.sub.i represents a posterior probability LLR value.

(16) S3: Calculate, based on π, a PAR value corresponding to each cluster in the check matrix H.

(17) A formula for calculating the PAR value corresponding to each cluster is as follows:

(18) $\begin{array}{cc}=\frac{\underset{k=0}{\overset{z_0}{\Sigma }}.Math.r_k.Math.}{z_0}& \left(6\right)\end{array}$
wherein r.sub.k represents a residual value of a k-th edge.

(19) S4: Sort m/π clusters in descending order of corresponding PAR values, and update an edge with a largest edge residual in each cluster according to formula (5).

(20) S5: Update the edge information m.sub.c.sub.i.sub..fwdarw.v.sub.j from the check node c.sub.i to the variable node v.sub.j, and then update an LLR value L(v.sub.j) of the variable node v.sub.j.

(21) An expression for updating the LLR value L(v.sub.j) of the variable node v.sub.j is as follows:
L(v.sub.j)=Σ.sub.c.sub.a.sub.∈M(v.sub.j.sub.)m.sub.c.sub.a.sub..fwdarw.v.sub.j+C.sub.v.sub.j  (7)
wherein C.sub.v.sub.j represents original channel information of the variable node v.sub.j, and M(v.sub.j) represents all check nodes connected to the variable node v.sub.j.

(22) S6: After the updating, making a decoding decision; and if the decoding decision is successful or a maximum number of iterations is reached, end the decoding; or if the decoding decision is unsuccessful and the maximum number of iterations is not reached, go to step S2 to continue decoding.

(23) Specifically, if the decoding decision is unsuccessful and the maximum number of iterations is not reached, edge information from the variable node v.sub.j to a check node c.sub.a is updated according to formula (8):
m.sub.c.sub.a.sub..fwdarw.v.sub.j=Σ.sub.c.sub.a′.sub.∈M(v.sub.j.sub.)\c.sub.am.sub.c.sub.a′.sub..fwdarw.v.sub.j+c.sub.v.sub.j  (8)
wherein M(v.sub.j)\c.sub.a represents all the check nodes connected to the variable node v.sub.j except the check node c.sub.a.

(24) Edge information is pre-computed for all check nodes c.sub.a∈M(v.sub.j)\c.sub.i according to equation (5), and then an edge residual is calculated according to equation (4) for a next update iteration process.

(25) Compared with the conventional dynamic scheduling decoding algorithm, the method in this embodiment gives greater consideration to the structural characteristics of codewords. For single edge protograph LDPC codes, a degree distribution and ring structure of the check matrix H largely depend on a corresponding base matrix. In the base matrix, each cluster definitely has no ring structure. An update order is measured by using a cluster residual, and an edge with a largest edge residual is found in the cluster and updated, so as to ensure that each update can achieve highly reliable information and a largest amount of information, and minimize a range of finding the edges with the largest edge residual. In this way, the computing speed can be increased locally and the spatial complexity can be reduced, thereby greatly improving the convergence speed and avoiding the greediness in global decoding to the greatest extent.

(26) To better illustrate the advantages of the decoding method of LDPC codes proposed in this embodiment, performance comparison is performed between this method and the current mainstream dynamic scheduling decoding algorithms. To ensure performance comparison fairness, all simulations were performed under the same hardware configurations. A computer used for the simulation employs Intel® Core™ CPU i7-8700, a clock speed of 3.20 GHz, a memory of 16.0 GB, and a Windows 10 64-bit operating system. Specifically, randomly generated LDPC codes are transmitted on an additive white Gaussian noise (AWGN) channel, and a variety of different decoding algorithms including the algorithm in this embodiment are used for decoding, where the maximum number of iterations is set to 5, the maximum number of error frames is set to 100, a modulation coding scheme is set to binary phase shift keying (BPSK), and E.sub.b/N.sub.0 represents a normalized signal-to-noise ratio in decibels (dB).

(27) FIG. 4 and FIG. 5 are comparison diagrams of BERs and FER performance of different decoding algorithms for (576, 288) LDPC codes on a fading channel. In the figures, at a low signal-to-noise ratio, for example, from 1.0 dB to 1.6 dB, error correction performance curves of different dynamic scheduling decoding algorithms almost overlap, meaning that the error correction performance of different algorithms has little difference. However, the error correction performance of the algorithms changes significantly at a signal-to-noise ratio above 1.6 dB. At 1.6 dB or below, performance curves of a residual-decaying-based RBP (RD-RBP) algorithm, a Lazy Queue Residual Decoding (LQRD) algorithm, and a dynamic silent-variable-node-free scheduling (D-SVNFS) algorithm almost overlap, but their performance declines much faster than other algorithms. Starting from 1.8 dB, as the signal-to-noise ratio increases, the PARBP algorithm gradually shows its advantages over the RD-RBP algorithm, the D-SVNFS algorithm, and the LQRD algorithm, and becomes the algorithm with the optimal decoding performance. When the BER is 1.0×10.sup.−4, compared with the suboptimal D-SVNFS algorithm, the PARBP algorithm in this embodiment increases the performance by about 0.28 dB. When the BER is 1.0×10.sup.−3, compared with the suboptimal D-SVNFS algorithm, the PARBP algorithm in this embodiment increases the performance by about 0.22 dB.

(28) FIG. 6 is a comparison diagram of convergence performance of different decoding algorithms for (576, 288) LDPC codes at a fixed signal-to-noise ratio of 3.0 dB as the number of iterations increases. As shown in FIG. 5, the PARBP algorithm in this embodiment has a good convergence performance. Compared with other decoding algorithms, the PARBP algorithm achieves a nearly converged BER after the 5-th iteration. During the 5-th to 20-th iteration, the BER performance of other decoding algorithms are still converging, while the BER performance of the PARBP algorithm in this embodiment has converged as early as before the 10-th iteration. During the 5-th to 50-th iteration, the BER performance of the PARBP algorithm in this embodiment is significantly better than the BER performance of other algorithms, meaning that the PARBP algorithm in this embodiment has better convergence performance than other algorithms, especially in the speed of convergence.

Embodiment 2

(29) A computer system is provided, including a memory, a processor, and a computer program stored in the memory and executable on the processor, where the processor implements the following method steps when executing the computer program:

(30) S1: calculating the size π of a cluster of a base matrix in a protograph based on a code length m and a code rate of a target codeword:

(31) S2: pre-computing an edge residual r.sub.c.sub.i.sub..fwdarw.v.sub.j corresponding to each edge from a variable node to a check node in a check matrix H, where the check matrix H is obtained by lifting the base matrix based on a structural characteristic of the protograph;

(32) S3: calculating, based on π, a PAR value corresponding to each cluster in the check matrix H;

(33) S4: sorting m/π clusters in descending order of corresponding PAR values, and updating an edge with a largest edge residual in each cluster;

(34) S5: updating edge information m.sub.c.sub.i.sub..fwdarw.v.sub.j from a check node c.sub.i to a variable node v.sub.j, and then updating an LLR value L(v.sub.j) of the variable node v.sub.j; and

(35) S6: after the updating, making a decoding decision; and if the decoding decision is successful or a maximum number of iterations is reached, ending the decoding; or if the decoding decision is unsuccessful and the maximum number of iterations is not reached, going to step S2 to continue decoding.

Embodiment 3

(36) A computer-readable storage medium storing a computer program is provided, where the following method steps are implemented when the computer program is executed by a processor:

(37) S1: calculating the size π of a cluster of a base matrix in a protograph based on a code length m and a code rate of a target codeword:

(38) S2: pre-computing an edge residual r.sub.c.sub.i.sub..fwdarw.v.sub.j corresponding to each edge from a variable node to a check node in a check matrix H, where the check matrix H is obtained by lifting the base matrix based on a structural characteristic of the protograph;

(39) S3: calculating, based on π, a PAR value corresponding to each cluster in the check matrix H;

(40) S4: sorting m/π clusters in descending order of corresponding PAR values, and updating an edge with a largest edge residual in each cluster;

(41) S5: updating edge information m.sub.c.sub.i.sub..fwdarw.v.sub.j from a check node c.sub.i to a variable node v.sub.j, and then updating an LLR value L(v.sub.j) of the variable node v.sub.j; and

(42) S6: after the updating, making a decoding decision; and if the decoding decision is successful or a maximum number of iterations is reached, ending the decoding; or if the decoding decision is unsuccessful and the maximum number of iterations is not reached, going to step S2 to continue decoding.

(43) It is apparent that the above embodiments are merely intended to describe the present disclosure clearly, rather than to limit the implementations of the present disclosure. Any modification, equivalent substitution and improvement made within the spirit and principle of the present disclosure should fall within the protection scope of the claims of the present disclosure.