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

IEEE Transactions on Information Theory

Results on Punctured Low-Density Parity-Check Codes and Improved Iterative Decoding Techniques

Hossein Pishro-Nik, Faramarz Fekri

Published Jan 23, 2007• 100 citations
Publisher

Abstract

This paper first introduces an improved decoding algorithm for low-density parity-check (LDPC) codes over binary-input-output-symmetric memoryless channels. Then some fundamental properties of punctured LDPC codes are presented. It is proved that for any ensemble of LDPC codes, there exists a puncturing threshold. It is then proved that for any rates R1and R2satisfying 0121to R2resulting in asymptotically good codes for all rates R1lesRlesR2. Specifically, this implies that rates arbitrarily close to one are achievable via puncturing. Bounds on the performance of punctured LDPC codes are also presented. It is also shown that punctured LDPC codes are as good as ordinary LDPC codes. For BEC and arbitrary positive numbers R121lesRlesR2is shown. Based on the above observations, a method is proposed to design good punctured LDPC codes over a broad range of rates. Finally, it is shown that the results of this paper may be used for the proof of the existence of the capacity-achieving LDPC codes over binary-input-output-symmetric memoryless channels

DOI
10.1109/tit.2006.889701

Related papers

On Achievable Rates and Complexity of LDPC Codes Over Parallel Channels: Bounds and Applications

Igal Sason, Gil Wiechman

A variety of communication scenarios can be modeled by a set of parallel channels. Upper bounds on the achievable rates under maximum-likelihood (ML) decoding, and lower bounds on the decoding complexity per iteration of ensembles of low-density parity-check (LDPC) codes are presented. The communication of these codes is assumed to take place over statistically independent parallel channels where the component channels are memoryless, binary-input, and output-symmetric. The bounds are applied to ensembles of punctured LDPC codes where the puncturing patterns are either random or possess some structure. Our discussion is concluded by a diagram showing interconnections between the new theorems and some previously reported results.

IEEE Transactions on Information Theory•Jan 23, 2007•21 citations

On Achievable Rates and Complexity of LDPC Codes for Parallel Channels: Information-Theoretic Bounds and Applications

Igal Sason, Gil Wiechman

The paper presents bounds on the achievable rates and the decoding complexity per iteration of low-density parity-check (LDPC) codes. It is assumed that the communication of these codes takes place over statistically independent parallel channels where these channels are memoryless, binary-input and output-symmetric. The bounds are applied to punctured LDPC codes. A diagram concludes our discussion by showing interconnections between the theorems in this paper and some previously reported results

arXiv:cs/0512076•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2006•1 citation

On Achievable Rates and Complexity of LDPC Codes for Parallel Channels with Application to Puncturing

Igal Sason, Gil Wiechman

This paper considers the achievable rates and decoding complexity of low-density parity-check (LDPC) codes over statistically independent parallel channels. The paper starts with the derivation of bounds on the conditional entropy of the transmitted codeword given the received sequence at the output of the parallel channels; the component channels are considered to be memoryless, binary-input, and output-symmetric (MBIOS). These results serve for the derivation of an upper bound on the achievable rates of ensembles of LDPC codes under optimal maximum-likelihood (ML) decoding when their transmission takes place over parallel MBIOS channels. The paper relies on the latter bound for obtaining upper bounds on the achievable rates of ensembles of randomly and intentionally punctured LDPC codes over MBIOS channels. The paper also provides a lower bound on the decoding complexity (per iteration) of ensembles of LDPC codes under message-passing iterative decoding over parallel MBIOS channels; the bound is given in terms of the gap between the rate of these codes for which reliable communication is achievable and the channel capacity. The paper presents a diagram which shows interconnections between the theorems introduced in this paper and some other previously reported results. The setting which serves for the derivation of the bounds on the achievable rates and decoding complexity is general, and the bounds can be applied to other scenarios which can be treated as different forms of communication over parallel channels.

arXiv:cs/0508072•Aug 16, 2005•5 citations

Randomly Punctured LDPC Codes

David G. M. Mitchell, Michael Lentmaier, Alí Emre Pusane +1 more

In this paper, we present a random puncturing analysis of low-density parity-check (LDPC) code ensembles. We derive a simple analytic expression for the iterative belief propagation (BP) decoding threshold of a randomly punctured LDPC code ensemble on the binary erasure channel (BEC) and show that, with respect to the BP threshold, the strength and suitability of an LDPC code ensemble for random puncturing is completely determined by a single constant that depends only on the rate and the BP threshold of the mother code ensemble. We then provide an efficient way to accurately predict BP thresholds of randomly punctured LDPC code ensembles on the binary-input additive white Gaussian noise channel (BI-AWGNC), given only the BP threshold of the mother code ensemble on the BEC and the design rate, and we show how the prediction can be improved with knowledge of the BI-AWGNC threshold. We also perform an asymptotic minimum distance analysis of randomly punctured code ensembles and present simulation results that confirm the robust decoding performance promised by the asymptotic results. Protograph-based LDPC block code and spatially coupled LDPC code ensembles are used throughout as examples to demonstrate the results.

IEEE Journal on Selected Areas in Communications•Dec 11, 2015•48 citations

Rate-Compatible Puncturing of Finite-Length Low-Density Parity-Check Codes

Badri N. Vellambi, R. Badri, Faramarz Fekri

In this paper, we study rate-compatible puncturing of finite-length Low-Density Parity-Check (LDPC) codes. First, we derive simple and yet good bounds on the expected performance of punctured codes (constructed by random puncturing) over Binary Erasure Channel (BEC) as a function of the performance of their parent LDPC code. We then present a novel rate-compatible puncturing scheme that is very easy to implement. Our scheme uses the idea that a more uniform distribution of punctured bits across the Tanner graph results in punctured codes with better performance. Although the puncturing scheme tailored to regular codes is presented, it is also directly applicable to irregular parent ensembles. By simulations, the proposed rate-compatible puncturing scheme is shown to be superior to the existing puncturing methods for both regular and irregular LDPC codes over BEC and Additive White Gaussian Noise (AWGN) Channel.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2006•5 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
This paper first introduces an improved decoding algorithm for low-density parity-check (LDPC) codes over binary-input-output-symmetric memoryless channels. Then some fundamental properties of punctured LDPC codes are presented. It is proved that for any ensemble of LDPC codes, there exists a puncturing threshold. It is then proved that for any rates R1and R2satisfying 0121to R2resulting in asymptotically good codes for all rates R1lesRlesR2. Specifically, this implies that rates arbitrarily close to one are achievable via puncturing. Bounds on the performance of punctured LDPC codes are also presented. It is also shown that punctured LDPC codes are as good as ordinary LDPC codes. For BEC and arbitrary positive numbers R121lesRlesR2is shown. Based on the above observations, a method is proposed to design good punctured LDPC codes over a broad range of rates. Finally, it is shown that the results of this paper may be used for the proof of the existence of the capacity-achieving LDPC codes over binary-input-output-symmetric memoryless channels
A variety of communication scenarios can be modeled by a set of parallel channels. Upper bounds on the achievable rates under maximum-likelihood (ML) decoding, and lower bounds on the decoding complexity per iteration of ensembles of low-density parity-check (LDPC) codes are presented. The communication of these codes is assumed to take place over statistically independent parallel channels where the component channels are memoryless, binary-input, and output-symmetric. The bounds are applied to ensembles of punctured LDPC codes where the puncturing patterns are either random or possess some structure. Our discussion is concluded by a diagram showing interconnections between the new theorems and some previously reported results.
The paper presents bounds on the achievable rates and the decoding complexity per iteration of low-density parity-check (LDPC) codes. It is assumed that the communication of these codes takes place over statistically independent parallel channels where these channels are memoryless, binary-input and output-symmetric. The bounds are applied to punctured LDPC codes. A diagram concludes our discussion by showing interconnections between the theorems in this paper and some previously reported results
This paper considers the achievable rates and decoding complexity of low-density parity-check (LDPC) codes over statistically independent parallel channels. The paper starts with the derivation of bounds on the conditional entropy of the transmitted codeword given the received sequence at the output of the parallel channels; the component channels are considered to be memoryless, binary-input, and output-symmetric (MBIOS). These results serve for the derivation of an upper bound on the achievable rates of ensembles of LDPC codes under optimal maximum-likelihood (ML) decoding when their transmission takes place over parallel MBIOS channels. The paper relies on the latter bound for obtaining upper bounds on the achievable rates of ensembles of randomly and intentionally punctured LDPC codes over MBIOS channels. The paper also provides a lower bound on the decoding complexity (per iteration) of ensembles of LDPC codes under message-passing iterative decoding over parallel MBIOS channels; the bound is given in terms of the gap between the rate of these codes for which reliable communication is achievable and the channel capacity. The paper presents a diagram which shows interconnections between the theorems introduced in this paper and some other previously reported results. The setting which serves for the derivation of the bounds on the achievable rates and decoding complexity is general, and the bounds can be applied to other scenarios which can be treated as different forms of communication over parallel channels.
In this paper, we present a random puncturing analysis of low-density parity-check (LDPC) code ensembles. We derive a simple analytic expression for the iterative belief propagation (BP) decoding threshold of a randomly punctured LDPC code ensemble on the binary erasure channel (BEC) and show that, with respect to the BP threshold, the strength and suitability of an LDPC code ensemble for random puncturing is completely determined by a single constant that depends only on the rate and the BP threshold of the mother code ensemble. We then provide an efficient way to accurately predict BP thresholds of randomly punctured LDPC code ensembles on the binary-input additive white Gaussian noise channel (BI-AWGNC), given only the BP threshold of the mother code ensemble on the BEC and the design rate, and we show how the prediction can be improved with knowledge of the BI-AWGNC threshold. We also perform an asymptotic minimum distance analysis of randomly punctured code ensembles and present simulation results that confirm the robust decoding performance promised by the asymptotic results. Protograph-based LDPC block code and spatially coupled LDPC code ensembles are used throughout as examples to demonstrate the results.
In this paper, we study rate-compatible puncturing of finite-length Low-Density Parity-Check (LDPC) codes. First, we derive simple and yet good bounds on the expected performance of punctured codes (constructed by random puncturing) over Binary Erasure Channel (BEC) as a function of the performance of their parent LDPC code. We then present a novel rate-compatible puncturing scheme that is very easy to implement. Our scheme uses the idea that a more uniform distribution of punctured bits across the Tanner graph results in punctured codes with better performance. Although the puncturing scheme tailored to regular codes is presented, it is also directly applicable to irregular parent ensembles. By simulations, the proposed rate-compatible puncturing scheme is shown to be superior to the existing puncturing methods for both regular and irregular LDPC codes over BEC and Additive White Gaussian Noise (AWGN) Channel.
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.