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 Wireless Communications and Networking Conference

Efficient Implementation of Interior Point Decoding Based on Barrier Function for LDPC Codes

Telex M. N. Ngatched, Attahiru Sule Alfa, Jun Cai

Published Apr 1, 2010• 0 citations
Publisher

Abstract

In this paper, an efficient implementation of the interior point algorithm recently proposed by Wadayama for linear programming (LP) decoding of low-density parity-check (LDPC) codes is presented. The main idea behind the modification is to approximate the barrier function for the fundamental polytope defining the code so that it contains only one linear constraint for each of the parity-check constraints. Simulation results show that the approximations introduced do not result in any performance degradation, while considerably reducing the decoding complexity and latency.

DOI
10.1109/wcnc.2010.5506378

Related papers

Hybrid Linear Programming Based Decoding Algorithm for LDPC Codes

Telex M. N. Ngatched, Attahiru Sule Alfa, Jun Cai

This paper presents a hybrid decoding algorithm for low-density parity-check (LDPC) codes based on the interior point method with barrier function for linear programming (LP) decoding introduced by Wadayama . First, an efficient implementation of Wadayama's algorithm is presented. The main idea behind the modification is to approximate the barrier function for the fundamental polytope defining the code so that it contains only one linear constraint for each of the parity-check constraints. A two-stage hybrid decoding which combines the interior point decoding and a low-complexity decoding algorithm for LDPC codes is then proposed. Simulation results show that the approximations introduced in the proposed algorithms do not result in any performance degradation, while considerably reducing the decoding complexity and latency.

IEEE Transactions on Communications•Jan 21, 2011•3 citations

Hybrid Decoding of LDPC Codes Based on Interior Point Method

Telex M. N. Ngatched, Attahiru Sule Alfa, J. Cai

In this paper, a hybrid decoding algorithm for finite-geometry low-density parity-check (FG-LDPC) codes is proposed. The algorithm is based on the interior point method with barrier function introduced by Wadayama. First, an efficient implementation of Wadayama's algorithm is presented. The main idea behind the modification is to approximate the barrier function for the fundamental polytope defining the code so that it contains only one linear constraint for each of the parity-check constraints. A two-stage hybrid decoding which combines the interior point decoding (IPD) and a low-complexity decoding algorithm for FG-LDPC codes is then proposed. In the first stage, the interior point decoding is used to generate a search point. If the first stage decoding fails, the decoding is continued by the low-complexity algorithm that is initialized by the result of the IPD. Compared with a conventional iterative message-passing (IMP) decoder, the proposed hybrid algorithm achieves better bit-error rate (BER) and frame-error rate (FER) for small block lengths at medium to high signal-to-noise ratio (SNR).

International Conference on Communications•May 1, 2010•0 citations

Efficient implementation of linear programming decoding

Mohammad Hossein Taghavi, Amin Shokrollahi, Paul H. Siegel

This paper explores ideas for fast linear programming (LP) decoding of low-density parity-check (LDPC) codes. We first propose a modification of adaptive LP decoding, and prove that it performs LP decoding by solving a number of linear programs that contain at most one linear constraint derived from each of the parity-check constraints. Then, as a step toward designing an efficient LP solver that exploits the structure of LDPC codes, we study a sparse interior-point implementation for solving this sequence of linear programs. Since the most complex part of each iteration of the interior-point algorithms is to solve a (usually ill-conditioned) system of linear equations for finding the step direction, we propose a framework for designing preconditioners to be used with the iterative methods for solving these systems. The effectiveness of the proposed approach is demonstrated via both analytical and simulation results.

Allerton Conference on Communication, Control, and Computing•Sep 1, 2008•11 citations

Efficient Implementation of Linear Programming Decoding

Mohammad Hossein Taghavi, Amin Shokrollahi, Paul H. Siegel

While linear programming (LP) decoding provides more flexibility for finite-length performance analysis than iterative message-passing (IMP) decoding, it is computationally more complex to implement in its original form, due to both the large size of the relaxed LP problem and the inefficiency of using general-purpose LP solvers. This paper explores ideas for fast LP decoding of low-density parity-check (LDPC) codes. By modifying the previously reported Adaptive LP decoding scheme to allow removal of unnecessary constraints, we first prove that LP decoding can be performed by solving a number of LP problems that each contains at most one linear constraint derived from each of the parity-check constraints. By exploiting this property, we study a sparse interior-point implementation for solving this sequence of linear programs. Since the most complex part of each iteration of the interior-point algorithm is the solution of a (usually ill-conditioned) system of linear equations for finding the step direction, we propose a preconditioning algorithm to facilitate solving such systems iteratively. The proposed preconditioning algorithm is similar to the encoding procedure of LDPC codes, and we demonstrate its effectiveness via both analytical methods and computer simulation results.

IEEE Transactions on Information Theory•Sep 1, 2011•48 citations

Efficient implementation of linear programming decoding

Mohammad Hossein Taghavi, Amin Shokrollahi, Paul H. Siegel

While linear programming (LP) decoding provides more flexibility for finite-length performance analysis than iterative message-passing (IMP) decoding, it is computationally more complex to implement in its original form, due to both the large size of the relaxed LP problem, and the inefficiency of using general-purpose LP solvers. This paper explores ideas for fast LP decoding of low-density parity-check (LDPC) codes. We first prove, by modifying the previously reported Adaptive LP decoding scheme to allow removal of unnecessary constraints, that LP decoding can be performed by solving a number of LP problems that contain at most one linear constraint derived from each of the parity-check constraints. By exploiting this property, we study a sparse interior-point implementation for solving this sequence of linear programs. Since the most complex part of each iteration of the interior-point algorithm is the solution of a (usually ill-conditioned) system of linear equations for finding the step direction, we propose a preconditioning algorithm to facilitate iterative solution of such systems. The proposed preconditioning algorithm is similar to the encoding procedure of LDPC codes, and we demonstrate its effectiveness via both analytical methods and computer simulation results.

arXiv:0902.0657•Feb 4, 2009•2 citations

Infeasible primal-dual interior-point algorithm for linear-programming decoding of LDPC codes

Xuye Wang, Piming Ma

The linear programming (LP) decoding of Low-Density Parity-Check (LDPC) codes is widely concerned for its maximum likelihood (ML) features. It is that the ML decoding rule for LDPC codes can be relaxed to LP optimization problem. Therefore, this paper focus on an efficient algorithm called infeasible primal-dual interior-point (IPDIP) to solve the LP problem. In each iteration, the IPDIP algorithm obtains the predictor and corrector steps by solving the Karush-Kuhn-Tucker (KKT) equation twice. The predictor term is used to responsible for optimal solution and the corrector term keeps the current iteration away from the boundary of the feasible region. Furthermore, a modification of the centering parameter is developed to accelerate the convergence speed for the IPDIP algorithm. Simulation results of LP decoding demonstrate that the proposed IPDIP algorithm achieves beautiful bit error rate (BER) performance and good global convergence properties with less iteration number and time than other algorithms which only solve the KKT equation once by Newton method or use the not modified centering parameter.

IEEE International Conference on Communication Technology (ICCT)•Sep 1, 2011•0 citations
In this paper, an efficient implementation of the interior point algorithm recently proposed by Wadayama for linear programming (LP) decoding of low-density parity-check (LDPC) codes is presented. The main idea behind the modification is to approximate the barrier function for the fundamental polytope defining the code so that it contains only one linear constraint for each of the parity-check constraints. Simulation results show that the approximations introduced do not result in any performance degradation, while considerably reducing the decoding complexity and latency.
This paper presents a hybrid decoding algorithm for low-density parity-check (LDPC) codes based on the interior point method with barrier function for linear programming (LP) decoding introduced by Wadayama . First, an efficient implementation of Wadayama's algorithm is presented. The main idea behind the modification is to approximate the barrier function for the fundamental polytope defining the code so that it contains only one linear constraint for each of the parity-check constraints. A two-stage hybrid decoding which combines the interior point decoding and a low-complexity decoding algorithm for LDPC codes is then proposed. Simulation results show that the approximations introduced in the proposed algorithms do not result in any performance degradation, while considerably reducing the decoding complexity and latency.
In this paper, a hybrid decoding algorithm for finite-geometry low-density parity-check (FG-LDPC) codes is proposed. The algorithm is based on the interior point method with barrier function introduced by Wadayama. First, an efficient implementation of Wadayama's algorithm is presented. The main idea behind the modification is to approximate the barrier function for the fundamental polytope defining the code so that it contains only one linear constraint for each of the parity-check constraints. A two-stage hybrid decoding which combines the interior point decoding (IPD) and a low-complexity decoding algorithm for FG-LDPC codes is then proposed. In the first stage, the interior point decoding is used to generate a search point. If the first stage decoding fails, the decoding is continued by the low-complexity algorithm that is initialized by the result of the IPD. Compared with a conventional iterative message-passing (IMP) decoder, the proposed hybrid algorithm achieves better bit-error rate (BER) and frame-error rate (FER) for small block lengths at medium to high signal-to-noise ratio (SNR).
This paper explores ideas for fast linear programming (LP) decoding of low-density parity-check (LDPC) codes. We first propose a modification of adaptive LP decoding, and prove that it performs LP decoding by solving a number of linear programs that contain at most one linear constraint derived from each of the parity-check constraints. Then, as a step toward designing an efficient LP solver that exploits the structure of LDPC codes, we study a sparse interior-point implementation for solving this sequence of linear programs. Since the most complex part of each iteration of the interior-point algorithms is to solve a (usually ill-conditioned) system of linear equations for finding the step direction, we propose a framework for designing preconditioners to be used with the iterative methods for solving these systems. The effectiveness of the proposed approach is demonstrated via both analytical and simulation results.
While linear programming (LP) decoding provides more flexibility for finite-length performance analysis than iterative message-passing (IMP) decoding, it is computationally more complex to implement in its original form, due to both the large size of the relaxed LP problem and the inefficiency of using general-purpose LP solvers. This paper explores ideas for fast LP decoding of low-density parity-check (LDPC) codes. By modifying the previously reported Adaptive LP decoding scheme to allow removal of unnecessary constraints, we first prove that LP decoding can be performed by solving a number of LP problems that each contains at most one linear constraint derived from each of the parity-check constraints. By exploiting this property, we study a sparse interior-point implementation for solving this sequence of linear programs. Since the most complex part of each iteration of the interior-point algorithm is the solution of a (usually ill-conditioned) system of linear equations for finding the step direction, we propose a preconditioning algorithm to facilitate solving such systems iteratively. The proposed preconditioning algorithm is similar to the encoding procedure of LDPC codes, and we demonstrate its effectiveness via both analytical methods and computer simulation results.
While linear programming (LP) decoding provides more flexibility for finite-length performance analysis than iterative message-passing (IMP) decoding, it is computationally more complex to implement in its original form, due to both the large size of the relaxed LP problem, and the inefficiency of using general-purpose LP solvers. This paper explores ideas for fast LP decoding of low-density parity-check (LDPC) codes. We first prove, by modifying the previously reported Adaptive LP decoding scheme to allow removal of unnecessary constraints, that LP decoding can be performed by solving a number of LP problems that contain at most one linear constraint derived from each of the parity-check constraints. By exploiting this property, we study a sparse interior-point implementation for solving this sequence of linear programs. Since the most complex part of each iteration of the interior-point algorithm is the solution of a (usually ill-conditioned) system of linear equations for finding the step direction, we propose a preconditioning algorithm to facilitate iterative solution of such systems. The proposed preconditioning algorithm is similar to the encoding procedure of LDPC codes, and we demonstrate its effectiveness via both analytical methods and computer simulation results.
The linear programming (LP) decoding of Low-Density Parity-Check (LDPC) codes is widely concerned for its maximum likelihood (ML) features. It is that the ML decoding rule for LDPC codes can be relaxed to LP optimization problem. Therefore, this paper focus on an efficient algorithm called infeasible primal-dual interior-point (IPDIP) to solve the LP problem. In each iteration, the IPDIP algorithm obtains the predictor and corrector steps by solving the Karush-Kuhn-Tucker (KKT) equation twice. The predictor term is used to responsible for optimal solution and the corrector term keeps the current iteration away from the boundary of the feasible region. Furthermore, a modification of the centering parameter is developed to accelerate the convergence speed for the IPDIP algorithm. Simulation results of LP decoding demonstrate that the proposed IPDIP algorithm achieves beautiful bit error rate (BER) performance and good global convergence properties with less iteration number and time than other algorithms which only solve the KKT equation once by Newton method or use the not modified centering parameter.