International Conference on Communications

Hybrid Decoding of LDPC Codes Based on Interior Point Method

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

Published May 1, 2010• 0 citations

Abstract

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

DOI: 10.1109/icc.2010.5502379

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 CommunicationsJan 21, 20113 citations

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

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

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.

IEEE Wireless Communications and Networking ConferenceApr 1, 20100 citations

Hybrid Iterative Decoding for Low-Density Parity-Check Codes Based on Finite Geometries

Li Jian, Xian‐Da Zhang

In this letter, a two-stage hybrid iterative decoding algorithm which combines two iterative decoding algorithms is proposed to reduce the computational complexity of finite geometry low-density parity-check (FG-LDPC) codes. We introduce a fast weighted bit-flipping (WBF) decoding algorithm for the first stage decoding. If the first stage decoding fails, the decoding is continued by the powerful belief propagation (BP) algorithm. The proposed hybrid decoding algorithm greatly reduces the computational complexity while maintains the same performance compared to that of using the BP algorithm only.

IEEE Communications LettersJan 1, 200816 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 TheorySep 1, 201148 citations

A Decoding Algorithm for Finite-Geometry LDPC Codes

Zhouding Liu, Dimitris A. Pados

In this paper, we develop a new low-complexity algorithm to decode low-density parity-check (LDPC) codes. The developments are oriented specifically toward low-cost, yet effective, decoding of (high-rate) finite-geometry (FG) LDPC codes. The decoding procedure updates iteratively the hard-decision received vector in search of a valid codeword in the vector space. Only one bit is changed in each iteration, and the bit-selection criterion combines the number of failed checks and the reliability of the received bits. Prior knowledge of the signal amplitude and noise power is not required. An optional mechanism to avoid infinite loops in the search is also proposed. Our studies show that the algorithm achieves an appealing tradeoff between performance and complexity for FG-LDPC codes.

IEEE Transactions on CommunicationsMar 1, 200574 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.0657Feb 4, 20092 citations