# Matching Pursuit Algorithm for Decoding of Binary LDPC Codes

Authors: Jianzhong Guo; Cong Cao; Dehui Shi; Jing Chen; Shuai Zhang; Xiaohu Huo; Dejin Kong; Jian Li; Yukang Tian; Min Guo
Journal: Wireless Communications and Mobile Computing
 (2021)

---

## Abstract

This paper presents a novel hard decision decoding algorithm for low-density parity-check (LDPC) codes, in which the stand matching pursuit (MP) is adapted for error pattern recovery from syndrome over GF(2). In this algorithm, the operation of inner product can be converted into XOR and accumulation, which makes the matching pursuit work with a high efficiency. In addition, the maximum iteration is theoretically explored in relation to sparsity and error probability according to the sparse theory. To evaluate the proposed algorithm, two MP-based decoding algorithms are simulated and compared over an AWGN channel, i.e., generic MP (GMP) and syndrome MP (SMP). Simulation results show that the GMP algorithm outperforms the SMP by 0.8 dB atBER=10−5.


---

## Body

## 1. Introduction

Low-density parity-check (LDPC) code is known for its capacity-approaching performance and belief propagation (BP) decoding algorithms [1–6]. However, this kind of soft decision algorithm has high implementation complexity, which may not be tolerated in some applications, for example, space optical communications. Hard decision decoding methods [1], on the other hand, are simple and have low complexity, but incur considerable performance loss. Therefore, researchers keep unrelenting efforts for good hard decision decoding algorithm, trying to offer a tradeoff among performance, complexity, and efficiency.Matching pursuit, a powerful scheme developed in compressed sensing [7], can recover sparse pattern (position of nonzero element) with great efficiency and accuracy in real or complex field. Therefore, literature [8] introduced a MP-based algorithm to decode hard decision LDPC code and called it the syndrome matching pursuit (SMP).In standard MP algorithm, the inner product between residual and the dictionary acts as the measure of matching. An atom, or a column of the dictionary, is said to be matching if it maximizes the inner product. Unfortunately, in binary LDPC decoding, as there tends to be more than one atom (a column of the parity-check matrix) that generates the maximum inner product between residual and the dictionary (parity-check matrix), it is very difficult to recognize which is the matching one. If a wrong atom is chosen, mismatching and error will occur. Moreover, mismatching can propagate during iteration. In view of these facts, we propose an improvement on SMP and refer it as the generic MP (GMP) algorithm, which can partly reduce the mismatching and error bits.Hard decision decoding algorithms, including the MP-based algorithms, have a lot of applications in free space optical communications, deep space optical communications, and underwater wireless optical communications. In these long distance and high rate systems, in order to reduce complexity, it is preferable to adopt simple modulating and demodulating scheme, for example, OOK with hard decision demodulation. Considering for compatibility, hard decision coding scheme is adopted [9]. So, in this paper, we investigate MP-based decoding algorithm for LDPC codes and explore the possibility of applying them to these communications.The rest of this paper is organized as follows. In Section2, there is a brief overview of compressed sensing model and linear block codes. Section 3 presents the MP-based decoding algorithm for LDPC codes. Simulations are conducted in Section 4, and some comparisons are made therein.


## 2. Compressed Sensing and Linear Block Codes

In compressed sensing, an important process is to determine the locations of the nonzero components during the course of reconstruction, and this is known as support recovery or sparsity pattern recovery, which has applications in signal processing, signal denoising, digital communications, and so on. Similarly, in linear block code, a crucial part is to determine the locations of error bits during the course of decoding, and this process is referred to as error pattern recovery.


### 2.1. Sparsity Pattern Recovery and MP Algorithm

A common problem in compressed sensing is to estimate an unknown sparse vectorx∈ℝn from linear measurements of the following form [10, 11].
(1)y=Hx+N,where matrix H∈ℝm×n is a given measurement matrix or redundant dictionary and N is an additive noise vector. The vector x∈ℝn is said to be sparse in that it is known a priori to have a relatively small number of nonzero components, but the locations and values of those components are not known and must be detected as part of signal estimation. To determine the locations of the nonzero components is known as sparsity pattern recovery or support recovery as mentioned above. As for a κ sparse signal, the maximum number of nonzero components isκ.The problem to find sparsity pattern is NP-hard, but MP algorithm and its variants can be effective under certain conditions. For the convenience of reading, the standard MP algorithm in sparsity pattern recovery is described as follows (Algorithm1), which involves four important parameters: received signal y, sparsity κ, tolerance ε, and dictionary H.Algorithm 1: Standard MP algorithm in sparsity pattern recovery.
Input: Received signaly, sparsity κ, tolerance ε and dictionary H=H1,H2,⋯,Hω,⋯,HnInitialization: Set the residualr0=y, sparsity pattern Λ=∅ (null)Step 1: At iterationi (i≥1), select the atom that maximizes the absolute value of the inner product between residual ri−1 and dictionary H, with its index λi∈argmaxri−1,HωStep 2: Update the sparsity patternΛ=Λ∪λiStep 3: Calculate and update residualri=ri−1‐ri−1,HλiHλiStep 4: Leti=i+1 and go to Step1; stop if ri2<ε or κ atoms are all chosenOutput: Sparsity patternΛ, residual ri


### 2.2. Linear Measurement in Linear Block Codes

Given ann,k linear block code ℂ defined as the null space of a m×n parity-check matrix H=H1,H2,⋯,Hω,⋯,Hn, equation HcT=0 holds for any codeword c∈ℂ.Letc^T=c^0,c^1,⋯,c^n−1 be a received version of cT, and eT=e0,e1,⋯,en−1 be the corresponding error pattern, where ei equals 1 or 0 indicating if there is an error or not, we have c^=c+e. Then, the syndrome can be expressed as the form of linear measurements.
(2)s=He.Clearly, Equation (2) is a noise-free version of Equation (1), in which the parity-check matrix is equivalent to the measurement matrix or dictionary, and every column of the parity-check matrix is an atom. Usually, error pattern e is such sparse a vector as sparsity ratio (equals to bit error ratio) below 0.1 that it can be solved by some algorithms if the condition is satisfied.


## 2.1. Sparsity Pattern Recovery and MP Algorithm

A common problem in compressed sensing is to estimate an unknown sparse vectorx∈ℝn from linear measurements of the following form [10, 11].
(1)y=Hx+N,where matrix H∈ℝm×n is a given measurement matrix or redundant dictionary and N is an additive noise vector. The vector x∈ℝn is said to be sparse in that it is known a priori to have a relatively small number of nonzero components, but the locations and values of those components are not known and must be detected as part of signal estimation. To determine the locations of the nonzero components is known as sparsity pattern recovery or support recovery as mentioned above. As for a κ sparse signal, the maximum number of nonzero components isκ.The problem to find sparsity pattern is NP-hard, but MP algorithm and its variants can be effective under certain conditions. For the convenience of reading, the standard MP algorithm in sparsity pattern recovery is described as follows (Algorithm1), which involves four important parameters: received signal y, sparsity κ, tolerance ε, and dictionary H.Algorithm 1: Standard MP algorithm in sparsity pattern recovery.
Input: Received signaly, sparsity κ, tolerance ε and dictionary H=H1,H2,⋯,Hω,⋯,HnInitialization: Set the residualr0=y, sparsity pattern Λ=∅ (null)Step 1: At iterationi (i≥1), select the atom that maximizes the absolute value of the inner product between residual ri−1 and dictionary H, with its index λi∈argmaxri−1,HωStep 2: Update the sparsity patternΛ=Λ∪λiStep 3: Calculate and update residualri=ri−1‐ri−1,HλiHλiStep 4: Leti=i+1 and go to Step1; stop if ri2<ε or κ atoms are all chosenOutput: Sparsity patternΛ, residual ri


## 2.2. Linear Measurement in Linear Block Codes

Given ann,k linear block code ℂ defined as the null space of a m×n parity-check matrix H=H1,H2,⋯,Hω,⋯,Hn, equation HcT=0 holds for any codeword c∈ℂ.Letc^T=c^0,c^1,⋯,c^n−1 be a received version of cT, and eT=e0,e1,⋯,en−1 be the corresponding error pattern, where ei equals 1 or 0 indicating if there is an error or not, we have c^=c+e. Then, the syndrome can be expressed as the form of linear measurements.
(2)s=He.Clearly, Equation (2) is a noise-free version of Equation (1), in which the parity-check matrix is equivalent to the measurement matrix or dictionary, and every column of the parity-check matrix is an atom. Usually, error pattern e is such sparse a vector as sparsity ratio (equals to bit error ratio) below 0.1 that it can be solved by some algorithms if the condition is satisfied.


## 3. Decoding Binary LDPC Codes with MP Algorithm

The restricted isometry property (RIP) [12] can guarantee the accuracy of reconstruction in compressed sensing. However, for most linear block codes, it is very difficult to determine whether the parity-check matrix meets the RIP condition. Fortunately, there are some relevant literatures that can help us to address this problem [1, 13].


### 3.1. Parity-Check Matrix and RIP

LDPC code is a special kind of linear block code in which the syndromes, parity-check matrix H, and error pattern e are constrained by Equation (2). If the RIP condition is satisfied, the error pattern e can be recovered from syndrome s by MP-based algorithm.In LDPC code, the parity-check matrix has the following properties: (1) the number of “ones” in common between any two columns is no greater than 1; (2) the number of ones in each row or column is small compared to the parametersm and n; (3) the locations of ones have good random characteristics [1].Property (3) suggests that the parity-check matrixH satisfies the RIP condition if error pattern e is sparse enough, and this guarantees the accuracy of recovery of error pattern when some algorithm is employed. Furthermore, literature [13] proves that a good parity-check matrix for LDPC codes is a good measurement matrix for compressed sensing and can preserve enough information for recovery of sparse signal. This means the syndrome contains enough information of error pattern so that it can be recovered by some algorithms, for example, the MP-based algorithm.


### 3.2. Error Pattern Recovery with GMP Algorithm

In literature [6], the syndrome MP (SMP) algorithm is introduced to decode hard decision LDPC codes, but it is liable to mismatching. Therefore, a generic MP (GMP) algorithm is developed from the standard MP algorithm to recover the error pattern. In both algorithms, all addition of vectors works over GF(2), with the exception of inner product, which is computed over the integers. For the convenience of analysis and comparing, the GMP algorithm is described as the following Algorithm 2, in which three important parameters are involved: the received codeword c^, maximum errors κ, and parity-check matrix H.Algorithm 2: GMP algorithm in error pattern recovery for LDPC codes decoding.
Input: Received codewordc^, maximum errors κ, and parity-check matrix H=H1,H2,⋯,Hω,⋯,HnInitialization: Set the error patterne=0, error location Λ=∅,calculate syndrome s=Hc^ (mod 2), and set the initial residual r0=sStep 1: At iterationi (i≥1), select the column that maximizes the inner product between residual ri−1 and parity-check matrix H, with the index λi∈argmaxri−1,HωStep 2: Update the error patterneλi=1, error location Λ=Λ∪λiStep 3: Calculate residual and updateri=ri−1⊕Hλi (mod 2)Step 4: Leti=i+1 and go to Step1; stop if residual ri=0 or κ error locations are foundOutput: Error patterne, error location Λ, and residual riIn Algorithm2, the inner product in step 1 is computed over the integers, i.e.,
(3)ri−1,hω=r0i−1h0,ω+r1i−1h1,ω+⋯+rm−1i−1hm−1,ω.The matching atom can be found via its indexλi by Equation (4) from Algorithm 2, i.e.,
(4)λi∈argmaxri−1,Hω.The GMP algorithm differs from the SMP in one point that the SMP algorithm only chooses the atom that has never been chosen previously during the course of matching, as expressed in Equation (5).
(5)λi∈argmaxri−1,Hω:ω∉Λ.However, in the GMP algorithm, this limitation does not exist. The atom that has been chosen previously can be selected again, as described in Equation (4).If error patterne is recovered, the output codeword c~ can be obtained by the following equation.
(6)c~=c^+e.


### 3.3. Sparsity and Maximum Iterations

One fundamental in compressed sensing is that the signal should be sparse. Actually, the error patterne is a sparse vector under normal conditions. For a BPSK system without channel coding, the error probability Pe can be theoretically determined with relation to signal-to-noise ratio (SNR) by the following equation.
(7)Pe=erfcSNR2,where erfc· represents the complementary error function and SNR is the signal-to-noise ratio. For example, when SNR=1, the error probability or sparse ratio is below 0.08, this means that under normal conditions, the error pattern e is so sparse that it can be recovered by MP algorithm.For an,k linear block code, the average errors for each block can be approximated by the following equation.
(8)e0=nPe,where ⋅0 represents the zero norm. Therefore, the sparsity, which is equal to the number of errors in error pattern e, is very small.In order to recover the error patterne, the maximum iterations should cover all the errors. Therefore, the maximum iteration, which is equal to the maximum errors κ, should be greater than the average errors, that is,
(9)κ>e0.


## 3.1. Parity-Check Matrix and RIP

LDPC code is a special kind of linear block code in which the syndromes, parity-check matrix H, and error pattern e are constrained by Equation (2). If the RIP condition is satisfied, the error pattern e can be recovered from syndrome s by MP-based algorithm.In LDPC code, the parity-check matrix has the following properties: (1) the number of “ones” in common between any two columns is no greater than 1; (2) the number of ones in each row or column is small compared to the parametersm and n; (3) the locations of ones have good random characteristics [1].Property (3) suggests that the parity-check matrixH satisfies the RIP condition if error pattern e is sparse enough, and this guarantees the accuracy of recovery of error pattern when some algorithm is employed. Furthermore, literature [13] proves that a good parity-check matrix for LDPC codes is a good measurement matrix for compressed sensing and can preserve enough information for recovery of sparse signal. This means the syndrome contains enough information of error pattern so that it can be recovered by some algorithms, for example, the MP-based algorithm.


## 3.2. Error Pattern Recovery with GMP Algorithm

In literature [6], the syndrome MP (SMP) algorithm is introduced to decode hard decision LDPC codes, but it is liable to mismatching. Therefore, a generic MP (GMP) algorithm is developed from the standard MP algorithm to recover the error pattern. In both algorithms, all addition of vectors works over GF(2), with the exception of inner product, which is computed over the integers. For the convenience of analysis and comparing, the GMP algorithm is described as the following Algorithm 2, in which three important parameters are involved: the received codeword c^, maximum errors κ, and parity-check matrix H.Algorithm 2: GMP algorithm in error pattern recovery for LDPC codes decoding.
Input: Received codewordc^, maximum errors κ, and parity-check matrix H=H1,H2,⋯,Hω,⋯,HnInitialization: Set the error patterne=0, error location Λ=∅,calculate syndrome s=Hc^ (mod 2), and set the initial residual r0=sStep 1: At iterationi (i≥1), select the column that maximizes the inner product between residual ri−1 and parity-check matrix H, with the index λi∈argmaxri−1,HωStep 2: Update the error patterneλi=1, error location Λ=Λ∪λiStep 3: Calculate residual and updateri=ri−1⊕Hλi (mod 2)Step 4: Leti=i+1 and go to Step1; stop if residual ri=0 or κ error locations are foundOutput: Error patterne, error location Λ, and residual riIn Algorithm2, the inner product in step 1 is computed over the integers, i.e.,
(3)ri−1,hω=r0i−1h0,ω+r1i−1h1,ω+⋯+rm−1i−1hm−1,ω.The matching atom can be found via its indexλi by Equation (4) from Algorithm 2, i.e.,
(4)λi∈argmaxri−1,Hω.The GMP algorithm differs from the SMP in one point that the SMP algorithm only chooses the atom that has never been chosen previously during the course of matching, as expressed in Equation (5).
(5)λi∈argmaxri−1,Hω:ω∉Λ.However, in the GMP algorithm, this limitation does not exist. The atom that has been chosen previously can be selected again, as described in Equation (4).If error patterne is recovered, the output codeword c~ can be obtained by the following equation.
(6)c~=c^+e.


## 3.3. Sparsity and Maximum Iterations

One fundamental in compressed sensing is that the signal should be sparse. Actually, the error patterne is a sparse vector under normal conditions. For a BPSK system without channel coding, the error probability Pe can be theoretically determined with relation to signal-to-noise ratio (SNR) by the following equation.
(7)Pe=erfcSNR2,where erfc· represents the complementary error function and SNR is the signal-to-noise ratio. For example, when SNR=1, the error probability or sparse ratio is below 0.08, this means that under normal conditions, the error pattern e is so sparse that it can be recovered by MP algorithm.For an,k linear block code, the average errors for each block can be approximated by the following equation.
(8)e0=nPe,where ⋅0 represents the zero norm. Therefore, the sparsity, which is equal to the number of errors in error pattern e, is very small.In order to recover the error patterne, the maximum iterations should cover all the errors. Therefore, the maximum iteration, which is equal to the maximum errors κ, should be greater than the average errors, that is,
(9)κ>e0.


## 4. Simulation Results and Performance Analysis

In this section, simulation is conducted via BPSK modulation over an AWGN channel to test the validity of MP-based algorithm in decoding of LDPC codes. For simplicity, a short irregular LDPC code—(128, 64) PEG LDPC code—is employed, in which the column weight is 3, and the row weight is 5, 6, and 7 unequally.


### 4.1. Iterations and BER Performance

Equations (7), (8), and (9) reveal the relation between sparsity and number of errors. In order to recover the error pattern e, the maximum iterations should cover all the errors. For a (128, 64) LDPC code, the iterations should be above 10 according to Equation (9). Therefore, the maximum iterations are set to be 5, 10, 15, and 20, respectively. The results of simulation of the GMP algorithm described by Algorithm 2 are shown in Figure 1.Figure 1
BER performance of GMP algorithm with different iterations.From Figure1, we can see that the BER performance goes better and better as the maximum iterations increase, but the gap becomes smaller and smaller. When iterations are below 10, the performance increases obviously. However, as the iterations are above 10, the performance increases slowly. When the maximum number equals 15 and 20, respectively, the BER curves approach the same.


### 4.2. Comparison of BER Performance

In order to make a comparison, we conduct a simulation of SMP and GMP algorithm under the same conditions, and the log-BP algorithm is also simulated for reference. For the three decoding schemes, the maximum iterations are all 20, and the simulation results are shown in Figure2. From the figure, we can see that though the difference between GMP and SMP is slight, the gap of the performance is obvious. At BER=10−5, the GMP algorithm has a gain of 0.8 dB over the SMP algorithm.Figure 2
Comparison of BER performance between GMP and SMP algorithms.


### 4.3. Comparison of Computational Complexity

There are two kinds of decoding methods for LDPC codes: the hard decision decoding method and the soft decision decoding method. The hard decision decoding method, such as bit flipping (BF) algorithm and MP-based algorithm, simply involves in binary addition and multiplication, and multiplication can be converted into XOR and accumulation in practice. The soft decision decoding method, such as log-BP algorithm, operates in real number field; besides addition and subtraction, it involves in multiplication, division, exponent, and logarithm operations. In hardware implementation, the last four types of operations, especially exponent and logarithm, are much more complex than XOR. Therefore, the soft decision decoding method has a much higher computational complexity than the hard decision method.As hard decision decoding method, BF algorithm has a complexity which is comparable to that of MP-based algorithm. To be more specific, the former is a little more complex than the latter, because the former needs parity check in each iteration after bit flipping, but the latter algorithm does not need. As for the MP-based algorithm, the SMP algorithm is a little more complex than GMP, because the latter can reduce mismatching and converges faster.


## 4.1. Iterations and BER Performance

Equations (7), (8), and (9) reveal the relation between sparsity and number of errors. In order to recover the error pattern e, the maximum iterations should cover all the errors. For a (128, 64) LDPC code, the iterations should be above 10 according to Equation (9). Therefore, the maximum iterations are set to be 5, 10, 15, and 20, respectively. The results of simulation of the GMP algorithm described by Algorithm 2 are shown in Figure 1.Figure 1
BER performance of GMP algorithm with different iterations.From Figure1, we can see that the BER performance goes better and better as the maximum iterations increase, but the gap becomes smaller and smaller. When iterations are below 10, the performance increases obviously. However, as the iterations are above 10, the performance increases slowly. When the maximum number equals 15 and 20, respectively, the BER curves approach the same.


## 4.2. Comparison of BER Performance

In order to make a comparison, we conduct a simulation of SMP and GMP algorithm under the same conditions, and the log-BP algorithm is also simulated for reference. For the three decoding schemes, the maximum iterations are all 20, and the simulation results are shown in Figure2. From the figure, we can see that though the difference between GMP and SMP is slight, the gap of the performance is obvious. At BER=10−5, the GMP algorithm has a gain of 0.8 dB over the SMP algorithm.Figure 2
Comparison of BER performance between GMP and SMP algorithms.


## 4.3. Comparison of Computational Complexity

There are two kinds of decoding methods for LDPC codes: the hard decision decoding method and the soft decision decoding method. The hard decision decoding method, such as bit flipping (BF) algorithm and MP-based algorithm, simply involves in binary addition and multiplication, and multiplication can be converted into XOR and accumulation in practice. The soft decision decoding method, such as log-BP algorithm, operates in real number field; besides addition and subtraction, it involves in multiplication, division, exponent, and logarithm operations. In hardware implementation, the last four types of operations, especially exponent and logarithm, are much more complex than XOR. Therefore, the soft decision decoding method has a much higher computational complexity than the hard decision method.As hard decision decoding method, BF algorithm has a complexity which is comparable to that of MP-based algorithm. To be more specific, the former is a little more complex than the latter, because the former needs parity check in each iteration after bit flipping, but the latter algorithm does not need. As for the MP-based algorithm, the SMP algorithm is a little more complex than GMP, because the latter can reduce mismatching and converges faster.


## 5. Conclusions

In this paper, matching pursuit algorithms have been investigated to decode hard decision LDPC codes. Based on the compressed sensing theory, the number of maximum iterations in relation to sparsity and error probability was derived theoretically, which could provide a guide in practice. To evaluate the effectiveness of the two algorithms in LDPC codes decoding, performance simulations were conducted with GMP and SMP. Simulation results show that the GMP algorithm outperforms SMP by 0.8 dB atBER=10−5, and both methods can decode efficiently. In addition, simulation results show that the MP-based algorithms work effectively on regular LDPC codes, as well as irregular LDPC codes with uniform column weight. However, as for the irregular LDPC code with different column weights, the MP-based algorithms do not perform well.



---

*Source: 9980774-2021-10-31.xml*