Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2010.09534

Proximal-ADMM Decoder for Nonbinary LDPC Codes

Yongchao Wang, Jing Bai

Published Oct 19, 2020• 2 citations
arXivHTMLPDF

Abstract

In this paper, we develop an efficient decoder via the proximal alternating direction method of multipliers (proximal-ADMM) technique for nonbinary linear block codes in the Galois field. Its main contents are as follows: first, exploiting the decomposition technique based on the three-variables check equation, we formulate the maximum likelihood (ML) decoding problem approximately to a non-convex quadratic program; second, an efficient algorithm based on the proximal-ADMM technique is proposed to solve the formulated QP problem. Exploiting the QP problem's inherent structures, its variables can be updated in parallel; third, we prove that the proposed decoding algorithm can converge to some stationary point of the formulated QP problem. Moreover, we also show, for nonbinary low-density parity-check (LDPC) codes, its computational complexity in each proximal-ADMM iteration scales linearly with block length and the size of the considered Galois field. Simulation results demonstrate that the proposed proximal-ADMM decoder outperforms state-of-the-art nonbinary LDPC decoders in terms of either error correction performance or computational complexity.

DOI
10.48550/arxiv.2010.09534

Related papers

Decoding Nonbinary LDPC Codes via Proximal-ADMM Approach (include convergence proofs)

Yongchao Wang, Jing Bai

In this paper, we focus on decoding nonbinary low-density parity-check (LDPC) codes in Galois fields of characteristic two via the proximal alternating direction method of multipliers (proximal-ADMM). By exploiting Flanagan/Constant-Weighting embedding techniques and the decomposition technique based on three-variables parity-check equations, two efficient proximal-ADMM decoders for nonbinary LDPC codes are proposed. We show that both of them are theoretically guaranteed convergent to some stationary point of the decoding model and either of their computational complexities in each proximal-ADMM iteration scales linearly with LDPC code's length and the size of the considered Galois field. Moreover, the decoder based on the Constant-Weight embedding technique satisfies the favorable property of codeword symmetry. Simulation results demonstrate their effectiveness in comparison with state-of-the-art LDPC decoders.

arXiv:2201.00370•Jan 2, 2022•0 citations

Decoding Nonbinary LDPC Codes via Proximal-ADMM Approach

Yongchao Wang, Jing Bai

In this paper, we focus on decoding nonbinary low-density parity-check (LDPC) codes in Galois fields of characteristic two via the proximal alternating direction method of multipliers (proximal-ADMM). By exploiting Flanagan/Constant-Weighting embedding techniques and the decomposition technique based on three-variables parity-check equations, two efficient proximal-ADMM decoders for nonbinary LDPC codes are proposed. We show that both of them are theoretically guaranteed convergent to some stationary point of the decoding model and either of their computational complexities in each proximal-ADMM iteration scales linearly with LDPC code’s length and the size of the considered Galois field. Moreover, the decoder based on the Constant-Weight embedding technique satisfies the favorable property of codeword symmetry. Simulation results demonstrate their effectiveness in comparison with state-of-the-art LDPC decoders.

IEEE Transactions on Information Theory•Jan 31, 2022•11 citations

Efficient QP-ADMM Decoder for Binary LDPC Codes and Its Performance Analysis

Jing Bai, Yongchao Wang, Qingjiang Shi

This paper presents an efficient quadratic programming (QP) decoder via the alternating direction method of multipliers (ADMM) technique, called QP-ADMM, for binary low-density parity-check (LDPC) codes. Its main contents are as follows: first, we relax the maximum likelihood (ML) decoding problem to a non-convex quadratic program. Then, we develop an ADMM solving algorithm for the formulated non-convex QP decoding model. In the proposed QP-ADMM decoder, complex Euclidean projections onto the check polytope are eliminated and variables in each updated step can be solved analytically in parallel. Moreover, it is proved that the proposed ADMM algorithm converges to a stationary point of the non-convex QP problem under the assumption of sequence convergence. We also verify that the proposed decoder satisfies the favorable property of the all-zeros assumption. Furthermore, by exploiting the inside structures of the QP model, the complexity of the proposed algorithm in each iteration is shown to be linear in terms of LDPC code length. Simulation results demonstrate the effectiveness of the proposed QP-ADMM decoder.

arXiv:1910.12712•IEEE Transactions on Signal Processing•Jan 1, 2020•18 citations

Efficient ADMM Decoder for Non-binary LDPC Codes based on Bit Embedding Technique

Xiaomeng Guo, Yongchao Wang

In this paper, we devise a new alternating direction method of multipliers (ADMM) decoder for non-binary low-density parity-check (LDPC) codes in Galois fields of characteristic two $\left( {{\mathbb{F}_{{2^q}}}} \right)$. Its main content are threefold: first, the procedure of formulating the maximum likelihood (ML) decoding problem in ${\mathbb{F}_{{2^q}}}$ to a linear integer problem in real space is presented; Second, after relaxing the integer problem to a continuous one, an efficient ADMM algorithm is customized to solve the latter, where all the entries of the variable vectors can be obtained in parallel; Third, we show that the proposed ADMM decoder satisfies the favorable codeword-independent property under some mild conditions and its computation complexity in each ADMM iteration is roughly $\mathcal{O}\left( {nq} \right)$, where n is code length of the considered non-binary LDPC code. Simulation results demonstrate that its performance, such as error-correction and decoding efficiency, is very competitive in comparison with state-of-the-art non-binary LDPC decoders.

IEEE International Symposium on Information Theory (ISIT)•Jun 26, 2022•1 citation

Quadratic Programming Decoder for Binary LDPC Codes via ADMM Technique with Linear Complexity

Jing Bai, Yongchao Wang

In this paper, we develop an efficient quadratic programming (QP) decoding algorithm via the alternating direction method of multipliers (ADMM) technique for binary low density parity check (LDPC) codes. Its main content is as follows: first, through transforming the three-variables parity check equation to its equivalent expression, we relax the maximum likelihood decoding problem to a quadratic program. Second, the ADMM technique is exploited to design the solving algorithm of the resulting QP decoding model. Compared with the existing ADMM-based mathematical programming (MP) decoding algorithms, our proposed algorithm eliminates complex Euclidean projection onto the check polytope. Third, we prove that the proposed algorithm satisfies the favorable property of all-zeros assumption. Moreover, by exploiting the inside structure of the QP model, we show that the decoding complexity of our proposed algorithm in each iteration is linear in terms of LDPC code length. Simulation results demonstrate that the proposed QP decoder attains better error-correction performance than the sum-product BP decoder and costs the least amount of decoding time amongst the state-of-the-art ADMM-based MP decoding algorithms.

International Conference on Communications•Jun 1, 2020•3 citations

Efficient ADMM Decoder for Non-binary LDPC Codes with Codeword-Independent Performance

Xiaomeng Guo, Yongchao Wang

In this paper, we devote to devise a non-binary low-density parity-check (LDPC) decoder in Galois fields of characteristic two ($\mathbb{F}_{2^q}$) via the alternating direction method of multipliers (ADMM) technique. Through the proposed bit embedding technique and the decomposition technique of the three-variables parity-check equation, an efficient ADMM decoding algorithm for non-binary LDPC codes is proposed. The computation complexity in each ADMM iteration is roughly $\mathcal{O}(nq)$, which is significantly lower than the existing LDPC decoders. Moreover, we prove that the proposed decoder satisfies the favorable property of the codeword-independent. Simulation results demonstrate the outstanding performance of the proposed decoder in contrast with state-of-the-art LDPC decoders.

arXiv:2202.02961•Feb 7, 2022•1 citation
In this paper, we develop an efficient decoder via the proximal alternating direction method of multipliers (proximal-ADMM) technique for nonbinary linear block codes in the Galois field. Its main contents are as follows: first, exploiting the decomposition technique based on the three-variables check equation, we formulate the maximum likelihood (ML) decoding problem approximately to a non-convex quadratic program; second, an efficient algorithm based on the proximal-ADMM technique is proposed to solve the formulated QP problem. Exploiting the QP problem's inherent structures, its variables can be updated in parallel; third, we prove that the proposed decoding algorithm can converge to some stationary point of the formulated QP problem. Moreover, we also show, for nonbinary low-density parity-check (LDPC) codes, its computational complexity in each proximal-ADMM iteration scales linearly with block length and the size of the considered Galois field. Simulation results demonstrate that the proposed proximal-ADMM decoder outperforms state-of-the-art nonbinary LDPC decoders in terms of either error correction performance or computational complexity.
In this paper, we focus on decoding nonbinary low-density parity-check (LDPC) codes in Galois fields of characteristic two via the proximal alternating direction method of multipliers (proximal-ADMM). By exploiting Flanagan/Constant-Weighting embedding techniques and the decomposition technique based on three-variables parity-check equations, two efficient proximal-ADMM decoders for nonbinary LDPC codes are proposed. We show that both of them are theoretically guaranteed convergent to some stationary point of the decoding model and either of their computational complexities in each proximal-ADMM iteration scales linearly with LDPC code's length and the size of the considered Galois field. Moreover, the decoder based on the Constant-Weight embedding technique satisfies the favorable property of codeword symmetry. Simulation results demonstrate their effectiveness in comparison with state-of-the-art LDPC decoders.
In this paper, we focus on decoding nonbinary low-density parity-check (LDPC) codes in Galois fields of characteristic two via the proximal alternating direction method of multipliers (proximal-ADMM). By exploiting Flanagan/Constant-Weighting embedding techniques and the decomposition technique based on three-variables parity-check equations, two efficient proximal-ADMM decoders for nonbinary LDPC codes are proposed. We show that both of them are theoretically guaranteed convergent to some stationary point of the decoding model and either of their computational complexities in each proximal-ADMM iteration scales linearly with LDPC code’s length and the size of the considered Galois field. Moreover, the decoder based on the Constant-Weight embedding technique satisfies the favorable property of codeword symmetry. Simulation results demonstrate their effectiveness in comparison with state-of-the-art LDPC decoders.
This paper presents an efficient quadratic programming (QP) decoder via the alternating direction method of multipliers (ADMM) technique, called QP-ADMM, for binary low-density parity-check (LDPC) codes. Its main contents are as follows: first, we relax the maximum likelihood (ML) decoding problem to a non-convex quadratic program. Then, we develop an ADMM solving algorithm for the formulated non-convex QP decoding model. In the proposed QP-ADMM decoder, complex Euclidean projections onto the check polytope are eliminated and variables in each updated step can be solved analytically in parallel. Moreover, it is proved that the proposed ADMM algorithm converges to a stationary point of the non-convex QP problem under the assumption of sequence convergence. We also verify that the proposed decoder satisfies the favorable property of the all-zeros assumption. Furthermore, by exploiting the inside structures of the QP model, the complexity of the proposed algorithm in each iteration is shown to be linear in terms of LDPC code length. Simulation results demonstrate the effectiveness of the proposed QP-ADMM decoder.
In this paper, we devise a new alternating direction method of multipliers (ADMM) decoder for non-binary low-density parity-check (LDPC) codes in Galois fields of characteristic two (F2q)\left( {{\mathbb{F}_{{2^q}}}} \right)(F2q​). Its main content are threefold: first, the procedure of formulating the maximum likelihood (ML) decoding problem in F2q{\mathbb{F}_{{2^q}}}F2q​ to a linear integer problem in real space is presented; Second, after relaxing the integer problem to a continuous one, an efficient ADMM algorithm is customized to solve the latter, where all the entries of the variable vectors can be obtained in parallel; Third, we show that the proposed ADMM decoder satisfies the favorable codeword-independent property under some mild conditions and its computation complexity in each ADMM iteration is roughly O(nq)\mathcal{O}\left( {nq} \right)O(nq), where n is code length of the considered non-binary LDPC code. Simulation results demonstrate that its performance, such as error-correction and decoding efficiency, is very competitive in comparison with state-of-the-art non-binary LDPC decoders.
In this paper, we develop an efficient quadratic programming (QP) decoding algorithm via the alternating direction method of multipliers (ADMM) technique for binary low density parity check (LDPC) codes. Its main content is as follows: first, through transforming the three-variables parity check equation to its equivalent expression, we relax the maximum likelihood decoding problem to a quadratic program. Second, the ADMM technique is exploited to design the solving algorithm of the resulting QP decoding model. Compared with the existing ADMM-based mathematical programming (MP) decoding algorithms, our proposed algorithm eliminates complex Euclidean projection onto the check polytope. Third, we prove that the proposed algorithm satisfies the favorable property of all-zeros assumption. Moreover, by exploiting the inside structure of the QP model, we show that the decoding complexity of our proposed algorithm in each iteration is linear in terms of LDPC code length. Simulation results demonstrate that the proposed QP decoder attains better error-correction performance than the sum-product BP decoder and costs the least amount of decoding time amongst the state-of-the-art ADMM-based MP decoding algorithms.
In this paper, we devote to devise a non-binary low-density parity-check (LDPC) decoder in Galois fields of characteristic two (F2q\mathbb{F}_{2^q}F2q​) via the alternating direction method of multipliers (ADMM) technique. Through the proposed bit embedding technique and the decomposition technique of the three-variables parity-check equation, an efficient ADMM decoding algorithm for non-binary LDPC codes is proposed. The computation complexity in each ADMM iteration is roughly O(nq)\mathcal{O}(nq)O(nq), which is significantly lower than the existing LDPC decoders. Moreover, we prove that the proposed decoder satisfies the favorable property of the codeword-independent. Simulation results demonstrate the outstanding performance of the proposed decoder in contrast with state-of-the-art LDPC decoders.