arXiv:1803.04798

A Branch-Price-and-Cut Algorithm for Optimal Decoding of LDPC Codes

Banu Kabakulak, Z. Caner Taşkın, Alí Emre Pusane

Published Mar 13, 2018• 2 citations

Abstract

Channel coding aims to minimize errors that occur during the transmission of digital information from one place to another. Low-density parity-check (LDPC) codes can detect and correct transmission errors if one encodes the original information by adding redundant bits. In practice, heuristic iterative decoding algorithms are used to decode the received vector. However, these algorithms may fail to decode if the received vector contains multiple errors. We consider decoding the received vector with minimum error as an integer programming problem and propose a branch-and-price method for its solution. We improve the performance of our method by introducing heuristic feasible solutions and adding valid cuts to the mathematical formulation. Computational results reveal that our branch-price-and-cut algorithm significantly improves solvability of the problem compared to a commercial solver in high channel error rates. Our proposed algorithm can find higher quality solutions than commonly used iterative decoding heuristics.

DOI: 10.48550/arxiv.1803.04798

Related papers

Optimization–based decoding algorithms for LDPC convolutional codes in communication systems

Banu Kabakulak, Z. Caner Taşkın, Alí Emre Pusane

In a digital communication system, information is sent from one place to another over a noisy communication channel. It may be possible to detect and correct errors that occur during the transmission if one encodes the original information by adding redundant bits. Low–Density Parity–Check (LDPC) convolutional codes, a member of the LDPC code family, encode the original information to improve error correction capability. In practice these codes are used to decode very long information sequences, where the information arrives in subsequent packets over time, such as video streams. We consider the problem of decoding the received information with minimum error from an optimization point of view and investigate integer programming–based exact and heuristic decoding algorithms for its solution. In particular, we consider relax–and–fix heuristics that decode information in small windows. Computational results indicate that our approaches identify near–optimal solutions significantly faster than a commercial solver in high channel error rates. Our proposed algorithms can find higher quality solutions compared with the state of the art iterative decoding heuristic.

arXiv:1708.05618IISE TransactionsDec 20, 20184 citations

A Branch-and-Cut Algorithm to Design LDPC Codes without Small Cycles in Communication Systems

Banu Kabakulak, Z. Caner Taşkın, Alí Emre Pusane

In a digital communication system, information is sent from one place to another over a noisy communication channel using binary symbols (bits). Original information is encoded by adding redundant bits, which are then used by low--density parity--check (LDPC) codes to detect and correct errors that may have been introduced during transmission. Error correction capability of an LDPC code is severely degraded due to harmful structures such as small cycles in its bipartite graph representation known as Tanner graph (TG). We introduce an integer programming formulation to generate a TG for a given smallest cycle length. We propose a branch-and-cut algorithm for its solution and investigate structural properties of the problem to derive valid inequalities and variable fixing rules. We introduce a heuristic to obtain feasible solutions of the problem. Our computational experiments show that our algorithm can generate LDPC codes without small cycles in acceptable amount of time for practically relevant code lengths.

arXiv:1709.09936Sep 28, 20170 citations

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 TheoryOct 27, 200967 citations

Low complexity decoding of finite geometry LDPC codes

Zhenyu Liu, Dimitris A. Pados

We develop a new low complexity algorithm for decoding low-density parity-check (LDPC) codes. The developments are oriented specifically toward the low cost-yet effective-decoding of (high rate) finite geometry LDPC codes. The decoding procedure updates the hard-decision received vector iteratively 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 optimal mechanism to avoid infinite loops in the search is also proposed. Our studies show that the algorithm achieves an appealing performance versus complexity trade-off for finite geometry LDPC codes.

International Conference on CommunicationsMar 30, 200416 citations

A Decoding Algorithm for Finite-Geometry LDPC Codes

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 LDPC codes. The decoding procedure iteratively updates 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 finite-geometry LDPC codes.

IEEE Transactions on CommunicationsFeb 1, 20052 citations

Techniques for the decoding of low density parity check codes: efficient simulation, algorithm improvement and implementation

Babak Daneshrad, Enver Çavuş

After the introduction of iterative coding, Low Density Parity Check (LDPC) codes have received a lot of attention due to their remarkable near Shannon-limit performance and practical decoder implementation. However, when employing an LDPC code for various applications, multiple issues do arise at the simulation, algorithm and implementation levels. The first issue is the performance evaluation of the iterative LDPC decoder in the very low Bit Error Rate (BER) regions. So far, no analytical tool has been developed to evaluate the performance of LDPC codes. Unfortunately standard Monte Carlo (MC) simulations cannot be used for performance estimation in these low BER regions due to prohibitive execution times. The second issue is the efficiency of the decoding algorithm. Due to the presence of short cycles in the bipartite graph, sum-product decoding algorithms lead to considerable performance loss for short block-length LDPC codes and produce error floors for longer codes. In addition, the iterative processing and estimation of soft probabilistic values with these algorithms result in very high computational complexity, which in turn impedes the adoption of LDPC codes for power constrained systems. Another prime objective is to design a high throughput decoder architecture which is capable of supporting multiple rates and variable code lengths within minimal area. This work aims to address and provide solutions to the above problems. As a solution to the performance estimation problem of LDPC codes, a highly efficient and novel fast BER simulation technique is developed. At the algorithm level, a performance improvement and error floor avoidance method is introduced, and a computationally efficient algorithm is developed for the sum-product decoding of LDPC codes. And finally, at the architecture level, a high throughput multi-rate variable code length implementation is presented which, when implemented, efficiently minimizes device resources while alleviating the routing complexity of the decoder.

Jan 1, 20072 citations