IEEE International Symposium on Information Theory (ISIT)

Low complexity algorithm approaching the ML decoding of binary LDPC codes

Irina E. Bocharova, Boris D. Kudryashov, Vitaly Skachek, Yauhen Yakimenka

Published Jul 1, 2016• 8 citations

Abstract

A novel method for decoding of low-density parity-check codes on the AWGN channel is presented. In the proposed method, first, a standard belief-propagation decoder is applied, then a certain number of positions is erased using a combination of a reliability criterion and a set of masks. A list erasure decoder is then applied to the resulting word. The performance of the proposed method is analyzed mathematically and demonstrated by simulations.

DOI: 10.1109/isit.2016.7541790

Related papers

BP-LED Decoding Algorithm for LDPC Codes Over AWGN Channels

Irina E. Bocharova, Boris D. Kudryashov, Vitaly Skachek +1 more

A new method is presented for low-complexity near-maximum-likelihood (ML) decoding of low-density parity-check (LDPC) codes over the additive white Gaussian noise channel. The proposed method termed belief-propagation-list erasure decoding (BP-LED) is based on erasing carefully chosen unreliable bits performed in case of BP decoding failure. A strategy of introducing erasures into the received vector and a new erasure decoding algorithm are proposed. The new erasure decoding algorithm, called list erasure decoding, combines ML decoding over the BEC with list decoding applied if the ML decoder fails to find a unique solution. The asymptotic exponent of the average list size for random regular LDPC codes from the Gallager ensemble is analyzed. Furthermore, a few examples of irregular quasi-cyclic LDPC as well as randomly constructed regular LDPC codes of short and moderate lengths are studied by simulations and their performance is compared to the tightened upper bound on the LDPC ensemble-average performance and the upper bound on the average performance of random linear codes under ML decoding. A comparison of the BP decoding and BP-LED performance of the WiMAX standard codes and performance of the near-ML BEAST decoding are presented. The new algorithm is applied to decoding a short nonbinary (NB) LDPC code over extensions of the binary Galois field. The obtained simulation results are compared to the tightened upper bound on the ensemble-average performance of the binary image of regular NB LDPC codes.

arXiv:1705.09507IEEE Transactions on Information TheoryAug 24, 201814 citations

On Decoding of Low-Density Parity-Check Codes Over the Binary Erasure Channel

Hossein Pishro-Nik, Faramarz Fekri

This paper investigates decoding of low-density parity-check (LDPC) codes over the binary erasure channel (BEC). We study the iterative and maximum-likelihood (ML) decoding of LDPC codes on this channel. We derive bounds on the ML decoding of LDPC codes on the BEC. We then present an improved decoding algorithm. The proposed algorithm has almost the same complexity as the standard iterative decoding. However, it has better performance. Simulations show that we can decrease the error rate by several orders of magnitude using the proposed algorithm. We also provide some graph-theoretic properties of different decoding algorithms of LDPC codes over the BEC which we think are useful to better understand the LDPC decoding methods, in particular, for finite-length codes.

IEEE Transactions on Information TheoryMar 1, 2004147 citations

Adaptive Decoding Algorithms for Low-Density Parity-Check Codes over the Binary Erasure Channel

Gou Hosoya, Hideki Yagi, Manabu Kobayashi +1 more

Two decoding procedures combined with a belief-propagation (BP) decoding algorithm for low-density parity-check codes over the binary erasure channel are presented. These algorithms continue a decoding procedure after the BP decoding algorithm terminates. We derive a condition that our decoding algorithms can correct an erased bit which is uncorrectable by the BP decoding algorithm. We show by simulation results that the performance of our decoding algorithms is enhanced compared with that of the BP decoding algorithm with little increase of the decoding complexity.

IEICE Transactions on Fundamentals of Electronics Communications and Computer SciencesJan 1, 20091 citation

Low Decoding Complexity of LDPC Codes Over the Binary Erasure Channel

Sareh Majidi Ivari, M. Reza Soleymani, Yousef R. Shayan

In this paper, we present a new low complexity decoding algorithm outperforming existing schemes. When the Belief Propagation fails and cannot solve all the erased bits, the guessing algorithm makes assumptions on a set of erased bits. However, in our new algorithm instead of guessing the values of a set of message bits, the decoder selects a set of check nodes and makes assumption on bits connected to them. The number of possibilities is reduced by half because the field is binary resulting in lower decoding complexity. The proposed decoding algorithm is applied to two regular half rate LDPC codes with lengths of 1000 and 2000. The theoretical belief propagation (BP) threshold for these two codes is 0.429. It is shown that the actual BP threshold is improved using the new algorithm. Setting the number of possibilities to two, we achieve a threshold of 0.43 which is higher than the BP theoretical.

Iranian Conference on Electrical EngineeringMay 1, 20180 citations

Joint decoding algorithm of LDPC codes

Yi Fang, Jianwen Zhang, Lin Wang +2 more

Designing a realizable maximum likelihood(ML) decoder for low-density parity-check(LDPC) codes is always a challenging work over an additive white Gaussian noise(AWGN) channel.Although Maxwell decoder is well known for its excellent performance over the binary erasure channel(BEC),it seems that generalizing this algorithm for other channels is difficult.This paper introduces an idea called channel transformation which could realize the conversation between two different channels.A Maxwell decoder is applied to an AWGN channel.In terms of this method,and a joint decoder-BP-Maxwell(BM) decoder is proposed which combines a belief propagation(BP) decoder and a Maxwell decoder,to reduce the gap to the ML decoder in performance.Simulation results show that the BM decoding algorithm could break most small trapping sets to accomplish a lower frame error rate(FER).Moreover it also could eliminate most of the small-scale errors compared with a BP decoder.

Systems engineering and electronicsJan 1, 20110 citations

A List Decoding Algorithm for Short Low-Density Parity-Check Codes

Telex M. N. Ngatched, Fambirai Takawira

Abstract In this paper, a list decoding algorithm for lowdensity parity-check (LDPC) codes is presented. The algorithm uses a modification of the simple Gallager bit-flipping algorithm to generate a sequence of candidate codewords iteratively one at a time using a set of test error patterns based on the reliability information of the received symbols. It is particularly efficient for short block LDPC codes, both regular and irregular. Computer simulation results are used to compare the performance of the proposed algorithm with other known decoding algorithms for LDPC codes, with the result that the presented algorithm offers excellent performances. Performances comparable to those obtained with iterative decoding based on belief propagation can be achieved at a much smaller complexity. 1 I.

Apr 3, 20060 citations