IEICE Transactions on Fundamentals of Electronics Communications and Computer Sciences

Construction of Universal Codes Using LDPC Matrices and Their Error Exponents

S. MIYAKE, M. MARUYAMA

Published Sep 1, 2007• 9 citations

Abstract

A universal coding scheme for information from i.i.d., arbitrarily varying sources, or memoryless correlated sources is constructed using LDPC matrices and shown to have an exponential upper bound of decoding error probability. As a corollary, we construct a universal code for the noisy channel model, which is not necessarily BSC. Simulation results show universality of the code with sum-product decoding, and presence of a gap between the error exponent obtained by simulation and that obtained theoretically.

DOI: 10.1093/ietfec/e90-a.9.1830

Related papers

Error Exponents of LDPC Codes under Low-Complexity Decoding

Pavel S. Rybin, Kirill Andreev, Victor Zyablov

This paper deals with the specific construction of binary low-density parity-check (LDPC) codes. We derive lower bounds on the error exponents for these codes transmitted over the memoryless binary symmetric channel (BSC) for both the well-known maximum-likelihood (ML) and proposed low-complexity decoding algorithms. We prove the existence of such LDPC codes that the probability of erroneous decoding decreases exponentially with the growth of the code length while keeping coding rates below the corresponding channel capacity. We also show that an obtained error exponent lower bound under ML decoding almost coincide with the error exponents of good linear codes.

EntropyFeb 22, 20215 citations

Bounds on the maximum likelihood decoding error probability of low density parity check codes

G. Miller, D. Burshtein

We derive bounds on the error probability of ML decoded LDPC (low density parity check) codes, for any binary-input symmetric-output channel. For appropriately chosen ensembles of LDPC codes, reliable communication is possible up to channel capacity. The lower and upper bounds coincide asymptotically, indicating a polynomially decreasing ensemble averaged error probability. For ensembles with suitably chosen parameters, the error probability of almost all codes is exponentially decreasing. Furthermore, the error exponent can be set arbitrarily close to the standard random coding exponent.

IEEE International Symposium on Information Theory (ISIT)Nov 7, 20027 citations

Bounds on the maximum-likelihood decoding error probability of low-density parity-check codes

G. Miller, David Burshtein

We derive both upper and lower bounds on the decoding error probability of maximum-likelihood (ML) decoded low-density parity-check (LDPC) codes. The results hold for any binary-input symmetric-output channel. Our results indicate that for various appropriately chosen ensembles of LDPC codes, reliable communication is possible up to channel capacity. However, the ensemble averaged decoding error probability decreases polynomially, and not exponentially. The lower and upper bounds coincide asymptotically, thus showing the tightness of the bounds. However, for ensembles with suitably chosen parameters, the error probability of almost all codes is exponentially decreasing, with an error exponent that can be set arbitrarily close to the standard random coding exponent.

IEEE Transactions on Information TheoryJan 1, 2001157 citations

On Universal LDPC Code Ensembles Over Memoryless Symmetric Channels

Igal Sason, Boaz Shuval

A design of robust error-correcting codes that achieve reliable communication over various channels is of great theoretical and practical interest. Such codes are termed universal. This paper considers the universality of low-density parity-check (LDPC) code ensembles over families of memoryless binary-input output-symmetric (MBIOS) channels. Universality is considered both under belief-propagation (BP) and maximum-likelihood (ML) decoding. For the BP decoding case, we derive a density-evolution-based analytical method for designing LDPC code ensembles that are universal over various families of MBIOS channels. We also derive a necessary condition for universality of LDPC code ensembles under BP decoding; this condition is used to provide bounds on the universally achievable fraction of capacity. These results enable us to provide conditions for reliable/unreliable communications under BP decoding that are based on the Bhattacharyya parameter of the channel. For the ML decoding case, we prove that properly selected regular LDPC code ensembles are universally capacity-achieving for the set of equi-capacity MBIOS channels and extend this result to punctured regular LDPC code ensembles.

IEEE Transactions on Information TheoryAug 1, 201120 citations

ON UNIVERSAL LDPC CODES OVER MEMORYLESS SYMMETRIC CHANNELS

Igal Sason, Boaz Shuval

A design of robust error-correcting codes that achieve reli able communication over various channels is of great theoretical and practical interest. Such codes are termed universal. This paper considers the universality of lowdensity parity-check (LDPC) code ensembles over families of memoryless binary-input output-symmetric (MBIOS) channels. Universality is considered both under belief-pr opagation (BP) and maximum-likelihood (ML) decoding. For the BP decoding case, we derive a density-evolution-based analytical method for designing LDPC code ensembles that are universal over various families of MBIOS channels. We also derive a necessary condition for universality of LDPC code ensembles under BP decoding; this condition is used to provide bounds on the universally achievable fraction of capacity. These results enable us to provide conditions for reliable / unreliable communications under BP decoding that are based on the Bhattacharyya parameter of the channel. For the ML decoding case, we prove that properly selected regular LDPC code ensembles are universally capacity-achieving for the set of equicapacity MBIOS channels and extend this result to punctured regular LDPC code ensembles. Index Terms Belief propagation (BP), Bhattacharyya parameter (B-parameter), density evolution (DE), linear programming (LP) bounds, low-density parity-check (LDPC) codes, maximum-likelihood (ML), memoryless binary-input outputsymmetric (MBIOS) channels, stability.

Jan 1, 20111 citation

The capacity of low-density parity-check codes under message-passing decoding

Tom Richardson, Rudiger L. Urbanke

We present a general method for determining the capacity of low-density parity-check (LDPC) codes under message-passing decoding when used over any binary-input memoryless channel with discrete or continuous output alphabets. Transmitting at rates below this capacity, a randomly chosen element of the given ensemble will achieve an arbitrarily small target probability of error with a probability that approaches one exponentially fast in the length of the code. (By concatenating with an appropriate outer code one can achieve a probability of error that approaches zero exponentially fast in the length of the code with arbitrarily small loss in rate.) Conversely, transmitting at rates above this capacity the probability of error is bounded away from zero by a strictly positive constant which is independent of the length of the code and of the number of iterations performed. Our results are based on the observation that the concentration of the performance of the decoder around its average performance, as observed by Luby et al. in the case of a binary-symmetric channel and a binary message-passing algorithm, is a general phenomenon. For the particularly important case of belief-propagation decoders, we provide an effective algorithm to determine the corresponding capacity to any desired degree of accuracy. The ideas presented in this paper are broadly applicable and extensions of the general method to low-density parity-check codes over larger alphabets, turbo codes, and other concatenated coding schemes are outlined.

IEEE Transactions on Information TheoryJan 1, 20013,067 citations