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

IEEE Communications Letters

An Efficient Procedure for Bilayer-Expurgated LDPC Codes Design in Cooperative Relay Channels

Sajad Mehrizi, Sara Khosravi, Mahmoud Ahmadian‐Attari

Published May 26, 2017• 2 citations
Publisher

Abstract

This letter proposes a fast optimization procedure to design bilayer-expurgated low density parity check codes in the relay channel. The code optimization problem aims to maximize the code rate while guaranteeing the convergence of the density evolution relations in upper and lower layer codes. The original problem is linear programming. Nevertheless, it suffers from high computational complexity, as it is semi-infinite programming (SIP) in a 2-D continuous interval. To efficiently solve it, we first approximate the density evolutions by polynomials. Then, leveraging optimization problems over the solution of sum of square multivariate polynomials the problem is transformed to semi-definite programming (SDP), where the global solution can be found efficiently using available SDP solvers. Our simulation shows that our approach results in significantly lower computational complexity with respect to the well-known method of quantization for solving the SIP problem, while both achieve the same performance.

DOI
10.1109/lcomm.2017.2708699

Related papers

On the Design of Fast Convergent LDPC Codes for the BEC: An Optimization Approach

Vahid Jamali, Yasser Karimian, Johannes B. Huber +1 more

The complexity-performance trade-off is a fundamental aspect of the design of low-density parity-check (LDPC) codes. In this paper, we consider LDPC codes for the binary erasure channel (BEC), use code rate for performance metric, and number of decoding iterations to achieve a certain residual erasure probability for complexity metric. We first propose a quite accurate approximation of the number of iterations for the BEC. Moreover, a simple but efficient utility function corresponding to the number of iterations is developed. Using the aforementioned approximation and the utility function, two optimization problems w.r.t. complexity are formulated to find the code degree distributions. We show that both optimization problems are convex. In particular, the problem with the proposed approximation belongs to the class of semi-infinite problems which are computationally challenging to be solved. However, the problem with the proposed utility function falls into the class of semi-definite programming (SDP) and thus, the global solution can be found efficiently using available SDP solvers. Numerical results reveal the superiority of the proposed code design compared to existing code designs from literature.

arXiv:1401.4337•IEEE Transactions on Communications•Dec 24, 2014•8 citations

An efficient complexity-optimizing LDPC code design for the binary erasure channel

Vahid Jamali, Yasser Karimian, Johannes B. Huber +1 more

The complexity-performance trade-off is a fundamental aspect of the design of low-density parity-check (LDPC) codes. In this paper, we consider LDPC codes for the binary erasure channel (BEC), use code rate for performance metric, and number of decoding iterations to achieve a certain residual erasure probability for complexity metric. The available complexity-optimizing problems in the literature for the BEC are either non-convex or belong to the class of semi-infinite problems which are computationally challenging to be solved. Hence, in this paper, we first propose a lower bound on the number of iterations for the BEC. Moreover, a simple but efficient utility function corresponding to the number of iterations is developed. Using this utility function, an optimization problem w.r.t. complexity is formulated to find complexity-optimized code degree distributions. We prove that the considered problem with the proposed utility function falls into the class of semi-definite programming (SDP) and thus, the global solution can be found efficiently using available SDP solvers. Numerical results reveal the superiority of the proposed code design compared to existing code designs from literature.

International Symposium on Turbo Codes and Iterative Information Processing•Aug 1, 2014•3 citations

Design of multi-edge type bilayer-expurgated LDPC codes

Marwan Hadri Azmi, Jinhong Yuan

This paper presents a new bilayer-expurgated LDPC (BE-LDPC) code design for decode-and-forward relay system. The code design is based on the multi-edge type LDPC (MET-LDPC) code structure. The lower and upper graphs' edges of the BE-LDPC codes are represented via different edge types. We call the codes as multi-edge type bilayer-expurgated LDPC (MET-BE-LDPC) codes. We derive the relationship between the lower and the overall graphs of the MET-BE-LDPC codes using the multi-edge type multinomials. This relationship acts as a constraint in optimizing the MET-BE-LDPC codes under the density evolution. We apply the differential evolution algorithm to search for the best MET-BE-LDPC codes. Applying the proposed methodology, two MET-BE-LDPC codes are designed. The codes perform asymptotically within 0.08474-0.5087 dB from the theoretical limits. Finally, we demonstrate that the proposed methodology can be used to design the BE-LDPC codes at a larger source-to-relay and source-to-destination SNR differences.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2009•12 citations

Discrete density evolution and LDPC codes designwith asymmetric channels

涛 袁, 征 马, 琦珂 庞 +1 more

To design low-density parity-check (LDPC) codes with asymmetric channels and analyze their performance, an achievable asymmetric discrete density evolution method is proposed, which is based on offset min-sum decoding. First, the iterative formula of low-complexity asymmetric channel discrete density evolution is derived by means of combinatorics, difference method and the binomial theorem. The iterative formula is applied to further optimize the design of the LDPC codes using the offset min-sum decoding, and the optimal degree distributions and performance of the LDPC codes under different quantization ranges and step sizes are obtained under the asymmetric channel. Finally, the optimal offset values under high-precision quantization are obtained. The results show that under the asymmetric channel, the complexity of the proposed asymmetric density evolution method based on the offset min-sum decoding is reduced by an order of magnitude than that using the original method. For a fixed code rate, the smaller the variable node degree of the regular codes, the better the performance and the smaller the optimal offset value. For irregular LDPC codes, the optimal degree distributions and offset values are determined according to the differential evolution algorithm. For a fixed code rate, the larger the maximum variable node degree, the better the performance of irregular codes.

Scientia Sinica Informationis•Aug 29, 2022•1 citation

Iterative Approximate Linear Programming Decoding of LDPC Codes With Linear Complexity

David Burshtein

The problem of low complexity linear programming (LP) decoding of low-density parity-check (LDPC) codes is considered. An iterative algorithm, similar to min-sum and belief propagation, for efficient approximate solution of this problem was proposed by Vontobel and Koetter. In this paper, the convergence rate and computational complexity of this algorithm are studied using a scheduling scheme that we propose. In particular, we are interested in obtaining a feasible vector in the LP decoding problem that is close to optimal in the following sense. The distance, normalized by the block length, between the minimum and the objective function value of this approximate solution can be made arbitrarily small. It is shown that such a feasible vector can be obtained with a computational complexity which scales linearly with the block length. Combined with previous results that have shown that the LP decoder can correct some fixed fraction of errors we conclude that this error correction can be achieved with linear computational complexity. This is achieved by first applying the iterative LP decoder that decodes the correct transmitted codeword up to an arbitrarily small fraction of erroneous bits, and then correcting the remaining errors using some standard method. These conclusions are also extended to generalized LDPC codes.

IEEE Transactions on Information Theory•Oct 27, 2009•67 citations

Bilayer Lengthened QC-LDPC Codes Design for Relay Channel

Hua Xu

The relay channel is the common approach to cooperative communication. Quasi-cyclic low-density parity-check (QC-LDPC) code design for the relay channel is important to cooperative communication. This paper proposes a bilayer QC-LDPC code design scheme for the relay channel. Combined with the bilayer graphical code structure, an improved Chinese remainder theorem (CRT) method, the Biff-CRT method is presented. For the proposed method we introduce a finite field approach. The good performance of the finite field based QC-LDPC code can improve the performance of its corresponding objective QC-LDPC code in the proposed scheme. We construct the FF code and the FA code by the Biff-CRT method. The FF code and the FA code are both named as their two component codes. For the FF code, the two component code are both finite field based QC-LDPC codes. For the FA code, one of the component codes is the finite field based QC-LDPC code and the other is the array code. For the existing CRT method, the shortened array code and the array code are usually used as the component codes to construct the SA code. The exponent matrices of FF code, FA code and SA code are given both for the overall graph and the lower graph. Bit error rate (BER) simulation results indicate that the proposed FF code and FA code are superior to the SA code both at the relay node and the destination node. In addition, the theoretical limit and the BER of the bilayer irregular LDPC code are also given to compare with the BER of the proposed QC-LDPC codes. Moreover, the proposed Biff-CRT method is flexible, easy to implement and effective for constructing the QC-LDPC codes for the relay channel, and it is attractive for being used in the future cooperative communication systems.

IEICE Transactions on Communications•Jan 1, 2014•4 citations
This letter proposes a fast optimization procedure to design bilayer-expurgated low density parity check codes in the relay channel. The code optimization problem aims to maximize the code rate while guaranteeing the convergence of the density evolution relations in upper and lower layer codes. The original problem is linear programming. Nevertheless, it suffers from high computational complexity, as it is semi-infinite programming (SIP) in a 2-D continuous interval. To efficiently solve it, we first approximate the density evolutions by polynomials. Then, leveraging optimization problems over the solution of sum of square multivariate polynomials the problem is transformed to semi-definite programming (SDP), where the global solution can be found efficiently using available SDP solvers. Our simulation shows that our approach results in significantly lower computational complexity with respect to the well-known method of quantization for solving the SIP problem, while both achieve the same performance.
The complexity-performance trade-off is a fundamental aspect of the design of low-density parity-check (LDPC) codes. In this paper, we consider LDPC codes for the binary erasure channel (BEC), use code rate for performance metric, and number of decoding iterations to achieve a certain residual erasure probability for complexity metric. We first propose a quite accurate approximation of the number of iterations for the BEC. Moreover, a simple but efficient utility function corresponding to the number of iterations is developed. Using the aforementioned approximation and the utility function, two optimization problems w.r.t. complexity are formulated to find the code degree distributions. We show that both optimization problems are convex. In particular, the problem with the proposed approximation belongs to the class of semi-infinite problems which are computationally challenging to be solved. However, the problem with the proposed utility function falls into the class of semi-definite programming (SDP) and thus, the global solution can be found efficiently using available SDP solvers. Numerical results reveal the superiority of the proposed code design compared to existing code designs from literature.
The complexity-performance trade-off is a fundamental aspect of the design of low-density parity-check (LDPC) codes. In this paper, we consider LDPC codes for the binary erasure channel (BEC), use code rate for performance metric, and number of decoding iterations to achieve a certain residual erasure probability for complexity metric. The available complexity-optimizing problems in the literature for the BEC are either non-convex or belong to the class of semi-infinite problems which are computationally challenging to be solved. Hence, in this paper, we first propose a lower bound on the number of iterations for the BEC. Moreover, a simple but efficient utility function corresponding to the number of iterations is developed. Using this utility function, an optimization problem w.r.t. complexity is formulated to find complexity-optimized code degree distributions. We prove that the considered problem with the proposed utility function falls into the class of semi-definite programming (SDP) and thus, the global solution can be found efficiently using available SDP solvers. Numerical results reveal the superiority of the proposed code design compared to existing code designs from literature.
This paper presents a new bilayer-expurgated LDPC (BE-LDPC) code design for decode-and-forward relay system. The code design is based on the multi-edge type LDPC (MET-LDPC) code structure. The lower and upper graphs' edges of the BE-LDPC codes are represented via different edge types. We call the codes as multi-edge type bilayer-expurgated LDPC (MET-BE-LDPC) codes. We derive the relationship between the lower and the overall graphs of the MET-BE-LDPC codes using the multi-edge type multinomials. This relationship acts as a constraint in optimizing the MET-BE-LDPC codes under the density evolution. We apply the differential evolution algorithm to search for the best MET-BE-LDPC codes. Applying the proposed methodology, two MET-BE-LDPC codes are designed. The codes perform asymptotically within 0.08474-0.5087 dB from the theoretical limits. Finally, we demonstrate that the proposed methodology can be used to design the BE-LDPC codes at a larger source-to-relay and source-to-destination SNR differences.
To design low-density parity-check (LDPC) codes with asymmetric channels and analyze their performance, an achievable asymmetric discrete density evolution method is proposed, which is based on offset min-sum decoding. First, the iterative formula of low-complexity asymmetric channel discrete density evolution is derived by means of combinatorics, difference method and the binomial theorem. The iterative formula is applied to further optimize the design of the LDPC codes using the offset min-sum decoding, and the optimal degree distributions and performance of the LDPC codes under different quantization ranges and step sizes are obtained under the asymmetric channel. Finally, the optimal offset values under high-precision quantization are obtained. The results show that under the asymmetric channel, the complexity of the proposed asymmetric density evolution method based on the offset min-sum decoding is reduced by an order of magnitude than that using the original method. For a fixed code rate, the smaller the variable node degree of the regular codes, the better the performance and the smaller the optimal offset value. For irregular LDPC codes, the optimal degree distributions and offset values are determined according to the differential evolution algorithm. For a fixed code rate, the larger the maximum variable node degree, the better the performance of irregular codes.
The problem of low complexity linear programming (LP) decoding of low-density parity-check (LDPC) codes is considered. An iterative algorithm, similar to min-sum and belief propagation, for efficient approximate solution of this problem was proposed by Vontobel and Koetter. In this paper, the convergence rate and computational complexity of this algorithm are studied using a scheduling scheme that we propose. In particular, we are interested in obtaining a feasible vector in the LP decoding problem that is close to optimal in the following sense. The distance, normalized by the block length, between the minimum and the objective function value of this approximate solution can be made arbitrarily small. It is shown that such a feasible vector can be obtained with a computational complexity which scales linearly with the block length. Combined with previous results that have shown that the LP decoder can correct some fixed fraction of errors we conclude that this error correction can be achieved with linear computational complexity. This is achieved by first applying the iterative LP decoder that decodes the correct transmitted codeword up to an arbitrarily small fraction of erroneous bits, and then correcting the remaining errors using some standard method. These conclusions are also extended to generalized LDPC codes.
The relay channel is the common approach to cooperative communication. Quasi-cyclic low-density parity-check (QC-LDPC) code design for the relay channel is important to cooperative communication. This paper proposes a bilayer QC-LDPC code design scheme for the relay channel. Combined with the bilayer graphical code structure, an improved Chinese remainder theorem (CRT) method, the Biff-CRT method is presented. For the proposed method we introduce a finite field approach. The good performance of the finite field based QC-LDPC code can improve the performance of its corresponding objective QC-LDPC code in the proposed scheme. We construct the FF code and the FA code by the Biff-CRT method. The FF code and the FA code are both named as their two component codes. For the FF code, the two component code are both finite field based QC-LDPC codes. For the FA code, one of the component codes is the finite field based QC-LDPC code and the other is the array code. For the existing CRT method, the shortened array code and the array code are usually used as the component codes to construct the SA code. The exponent matrices of FF code, FA code and SA code are given both for the overall graph and the lower graph. Bit error rate (BER) simulation results indicate that the proposed FF code and FA code are superior to the SA code both at the relay node and the destination node. In addition, the theoretical limit and the BER of the bilayer irregular LDPC code are also given to compare with the BER of the proposed QC-LDPC codes. Moreover, the proposed Biff-CRT method is flexible, easy to implement and effective for constructing the QC-LDPC codes for the relay channel, and it is attractive for being used in the future cooperative communication systems.