arXiv:0910.1922 · IEEE Information Theory Workshop (ITW)

Binary linear-time erasure decoding for non-binary LDPC codes

Valentin Savin

Published Jan 1, 2009• 15 citations

Abstract

In this paper, we first introduce the extended binary representation of non-binary codes, which corresponds to a covering graph of the bipartite graph associated with the non-binary code. Then we show that non-binary codewords correspond to binary codewords of the extended representation that further satisfy some simplex-constraint: that is, bits lying over the same symbol-node of the non-binary graph must form a codeword of a simplex code. Applied to the binary erasure channel (BEC), this description leads to a binary erasure decoding algorithm of non-binary LDPC codes, whose complexity depends linearly on the cardinality of the alphabet. We also give insights into the structure of stopping sets for non-binary LDPC codes, and discuss several aspects related to upper-layer FEC applications.

DOI: 10.1109/itw.2009.5351204

Related papers

Non binary LDPC codes over the binary erasure channel: Density evolution analysis

Valentin Savin

In this paper we present a thorough analysis of non binary LDPC codes over the binary erasure channel. First, the decoding of non binary LDPC codes is investigated. The proposed algorithm performs ldquoon-the flyrdquo decoding, i.e. it starts decoding as soon as the first symbols are received, which generalizes the erasure decoding of binary LDPC codes. Next, we evaluate the asymptotical performance of ensembles of non binary LDPC codes, by using the density evolution method. Density evolution equations are derived by taking into consideration both the irregularity of the bipartite graph and the probability distribution of the graph edge labels. Finally, infinite-length performance of some ensembles of non binary LDPC codes for different edge label distributions are shown.

arXiv:0810.4404International Symposium on Applied Sciences in Biomedical and Communication TechnologiesOct 1, 200816 citations

Results on the Improved Decoding Algorithm for Low-Density Parity-Check Codes Over the Binary Erasure Channel

Badri N. Vellambi, Faramarz Fekri

In this correspondence, we first investigate some analytical aspects of the recently proposed improved decoding algorithm for low-density parity-check (LDPC) codes over the binary erasure channel (BEC). We derive a necessary and sufficient condition for the improved decoding algorithm to successfully complete decoding when the decoder is initialized to guess a predetermined number of guesses after the standard message-passing terminates at a stopping set. Furthermore, we present improved bounds on the number of bits to be guessed for successful completion of the decoding process when a stopping set is encountered. Under suitable conditions, we derive a lower bound on the number of iterations to be performed for complete decoding of the stopping set. We then present a superior, novel improved decoding algorithm for LDPC codes over the binary erasure channel (BEC). The proposed algorithm combines the observation that a considerable fraction of unsatisfied check nodes in the neighborhood of a stopping set are of degree two, and the concept of guessing bits to perform simple and intuitive graph-theoretic manipulations on the Tanner graph. The proposed decoding algorithm has a complexity similar to previous improved decoding algorithms. Finally, we present simulation results of short-length codes over BEC that demonstrate the superiority of our algorithm over previous improved decoding algorithms for a wide range of bit error rates

IEEE Transactions on Information TheoryApr 1, 200724 citations

Analysis of bipartite graph codes on the binary erasure channel

Arya Mazumdar

We derive density evolution equations for codes on bipartite graphs (BG codes) for the binary erasure channel (BEC).We study the cases of local codes being introduced on only one side of the graph (Generalized LDPC codes) as well as on both sides.Each local code is assumed to correct up to a number of erasures one less than its distance.We define and enumerate stopping sets for BG codes, which serves an important tool for analysis of decoding thresholds on the BEC.

Allerton Conference on Communication, Control, and ComputingJan 1, 20071 citation

Some Results on MAP Decoding of Non-Binary LDPC Codes Over the BEC

Vishwambhar Rathi, Iryna Andriyanova

In this paper, the transmission over the binary erasure channel (BEC) using non-binary LDPC (NBLDPC) codes is considered. The concept of peeling decoder and stopping sets is generalized to NBLDPC codes. Using these generalizations, a combinatorial characterization of decoding failures of NBLDPC codes is given, under assumption that the Belief Propagation (BP) decoder is used. Then, the residual ensemble of codes resulted by the BP decoder is defined and the design rate and the expectation of total number of codewords of the residual ensemble are computed. The decoding failure criterion combined with the density evolution analysis helps us to compute the asymptotic residual degree distribution for NBLDPC codes. Our approach to compute the residual degree distribution on the check node side is not efficient as it is based on enumeration of all the possible connections on the check node side which satisfy the decoding failure criterion. So, the computation of the asymptotic check node side residual degree distribution and further part of our analysis is performed for NBLDPC codes over GF2mwithm= 2 . In order to show that asymptotically almost every code in such LDPC ensemble has a rate equal to the design rate, we generalize the argument of the Maxwell construction to NBLDPC codes, defined over GF22. It is also observed that, like in the binary setting, the Maxwell construction, relating the performance of MAP and BP decoding holds in this setting.

IEEE Transactions on Information TheoryMar 15, 201110 citations

Fourier domain representation of non-binary LDPC codes

Valentin Savin

In this paper we propose a binary representation of non-binary codes, which consists in a q-fold covering of the non-binary graph, where q is the size of the non-binary alphabet. It is shown that this covering graph is actually the underlying graph of the Fourier-domain Belief-Propagation decoding, meaning that the exchanged messages carry information about the bit-nodes of the covering graph. Finally, a new coding scheme is proposed, in which the bits transmitted over the channel correspond to a set of bit-nodes of the Fourier domain representation. The proposed coding scheme allows using the same decoder, regardless of how many and which of the Fourier-domain bit-nodes have been transmitted. This considerably increases the flexibility of the system, without increasing its complexity.

IEEE International Symposium on Information Theory (ISIT)Jul 1, 20126 citations

Conditional entropy of non-binary LDPC codes over the BEC

Vishwambhar Rathi

We consider transmission over the binary erasure channel (BEC) using non-binary LDPC codes. We generalize the concept of stopping sets to non-binary LDPC codes. We give a combinatorial characterization of decoding failures for non-binary LDPC codes decoded via Belief Propagation (BP). Using the density evolution analysis, we compute the asymptotic residual degree distribution for non-binary LDPC codes. In order to show that asymptotically almost every code in the non-binary LDPC ensemble has a rate equal to the design rate, we generalize the arguments of Measson, Montanari, and Urbanke to the non-binary setting. This generalization enables us to compute the conditional entropy of non-binary LDPC codes. We observe that the Maxwell construction of Measson, Montanari, and Urbanke relating the performance of MAP and BP decoding, holds in the setting of non-binary LDPC codes.

IEEE International Symposium on Information Theory (ISIT)Jul 1, 200814 citations