Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Globecom

Low-density generator matrix codes for indoor and Markov channels

Hanqing Lou, Javier Garcia‐Frias

Published Feb 22, 2005• 0 citations
Publisher

Abstract

We propose a modified algorithm for the decoding of linear codes with low-density generator matrix (LDGM) codes (a class of LDPC codes) over indoor and finite-state binary Markov channels. In order to avoid error floors, a concatenation of two LDGM codes is utilized. The hidden Markov model representing the channel is incorporated into the graph corresponding to the LDGM codes, and the message passing algorithm is modified accordingly. The proposed scheme clearly outperforms systems in which the channel statistics are not exploited in the decoding process, allowing reliable communication at rates which are above the capacity of a memoryless channel with the same stationary bit error probability as the Markov channel. Moreover, the proposed method can be successfully applied for real wireless channels that can be modeled with hidden Markov models, such as indoor channels.

DOI
10.1109/glocom.2004.1377997

Related papers

Decoding of low-density parity check codes over finite-state binary Markov channels

Javier Garcia‐Frias

We propose a modified algorithm for decoding of low-density parity check codes over finite-state binary Markov channels. The hidden Markov model representing the channel is incorporated into the bipartite graph of the low-density parity check code, and the message passing algorithm is modified accordingly. This approach clearly outperforms systems in which the channel statistics are not exploited in the decoding, allowing reliable communication at rates which are above the capacity of a memoryless channel with the same stationary bit error probability as the Markov channel. Moreover, we introduce a joint estimation/decoding method that allows the estimation of the parameters of the channel when they are not known a priori.

IEEE International Symposium on Information Theory (ISIT)•Nov 13, 2002•19 citations

Capacity-Achieving Codes with Bounded Graphical Complexity on Noisy Channels

Chun-Hao Hsu, Achilleas Anastasopoulos

We introduce a new family of concatenated codes with an outer low-density parity-check (LDPC) code and an inner low-density generator matrix (LDGM) code, and prove that these codes can achieve capacity under any memoryless binary-input output-symmetric (MBIOS) channel using maximum-likelihood (ML) decoding with bounded graphical complexity, i.e., the number of edges per information bit in their graphical representation is bounded. In particular, we also show that these codes can achieve capacity on the binary erasure channel (BEC) under belief propagation (BP) decoding with bounded decoding complexity per information bit per iteration for all erasure probabilities in (0, 1). By deriving and analyzing the average weight distribution (AWD) and the corresponding asymptotic growth rate of these codes with a rate-1 inner LDGM code, we also show that these codes achieve the Gilbert-Varshamov bound with asymptotically high probability. This result can be attributed to the presence of the inner rate-1 LDGM code, which is demonstrated to help eliminate high weight codewords in the LDPC code while maintaining a vanishingly small amount of low weight codewords.

arXiv:cs/0509062•Allerton Conference on Communication, Control, and Computing•Sep 19, 2005•14 citations

Decoding of Low-Density Parity-Check Codes Over Finite-State Binary Markov Channels

Javier Garcia‐Frias

We propose a modified algorithm for decoding of low-density parity-check codes over finite-state binary Markov channels. The proposed approach clearly outperforms systems in which the channel statistics are not exploited in the decoding, even when the channel parameters are not known a priori at the decoder.

IEEE Transactions on Communications•Nov 1, 2004•53 citations

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 Theory•Jan 1, 2001•3,067 citations

On the Application of Error-Correcting Codes with Low-Density Generator Matrix over Different Quantum Channels

Hanqing Lou, Javier Garcia‐Frias

We propose the use of linear codes with low-density generator matrix in the context of error correction over different quantum channels. The basic idea is to construct a Calderbank-Shor-Steane (CSS) code based on the generator matrix and the parity-check matrix of an LDGM code, applying row operations in both matrices to achieve the desired quantum rate. Decoding is performed in an iterative manner, using message passing over the corresponding graphs. The proposed codes allow greater flexibility and are easier to design than existing sparse-graph quantum codes, while leading to better performance.

•Apr 3, 2006•23 citations

Finite State Markov Modeling of Fading Channels Towards Decoding of LDPC Codes

M. Sravan Kumar

Here we have proposed two decoding strategies of low-density parity-check (LDPC) codes over Markov noise channels with bit flipping noise. The sum-product algorithm used for decoding LDPC codes over memoryless channels is extended to include channel estimation and how much gain we obtain by doing so is simulated and verified. LDPC codes have been studied for years over memoryless channels and are known to have excellent performance. However, these codes over channels with memory is the topic of current research. Here, channels with memory are characterized by Markov modeling which is a useful busty channel model. With sufficient no. of states, they are able to model sufficient noise characteristics. We have gone for a two-state system as it shows a good compromise between complexity and performance.

arXiv:1912.09463•Oct 19, 2019•0 citations
We propose a modified algorithm for the decoding of linear codes with low-density generator matrix (LDGM) codes (a class of LDPC codes) over indoor and finite-state binary Markov channels. In order to avoid error floors, a concatenation of two LDGM codes is utilized. The hidden Markov model representing the channel is incorporated into the graph corresponding to the LDGM codes, and the message passing algorithm is modified accordingly. The proposed scheme clearly outperforms systems in which the channel statistics are not exploited in the decoding process, allowing reliable communication at rates which are above the capacity of a memoryless channel with the same stationary bit error probability as the Markov channel. Moreover, the proposed method can be successfully applied for real wireless channels that can be modeled with hidden Markov models, such as indoor channels.
We propose a modified algorithm for decoding of low-density parity check codes over finite-state binary Markov channels. The hidden Markov model representing the channel is incorporated into the bipartite graph of the low-density parity check code, and the message passing algorithm is modified accordingly. This approach clearly outperforms systems in which the channel statistics are not exploited in the decoding, allowing reliable communication at rates which are above the capacity of a memoryless channel with the same stationary bit error probability as the Markov channel. Moreover, we introduce a joint estimation/decoding method that allows the estimation of the parameters of the channel when they are not known a priori.
We introduce a new family of concatenated codes with an outer low-density parity-check (LDPC) code and an inner low-density generator matrix (LDGM) code, and prove that these codes can achieve capacity under any memoryless binary-input output-symmetric (MBIOS) channel using maximum-likelihood (ML) decoding with bounded graphical complexity, i.e., the number of edges per information bit in their graphical representation is bounded. In particular, we also show that these codes can achieve capacity on the binary erasure channel (BEC) under belief propagation (BP) decoding with bounded decoding complexity per information bit per iteration for all erasure probabilities in (0, 1). By deriving and analyzing the average weight distribution (AWD) and the corresponding asymptotic growth rate of these codes with a rate-1 inner LDGM code, we also show that these codes achieve the Gilbert-Varshamov bound with asymptotically high probability. This result can be attributed to the presence of the inner rate-1 LDGM code, which is demonstrated to help eliminate high weight codewords in the LDPC code while maintaining a vanishingly small amount of low weight codewords.
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.
We propose the use of linear codes with low-density generator matrix in the context of error correction over different quantum channels. The basic idea is to construct a Calderbank-Shor-Steane (CSS) code based on the generator matrix and the parity-check matrix of an LDGM code, applying row operations in both matrices to achieve the desired quantum rate. Decoding is performed in an iterative manner, using message passing over the corresponding graphs. The proposed codes allow greater flexibility and are easier to design than existing sparse-graph quantum codes, while leading to better performance.
Here we have proposed two decoding strategies of low-density parity-check (LDPC) codes over Markov noise channels with bit flipping noise. The sum-product algorithm used for decoding LDPC codes over memoryless channels is extended to include channel estimation and how much gain we obtain by doing so is simulated and verified. LDPC codes have been studied for years over memoryless channels and are known to have excellent performance. However, these codes over channels with memory is the topic of current research. Here, channels with memory are characterized by Markov modeling which is a useful busty channel model. With sufficient no. of states, they are able to model sufficient noise characteristics. We have gone for a two-state system as it shows a good compromise between complexity and performance.