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.

IEEE Transactions on Information TheoryJan 31, 202211 citations

Proximal-ADMM Decoder for Nonbinary LDPC Codes

Yongchao Wang, Jing Bai

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 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.

arXiv:2010.09534Oct 19, 20202 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.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.02961Feb 7, 20221 citation

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.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, 20221 citation

ℓ2-box ADMM Decoder for Non-binary LDPC Codes in F2q

Xiaomeng Guo, Xiaohe Li, Baoyi Xu +1 more

In this paper, we devise a novel decoding approach for Galois fields ( ${\mathbb{F}_{{2^q}}}$ )-based non-binary Low-Density Parity-Check (LDPC) codes, leveraging the Alternating Direction Method of Multipliers (ADMM). The development of this decoder is structured around three primary contributions: firstly, we reformulate the Maximum Likelihood (ML) decoding problem as a discrete optimization task in Euclidean space, facilitated by the bit-embedding technique; secondly, we demonstrate the conversion of this integer problem into a continuous format via the ℓp-box method, for which a customized ADMM algorithm is developed; thirdly, we theoretical verify the proposed decoder’s codeword-independent property with per-iteration operations scaling approximately linearly with the code dimension (denoted as $\mathcal{O}(nq)$ ). Simulation results show that the error-correction capability and decoding efficiency is very competitive in comparison with contemporary non-binary LDPC decoders.In this paper, we devise a novel decoding approach for Galois fields (${\mathbb{F}_{{2^q}}}$)-based non-binary Low-Density Parity-Check (LDPC) codes, leveraging the Alternating Direction Method of Multipliers (ADMM). The development of this decoder is structured around three primary contributions: firstly, we reformulate the Maximum Likelihood (ML) decoding problem as a discrete optimization task in Euclidean space, facilitated by the bit-embedding technique; secondly, we demonstrate the conversion of this integer problem into a continuous format via the ℓp-box method, for which a customized ADMM algorithm is developed; thirdly, we theoretical verify the proposed decoder’s codeword-independent property with per-iteration operations scaling approximately linearly with the code dimension (denoted as $\mathcal{O}(nq)$). Simulation results show that the error-correction capability and decoding efficiency is very competitive in comparison with contemporary non-binary LDPC decoders.

International Conference on Intelligent Computing and Signal Processing (ICSP)May 16, 20250 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.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.12712IEEE Transactions on Signal ProcessingJan 1, 202018 citations

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.

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.

In this paper, we devise a novel decoding approach for Galois fields (

{\mathbb{F}_{{2^q}}}

)-based non-binary Low-Density Parity-Check (LDPC) codes, leveraging the Alternating Direction Method of Multipliers (ADMM). The development of this decoder is structured around three primary contributions: firstly, we reformulate the Maximum Likelihood (ML) decoding problem as a discrete optimization task in Euclidean space, facilitated by the bit-embedding technique; secondly, we demonstrate the conversion of this integer problem into a continuous format via the ℓp-box method, for which a customized ADMM algorithm is developed; thirdly, we theoretical verify the proposed decoder’s codeword-independent property with per-iteration operations scaling approximately linearly with the code dimension (denoted as

\mathcal{O}(nq)

). Simulation results show that the error-correction capability and decoding efficiency is very competitive in comparison with contemporary non-binary LDPC decoders.