1. Introduction
Linear programming (LP) decoding of low-density parity check (LDPC) codes was first proposed by Feldman in [1]. Limited by its high decoding complexity, LP decoding algorithm was not widely used in the early days. Recently, inspired by the idea of the alternating direction multiplier method (ADMM) [2], Barman et al. proposed a linear programming decoding algorithm based on the alternating direction multiplier method (ADMM-LP) [3], reducing the complexity of LP decoding algorithm to a certain extent. However, compared with the belief propagation (BP) decoding algorithm [4], ADMM-LP has poor decoding performance at low signal-to-noise-ratios (SNRs). To enhance its decoding performance, Liu et al. proposed an ADMM decoding algorithm using a weighted penalty function [5]. References [6] and [7] introduced deep learning into ADMM-based decoder and provided a new idea for ADMM decoding. Despite these improvements, a major drawback of ADMM-LP decoding is that its decoding complexity is still high.
Simplifying the Euclidean projection onto check polytope is an efficient way to reduce the computational complexity of ADMM-LP. Zhang et al. proposed a simplification of the Euclidean projection using cut search algorithm (CSA) in [8]. G. Zhang et al. [9] transformed the complex projection onto a check polytope to projection onto a simplex. Gensheimer et al. presented a reduced-complexity projection algorithm relying on the findings that some components of the input can be fixed to 0 or 1, while the remaining components have to be projected onto a smaller-dimensional even or odd parity polytope [10].
Although the above exact projection algorithms have reduced the decoding complexity of ADMM-LP, there is still a lot of room for improvement. Recently, approximate projection algorithms with lower complexity have been proposed by scholars. Xia et al. proposed the even-vertex projection algorithm (EVA) [11], [12] and the line-segment algorithm (LSA) [13], [14], respectively projecting onto the closest even-vertex and the line-segment consisting of the two closest vertices of the polytope. Asadzadeh et al. proposed the sparse affine projection algorithm (SAPA) [15], projecting onto the affine hull of a small number of vertices of the polytope. However, experiments show that these approximate algorithms lose their accuracy in low-iteration regime.
In this work, by replacing line segment projection with projection onto a triangle consisting of the three even-vertices closest to the vector to be projected, we will propose a fast and highly accurate projection algorithm based on LSA. Simulation results show that compared with LSA, the proposed algorithm can improve the FER performance by 0.5 dB as well as save average number of iterations by 11.0\(\%\), and compared with SAPA, the proposed algorithm can improve the FER performance by 0.2 dB as well as save average number of iterations by 4.3\(\%\).
2. Preliminaries
Consider an LDPC code \(C\) defined by an \(m\times n\) parity check matrix H. Let \(i\in I=\{1,2,3\ldots,n\}\) and \(j\in J=\{1,2,3\ldots,m\}\) be the indexes of the columns and rows of check matrix H, respectively. The degree of variable node \({{v}_{i}}\) (check node \({{c}_{j}}\)) is denoted by \({{d}_{i}}\) (\({{d}_{j}}\)). Let \({{N}_{v}}(i)\) (\({{N}_{c}}(j)\)) denotes the set of check nodes (variable nodes) adjacent to variable node \({{v}_{i}}\) (check node \({{c}_{j}}\)).
Suppose a codeword \(\boldsymbol x=\{{{x}_{i}}\in \{0,1\}|i\in I\}\) is transmitted over memoryless binary input output-symmetric (MBIOS) channel and \(\boldsymbol y=\{{{y}_{i}}|i\in I\}\) is the received vector. The LP decoding model based on ADMM with L2 penalty is described as follows:
| \[\begin{equation*} \begin{aligned} &\underset{\boldsymbol x}{\mathop{\min }}\,{{\boldsymbol \gamma }^{T}}\boldsymbol x-\alpha \left\| \boldsymbol x-0.5 \right\|_{2}^{2}\\ &s.t.\ {{\boldsymbol P}_{j}}x={{\boldsymbol z}_{j}},{{\boldsymbol z}_{j}}\in {{P}_{{{d}_{j}}}},\forall j\in J \end{aligned} \tag{1} \end{equation*}\] |
where \(\boldsymbol \gamma =\{{{\gamma }_{i}}|i\in I\}\) represents the log-likelihood ratios (LLRs) vector, the \({i}\)-th entry of which is \({{\gamma }_{i}}=\log (\frac{\Pr \left( {{y}_{i}}|{{x}_{i}}=0 \right)}{\Pr \left( {{y}_{i}}|{{x}_{i}}=1 \right)})\). \({{\boldsymbol P}_{j}}\) is a \({{d}_{j}}\times n\) transfer matrix and \({{P}_{{{d}_{j}}}}\) is the convex hull of all permutations of a length-\({{d}_{j}}\) binary vector with even number of 1s, and it is called the check polytope. \({{\boldsymbol z}_{j}}\) is the auxiliary vector.
The augmented Lagrangian function corresponding to formulation (1) and the update rule for \(\boldsymbol z\) are as follows:
| \[\begin{eqnarray*} &&\!\!\!\!\!\hskip-7mm \begin{aligned} & L_\mu (\boldsymbol{x}, \boldsymbol{z}, \boldsymbol{\lambda}) = \boldsymbol{\gamma}^T \boldsymbol{x} \!+\! \sum\limits_{j\in J}\!{\boldsymbol{\lambda}_j}^T (\boldsymbol{P}_j\boldsymbol{x}\!-\!\boldsymbol{z}_j) \!+\! \frac{\mu}{2}\!\sum\limits_{j\in J}\! \left\|\boldsymbol{P}_j\boldsymbol{x}\!-\!\boldsymbol{z}_j\right\|_2^2\\ & \hphantom{{{L}_{\mu }} (\boldsymbol x , \boldsymbol z , \boldsymbol \lambda ) = } - \alpha \left\| \boldsymbol x-0.5 \right\|_{2}^{2}\\ \end{aligned} \tag{2} \\ &&\!\!\!\!\! {{\boldsymbol z}_{j}}^{k+1}=\prod\nolimits_{{{P}_{{{d}_{j}}}}}{({{\boldsymbol P}_{j}}{{\boldsymbol x}^{k+1}}+\boldsymbol \lambda _{j}^{k}/\mu )} \tag{3} \end{eqnarray*}\] |
where \({{\boldsymbol \lambda }_{j}}\in {{\mathbb{R}}^{{{d}_{j}}}}\) denotes the Lagrangian multiplier, \(\mu >0\) is a positive penalty parameter, \(\alpha >0\) is a positive penalty parameter of L2 penalty, \(k\ge 0\) is the iteration number, and \(\prod\nolimits_{{{P}_{{{d}_{j}}}}}{{}}\)is the check polytope projection operation.
3. ADMM-LP Decoding Algorithm with Triangle Projection Algorithm
Recently, a large number of scholars have carried out research on the Euclidean projection onto check polytope, proposing various exact projection algorithms and approximate projection algorithms and improving the decoding performance of ADMM-LP. In this section, we will propose TPA inspired by LSA and illustrate it in detail.
3.1 LSA
Even-vertex algorithm (EVA) is the simplest way to replace Euclidean projection with approximate projection but has poor FER performance. To improve this defect, Xia et al. proposed LSA, replacing check polytope projection with line segment projection. For a given vector \(\boldsymbol v\), the odd-vertex closest to \(\boldsymbol v\) can be solved in accordance with the indicator vector \({{\boldsymbol \theta }_{V}}\) (referred in [8, Algorithm 2]), which can be calculated as Algorithm 1, line 2-6, as follows:
| \[\begin{equation*} {{O}_{i}}=\begin{cases} 1,&{{\theta }_{V,i}}=1 \\ 0,&{{\theta }_{V,i}}=-1 \\ \end{cases} \tag{4} \end{equation*}\] |
After identifying the odd-vertex closest to \(\boldsymbol v\), the two even-vertexes closest to \(\boldsymbol v\) can be obtained as follows:
| \[\begin{equation*} \begin{aligned} {{\boldsymbol A}_{{}}}=\begin{cases} {{O}_{i}},&i\ne p \\ 1-{{O}_{i}},&i=p \end{cases}\\ \boldsymbol B=\begin{cases} {{O}_{i}},&i\ne q \\ 1-{{O}_{i}},&i=q \\ \end{cases} \end{aligned} \tag{5} \end{equation*}\] |
where \(p\) and \(q\) are the indexes of the two elements closest to 0.5 in the vector \(\boldsymbol v\).
We can calculate the projection of \(\boldsymbol v\) onto the line segment \({{L}_{\boldsymbol {AB}}}\) by Algorithm 2 in [13].
3.2 TPA
Simulation results show that when combined with over-relaxation method, LSA performs poorly in FER in low-iteration regime. This is because that as an approximate projection algorithm, the result of LSA is far away from the accurate projection, and LSA requires more iterations to converge.
Asadzadeh et al. proposed SAPA, projecting onto the affine hull of a small number of vertices of the polytope. Although SAPA has a similar FER performance as that of CSA in high-iteration regime, it loses its accuracy in low-iteration regime as the projection result of SAPA may not be on the check polytope, creating some errors.
In order to make the projection more accurate, we try to replace the line segment projection with the triangle projection. Similar to LSA, to determine a triangle only needs to determine its three vertices, that is, to solve the three even-vertices on the check polytope that are closest to \(\boldsymbol v\). They can be obtained as follows:
| \[\begin{equation*} \begin{aligned} {{\boldsymbol A}_{{}}}=\begin{cases} {{O}_{i}},&i\ne p \\ 1-{{O}_{i}},&i=p \end{cases}\\ \boldsymbol B=\begin{cases} {{O}_{i}},&i\ne q \\ 1-{{O}_{i}},&i=q \\ \end{cases}\\ \boldsymbol C=\begin{cases} {{O}_{i}},&i\ne r \\ 1-{{O}_{i}},&i=r \\ \end{cases} \end{aligned} \tag{6} \end{equation*}\] |
where \(p\), \(q\), and \(r\) are the indexes of the three elements closest to 0.5 in the vector \(\boldsymbol v\). Since \(\boldsymbol A\), \(\boldsymbol B\) and \(\boldsymbol C\) are only different at \(p\), \(q\), and \(r\), the projection on the triangle \(ABC\) can be considered as the projection in 3D space.
The specific process of TPA algorithm is shown in Algorithm 1. Above all, initialize the indicator vector \({{\boldsymbol{\theta }}_{V}}\). Then determine the odd-vertex closest to \(\boldsymbol v\) and subsequently obtain the three even-vertices. Afterward we refer to the CSA algorithm in [8] to solve the projection coefficient \(\eta\). Finally, we obtain the elements at \(p\), \(q\), \(r\) in Algorithm 1, line 16 and get the projection \(\boldsymbol z\).
 |
The solution of \(\eta\) is shown in Algorithm 2.
 |
Table 1 describes the number of comparisons, additions and multiplications for CSA, LSA, SAPA and the proposed TPA, respectively. The number of comparisons, additions and multiplications for CSA, LSA and SAPA can be found in the references [13] and [15]. There, \(d\) and \(\lambda\) respectively denote the dimension of the polytope, and the number of elements in set \(T\) (referred in [8, Algorithm 3, Line 1]). In conclusion, the complexity of LSA, SAPA, and TPA are all \(O(d)\), and the complexity of the proposed TPA is slightly higher than that of LSA and SAPA while much lower than that of CSA.
Table 1 Number of operations required by four projection algorithms for \(P_{d_j}\). |
 |
It should be noted that the dimension of \({\boldsymbol v}^{'}\) in Algorithms 2 is 3, and the sorting elements in \(T=\left\{ {{t}_{i}} \right\}\) only requires 3 comparisons at most. Additionally, the loop operation introduced by Algorithm 2 can be expanded into three separate computational processes, that is, there is no loop in the proposed algorithm and the parallelization capability of the proposed algorithm is almost the same with LSA.
4. Simulation Results
In our simulations, all the algorithms are implemented in C programming language and run on a computer with Intel Core i9 CPU (10 cores and 3.7 GHz), 64GB main memory. The additive white Gaussian noise (AWGN) channel with binary phase shift keying (BPSK) modulation is supposed. We consider four LDPC codes with different rates: the regular (1920, 640) rate-1/3 Gallager code \({{C}_{1}}\), the regular (2640, 1320) rate-1/2 Margulis code \({{C}_{2}}\), the irregular (576, 432) rate-3/4 code \({{C}_{3}}\) from IEEE 802.16e standard [16], and 5G-NR LDPC code \({{C}_{4}}\) with information length \(K=320\) and rate \(R=8/9\). The check node degrees of \({{C}_{1}}\)-\({{C}_{4}}\) are 4, 6, {14,15}, and {3, 19}, respectively.
The ADMM-LP decoding algorithm with L2 penalty combined with over-relaxation technique is adopted in the simulations, and the relaxation coefficient is 1.9. Considering that CSA is an exact projection algorithm, we optimize the parameters of CSA and apply them to all algorithms. The parameters for each code are shown in Table 2, where \(\mu >0\) is a positive penalty parameter of the augmented Lagrangian function and \(\alpha >0\) is a positive penalty parameter of L2 penalty function [5].
Table 2 The \(\mu\) and \(\alpha\) for each code. |
 |
Figure 1 shows the comparison of the FER performance of approximate projection algorithms LSA, SAPA and the exact projection algorithm CSA for \(C_2\) in low-iteration regime and high-iteration regime, respectively. As shown in the figure, BP algorithm has poor performance in the high-SNR regime, that is it suffers from an “error floor” phenomenon at high SNRs (occurs at about 2.2 dB), and although the FER performance of LSA and SAPA are quite close to CSA in the high-iteration regime, significant gaps are present in the low-iteration regime. Specifically, when \(\text{FER}=2\times 10^{-4}\), the FER performance of SAPA is worse than that of CSA about 0.1 dB, and the FER performance of LSA is worse than that of CSA about 0.25 dB.
 |
Fig. 1 Frame error rate for CSA, LSA and SAPA for \(C_2\) for both low-iteration (maximum set to 20) and high-iteration (maximum set to 100). |
In order to solve this problem, we propose TPA, whose decoding performance can be almost the same as that of CSA even in the low-iteration regime.
Figure 2 plots the FER performance for different projection algorithms for \({{C}_{1}}-{{C}_{4}}\) for low-iteration. Obviously, the proposed TPA outperforms LSA and SAPA, and its FER performance is almost the same as that of the exact projection algorithm CSA. For instance, for \({{C}_{1}}\), when \(\text{FER}=2\times {{10}^{-5}}\), the FER performance of SAPA is worse than that of TPA about 0.2 dB.
 |
Fig. 2 Frame error rate for CSA, LSA, SAPA and TPA for \({{C}_{1}}-{{C}_{4}}\) for low-iteration (maximum set to 20). |
Figure 3 shows the average number of iterations for different projection algorithms for \({{C}_{1}}-{{C}_{4}}\) for low-iteration. All data are acquired by generating at least 100, 000 frames and average number of iterations is obtained by (total number of iterations)/(total number of frames). Figure 3 suggests that the average number of iterations of the decoder with the proposed TPA is almost the same as that of the decoder with CSA and less than that of the decoder with other algorithms, which means that the proposed algorithm converges quickly. For example, the average number of iterations is saved by 11.01% that of LSA, and 4.3% that of SAPA for \({{C}_{2}}\) at 2.0 dB.
 |
Fig. 3 The average number of iterations for CSA, LSA, SAPA and TPA for \(C_1-C_4\) for low-iteration (maximum set to 20). |
The comparison of average decoding time is plotted in Fig. 4. It is noteworthy that although CSA has the fewest iterations, its average decoding time is the longest because of its much higher complexity than approximate projection algorithms. Figure 4 shows that the average decoding time of TPA is slightly more than that of SAPA and significantly less than that of CSA. Specifically, for \({{C}_{2}}\), the average decoding time of TPA is 6.7% more than that of SAPA while 55.1% less than that of CSA.
 |
Fig. 4 Average decoding time for CSA, LSA, SAPA and TPA for \(C_1-C_4\). |
5. Conclusion
By replacing check polytope projection with projection onto a triangle consisting of the three even-vertices closest to the vector to be projected, we proposed a fast and efficient projection algorithm. While most of the existing approximate projection algorithms sacrifice some decoding performance in exchange for decoding efficiency, losing their accuracy at low iterations, the FER performance of TPA is almost the same as that of the exact projection algorithm for low-iteration. Compared with SAPA, the proposed algorithm can improve the FER performance by 0.2 dB as well as save average number of iterations by 4.3%.
Acknowledgments
This work was supported by the National Natural Science Foundation of China under Grant 62101204.
References
[1] J. Feldman, M.J. Wainwright, and D.R. Karger, “Using linear programming to decode binary linear codes,” IEEE Trans. Inf. Theory, vol.51, no.3, pp.954-972, March 2005.
CrossRef
[2] S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, “Distributed optimization and statistical learning via the alternating direction method of multipliers,” Found. Trends Mach. Learn., vol.3, no.1, pp.1-122, Jan. 2011.
CrossRef
[3] S. Barman, X. Liu, S.C. Draper, and B. Recht, “Decomposition methods for large scale LP decoding,” IEEE Trans. Inf. Theory, vol.59, no.12, pp.7870-7886, Dec. 2013.
CrossRef
[4] F.R. Kschischang, B.J. Frey, and H.-A. Loeliger, “Factor graphs and the sum-product algorithm,” IEEE Trans. Inf. Theory, vol.47, no.2, pp.498-519, Feb. 2001.
CrossRef
[5] X. Liu and S.C. Draper, “The ADMM penalized decoder for LDPC codes,” IEEE Trans. Inf. Theory, vol.62, no.6, pp.2966-2984, June 2016.
CrossRef
[6] Y. Wei, M.-M. Zhao, M.-J. Zhao, and M. Lei, “ADMM-based decoder for binary linear codes aided by deep learning,” IEEE Commun. Lett., vol.24, no.5, pp.1028-1032, May 2020.
CrossRef
[7] X. Guo, T.-H. Chang and Y. Wang, “Model-driven deep learning ADMM decoder for irregular binary LDPC codes,” IEEE Commun. Lett., vol.27, no.2, pp.571-575, Feb. 2023.
CrossRef
[8] X. Zhang and P.H. Siegel, “Efficient iterative LP decoding of LDPC codes with alternating direction method of multipliers,” Proc. IEEE Int. Symp. Inf. Theory, pp.1501-1505, July 2013.
CrossRef
[9] G. Zhang, R. Heusdens, and W.B. Kleijn, “Large scale LP decoding with low complexity,” IEEE Commun. Lett., vol.17, no.11, pp.2152-2155, Nov. 2013.
CrossRef
[10] F. Gensheimer, T. Dietz, K. Kraft, S. Ruzika, and N. Wehn, “A reduced-complexity projection algorithm for ADMM-based LP decoding,” IEEE Trans. Inf. Theory, vol.66, no.8, pp.4819-4833, Aug. 2020.
CrossRef
[11] Q. Xia, X. Wang, H. Liu, and Q.L. Zhang, “A hybrid check polytope projection algorithm for ADMM decoding of LDPC codes,” IEEE Commun. Lett., vol.25, no.1, pp.108-112, 2020.
CrossRef
[12] Y. Zheng, Y. Lin, Z. Zhang, Q. Zhang, and Q. Xia, “An enhanced HDPC-EVA decoder based on ADMM,” IEICE Trans. Fundamentals, vol.E104-A, no.10, pp.1425-1429, Oct. 2021.
CrossRef
[13] Q. Xia, Y. Lin, S. Tang, and Q. Zhang, “A fast approximate check polytope projection algorithm for ADMM decoding of LDPC codes,” IEEE Commun. Lett., vol.23, no.9, pp.1520-1523, Sept. 2019.
CrossRef
[14] Q. Xia, P. He, X. Wang, H. Liu, and Q. Zhang, “Node-wise scheduling algorithm of ADMM decoding based on line segment projection,” IEEE Commun. Lett., vol.26, no.4, pp.738-742, April 2022.
CrossRef
[15] A. Asadzadeh, M. Barakatain, S.C. Draper, and J. Mitra, “SAPA: Sparse affine projection algorithm in ADMM-LP decoding of LDPC codes,” 2022 17th Canadian Workshop on Information Theory (CWIT), Ottawa, ON, Canada, pp.27-32, 2022.
CrossRef
[16] LDPC Coding for OFDMA PHY, Standard IEEE Std. C802.16e-05/0066r3, 2005.
